Поток минимальной стоимости. Транспортная задача

Поток минимальной стоимости. Предположим, что задана сеть с пропускными способностями дуг c_ij. Пусть также для каждой дуги (i; j) заданы число s_ij, интерпретируемое как затраты (напри­мер, затраты на перевозку единицы груза из вершины i в вершину j). Задача поиска потока минимальной стоимости заключается в нахождении для заданной величины (р суммарного потока ее рас­пределения по дугам, минимизирующего сумму затрат.

Частным случаем задачи о потоке минимальной стоимости яв­ляется транспортная задача, в которой имеется двудольный граф (двудольным называется граф, множество вершин которого может быть разбито на два непересекающихся подмножества, причем ребра (дуги) графа соединяют вершины только из разных подмно­жеств), представленный на рисунке 4: вершины сети разбиты на две группы - m поставщиков и n потребителей.

Известно, что граф является двудольным тогда и только тогда, когда он не содержит циклов нечетной длины, или когда в нем все простые циклы имеют четную длину {теорема Кенига).

Для поставщиков заданы имеющиеся у них количества единиц

товара (груза и т.д.) a _i , для потребителей - требуемые им

количества единиц товара b_i, . Также известны затраты s_ij перевозки единицы товара от i -го поставщика j -му потребителю.

Пусть задача является замкнутой, то есть - суммарное предложение равно суммарному спросу (вводя фиктивного поставщика или фиктивного потребителя любую незамкнутую задачу можно свести к замкнутой). Требуется определить потоки товаров от потребителей к поставщикам, минимизирующие сум­марные затраты.

 

Поставщики Потребители

s₁₁

. s_1j. b₁

..

a_i s_ij b_j

. s_in.

a_m..

. s_mj.

b_n

s_mn

 

 

рис.4 Транспортная задача

 

Формально транспортную задачу можно записать в виде:

 

 

 

 

Добавляя к двудольному графу вход «0» и выход «z» и соеди­няя вход и выход с остальными вершинами дугами с потоком

x_0i=a_i, ,x_jz=b_j, , получаем задачу о потоке мини­мальной стоимости.