Метод отыскания путей минимальной стоимости.

Построение ММ. Узлы транспортной сети классифицируем следующим образом:

1. - множество узлов с излишками продукции, назовем их пунктами производства.

2. - множество узлов с нехваткой продукции, назовем их пунктами потребления.

На сети можно выделить совокупность путей, позволяющих перейти из пункта в пункт :

i j

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

Пусть эта задача решена для любой пары (i,j), где и . При этом найдены величины - минимальные стоимости перевозок единицы продукции из пункта i в пункт j и естественно сами кратчайшие пути.

Пусть - объем перевозок из пункта i в пункт j по кратчайшему пути. Тогда оптимальные объемы перевозок по путям минимальной стоимости определяются из решения следующей КТЗ:

(1)

(2)

(3)

(4)

Т.О. в результате решения серии задач поиска кратчайшего пути для исходной транспортной сети, модель ТЗ в сетевой постановке сводится к КТЗ (1)-(4). Здесь в качестве производителей выступают узлы с излишками продукции, а в качестве потребителей – узлы с недостатком продукции.