11. Специальные задачи линейного программирования: задача о назначениях, решение средствами ms Excel

Задача о назначениях является частным случаем транспортной задачи, в котором все значения a_i и b_j равны 1. Такая задача возникает при распределении людей на должности или работы, водителей на машины, рабочих на станки, автомашин на маршруты, групп по аудиториям и т.п.

Постановка задачи (об оптимальном закреплении исполнителей на работы). Имеется n видов работ и n исполнителей этих работ. Известна эффективность c_ij выполнения исполнителем i работы j. Требуется так назначить исполнителей по видам работ, чтобы суммарный эффект от назначений был максимальным.

Часто исходные данные задачи о назначениях записывают в виде таблицы (матрицы) планирования:

Работы Исполнители	B1	B2		Bn	Число исполнителей
A1	c11	c12		c1n	1
A2	c21	c22		c2n	1
					
An	cn1	cn2		cnn	1
Количество работ	1	1		1

Составим экономико-математическую модель (задача о назначениях относится к двухиндексным задачам линейного программирования):

1. вводим переменные: , где

2. задаем целевую функцию , которая выражает суммарный эффект от назначений;

3. из условий задачи составляем ограничения:

1. каждый исполнитель должен быть назначен на работу, т.е.

;

2. на каждую работу должен быть назначен исполнитель, т.е.

.

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

Найти минимальное значение целевой функции
	(11.1)
при ограничениях
,	(11.2)
,	(11.3)
, , .	(11.4)

Замечание. Если число исполнителей m не равно числу работ n (т.е. задача является открытой), то возможно применение двух способов:

1. решение открытой задачи о назначениях сводим к решению закрытой задачи о назначениях; для этого вводим фиктивных исполнителей или фиктивные виды работ;

2. изменяем ограничения 11.2 и 11.3:

1. если число исполнителей m больше числа работ n, то

; ;

2. если число исполнителей m меньше числа работ n, то

; .

Решение средствами ms Excel

При решении задачи о назначениях необходимо учитывать, что переменные принимают значения «0» или «1». Поэтому при заполнении диалоговова окна Поиск решения в поле Ограничения необходимо ввести требование двоичности (бинарности в MS Office 2010) изменяемых переменных:

12. Задачи дискретной оптимизации, решение средствами ms Excel

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

Найти максимальное (минимальное) значение целевой функции
	(12.1)
при ограничениях
	(10.2)
целые неотрицательные числа, .	(10.3)

Для получения целочисленных решений применяются специальные методы:

• методы отсечения;

• методы дерева решений;

• эвристические (приближенные) методы.