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

1.Постановка  задачи

Пусть имеется n видов работ и n претендентов (рабочих, механизмов и др.) для их выполнения, причём каждый претендент может использоваться на любой работе. Известна производительность i-го претендента на j-й работе (с_ij). Требуется так распределить претендентов по работам, чтобы суммарная производительность была максимальной. При этом каждого претендента можно назначить только на одну работу и на каждую работу можно назначить только одного претендента.

Эффективным методом решения  задачи о назначениях является венгерский метод.

2.Описание венгерского  метода

Предварительный этап

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

Первое преобразование проделывается  со всеми столбцами матрицы С. Из максимального элемента j-го столбца (i=1, 2, …, n) вычитаются элементы этого столбца:

C = (c_ij) → C’ = (c’_ij) = (max c_ij – c_ij).

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

Второе преобразование производится со строками матрицы С’. Из элементов i-строки матрицы C’ вычитается минимальный элемент этой строки:

C’ = (c’_ij) → C” = (c”_ij) = (c’_ij – min c’_ij).

Если в каждой строке матрицы C’ = (c’_ij), полученной после первого преобразования матрицы С, уже имеется хотя бы один нуль, то второе преобразование не производится.

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

Отмечаем произвольный нуль в первом столбце звёздочкой (*). Затем  просматриваем второй столбец, и  если в нем есть нуль, расположенный  в строке, где нет 0*, то отмечаем его звездочкой. Аналогично просматриваются один за другим все остальные столбцы матрицы С”. Нули, отмеченные звездочкой, - независимые.

(k+1)-я итерация

Допустим, что k-я итерация проведена и в результате получена матрица C_k. Если в матрице С_k имеется ровно n нулей со звездочкой, то процесс решения заканчивается. Если же число нулей со звездочкой меньше n, то переходим к (k+1)-й итерации. Каждая итерация начинается первым и заканчивается вторым этапом. Между ними несколько раз может проводиться пара этапов: третий-первый. Перед началом итерации знаком   «+» выделяют столбцы матрицы C_k, которые содержат нули со звёздочкой.

Первый этап

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

а)строка, содержащая невыделенный нуль, содержит также  нуль со звездочкой;

б)эта строка не содержит нуля со звездочкой.

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

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

IB – все нули матрицы выделены, т.е. находятся в выделенных строках и столбцах. При этом переходят к третьему этапу.

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

Второй этап

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

Далее, над элементами цепочки, стоящими на нечетных местах (0’), ставят звездочки, уничтожая их над четными элементами (0*). Затем уничтожают все штрихи над элементами матрицы и знаки «+». При этом количество независимых нулей будет увеличено на единицу, итерация закончена.

Третий  этап

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

Поскольку среди  невыделенных элементов новой матрицы появятся новые нули (согласно определению), то переходят к первому этапу, совершая действия над новой матрицей. Завершив этот этап, либо переходят ко второму этапу, либо к третьему, если все нули – выделенные.

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

 

 

 

3.Решение задачи

Вариант 12

Условие: Определить оптимальный вариант назначений, если матрица эффективности имеет следующий вид:

С =

Предварительный этап

На этом этапе  осуществляются два последовательных преобразования матрицы С. Сначала находится максимальный элемент в каждом столбце: в первом столбце максимальный элемент равен 7, во втором – 9, в третьем – 8, в четвертом – 6, в пятом – 7. Из максимального элемента вычитаются элементы этого столбца. Получается неотрицательная матрица,  в каждом столбце которой есть хотя бы один нуль. Затем из каждой строки полученной матрицы вычитаем минимальный элемент этой строки. В результате подготовительного этапа осуществлен переход к неотрицательной матрице, в каждом столбце и каждой строке которой имеется хотя бы один нуль.

С = → С’ = →

→ C'' =

В первом столбце матрицы отмечаем звездочкой нуль, расположенный в пятой строке, во втором столбце – во второй строке. В третьем столбце единственный нуль находится во второй строке, в которой уже имеется 0*, поэтому нуль в третьем столбце звездочкой не отмечается. В четвертом столбце отмечается звездочкой нуль, находящийся в первой строке. В пятом столбце нуль не отмечается, т.к. 0* находится во втором столбце. В результате получается три независимых нуля.

C'' = 

Итерации

Перед началом  итерации знаком «+» выделяем первый, второй и четвертый столбцы, т.к. они содержат 0*.

Первый  этап

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

 

C'' = 

 

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

 

 

 

 

 

 

 

 

Третий этап

Среди невыделенных элементов матрицы выбираем минимальный  – h=1. Далее h=1 вычитаем из всех элементов матрицы, расположенных в первой, третьей, четвертой и пятой строках (невыделенные строки), и прибавляем к элементам, расположенным в первом и четвертом столбцах (выделенные столбцы).

C'' =  → →

→

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

Число независимых  нулей = 5, поэтому процесс закончен. 
Оптимальный вариант: 7+9+7+6+4=33

 

 

 

 

 

 

 

 

4.Решение задачи в Excel

 

 

 

 

 

 

 

 

 

 

 

 

В качестве переменных будем использовать диапазон B13:F17. Для значения целевой функции будем использовать ячейку С20, в которую введем формулу = СУММПРОИЗВ(B4:F8;B13:F17). Функция СУММПРОИЗВ перемножает соответствующие элементы заданных массивов и возвращает сумму произведений. Для вычисления ограничений задачи используется функция СУММ. Функция СУММ суммирует все числа в интервале ячеек.

Далее выбираем пункт меню «Поиск решения», устанавливаем целевую ячейку (С20), ограничения и диапазон изменения. Нажимаем кнопку «Выполнить»,  получаем решение.