Построение оптимального маршрута

Пусть транспортная сеть состоит из 10 узлов. На схеме показаны сеть дорог и стоимость перевозки единицы груза между пунктами сети. Ребра являются вариантами выбора решения.

Необходимо определить маршрут доставки груза из пункта 1 в пункт 10, обеспечивающий наименьшие транспортные расходы.

В задаче имеется ограничение — двигаться по изображенным на схеме маршрутам можно только слева направо, те. попав, например, в пункт 7, мы имеем право переместиться только в пункт 10 и не можем возвратиться обратно в 5-й или 6-й. Эта особенность транспортной сети дает право отнести каждый из десяти пунктов к одному из поясов. Будем считать, что пункт принадлежит 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);

C_ij- стоимость перевозки груза из пункта i в пункт j.

F_k(i)- минимальные затраты на перевозку груза на k-омшаге решения задачи из пункта i до конечного пункта.

Очевидно, что минимум затрат на перевозку груза из пунктов k-ого пояса до пункта 10 будет зависеть от того, в каком пункте этого пояса мы оказались. Номер i пункта, узел, принадлежащий k-омупоясу, будет являться переменной состояния системы на k-ом шаге. Поскольку оптимизация осуществляется с конца процесса, то, находясь в некотором пункте i k-огопояса, принимается решение о перемещении груза в один из пунктов (k -1)-го пояса, а направление дальнейшего движения известно из предьщущих шагов.

Номеру пункта (k -1)го пояса будет переменной управления на k-омшаге.

Для первого шага управления (к=1)функция Беллмана представляет собой минимальные затраты на перевозку груза из пунктов 1-го пояса в конечный пункт, т.е. F₁(i)=C_i10 .

Для последующих шагов затраты складываются из двух слагаемых — стоимости перевозки груза C_ijиз пункта i k-огопояса в пункт j (k -1)-го пояса и минимально возможных затрат на перевозку из пункта до конечного пункта, т.е. F_k-1(j).Таким образом, функциональное уравнение Беллмана будет иметь вид

Минимум затрат достигается на некотором значении j*, которое является оптимальным направлением движения из пункта i в конечный пункт.

На четвертом шаге попадаем на 4-й пояс; состояние системы становится определенным i = 1. Функция F₄(1) представляет собой минимально возможные затраты по перемещению груза из 1-го пункта в 10-й. Оптимальный маршрут определяется в результате анализа всех шагов в обратном порядке, а выбор некоторого управления j на k-мшаге приводит к тому, что состояние системы на (k - 1)-м шаге становится определенным.