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


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

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

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

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

 
 


i j

 

 

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

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

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

(1)

(2)

(3)

(4)

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



Дата добавления: 2022-04-12; просмотров: 181;


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.007 сек.