Метод отыскания путей минимальной стоимости.
Построение ММ. Узлы транспортной сети классифицируем следующим образом:
1. - множество узлов с излишками продукции, назовем их пунктами производства.
2. - множество узлов с нехваткой продукции, назовем их пунктами потребления.
На сети можно выделить совокупность путей, позволяющих перейти из пункта в пункт :
i j
Очевидно, стоимость перевозки единицы продукции будет зависеть от пути. Тогда естественно такую перевозку осуществлять по пути с минимальной стоимостью перевозок, т.е. по кратчайшему пути. Таким образом, возникает задача поиска кратчайшего пути между узлами и .
Пусть эта задача решена для любой пары (i,j), где и . При этом найдены величины - минимальные стоимости перевозок единицы продукции из пункта i в пункт j и естественно сами кратчайшие пути.
Пусть - объем перевозок из пункта i в пункт j по кратчайшему пути. Тогда оптимальные объемы перевозок по путям минимальной стоимости определяются из решения следующей КТЗ:
(1)
(2)
(3)
(4)
Т.О. в результате решения серии задач поиска кратчайшего пути для исходной транспортной сети, модель ТЗ в сетевой постановке сводится к КТЗ (1)-(4). Здесь в качестве производителей выступают узлы с излишками продукции, а в качестве потребителей – узлы с недостатком продукции.
Дата добавления: 2022-04-12; просмотров: 181;