Выбор оптимального маршрута перевозки грузов
Математический аппарат ДП, основанный на методологии пошаговой оптимизации, может быть использован при нахождении кратчайших расстояний, например, на географической карте, представленной в виде сети. Решение задачи по определению кратчайших расстояний между пунктами отправления и пунктами получения продукции по существующей транспортной сети является исходным этапом при решении таких экономических задач, как оптимальное прикрепление потребителей за поставщиками, повышение производительности транспорта за счет сокращения непроизводительного пробега и др.
Пусть транспортная сеть состоит из 10 узлов, часть из которых соединены магистралями. На рис. 44. показана сеть дорог и стоимости перевозки единицы груза между отдельными пунктами сети, которые проставлены у соответствующих ребер. Необходимо определить маршрут доставки груза из пункта 1 в пункт 10, обеспечивающий наименьшие транспортные расходы.
В задаче имеется ограничение – двигаться по изображенным на схеме маршрутам можно только слева направо, т.е. попав, например, в пункт 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);
cij – стоимость перевозки груза из пункта i в пункт j.
Fk(i) – минимальные затраты на перевозку груза на k-м шаге решения задачи из пункта i до конечного пункта.
Очевидно, что минимум затрат на перевозку груза из пунктов k-го пояса до пункта 10 будет зависеть от того, в каком пункте этого пояса мы оказались. Номер i пункта, принадлежащего k-му поясу, будет являться переменной состояния системы на k-м шаге. Поскольку оптимизация осуществляется с конца процесса, то, находясь в некотором пункте i k-го пояса, принимается решение о перемещении груза в один из пунктов (k-1)-го пояса, а направление дальнейшего движения известно из предыдущих шагов. Номер j пункта (k-1)-го пояса будет переменной управления на k–м шаге.
Для первого шага управления (k=1) функция Беллмана представляет собой минимальные затраты на перевозку груза из пунктов 1-го пояса в конечный пункт, т. е. . Для последующих шагов затраты складываются из двух слагаемых – стоимости перевозки груза Cij из пункта i k-го пояса в пункт j (k-1)-го пояса и минимально возможных затрат на перевозку из пункта j до конечного пункта, т.е. Fk1(j). Таким образом, функциональное уравнение Беллмана будет иметь вид
Минимум затрат достигается на некотором значении j*, которое является оптимальным направлением движения из пункта 1 в конечный пункт.
На четвертом шаге попадаем на 4-й пояс и состояние системы становится определенным i=1. Функция F4(1) представляет собой минимально возможные затраты по перемещению груза из 1-го пункта в 10-й. Оптимальный маршрут определяется в результате анализа всех шагов в обратном порядке, а выбор некоторого управления j на k-м шаге приводит к тому, что состояние системы на (k-1)-м шаге становится определенным.
Пример 75. Решим сформулированную выше задачу, исходные данные которой приведены на рис. 43.
Решение.1 этап. Условная оптимизация.
1-й шаг. k=1.
F1(i)=Ci10
На первом шаге в пункт 10 груз может быть доставлен из пунктов 7, 8 или 9.
Таблица 29
j
i
| 10
| F1(i)
| j*
| 7
| 7
| 7
| 10
| 8
| 9
| 9
| 10
| 9
| 11
| 11
| 10
|
2-й шаг. k=2.
Функциональное уравнение на втором шаге принимает вид
Все возможные перемещения груза на втором шаге и результаты расчета приведены в следующей табл. 30:
Таблица 30
j
i
| 7
| 8
| 9
| F2(i)
| j*
| 5
| 8+7
| 6+9
| -
| 15
| 7; 8
| 6
| 5+7
| -
| 4+11
| 12
| 7
|
3-й шаг. k=3.
Таблица 31
j
i
| 5
| 6
| F3(i)
| j*
| 2
| 4+15
| -
| 19
| 5
| 3
| -
| 3+12
| 15
| 6
| 4
| -
| 9+12
| 21
| 6
|
4-й шаг. k=4.
Таблица 32
j
i
| 2
| 3
| 4
| F3(i)
| j*
| 1
| 7+19
| 5+15
| 6+21
| 20
| 3
|
Не нашли, что искали? Воспользуйтесь поиском по сайту:
©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.
|