Экономико-математические модели управления производством (теоретические аспекты). Ломкова Е.Н - 59 стр.

     В задаче имеется ограничение – двигаться по изображенным на
схеме маршрутам можно только слева на право, т. е. попав, например,
в пункт 8, мы имеем право переместиться только в пункт 10 и не мо-
жем возвратиться обратно в 5-й или 6-й. Эта особенность транспортной
сети дает право отнести каждый из десяти пунктов к одному из поясов.
Будем считать, что пункт принадлежит k-му поясу, если из него попасть в
конечный пункт ровно за k шагов, т. е. с заездом ровно в (k – 1)-й проме-
жуточный пункт. Таким образом, пункты 7, 8 и 9 принадлежат к первому
поясу, 5 и 6 – ко второму, 2, 3 и 4 – к третьему и 1 – к четвертому. Тогда на
k-м шаге будем находить оптимальные маршруты перевозки груза из пунк-
тов k-го пояса до конечного пункта. Оптимизацию будем производить с
конца процесса, и потому, дойдя до k-го шага, неизвестно, в каком из
пунктов k-го пояса окажется груз, перевозимый из первого пункта.
     Введем обозначения:
     k – номер шага (k = 1, 2, 3, 4);
     i – пункт, из которого осуществляются перевозки (i = 1, 2, ..., 9);
     j – пункт, в который доставляется груз (j = 2, 3 , .., 10);
     сi,j – стоимость перевозки груза из пункта i в пункт j.
     Fk(i) – минимальные затраты на перевозку груза на k-м шаге реше-
ния задачи из пункта i до конечного пункта.
     Очевидно, что минимум затрат на перевозку груза из пунктов k-го
пояса до пункта 10 будет зависеть от того, в каком пункте этого пояса мы
оказались. Номер i пункта, принадлежащего k-му поясу, будет являться
переменной состояния системы на k-м шаге. Поскольку оптимизация
осуществляется с конца процесса, то, находясь в некотором пункте i k-
го пояса, принимается решение о перемещении груза в один из пунктов
(k – 1)-го пояса, а направление дальнейшего движения известно из пре-
дыдущих шагов. Номер j пункта (k – 1)-го пояса будет переменной управ-
ления на k-м шаге.
     Для первого шага управления (k = 1) функция Беллмана представляет
собой минимальные затраты на перевозку груза из пунктов 1-го пояса в
конечный пункт, т. е. F1(i) = Сi,10. Для последующих шагов затраты скла-
дываются из двух слагаемых – стоимости перевозки груза Сi,j из пункта i
k-го пояса в пункт у (k – 1)-го пояса и минимально возможных затрат на
перевозку из пункта j до конечного пункта, т. е. Fk-1(j). Таким образом,
функциональное уравнение Беллмана будет иметь вид:
                          F ( i ) = min{C + F ( j)}                      (6.8)
                           k                i ,j   k −1
                                   j
     Минимум затрат достигается на некотором значении j*, которое являет-
ся оптимальным направлением движения из пункта i в конечный пункт.
     На четвертом шаге попадаем на 4-й пояс и состояние системы стано-
вится определенным i = 1. Функция F4(l) представляет собой минимально
возможные затраты по перемещению груза из 1-го пункта в 10-й. Опти-

                                       59