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

Прежде всего введем справедливость признака оптимальности, т.е. если , то план Х _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) выполняются как строгие равенства, то план Х ₀ - оптимален, согласно только что доказанному.

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

Второй этап. Он состоит в построении цепочки из нулей со штрихами и звездочками и переходе к Х _{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. Приходим к матрице С₁. Далее, вычитая минимальный элемент из элементов каждой строки, получаем матрицу С₀:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Второй этап. Вся цепочка состоит из одного элемента . Поэтому q₃ = min { d ₁ = 4, d ₂ = 4} = 4. Прибавим q₃ к , получим матрицу X ₃.

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