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

Задача о назначениях представляет собой разновидность транспортной задачи со специфической структурой. Постановка задачи такова.

Имеется видов работ и исполнителей, каждый из которых может выполнять произвольную работу, но только одну. Стоимость выполнения –й работы –м исполнителем равна . С самого начала можно считать, что за счет ввода фиктивного исполнителя или фиктивной работы с нулевыми индексами . Задача заключается в распределении видов работ по исполнителям, при котором суммарная стоимость выполнения работ минимальна.

Математическая формулировка задачи имеет следующий вид. Пусть

Тогда требуется минимизировать функцию

при ограничениях

, ,

, ,

.

Решение задачи о назначениях основано на следующем свойстве:

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

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

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

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

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

Задача 6.5. На предприятии имеется пять различных станков, каждый из которых может выполнять пять различных операций по обработке деталей. Производительность станков при выполнении каждой из операций задана в таблице:

Станок	Операция
I	II	III	IV	V

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

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

.

Чтобы найти максимальную производительность, нужно минимизировать функцию . Чтобы коэффициенты соответствующей транспортной задачи стали положительными, добавим к каждому из них число 20 (максимальный коэффициент среди ). В результате получим таблицу

.

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

Проведем вычеркивания нулевых элементов таблицы.

Среди не вычеркнутых элементов минимальным является число 1. Вычтем 1 из всех не вычеркнутых элементов и добавим 1 к тем трем вычеркнутым элементам, через которых проходит две прямые. Получим:

План оптимален. Ответ: , , , , , суммарная производительность равна 66.

Литература.

1. В. Е. Гмурман. Теория вероятностей и математическая статистика М.: Высшая школа, 2001.

2. В. Е. Гмурман. Руководство к решению задач по теории вероятностей и математической статистике М.: Высшая школа, 2001.

3. Исследование операций в экономике (под ред. Н. Ш. Кремера). М.: ЮНИТИ, 1997.

4. Экономико-математические методы и прикладные модели. Под ред. В.В. Федосеева. – М.: ЮНИТИ, 1999.

5. Калихман И. Л. Сборник задач по математическому программированию. Москва, Высшая школа. 1975.

6. Х. Таха. Введение в исследование операций. Т.1,2. Москва, Мир. 1985.

7. Борисова О.Н., Щиканов А.Ю., Яцкевич А.Б. (под редакцией Борисова В.Ф.) Математика и ее приложения. Сборник задач для студентов заочной формы обучения КИУЭС. - Королев: КИУЭС, 2004, 26 с.

8. Борисова О.Н. Математика: Учебная программа и методические материалы. - Королев: КИУЭС, 2003, 26 с.

9. Борисова О.Н. Методы и модели в экономике: Учебная программа и методические материалы.- Королев: КИУЭС, 2003, 11 с.