Задача о назначениях

Каждая итерация начинается первым и заканчивается вторым этапом. Между ними может несколько раз  проводиться пара этапов: третий - первый. Перед началом итерации знаком “+”  выделяют столбцы матрицы С_k, которые содержат нули со звездочками.

Первый этап. Просматривают  невыделенные столбцы С_k. Если среди них не окажется нулевых элементов, то переходят к третьему этапу. Если же невыделенный нуль матрицы С_k обнаружен, то возможен один из двух случаев: 1) строка, содержащая невыделенный нуль, содержит также и нуль со звездочкой; 2) эта строка не содержит нуля со звездочкой.

Во втором случае переходим  сразу ко второму этапу, отметив  этот нуль штрихом.

В первом случае этот невыделенный нуль отмечают штрихом и выделяют строку, в которой он содержится (знаком “+” справа от строки). Просматривают  эту строку, находят нуль со звездочкой и уничтожают знак “+” выделения  столбца, в котором содержится данный нуль.

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

Этот процесс за конечное число шагов заканчивается одним  из следующих исходов:

1). все нули матрицы С_k выделены, т.е. находятся в выделенных строках или столбцах. При этом переходят к третьему этапу;

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

Второй этап. На этом этапе  строят следующую цепочку из нулей  матрицы С_k: исходный нуль со штрихом, нуль со звездочкой, расположенный в одном столбце с первым нулем со штрихом в одной строке с предшествующим нулем со звездочкой и т.д. Итак, цепочка образуется передвижением от 0' к 0^* по столбцу, от 0^* к 0' по строке и т.д.

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

Далее над элементами цепочки, стоящими на нечетных местах ( 0' ) -, ставим звездочки, уничтожая их над четными элементами ( 0^* ). Затем уничтожаем все штрихи над элементами С_k и знаки выделения “+”. Количество независимых нулей будет увеличено на единицу. На этом (k+1) -я итерация закончена.

Третий этап. К этому  этапу переходят после первого, если все нули матрицы С_k выделены. В таком случае среди невыделенных элементов С_k выбирают минимальный и обозначают его h (h>0). Далее вычитают h из всех элементов матрицы С_k, расположенных в невыделенных строках и прибавляют ко всем элементам, расположенным в выделенных столбцах. В результате получают новую матрицу С^'_k, эквивалентную С_k. Заметим, что при таком преобразовании, все нули со звездочкой матрицы С_k остаются нулями и в С^'_k, кроме того, в ней появляются новые невыделенные нули. Поэтому переходят вновь к первому этапу. Завершив первый этап, в зависимости от его результата либо переходят ко второму этапу, либо вновь возвращаются к третьему этапу.

После конечного числа  повторений очередной первый этап обязательно  закончится переходом на второй этап. После его выполнения количество независимых нулей увеличится на единицу и (k+1) - я итерация будет  закончена.

Пример. Решить задачу о назначениях  с матрицей

При решении задачи используем следующие обозначения:

Знак выделения “+”, подлежащий уничтожению, обводим кружком; цепочку, как и ранее, указываем стрелками.

Предварительный этап. Отыскиваем максимальный элемент первого столбца - 4. Вычитаем из него все элементы этого  столбца. Аналогично для получения  второго, третьего, четвертого и пятого столбцов новой матрицы вычитаем все элементы этих столбцов от п'яти, трех, двух и трех соответственно. Получим матрицу С^'(C^'~C). Так как в каждой строке С^' есть нуль, то С^' = С₀ и процесс приведения матрицы заканчивается. Далее ищем и отмечаем знаком “*” независимые нули в С₀, начиная с первой строки.

Первая итерация. Первый этап. Выделяем знаком “+” первый, второй, и четвертый столбцы матрицы  С₀, которые содержат 0^*.

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

Третий этап. Находим минимальный  элемент в невыделенной части  матрицы С₀ (т.е. элементы, которые лежат в столбцах и строках, не отмеченных знаком “+”). Он равен h = 1.

Вычтем h = 1 из всех элементов  невыделенных строк (т.е. всех, кроме  второго) и прибавим ко всем элементам  выделенных столбцов (первого и четвертого). Получим матрицу С^'₁ и перейдем к первому этапу.

Первый этап. Перед его  началом вновь выделяем знаком “+”  первый, второй и четвертый столбцы. Просматриваем невыделенный третий столбец, находим в нем невыделенный нуль С₂₃ = 0, отмечаем его знаком штрих. Поскольку во второй строке есть 0^* (элемент С₂₂), то выделяем знаком “+” вторую строку, далее уничтожаем знак выделения второго столбца, где лежит 0^*. Потом просмотрим второй столбец, находим в нем невыделенный нуль С₁₂ = 0, отмечаем его знаком штрих. Поскольку в первой строке есть нуль со звездочкой С₁₄ = 0^*, то выделяем его знаком “+”, и уничтожаем знак выделения четвертого столбца, где находился этот знак 0^*. Затем пересматриваем четвертый столбец и находим в нем невыделенный нуль С₅₄ = 0. Так как в строке, где он находится, нет нуля со звездочкой, то отметив этот 0 штрихом, переходим ко второму этапу.

Второй этап. Начиная с  элемента с₅₄ = 0', строим цепочку, двигаясь от него по столбцу. Находим нуль со звездочкой с₁₄ = 0^*, далее от него движемся вдоль первой строки и находим 0'(с₁₂), от этого элемента движемся вдоль первого столбца к с₂₂ = 0^*, в конечном итоге, двигаясь от с₂₂ = 0^* вдоль второй строки приходим к исходному с₂₃ = 0'. Таким образом, цепочка построена: 0'₅₄-0^*_14-0'_12-0^*_22-0'₂₃. Заменяем штрих на звездочку и уничтожаем звездочки над четными элементами цепочки, а также все знаки выделения столбцов и строк. На этом первая итерация заканчивается. В результате число независимых нулей увеличилось на единицу. Поскольку следующие итерации выполняются аналогично, то приведем результаты их выполнения без дополнительных пояснений. После второй итерации количество независимых нулей (0^*) стало равно 5 (размерности матрицы С) и поэтому алгоритм заканчивает работу. Искомые элементы назначения соответствуют позициям независимых нулей матрицы С₃ (т.е. 0^*).

Соответствующее значение целевой  функции

Первая итерация. Первый этап Третий этап

h=1

Первая итерация. Первый этап. Второй этап.

Вторая итерация

Первый этап Второй этап

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

Рассмотренная выше задача о назначениях представляет собой  частный случай Т-задачи, когда . Поэтому венгерский метод, применимый для решения транспортной задачи специального вида, можно распространить на общий случай Т-задачи. [18; 59].

Пусть требуется решить Т-задачу следующего вида минимизировать

при условиях

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

В результате предварительного этапа вычисляют матрицу

элементы которой удовлетворяют следующим условиям:

(3.3.1)

(3.3.2)

Если в условиях (3.3.1), (3.3.2) строгие равенства, то матрица Х₀ является решением Т-задачи.

Матрицу, построенную в  результате k-й итерации, обозначим

Обозначим также

(3.3.3)

 

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

Описание алгоритма Венгерского метода

Предварительный этап. В каждом из столбцов матрицы транспортных издержек отыскивают минимальный элемент, который вычитают из всех элементов этого столбца. Получают матрицу С'. Далее в каждой строке матрицы С' выбирают минимальный элемент и вычитают его из всех элементов рассматриваемой строки. Приходят к матрице С₀ (С₀ ~ C), все элементы которой неотрицательны, причем в каждой строке и столбце С₀ имеем по крайней мере, один нуль. Строят матрицу Х₀ так, чтобы ее ненулевые элементы были расположены в позициях нулей матрицы С₀.

Пусть -- номер строки, в которой расположен k-й нуль j-го столбца матрицы С₀. Тогда элементы первого столбца матрицы Х₀ определяют по рекуррентной формуле

(3.3.4)

Т.е. все элементы первого  столбца , которым соответствуют ненулевые элементы в матрицы С₀, заполняют нулями, а остальные элементы этого столбца заполняют по методу северо-западного угла.

Допустим, что столбцы  Х₀ от первого до (j-1) - го включительно уже заполнены. Тогда элементы j-го столбца определяют в соответствии с формулой

(3.3.5)

 

Если , то Х₀ - оптимальный план Т-задачи. Если , то переходим к первой итерации.

(k+1)-я итерация. Допустим, что уже проведено k итераций, причем . В этом случае необходимо, используя матрицы С_k и Х_k, провести следующую (k+1)-ю итерацию. Перед началом итерации выделяют знаком «+» те столбцы матрицы С_k, для которых невязки по столбцам равны

этап. Если все ненулевые  элементы матрицы С_k окажутся в выделенных столбцах, то переходят к третьему этапу. В противном случае пусть некоторый невыделенный нуль находится в -й строке и в -м столбце. Тогда вычисляют значения невязки -й строки:

Возможен один из двух случаев: 1) , 2) . В первом случае -ю строку С_k отмечают знаком “+” справа от нее, а сам невыделенный нуль отмечают штрихом. Далее просматривают элементы -й строки, которые лежат в выделенных столбцах и ищут среди них существенные нули (напомним, что существенным нулем С_k называется такой элемент , для которого ). Если таким существенным нулем оказался элемент , а сам столбец m -- выделен, то знак выделения “+” над столбцом m уничтожают, а сам этот нуль отмечают звездочкой.

Затем просматривают m-й столбец  и отыскивают в нем нуль (нули), расположенные в отличных от -й строках. Если такой нуль имеется, то отмечают его штрихом и анализируют невязку его строки.

Далее процесс поиска нулей  и выделение их (штрихами или звездочками) продолжается аналогично, и за несколько  шагов он заканчивается одним  из следующих исходов:

1) найдем очередной невыделенный  нуль матрицы С_k, для которого невязкая в строке . Тогда отметив его штрихом, переходим ко второму этапу;

2) все нули матрицы  С_k оказались выделенными, причем для каждого из нулей, выделяемых штрихом, невязка . Тогда переходим к третьему этапу.

Во втором случае, отметив  этот нуль штрихом, сразу переходим  к третьему этапу.

Второй этап. Состоит в  построении цепочки из нулей матрицы  С_k, отмеченных штрихами и звездочками, и в последующем переходе к новой матрице Х_k+1

Пусть для некоторого нуля со штрихом матрицы С_k, расположенного, например, в позиции ( ), невязка строки . Начиная с этого элемента , строят цепочку из отмеченных нулей матрицы С_k: двигаясь по столбцу , выбирают нуль со звездочкой , далее двигаясь от него по строке , находят нуль со штрихом . Потом движутся от него по столбцу m₂ к следующему нулю со звездочкой и т.д.. Такой последовательный переход от 0' к 0^* по столбцу и от 0^* к 0' по строке осуществляют до тех пор, пока это возможно.

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

После того как цепочка  вида

построена, осуществляют переход  к матрице от матрицы Х_k по формулам

(3.3.7)

где (3.3.8)

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

Вычисляем невязку для

На этом (k+1)-я итерация заканчивается.

Третий этап. Итак, допустим, что все нули выделены. Третий этап заключается в переходе от матрицы  С_k к эквивалентной матрице С?_k, в которой появляется новый невыделенный нуль (или нули). Пусть , где минимум выбирают из всех невыделенных элементов матрицы С_k. Тогда из всех элементов невыделенных строк матрицы С_k вычитают h, а ко всем элементам выделенных столбцов прибавляют h. В результате получают матрицу С'_k(С'_k ~ C_k), в которой все существенные нули матрицы С_k остаются нулями, и кроме того, появляются новые невыделенные нули.

Далее переходят к первому  этапу, и в зависимости от его  результата либо переходят ко второму  этапу, либо снова возвращаются к  третьему этапу. За конечное число повторов пары этапов третий - первый обязательно  перейдем ко второму этапу.

Если после выполнения второго этапа то Х_k+1 - оптимальный план. В противном случае переходим к (k+2) итерации.

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

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

Метод позволяет на каждой итерации по величине невязки оценить близость Х_k к оптимальному плану, а также верхнюю границу необходимого числа оставшихся итераций N_ост:

(3.3.9)

Эта формула справедлива  для целочисленных значений всех переменных и .

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

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

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

(3.3.10)

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

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

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