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

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

 

Теперь требование о размещении четырех назначений в клетки с нулевой стоимостью выполняется, следовательно, полученное решение является оптимальным. Перевозки осуществляются со сбытовой базы А к потребителю I, с базы В — к потребителю II, с базы С — к потребителю III и с базы D — к потребителю IV. Хотя данное решение и является оптимальным, однако оно не единственное. В любом оптимальном решении должен присутствовать маршрут (С,III), поскольку это единственный элемент с нулевой стоимостью в строке С. Два других оптимальных распределения назначений представлены ниже.

Таблица Первое альтернативное оптимальное решение
		I		II		III		IV
A		0		0		1		8
В		0		0		2		0
С		3		1		0		3
D		9		0		2		0
Таблица Второе альтернативное оптимальное решение
	I		II		III		IV
А	0		0		7		8
В	0		0		2		0
С	3		1		0		3
D	9		0		2		0

 

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

Решение 1: 68 + 60 + 35 + 45 - 208 миль;

Решение 2: 68 + 63 + 35 + 42 = 208 миль;

Решение 3: 72 + 56 + 35 + 45 = 208 миль.

Общая дальность перевозок для всех трех решений одинакова.

Примечание: в задачах большей размерности, чем задача из примера 13.7. убедиться в том, что проведенное в соответствии с пунктом 1 этапа 3 число прямых является минимальным, гораздо труднее. В этой связи может оказаться полезным так называемое "правило правой руки":

1. Выбирается любая строка или столбец, содержащие только один нулевой элемент.

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

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

4. Пункты 1-3 повторяются до тех пор, пока не будут учтены все входящие в таблицу нули.

 

3.4. Анализ входных и выходных даннях

 

Заключение

 

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

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

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