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

При принятии управленческих решений часто приходится сталкиваться с задачей распределения ресурсов по исполнителям, которая называется задачей о назначениях. Эту задачу, как и задачу принятия решений в условиях конфликта, можно свести к задаче линейного программирования. Рассмотрим ее решение на примере.

Пример. Цеху металлообработки нужно выполнить срочный заказ на производство деталей. Каждая деталь обрабатывается на 4-х станках С1, С2, С3 и С4. На каждом станке может работать любой из четырех рабочих Р1, Р2, Р3, Р4, однако, каждый из них имеет на каждом станке различный процент брака. Из документации ОТК имеются данные о проценте брака каждого рабочего на каждом станке:

Необходимо так распределить рабочих по станкам, чтобы суммарный процент брака (который равен сумме процентов брака всех 4-х рабочих) был минимален. Чему равен этот процент?

Обозначим за - переменные, которые принимают значения 1, если i -й рабочий работает на j -м станке. Если данное условие не выполняется, то . Целевая функция есть:

Вводим ограничения. Каждый рабочий может работать только на одном станке, то есть

Кроме этого, каждый станок обслуживает только один рабочий:

Кроме того, все переменные должны быть целыми и неотрицательными: .

Открываем электронную таблицу EXCEL. Вводим в диапазон В3-Е6 проценты по браку, ячейки G3-J6 выделяем под переменные и вводим в них произвольные числа, например единицы, задаем подписи как показано на рисунке.

Целевая функция равна сумме произведений данных из диапазона В3-Е6 умноженных на переменные из диапазона G3-J6. Для ее вычисления ставим курсор в ячейку В7, вызываем мастер функций кнопкой f_x и выбираем функцию СУММПРОИЗВ из категории «Статистические». В полях «Массив 1» обводим ячейки В3-Е6, делая на них ссылку, а в «Массив 2» обводим G3-J6, нажимаем «ОК».

Вводим левые части ограничений. Ставим курсор в В8 и вводим туда функцию «=G3+G4+G5+G6». Автозаполняем на В8, С8, D8 и Е8. Ставим курсор на F8 и вводим формулу: «=G3+H3+I3+J3» и автозаполняем ее на F9, F10, F11.

Вызываем надстройку СЕРВИС/ПОИСК РЕШЕНИЯ. В поле «Установить целевую ячейку» даем ссылку на В7. Ставим точку на переключателе «Минимальному значению». В поле «Изменяя ячейки» даем ссылку на G3-J6. Нажимаем «Добавить» и вызываем окно добавление ограничения. Вводим 4 ограничения как показано на рисунке. Нажимаем «Выполнить». Получаем результат, таблица переменных состоит из единиц и нулей, по единицам определяем, что 1-й рабочий должен работать на втором станке, 2-й на 4-м, 3-й на 3-м, 4-й на 1-м. Суммарный процент брака (целевая функция) будет равен 7,9.

Задание 1. На предприятии имеется 6 автомобилей разных моделей. Необходимо в разные районы области перевести 5 грузов. Затраты по перевозке каждого груза каждым автомобилем различны и приведены в таблице:

Выбрать автомобиль для каждого вида груза так, чтобы затраты на перевозку были минимальными. Определить эти затраты.

Обратите внимание, что автомобилей больше, чем грузов, то есть один автомобиль окажется невостребованным. По этой причине во второй группе ограничений будет не равенство их нулю, а знак «£», то есть ограничения будут иметь вид:

Задание 2. Три учебные группы экономического факультета вуза собираются посетить во время практики 6 предприятий и НИИ. Каждая учебная группа может посетить две организации. Путем опроса студентов выявлены предпочтения каждой группы для 10 организаций (1 означает «наиболее предпочтительна», а 10 — «наименее предпочтительна»). Предпочтения каждой из пяти учебных групп показаны в таблице (П-1, П-2, П-3 — промышленные предприятия; НИИ-1, НИИ-2, НИИ-3 — научно-исследовательские институты):

Необходимо:

1. Определите, какие две организации должна посетить каждая группа, чтобы в максимальной степени были учтены предпочте­ния всех студентов.

2. Деканат внес предложение, чтобы каждая группа посетила одно предприятие и один НИИ. Укажите теперь такой вариант распределения, чтобы каждой группе досталось по одному промышленному предприятию и одному НИИ. Чему равна сумма оценочных баллов в этом случае?

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

Если учесть предложение деканата, то надо решить две задачи о назначени­ях: сначала распределить группы по предприятиям, затем — по НИИ. Эти две за­дачи можно представить в виде одной оптимизационной задачи, имеющей сле­дующую таблицу ( М — большое число, например 11):