Решение. Определение минимального значения

Пример.

Определение минимального значения.

Каждый из сотрудников ресторана (например, бармен, официант, повар и т.д.) может выполнять определенные виды работ. Почасовая оплата С_ij i-му сотруднику по j – му виду работ приведена в таблице 3. Составить план выполнения работ, так, чтобы все виды работ были проведены, каждый сотрудник выполнял только работу одного вида, а суммарная стоимость почасовой оплаты была минимальной.

Таблица3. Стоимости выполнения работы

Сотрудники	Почасовая оплата работ

1. Проверка задачи на сбалансированность - задача является сбалансированной, т. к. количество сотрудников соответствует числу возможных видов работ. В случае несбалансированности задачи необходимо ввести недостающее число фиктивных сотрудников (строчек) или видов работ (столбцов).

2. Построение математической модели задачи - пусть х_ij = 1
в случае выполнения i-м сотрудником j-го вида работ, и
х_ij = 0 - в случае невыполнения вида работ. Тогда математическая модель задачи примет вид:

• найти минимум функционала:

Z= ®min

• при следующих ограничениях:

=1, j=

=1, i=

(0;1), j=i=

3. Решение задачи с помощью надстройки Поиск решения:

· подготовку рабочего листа осуществляем в соответствии с рис. 3, формулы для расчета приведены в табл. 4;

Таблица 4. Формулы для расчета в задаче о назначениях

Описание	Ячейка	Формула
Ограничения	G1I	=CУMM(Cll:Fll)
G12	=CУMM(C12:F12)
G13	=CУMM(C13:F13)
GI4	=CУMM(C14:F14)
Ограничения	С15	=СУММ(С11:С14)
D15	=CУMM(Dll:D14)
Е15	=СУММ(Е11:Е14)
F15	=CУMM(Fll:F14)
Стоимость всех работ	G15	=СУММПРИЗВ(С5:C8;C11:F14)

Рис. 3. Подготовка рабочего листа

Рис.4. Установка параметров

• устанавливаем ограничения в окне Поиск решения, как показано на рис. 4. В окне Параметры поиска решения необходимо также установить флажок Линейная модель;

• решение задачи представлено на рис. 5.

Рис. 5. Решение задачи о назначениях

Самостоятельные задания

Задания по теме сформулированы в виде задач о назначениях. Имеется n сотрудников и т видов работ. Стоимость С_ij выполнения i-м сотрудником j-го вида работ приведена в таблицах, где сотрудникам соответствуют строки, а видам работ - столбцы. Составить план выполнения видов работ так, чтобы все виды работ были проведены, каждый сотрудник был занят только одним видом деятельности, а суммарная стоимость проведения всех видов работ была минимальной.

Вариант №1