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

Аналогично вычислим значения функции для третьего шага (n = 3):

f3(2) = min(c2,4 + f2(4); c2,5 + f2(5)) = min(20; 14) = 14, s = 2, j3(2) = 5;

f3(3) = min(c3,4 + f2(4); c3,5 + f2(5)) = min(17; 16) = 16, s = 3, j3(3) = 5.

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

Таблица 2.3

Вычисления для четвертого шага (п = 4).

f4(1) = min(c1,2 + f3(2); c1,3 + f3(3)) = min(16; 19) = 16, s = 1, j4(1) = 2.

Таблица 2.4

Очевидно, что минимальные затраты f4(1) = 16 и оптимальный маршрут проходит через вторую вершину, так как j4(1) = 2. Далее из таблицы 2.3 при s = 2 следует, что оптимальный маршрут проходит через вершину 5, так как j3(2) = 5. Продолжая рассмотрение таблиц, для п = 2 определяем, что оптимальный маршрут проходит через вершину 7 (j2(5) = 7). Наконец, из вершины 7 попадаем в конечную вершину 9.

Таким образом, двигаясь от последней таблицы к первой, определяем оптимальный маршрут = (1 – 2 – 5 – 7 – 9), затраты прохождения пути составляют f4(1) = 2 + 4 + 3 + + 7 = 16.

Пример 2

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

Рис. 2.2

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

Пронумеруем этапы от конечной вершины сети к начальной (см. рис. 2.2) и введем обозначения: п – номер шага (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(10) = 0, так как вершина 10 конечная.

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

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

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

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

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

Таблица 2.5

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

f2(4) = min(c4,7 + f1(7); c4,8 + f1(8); c4,9 + f1(9)) = min(10; 12; 14) = 10

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

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

f2(5) = c5,7 + f1(7) = 13, j2(5) = 7;

f2(6) = c6,9 + f1(9) = 16, j2(6) = 9;

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

Таблица 2.6

Здесь четыре клетки зачеркнуты, поскольку из вершины 6 нельзя попасть в вершины 7 и 8, а из вершины 5 – в вершины 8 и 9.

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

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