Использование метода динамического программирования для решения экономических задач

В соответствии с вычислительной схемой динамического программирования рассмотрим сначала случай п = 1, т.е. предположим, что все имеющиеся средства выделяются на реконструкцию и модернизацию одного предприятия. Обозначим через f1(x) максимально возможный прирост выпуска продукции на этом предприятии, соответствующий выделенной сумме х. Каждому значению х отвечает вполне определенное (единственн

ое) значение gi(x) выпуска, поэтому можно записать, что

f1(x) = max (g1(x)) = g1(x). (1.7)

Пусть теперь n = 2, т.е. средства распределяются между двумя предприятиями. Если второму предприятию выделена сумма х, то прирост продукции на нем составит g2(x). Оставшиеся другому предприятию средства (c – x) в зависимости от величины х (а значит, и c – x) позволят увеличить прирост выпуска продукции до максимально возможного значения f1(c – x). При этом условии общий прирост выпуска продукции на двух предприятиях

g2(x) + f1(c – x) (1.8)

Оптимальному значению f2(с) прироста продукции при распределении суммы c между двумя предприятиями соответствует такое х, при котором сумма (1.8) максимальна. Это можно выразить записью

f2(с) = (g2(x) + f1(c – x))

Значение f3(с) можно вычислить, если известны значении f2(с), и т.д.

Функциональное уравнение Беллмана для рассматриваемой задачи запишется в следующем виде:

fn(с) = (gn(x) + fn – 1(c – x)) (1.9)

Итак, максимальный прирост выпуска продукции на n предприятиях определяется как максимум суммы прироста выпуска на n-м предприятии и прироста выпуска на остальных n – 1 предприятиях при условии, что оставшиеся после n-го предприятия средства распределяются между остальными предприятиями оптимально.

Имея функциональные уравнения (1.7) и (1.9), мы можем последовательно найти сначала f1, затем f2, f3, … и, наконец, fn – 1 и fn для различных значений распределяемой суммы средств.

Для отыскания оптимального распределения средств, прежде всего, находим величину xn*(c) ассигнований n-му предприятию, которая позволяет достичь полученного нами максимального значения fn прироста продукции. По величине оставшихся средств c – xn*(c) и уже известному нам значению fn – 1 устанавливаем xn – 1*(c) – величину ассигнований (n – 1)-му предприятию и т.д. и, наконец, находим x2*(c), x1*(c).

2. РЕШЕНИЕ ЭКОНОМИЧЕСКИХ ЗАДАЧ МЕТОДОМ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

2.1 Задачи выбора кратчайшего пути

В задачах выбора кратчайшего пути нет естественного деления на шаги. Это деление вводиться искусственно, для чего расстояние между начальной и конечной вершинами сети разбивается на N частей и за каждый шаг оптимизации принимается каждая такая часть.

Пример 1

Найти путь минимальной длины между начальной и конечной вершинами сети методом динамического программирования (цифры, приписанные дугам сети, означают расстояния между соответствующими вершинами) для рис. 2.1.

Рис 2.1

Решение: разобьем все множество вершин на подмножества. В первое подмножество включим исходную вершину 1, во второе – вершины, в которые входят дуги, выходящие из вершины 1, в третье – вершины, в которые входят дуги, выходящие из вершин второго подмножества. Таким образом, продолжая разбиение, получаем пять подмножеств: {1}, {2, 3}, {4, 5}, {6, 7, 8}, {9}. Очевидно, что любой маршрут из вершины 1 в вершину 9 содержит ровно четыре дуги, каждая из которых связывает вершины, принадлежащие соответствующим подмножествам. Следовательно, процесс решения задачи (нахождения оптимального маршрута) разбивается на четыре этапа. На первом этапе принимается решение, через какую вершину, принадлежащую второму подмножеству, начать путь из вершины 1. На втором этапе необходимо определить, через какую вершину, принадлежащую третьему подмножеству, начать путь из некоторой вершины, и т. д.

Пронумеруем этапы от конечной вершины сети к начальной (см. рис. 2.1) и введем обозначения: п – номер шага (n = 1, 2, 3, 4); fn(s) – минимальные затраты прохождения пути от вершины s до конечной вершины, если до конечной вершины осталось n шагов; jn(s) – номер вершины, через которую нужно продолжить путь из вершины s, чтобы достичь fn(s); csj – стоимость прохождения пути из вершины s в вершину j. Здесь все обозначения несут важную смысловую нагрузку: f означает целевую функцию, s – состояние системы (номер вершины), индекс n несет динамическую информацию о том, что из вершины s до конечной вершины осталось п шагов.

Предположим, что путь пройден, следовательно, число оставшихся шагов равно нулю (n = 0) и fn(s) = f0(9) = 0, так как вершина 9 конечная.

Рассмотрим последний шаг (n = 1) и вычислим для него значение функции. Очевидно, что в вершину 9 можно попасть из вершин 8, 7, 6. Вычислим затраты прохождения пути для этих трех состояний:

f1(6) = c6,9 + f0(9) = 5 + 0 = 5, s = 6, j1(6) = 9;

f1(7) = c7,9 + f0(9) = 7 + 0 = 7, s = 7, j1(7) = 9;

f1(8) = c8,9 + f0(9) = 8 + 0 = 8, s = 8, j1(8) = 9;

Занесем данные для удобства в таблицу.

Таблица 2.1

Произведем расчет для n = 2. Из вершины 4 в вершину 9 можно попасть через вершину 6, или через вершину 7, или через 8. Поэтому оптимальный маршрут из вершины 4 найдется из выражения

f2(4) = min(c4,6 + f1(6); c4,7 + f1(7); c4,8 + f1(8)) = min(14; 13; 16) = 13

Здесь s = 6 и j2(4) = 7, т. е. условно-оптимальный маршрут проходит через вершину 7.

Аналогично находим значения функции для s = 5:

f2(5) = min(c5,6 + f1(6); c5,7 + f1(7); c5,8 + f1(8)) = min(11; 10; 12) = 10, j2(5) = 7;

Занесем данные для удобства в таблицу.

Таблица 2.2

Цифры в столбцах таблиц, находящиеся слева от двойной вертикальной черты, представляют собой сумму стоимости csj прохождения пути из вершины s в вершину j и стоимости fn – 1(j) прохождения пути из вершины j в вершину 9. В каждой строке выбирается наименьшая из этих сумм. Этим определяются условно-оптимальные затраты прохождения пути из вершины s в конечную вершину. Затраты (значение функции) обозначены fn(s) и записаны в первом столбце справа от вертикальной черты, а вершина, через которую проходит условно-оптимальный маршрут, обозначен jn(s).

 Скачать реферат