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

(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.

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

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

Предварительный этап. Вычитаем из элементов первого столбца 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).

3. Алгоритм решения задачи о назначениях

Этот алгоритм состоит  из трех этапов.

Этап 1:

1. Формализация проблемы  в виде транспортной таблицы  по аналогии с решением транспортной  задачи.

2. В каждой строке таблицы  найти наименьший элемент и  вычесть его из всех элементов  данной строки.

3. Повторить ту же самую  процедуру для столбцов.

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

Этап 2.

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

1. Найти строку, содержащую  только одно нулевое значение  стоимости, и в клетку, соответствующую  данному значению, поместить один  элемент. Если такие строки  отсутствуют, допустимо начать  с любого нулевого значения  стоимости.

2. Зачеркнуть оставшиеся  нулевые значения данного столбца.

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

4. Найти столбец, содержащий  только одно нулевое значение, и в соответствующую клетку  поместить один элемент.

5. Зачеркнуть оставшиеся  нули в данной строке.

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

Если окажется, что таблица  содержит неучтенные нули, повторить  операции 1-6. Если решение является допустимым, т.е. все элементы распределены в клетки, которым соответствует  нулевая стоимость, то полученное решение  одновременно является оптимальным. Если решение является недопустимым, осуществляется переход к этапу 3.

Этап 3.

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

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

3. Вычесть его из всех  элементов, через которые не  проходят прямые.

4. Прибавить найденный  элемент ко всем элементам  таблицы, которые лежат на пересечении  проведенных ранее прямых

5. Все элементы матрицы,  через которые проходит только  одна прямая, оставить без изменения.

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

Пример. Некоторая компания имеет четыре сбытовые базы и четыре заказа, которые необходимо доставить различным потребителям. Складские помещения каждой базы вполне достаточны для того, чтобы вместить один из этих заказов. В табл. 13.29 содержится информация о расстоянии между каждой базой и каждым потребителем. Как следует распределить заказы по сбытовым базам, чтобы общая дальность транспортировки была минимальной?

Таблица Расстояние от сбытовых баз до потребителей
Сбытовая база	Расстояние, миль Потребители
	I	II	III	IV
А В С D	68 56 3847	72 60 40 42	75 58 35 40	83 63 45 45

Решение

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

Этап 1 Венгерского метода: В каждой строке находится наименьший элемент.

Таблица Выявление наименьших элементов по строкам
	Потребители	Наименьший элемент строки
	I	II	III	IV
А В С D	68 56 38 47	72 60 40 42	75 58 35 40	83 63 45 45	68 56 35 40

 

Наименьший элемент вычитается из всех элементов соответствующей  строки

Таблица 13.31. Вычитание наименьшего  элемента по строкам и выявление  наименьшего элемента по столбцам
0	4	7	15
0	4	2	7
3	5	0	10
7	2	0	5
0	2	0	0	?Наименьший элемент столбца

Найденный наименьший элемент  вычитается из всех элементов соответствующего столбца.

Таблица Вычитание наименьшего  элемента по столбцам
0	2	7	10
0	2	2	2
3	3	0	5
7	0	0	0

В соответствии с процедурой, описанной в этапе 2, осуществляются назначения. Наличие назначения обозначается через

Таблица Назначения в клетки с нулевыми значениями

0	2	7	10
0	2	2	2
3	3	0	5
7	0	0	0

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

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

Таблица Скорректированная таблица с назначениями для нулевых клеток
	I	II	III	IV
А	0	0	7	8
В	0	0	2	0
С	3	1	0	3
D	9	0	2	0