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

Общая задача для двудольного графа G = {Х [] Х', А) широко известна как транспортная задача (ТЗ) [8, 16, 18, 25, 4, 21] и является обобщением ЗН, обсуждавшейся в разд. 4. Транспортная задача получила свое название из-за следующей ее интерпретации. Имеется Л источников (пунктов снабжения) и М стоков (пунктов потребления). Производительность i-ro источника снабжения равна aj, потребление к-то стока равно Pft, причем

iV м

2 j=2Pft-

i=l S=l

Требуется найти такую схему транспортировки груза от источников к стокам, которая имеет минимальную стоимость, если стоимость транспортировки единицы груза от i-ro источника к к-щ стоку равна с^.

Если аг и - целые числа, то ТЗ можно также рассматривать как общую задачу о паросочетании в двудольном графе и сначала построить граф G, как было объяснено ранее, а затем решить для этого графа ЗН. При альтернативном подходе ТЗ можно рассматривать как задачу о потоке в сети, точно так же, как это делалось для ЗН в разд. 4.

Ввиду практической важности ТЗ мы дадим матричную форму венгерского алгоритма для этой задачи. Этот алгоритм очень

похож на алгоритм из разд. 4.1.2 для ЗН и приводится здесь без

дальнейших пояснений.

Теперь совершенно очевидно, что общая задача для графа G соответствует задаче о назначениях для графа G. Если ребро (гу, Sj) лежит в паросочетании G, то это означает, что ребро (xj, Хи) не принадлежит графу G*. Если два ребра (xf, г,) и {sj, а|) лежат в паросочетании графа G, то это означает, что ребро {xi,Xk) принадлежит Gp. Существует взаимно однозначное соответствие между паросочетаниями в G и остовными подграфами с допустимыми степенями в графе G. Но так как число вершин в G намного больше п, вышеприведенное преобразование графа G в G с вычислительной точки зрения неэффективно. На самом деле не обязательно строить явно граф G и, возможно [13], так модифицировать алгоритм из разд. 3.1.1, что он будет оперировать непосредственно с первоначальным графом G, но все будет относиться к графу G.

5.1.1. Венгерский алгоритм для ТЗ

Присвоение начальных значений

Шаг 1. Начиная с матрицы стоимостей С, построить редуциро-1анную матрицу С.

Нахождение аугменталъной цепи

Шаг 2. Пометить строку s, для которой as ф О, пометкой \ = 0. Если таких строк нет, перейти к шагу 9.

Шаг 3. Пометить каждый непомеченный столбец к, содержа-щй О в помеченной строке i (т. е. имеющей с'ги - 0), пометкой ft = f. Если существует несколько возможностей, выбрать любую.

Шаг 4. Пометить каждую непомеченную строку i, содержа-(ую отмеченный элемент в помеченном столбце к, пометкой i = к.

Шаг 5. Повторять шаги 3 и 4 до тех пор, пока либо пе будет омечен столбец г с Р( О, в случае чего перейти к шагу 6, либо альнейшая расстановка пометок невозможна, в случае чего ерейти к шагу 8.

А угжнтация

Шаг 6. Найти аугментальпую цепь Р между s и f и взять в каче-ве е минимальное из следующих чисел:

min [ 5, 6{] и min [с1ь].

(i, Ь) в р и отмечен

Шаг 7. Попеременно прибавлять +е и - е (именно в таком фядке) ко всем элементам (i, к) в альтернирующей цепи Р. гметить те элементы, к которым е прибавлялось, и удалить метки у всех элементов, значение которых после вычитания стало равным нулю.

Уменьшить 5 и р( на е. Удалить все пометки и вернуться шагу 2.

Изменение матрицы

Шаг 8. Вычислить А = min [cluV, положить c,b = с'ги -

А, если ir w.kKviCiu = Сги + А, если iJ-vikK*; оставить без изменения в остальных случаях. Сохранить пометки вернуться к шагу 3.

Шаг 9. Найдено оптимальное решение. Грузы транспорти-ются только по отмеченным ребрам и, если элемент (i, к) отме-J, clh дает величину груза, транспортируемого по ребру (xj,

Следует заметить, что в вышеприведенном алгоритме матрица С служит двум целям. Неотмеченные элементы дают предварительные стоимости. (Некоторые из этих элементов могут быть нулями.) Все же отмеченные элементы имеют нулевые стоимости, но места, где они расположены, используются на самом деле для хранения величин грузов, транспортируемых по соответствующим ребрам. Это избавляет от необходимости использования отдельной матрицы для хранения транспортируемых величин.

5.2. Пример

Решим ТЗ с нижеприводимой матрицей стоимостей, где векторы, расположенные слева от матрицы и над ней, дают величины предложения и спроса соответственно источников и стоков. (Векторы весов [n] и Ыи] здесь не нужны.)

Вышеприведенная матрица редуцируется к следующей:

После нескольких применений шагов 2, 3, 6 и 7 с непосредствен' венным обнаружением аугментальной цепи матрица С, векторы