double arrow

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


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

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

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

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

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




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

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

 

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

s11

. s1j . b1

. .

ai sij bj

. sin .

am . .

. smj .

bn

smn

 

 

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

 

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

 

 

 

 

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

x0i=ai , ,xjz=bj, , получаем задачу о потоке мини­мальной стоимости.







Сейчас читают про: