7. Задача об оптимальном назначении

7.1. Постановка задачи

Пусть имеется n работ, которые могут выполнить n исполнителей. Известны затраты при назначении i-го исполнителя на j-ую работу.

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

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

Обозначим назначение i-го исполнителя на j-ую работу, как . Тогда

(7.1)

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

(7.2)

Кроме того:

x_ij =

Функция цели задачи по критерию минимума суммарных затрат:

Очевидно, что данная задача сводится к транспортной задаче, если запасы и потребности равны единице. Как правило, число исполнителей равно числу работ, то есть это закрытая задача. Если это условие не выполняется, то вводят либо фиктивного исполнителя, либо фиктивную работу, в результате задача становится закрытой, а в полученном оптимальном назначении одна работа не будет выполнена, либо один исполнитель будет простаивать. Запишем данные задачи в таблицу:

	B1	B2	B3	…	Bn	Запасы
А1	c11 x11	c12 x12	c13 x13	…	c1n x1n	1
А2	c21 x21	c22 x22	c23 x23	…	c2n x2n	1
…	…	…	…	…	…	…
Аn	cn1 xn1	cn2 xn2	cn3 xn3	…	cnn xnn	1
Потребности	1	1	1	1	1

Здесь А₁, А₂, …, А_n – работы, В₁, В₂, …, В_n – исполнители.

Так как «запасы» и «потребности» всегда равны 1, то при решении их не принято писать, кроме того величины «перевозок» также равны 1, поэтому занятые клетки можно просто помечать каким-либо образом.

Рассмотрим пример задачи о назначениях размерности n = 5. Здесь приведен первый опорный план, построенный по методу северо-западного угла:

	В1	В2	В3	В4	В5
А1	12 (1)	8	14	10	24
А2	31	15 (1)	22	7	30
А3	20	25	21 (1)	26	26
А4	11	17	18	15 (1)	8
А5	6	5	9	9	19 (1)

Из таблицы видно, что план вырожден n-1 раз. Такой особенностью обладают все планы задачи об оптимальном назначении. В результате этого стандартные методы решения транспортной задачи неэффективны и, кроме того, часто приводят к зацикливанию. Рассмотрим «венгерский метод» решения задачи.