1.6. Задания для самостоятельной работы}

Решить игру с платежной матрицей:

1.1		1.2
1.3		1.4
1.5		1.6
1.7		1.8
1.9		1.10
1.11		1.12

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

2.1. Содержательная постановка

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

Формально задача о назначениях может быть сформулирована следующим образом. Необходимо выбрать из каждой строки и каждого столбца матрицы

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

2.2. Математическая модель

Для каждой -й работы и для каждого -го исполнителя введем переменную , которая может принимать всего два значения (0 или 1):

если -я работа выполняется -м исполнителем,

в противном случае.

Тогда суммарная эффективность выполнения всех работ выражается функцией:

.

Ограничения задачи

, , (11)

, , (12)

интерпретируются следующим образом. Уравнения (11) означают, что каждая работа выполняется ровно одним исполнителем. Уравнения (12) предъявляют требования к исполнителям: каждый исполнитель выполняет ровно одну работу.

Таким образом, математическая модель задачи о назначениях является задачей целочисленного линейного (булева) программирования вида:

(13)

при ограничениях (11), (12) и

, , (14)

. (15)

Нетрудно видеть, что модель (11)-(15) является частным случаем классической транспортной задачи, в которой число поставщиков совпадает с числом потребителей (), а запасы и потребности всех пунктов совпадают и равны единице (). Задача (11)-(15), как транспортная задача, может быть решена методом потенциалов [1]. Однако здесь мы рассмотрим другой метод решения задачи назначениях, который, по существу, является уточнением двойственного симплекс-метода применительно к транспорной задаче.

2.3. Венгерский метод

Идея метода была высказана венгерским математиком Е.Эгервари в 1931 г.,а в 1953 г. другой венгерский математик Г.Кун развил его идею и назвал метод венгерским [3].

Введем следующие понятия:

1. Две матрицы и назовем эквивалентными , если, . Задачи о назначениях, определяемые эквивалентными матрицами, называются эквивалентными.

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

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

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