Обоснование венгерского метода

Прежде всего введем справедливость признака оптимальности, т.е. если , то план Хk - оптимален.

Действительно, в силу построения Хk, если , то (эти нули называют существенными). Поэтому план Хk оказывается оптимальным для задачи с матрицей Сk, так как

. (3.3.10)

Но матрица Сk получена эквивалентными преобразованиями из исходной матрицы С. Докажем, что Хk - оптимален и для задачи с матрицей С. Матрицы С и Сk как эквивалентные связаны соотношениями

для всех (i,j) (3.3.11)

Тогда значение целевой функции для плана Хk при матрице С будет равно

(3.3.12)

Но так как , то

і. (3.3.13)

Подставляя (3.3.13) в (3.3.12), получим с учетом (3.3.10)

. (3.3.14)

Но и не зависит от плана Хk, поэтому план Хk оптимален и для исходной задачи с матрицей С.

Перейдем теперь к обоснованию алгоритма.

Предварительный этап. На предварительном этапе строят матрицу Хk элементы которой удовлетворяют условиям

, (3.3.15)

. (3.3.16)

Если все условия (3.3.15), (3.3.16) выполняются как строгие равенства, то план Х0 - оптимален, согласно только что доказанному.

Первый этап. Цель первого этапа состоит в отыскании такого невыделенного нуля , для которого . Предположим, что такой нуль найден, и мы перешли ко второму этапу.

Второй этап. Он состоит в построении цепочки из нулей со штрихами и звездочками и переходе к Хk+1. Пусть цепочка имеет вид:

. (3.3.17)

Элементы матрицы Хk+1 вычисляют по рекуррентным формулами

где (3.3.18)

Так как в каждой строке и столбце имеется как 0', так и 0*, либо они оба отсутствуют, за исключением строки и столбца , где имеется лишь 0', то

(3.3.19)

(3.3.20)

Поэтому, если матрица Хk удовлетворяла ограничениям (3.3.15), (3.3.16), то и матрица Хk+1 будет им также удовлетворять.

Наконец, на основании соотношений (3.3.19), (3.3.20) получим

.

Третий этап. В соответствии с правилами перехода от Сk к С'k при выборе элемента h > 0 элементы невыделенных строк Сk уменьшаются на величину h, появляются новые нули, и можно снова перейти к первому этапу. При этом по правилу выделения строк и столбцов все существенные нули Сk останутся нулями и в матрице C'k.

Пример 3.5. Найти решение транспортной задачи со следующими условиями:

Проверим условие баланса

Предварительный этап. Вычитаем из элементов первого столбца 2, из второго - 3, из третьего -1, из четвертого -2. Приходим к матрице С1. Далее, вычитая минимальный элемент из элементов каждой строки, получаем матрицу С0:

Строим начальную матрицу перевозок

Невязки для столбцов dj = 0, 1, 9, 0, для строк dj = 4; 6; 0. Суммарная невязка

Первая итерация. Первый этап. Отмечаем знаком '+' сверху первый и четвертый столбцы, которым соответствуют нулевые невязки, а знаком 'х' слева первую и вторую строки, которым отвечают ненулевые невязки, черточкой сверху - существенные нули.

Просматриваем невыделенный второй столбец матрицы С0, находим в нем невыделенный нуль С32 = 0 и отмечаем его штрихом. Так как d3 = 0, то выделяем третью строку знаком '+'. Просматриваем третью строку относительно выделенных столбцов. Там существенных нулей нет. Поскольку в С0 больше не осталось невыделенных нулей (все нули расположены в выделенных строках или столбцах), то переходим к третьему этапу.

Третий этап. Среди элементов невыделенных строк и столбцов матрицы С0 находим минимальный элемент h = 1, прибавляем его ко всем элементам выделенных столбцов и вычитаем из всех элементов невыделенных строк. Получим матрицу С1.

Переходим к первому этапу.

Первый этап. Среди невыделенных столбцов находим нулевой элемент С22, который расположен в строке с ненулевой невязкой, а потому переходим ко второму этапу.

Второй этап. Цепочка состоит из одного элемента С22 = 0. Находим и прибавим q1 = 1 к элементу х1. Получим матрицу Х1.

Вторая итерация. Первый этап. В матрице С1 отмечаем знаком '+' первый, второй и четвертый столбцы, которым отвечают нулевые невязки. Находим в третьем столбце нуль С33 = 0 и отмечаем его штрихом.

Так как невязка в третьей строке равна нулю, то выделяем ее знаком '+'. Просматриваем эту строку, находим в ней существенный нуль С32, расположенный в выделенном столбце. Отмечаем его звездочкой и уничтожаем знак выделения второго столбца.

Далее просматриваем второй столбец и отыскиваем в нем невыделенный нуль С22. Так как невязка по строке d2 > 0, то отметив этот нуль штрихом, переходим ко второму этапу.

Второй этап. Строим цепочку в матрице С1 вида , а затем аналогичную цепочку в матрице Х1.

В результате получаем матрицу Х2: q2 = min {5, 8, 9} = 5

Третья итерация. Первый этап. В матрице С2 отмечаем знаком '+' первый, второй и четвертый столбцы, которым соответствуют нулевые невязки. Находим нулевой элемент С33 в третьем столбце. Так как ему соответствует нулевая невязка в третьей строке, то отмечаем этот нуль штрихом. Далее, просматриваем третью строку, отыскиваем в ней существенный нуль С32 = 0, расположенный в выделенном втором столбце, отмечаем звездочкой этот нуль и уничтожаем знак выделения над вторым столбцом. Просматриваем второй столбец, находим в нем нулевой элемент С22 = 0 и отмечаем его штрихом, а вторую строку, где он лежит, знаком '+' (так как d2 = 0).

Далее, просмотрев вторую строку, находим в ней существенный нуль С21 = 0 в выделенном первом столбце. Поэтому выделяем этот нуль звездочкой и уничтожаем знак '+' над первым столбцом.

h = min {4, 3, 2} = 2

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

Третий этап. Находим минимальный невыделенный элемент в матрице С2 h = 2, вычитаем h из всех элементов невыделенных строк и прибавляем ко всем элементам выделенных столбцов (т.е. прибавляем к четвертому столбцу и вычитаем из первой строки). В результате получим матрицу С3, в которой появился новый невыделенный нуль (С­ 13). Переходим к первому этапу.

Первый этап. В матрице С3 находим невыделенный нуль С13. Так как d1 > 0, то переходим ко второму этапу.

Второй этап. Вся цепочка состоит из одного элемента . Поэтому q3 = min {d1 = 4, d2 = 4} = 4. Прибавим q3 к , получим матрицу X3.

Так как D3 = 0, то Х3 - оптимальный план. Соответствующее значение целевой функции Lорт = (сравните с результатами решения этой задачи методом потенциалов, см. пример 3.3).