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)-х последовательно проводимых итераций. Каждая итерация состоит из эквивалентных преобразований матрицы и выбора максимального числа независимых нулей. Окончательным результатом каждой итерации является увеличение числа независимых нулей, имеющих в начале итерации, на единицу. Как только количество независимых нулей становится равным, задача о назначениях решена: оптимальный вариант определяется позициями независимых нулей в последней из матриц, эквивалентных исходной матрице.