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

Пусть требуется выполнить различных работ и имеется механизмов (машин) для их выполнения, причем каждый механизм может использоваться на любой работе. Производительность каждого механизма на различных работах, вообще говоря, различна. Задача заключается в таком распределении механизмов по работам, при котором суммарная производительность максимальна. Обозначим через производительность го механизма на й работе. Для построения математической модели сопоставим каждому из возможных вариантов распределения машин по работам набор значений неизвестных, относительно которых условимся, что = 1, если й механизм, назначается на ю работу, и = 0, если й механизм назначается не на ю работу. Для любого варианта среди чисел должно быть точно единиц, причем должны выполняться условия:

(каждый механизм назначается на одну работу);

(на каждую работу назначен один механизм).

Суммарная производительность в приданом варианте назначения машин на работы выразится суммой:

Таким образом, математическая модель рассматриваемой задачи будет такой:

max (1).

(2).

(3).

Условия (4) выводят задачу о назначениях из класса задач линейного программирования, так как они не линейны. Задачи, в которых на переменные налагаются такие условия, называются задачами с булевыми переменными. Известно, что в транспортной задаче при целочисленных исходных данных всегда можно найти целочисленные оптимальные планы, поэтому в задаче о назначениях условия (4) можно заменить условиями неотрицательности:

(5).

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

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

min ц (Y) = бв (6).

бв (7).

где неизвестные числа (потенциалы) б и в объединены в вектор Y = (бб…, бв, в,…, в).

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

Теорема 1. для того, чтобы вариант назначения был оптимальным, необходимо и достаточно существование чисел бб…, бв, в,…, в, таких, что:

бв (8).

бв, для () из базиса (9).