Венгерский метод решения задач

Далее просматриваем второй столбец и отыскиваем в нем невыделенный нуль С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).

 

 

 

 

Заключение

 
  Суть венгерского метода состоит в следующем: Путем прибавления оп-ределенным образом найденных чисел к некоторым столбцам и вычитания из них некоторых чисел находят систему так называемых независимых нулей. На-бор нулей называется системой независимых нулей, если никакие два (или больше) нуля не лежат на одной линии (в строке или столбце). Если число не-зависимых нулей равно n, то, приняв соответствующие им переменные xij рав-ными 1, а все остальные – равными 0, согласно утверждению 2, получим опти-мальный план назначения. 
 Алгоритм венгерского метода состоит из предварительного шага и не бо-лее, чем (n-2) последовательно повторяющихся итераций. На предварительном этапе в случае решения задачи на максимум, ее преобразуют в эквивалентную задачу на минимум. На этом же этапе выделяется система независимых нулей. Каждая последующая итерация направлена на увеличение хотя бы на 1 числа независимых нулей. Как только число независимых нулей k станет равным размерности матрицы (k=n) , задача решена. 
 Оптимальный план назначения определится положением независимых нулей на последней итерации.