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

Пусть для некоторого нуля со штрихом матрицы С_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 при матрице С будет равно

   (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 к элементу х₁. Получим матрицу Х_i.

Вторая итерация. Первый этап. В матрице С₁ отмечаем знаком “+” первый, второй и четвертый столбцы, которым отвечают нулевые невязки. Находим в третьем столбце нуль С₃₃ = 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 содержится информация о расстоянии между каждой базой и каждым потребителем. Как следует распределить заказы по сбытовым базам, чтобы общая дальность транспортировки была минимальной?