Поток минимальной стоимости.

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

Задача поиска потока минимальной стоимости заключается в нахождении для заданной величины j суммарного потока ее распределения по дугам, минимизирующего сумму затрат. Общие методы решения задачи о потоке минимальной стоимости рассматриваются в [5, 7, 19].

Частным случаем задачи о потоке минимальной стоимости является транспортная задача, в которой имеется двудольный граф (двудольным называется граф, множество вершин которого может

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

Известно [15], что граф является двудольным тогда и только тогда, когда он не содержит циклов нечетной длины, или когда в нем все простые циклы имеют четную длину (теорема Кенига). Для поставщиков заданы имеющиеся у них количества единиц

товара (груза и т.д.) ab i = 1, m , для потребителей - требуемые им

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

Пусть задача является замкнутой, то есть У ai = У bi - суммар-

i=1 i=1

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

ПОСТАВЩИКИ

ПОТРЕБИТЕЛИ

Рис.

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

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

(1) У У xij sij ® min

? j=1 1 1 {Xj ^

(2) У xit = a„ i = 1, m

J=1

У xv = bp J =1 n •

i=1

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

xffi = ait , i = 1,m, Xjz = bj, J = 1,n, получаем задачу о потоке минимальной стоимости. Алгоритмы решения транспортной и двойственной к ней задач описаны в [7, 12].

Частным случаем транспортной задачи является задача о назначении, заключающаяся в следующем: имеются n человек (работников), которые могут выполнять различные работы (занимать различные должности), число работ равно числу работников (введя фиктивные должности и/или фиктивные работы, всегда можно незамкнутую задачу привести к рассматриваемой замкнутой форме). Известны затраты sij на назначение i-го работника на j-ю должность (например, минимальная зарплата, за которую он согласится работать на этой должности). Требуется найти назначение работников на должности (каждого работника на одну и только одну должность), минимизирующее суммарные затраты (если sij интерпретируется как эффективность от работы i-го работника на j-ой должности, то оптимальное назначение должно максимизировать суммарную эффективность).

Формально задачу о назначении можно записать в виде (ср. с (1)-(3)):

У У xiJ siJ ® min

и М {Xjj

У Xj = 1, i = 1n

J=1

Пусть имеются n = 3 работника и столько же работ. Матрица 1 2 3 затрат имеет вид: 2 4 7 5 3 8 Алгоритм 8.

Шаг 0. Назначаем каждого человека на самую дешевую для него работу (назначение выделено на рисунке 5 тонкими дугами),

о Г1, если Sj = min slk то есть положим хц = < к . Если при этом

[0, в противном случае

назначение является допустимым (то есть все работы выполняются), то решение получено. Если имеется «дисбаланс», то есть не

все работы выполняются ($j1: ^ x^ > 1), то переходим к сле-

i=1

РАБОТНИКИ

Шаг к. Введем два подмножества множества дуг: P1 = {(i; j) | Xj = 1}, P2 = {(i; j) I Xj = 0}. Примем множество вершин-работ, на которых назначено несколько работников за вход сети, множество вершин-работ, которые не выполняются - за выход сети. Изменим направления дуг из множества P1 на обратные и примем их длины равными (-Sj), длины дуг из множества P2 примем равными Sj. Найдем путь / минимальной длины в полученной сети (потенциа- 22

лы вершин, вычисляемые при нахождении кратчайшего пути в рассматриваемом примере, приведены в квадратных скобках).

В результате в рассматриваемом примере за один шаг получим оптимальное назначение, отличающееся от найденного на нулевом шаге тем, что первому работнику назначается третья работа (см. дугу, обозначенную двойными линиями на рисунке 5).

На каждом шаге число «дисбалансов» уменьшается на единицу. Следовательно, число шагов алгоритма не превышает числа «дисбалансов», которое конечно.

Аналогичным способом можно решить любую транспортную задачу (искать кратчайший путь из множества вершин, в которые доставили товара больше, чем требуется, во множество вершин, где товара не хватает).

Решение общего случая задачи о потоке минимальной стоимости основывается на рассмотрении двойственной задачи [7, 12].

Поток минимальной стоимости.

Еще по теме Поток минимальной стоимости.: