2015-05-18
846
Требуется построить три объекта Oбj 
. К работе могут быть привлечены три бригады Брi 
. Каждая бригада из-за ограниченности своих ресурсов может одновременно строить только один объект. Каждый объект из-за технологических особенностей может строиться только одной бригадой. Известны сметные стоимости, которые установлены 
бригадой для 
объекта. Эти суммы (в тыс. руб.) приведены в матрице затрат 
:
| Об1 | Об2 | Об3 | |
| Бр1 | |||
| Бр2 | |||
| Бр3 |
Требуется разработать оптимальное по стоимости распределение бригад работников по объектам обслуживания.
Создадим ментальную карту по условиям задачи:
На связях бригад с объектами указаны нормативные коэффициенты — суммы, запрашиваемые бригадами за строительство объектов. Для удобства сравнения бригад между собой справа приведены суммарные стоимости работ каждой бригады для всех трех объектов. Из рисунка сразу видно, что Бригада 3 имеет наименьшие суммарные затраты. Но мы вынуждены учитывать ограничения по назначениям на работы: одна бригада может строить только один объект.
Математическая модель должна включать в себя три матрицы:
- матрицу назначений
; - матрицу нормативных коэффициентов ;
- матрицу затрат
.
Бинарные элементы матрицы назначений бригад на объекты равны 1, если 
бригада обслуживает 
объект и равны нулю в противоположном случае. При этом каждая бригада может одновременно обслуживать только один объект, и каждый объект может обслуживаться только одной бригадой. Поэтому сумма чисел по строкам и столбцам матрицы равна 1.
— матрица нормативных коэффициентов (тыс. руб.). Это матрица констант — они не меняются в процессе решения задачи.
Матрица затрат должна быть получена перемножением матрицы назначений на матрицу нормативных коэффициентов:
, 
; 
.
На листе книги таблицы выглядят следующим образом:
В ячейки матриц X и Z вставлены формулы:
В качестве целевой функции выбираем общие затраты (ячейка Е20). Целью решения является минимизация этой функции.
По команде Данные — Поиск решения вызываем надстройку "Поиск решения". Диалоговое окно вместе с результирующими данными показано на рисунке.
Суммарные затраты 228 тыс. руб. являются оптимальными при таком распределении работ по объектам:
- бригада 1 строит объект Об1;
- бригада 2 строит объект Об2;
- бригада 3 строит объект Об3.
Интересно, что в данной задаче имеется несколько оптимальных решений. Непосредственно из матрицы затрат видно, что суммарные затраты также равны 228 тыс. руб. и при некоторых других распределениях работ по объектам.
Часто оптимальное решение математической модели не может быть воплощено в практику по самым разным причинам. Поэтому необходимо при планировании проводить вариантный анализ задачи, просчитывая возможные осложнения. Предположим, в частности, что самая "дешевая" бригада 3 нашла себе срочную другую работу и пока не может быть назначена на наши объекты. Но бригада 2 и бригада 3 увеличили свои ресурсы и имеют возможность строить по два объекта. Какой же бригаде поручить строить два объекта?
В этом варианте решения изменятся лишь ограничения на сумму бинарных коэффициентов. Для бригады 1 и бригады 2 эта сумма может быть равной 1 или 2, а для бригады 3 эта сумма равна 0:
Решение будет выглядеть следующим образом:
Бригада 1 будет строить объект Об2, а бригада 2 будет строить два объекта: Об1 и Об3. Но наши расходы в этом варианте возрастут на 10 000 руб.
Задача 3. Составление расписания занятий учебных групп
По учебному плану недельная нагрузка для учебной группы второго курса должна составлять 36 часов — по шесть учебных часов (или по три "пары") в день:
- математика 12 часов (6 пар);
- информатика 8 часов (4 пары);
- экономика 4 часа (2 пары);
- английский язык 4 часа (2 пары);
- бухгалтерия 4 часа (2 пары);
- делопроизводство 4 часа (2 пары).
Составить расписание занятий для двух групп на неделю так, чтобы в один день у каждой группы были по три разных дисциплины.
В данной задаче удобно при расчетах за единицу измерения выбрать сдвоенный учебный час, т.е. "пару", как это и делается при составлении расписаний на практике. Математическая модель должна включать в себя бинарную матрицу назначений. Число 1 обозначает, что занятие есть, а число 0 обозначает, что занятия нет.
В задаче нет нормативных коэффициентов, так как все занятия считаются одинаково ценными. Поэтому нужно просто сравнивать количество занятий с заданными ресурсами студентов и преподавателей. Ресурс студентов одинаков для всех дней недели и составляет три пары. Ресурс преподавателей для каждой группы определен учебным планом и изложен в условиях задачи.
Обе группы рассмотрим в одной таблице, заполнив матрицу нормативных коэффициентов единицами:
В строке 10 суммируем число занятий студентов в день, а в столбцах N и O суммируем число занятий по дисциплинам по Гр.1 и Гр.2 соответственно. Целевую функцию помещаем в ячейку P10 как сумму ячеек N10 и O10.
В таблице присутствуют формулы автосуммы:
Десять столбцов скрыты, формулы в них аналогичны формулам в столбцах В и С.
Далее устанавливаем параметры "Поиска решения":
В результате поиска выдается одно из допустимых решений:
Данный процесс составления расписаний позволяет учитывать отдельные пожелания преподавателей. Например, преподаватель английского языка не может приходить по понедельникам. Тогда в параметры поиска решения вводим новое ограничение: В7:С7=0.
