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

Общая задача для двудольного графа широко известна как транспортная задача (ТЗ) [8, 16, 18, 25, 4, 21] и является обобщением ЗН, обсуждавшейся в разд. 4. Транспортная задача получила свое название из-за следующей ее интерпретации. Имеется источников (пунктов снабжения) и стоков (пунктов потребления). Производительность источника снабжения равна потребление стока равно причем

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

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

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

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

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

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

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

Шаг 2. Пометить строку для которой пометкой Если таких строк нет, перейти к шагу 9.

Шаг 3. Пометить каждый непомеченный столбец к, содержаший в помеченной строке (т. е. имеющей пометкой Если существует несколько возможностей, выбрать любую.

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

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

А угментация

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

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

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

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

Шаг 8. Вычислить положить если если оставить без изменения в остальных случаях. Сохранить пометки вернуться к шагу 3.

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

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