ВЫБОР ОПТИМАЛЬНОГО МАРШРУТА ПЕРЕВОЗКИ ГРУЗОВ

В этой статье рассматривается один из математических методов для определения
оптимального пути доставки груза.

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

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

Рис. 2.12

В задаче имеется ограничение — двигаться по изображенным на схеме маршрутам
можно только слева на право, т.е. попав, например, в пункт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.
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-го пояса в пункт j (k — 1)-го
пояса и минимально возможных затрат на перевозку из пункта j до конечного
пункта, т.е.- Fk — 1 (i). Таким образом, функциональное уравнение Беллмана
будет иметь вид

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

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

I этап. Условная оптимизация.
1-й шаг. k = 1
F1(i) = Сi 10
На первом шаге в пункт 10 груз может быть доставлен из пунктов 7,8 или 9.

Таблица. 2.18

2-й шаг. k = 2
Функциональное уравнение на втором шаге принимает вид

Все возможные перемещения груза на втором шаге и результаты расчета приведены
в табл. 2.19

Таблица 2.19

3-й шаг. k = 3.

Таблица 2.20

4-й шаг. k = 4.

Таблица 2.21

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

Рис.2.13.

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

Похожие записи