Принцип Беллмана для оптимальных путей.

Математический аппарат динамического программирования, основанный на методологии пошаговой оптимизации, может быть использован при нахождении кратчайших расстояний, например, на географической карте, представленной в виде сети. Решение задачи по определению кратчайших расстояний между пунктами отправления и пунктами получения продукции по существующей транспортной сети является исходным этапом при решении таких экономических задач, как оптимальное прикрепление потребителей за поставщиками, повышение производительности транспорта за счет сокращения непроизводительного пробега и др.

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

Рис. 52.1

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

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

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

Для первого шага управления (k - 1) функция Беллмана представляет собой минимальные затраты на перевозку груза из пунктов 1 -го пояса в конечный пункт, т.е. F₁(i) = С _i,10. Для последующих шагов затраты складываются из двух слагаемых - стоимости перевозки груза С_i,j из пункта i k -го пояса в пункт j (k - 1)-го пояса и минимально возможных затрат на перевозку из пункта j до конечного пункта, т.е. - F _{k - 1} (i). Таким образом, функциональное уравнение Беллмана будет иметь вид

(52.1)

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

Пример: решим сформулированную выше задачу, исходные данные которой приведены на рисунке.

I этап. Условная оптимизация.

1-й шаг. k = 1.

На первом шаге в пункт 10 груз может быть доставлен из пунктов 7,8 или 9.

Таблица 52.1

2-й шаг. k = 2.

Функциональное уравнение на втором шаге принимает вид:

Все возможные перемещения груза на втором шаге и результаты расчета приведены в следующей таблице 33.2:

Таблица 52.2

3-й шаг. k = 3.

 

Таблица 52.3

4-й шаг. k = 4.

Таблица 52.4

II этап. Безусловная оптимизация.

 

Рис. 52.2

На этапе условной оптимизации получено, что минимальные затраты на перевозку груза из пункта 1 в пункт 10 составляют F₄(1) = 20. Данный результат достигается при движении груза из 1 -го пункта в 3 -й. По данным табл.33.3, из пункта 3 необходимо двигаться в пункт 6, затем - в пункт 7 (см. табл.33.2) и из него - в конечный пункт (см. табл.33.1). Таким образом, оптимальный маршрут доставки груза: 1 => 3 => 6 => 7 => 10. На рисунке он показан жирными стрелками.