Задача о назначениях относится к задачам линейного программирования
.pdf
Зарегистрируйся в 2 клика в Кампус и получи неограниченный доступ к материалам с подпиской Кампус+ 🔥
Задача о назначениях относится к задачам линейного программирования, и является частным случаем транспортной задачи. Данная задача формулируется следующим образом. Имеются n работ и n кандидатов для их выполнения. Каждый из кандидатов может выполнить любую работу.
Назначению i-го кандидата (i=1, 2, …,n) на j-ю (j=1, 2, …,n) работу соответствует определенная эффективность (прибыль, производительность) или затраты какого-либо ресурса .
Требуется найти такие назначения кандидатов на все работы, которые обеспечат наибольшую эффективность, т.е. минимум суммарных затрат или максимум прибыли (производительности). При этом каждого кандидата можно назначить на выполнение только одной работы и каждая работа может быть выполнена только одним кандидатом.
Для монтажа четырех объектов (n=4) требуется четыре крана (n=4). Известно время монтажа i-м краном j-го объекта (i=1, 2, 3, 4, j=1, 2, 3, 4) (таблица 1).
Таблица 1 – Затраты времени на монтаж объектов
Код крана Объекты
I II III IV
1 3 7 5 8
2 2 4 4 5
3 4 7 2 8
4 9 7 3 8
Необходимо распределить краны по объектам так, чтобы суммарное время монтажа всех объектов было минимальным. Каждый кран может обслуживать любой объект. На объекте работает только один кран.
Нужно полное решение этой работы?
Решение
Составим математическую модель для решения поставленной задачи.
Обозначим переменные:
xij = 1, если i-ый кран обслуживает j-ый объект0 - в противном случае
сij - время монтажа i-м краном j-го объекта (i=1, 2, 3, 4, j=1, 2, 3, 4)
Математическая постановка данной задачи состоит в определении минимального значения целевой функции:
При условиях:
С учетом исходных данных целевая функция имеет вид:
F=3x11+7x12+5x13+8x14+2x21+4x22+4x23+5x24+4x31+7x32+2x33+8x34+9x41+7x42+3x43+8x44
При условиях:
x11+x12+x13+x14=1
x21+x22+x23+x24=1
x31+x32+x33+x34=1
x41+x42+x43+x44=1
x11+x21+x31+x41=1
x12+x22+x32+x42=1
x13+x23+x33+x43=1
x14+x24+x34+x44=1
Задача о назначениях является сбалансированной, т.к. число объектов равно числу кранов для выполнения работ на данных объектах. Создадим на рабочем листе таблицу для ввода исходных данных (рисунок 1). Заливкой выделены ячейки для ввода формул и вывода результата.
Рисунок 1.
Заполним таблицу.
Блок ячеек В4:Е7 содержит затраты времени сij на монтаж объектов.
Введем необходимые формулы согласно составленной модели задачи.
В ячейки F10:F13 суммарное количество кранов на объекте.
В ячейки В14:Е14 суммарное количество объектов.
В ячейку В16 введем формулу для целевой функции
F=3x11+7x12+5x13+8x14+2x21+4x22+4x23+5x24+4x31+7x32+2x33+8x34+9x41+7x42+3x43+8x44
. Для этого используем функцию=СУММПРОИЗВ ().
Блок ячеек B10:E13 будет содержать оптимальный план распределения кранов по объектам. Значения этих ячеек будет вычислено в процессе решения задачи.
На рисунке 2 покажем таблицу для решения задачи с исходными данными и необходимыми формулами.
Рисунок 2.
Для решения данной задачи используем инструмент MS Excel 2010 Поиск решения. Для этого на вкладке Данные в группе Анализ выберем команду Поиск решения.
На экране отобразится диалоговое окно Параметры поиска решения, в котором установим следующие параметры (рисунок 3):
в поле Оптимизировать целевую функцию указываем адрес ячейки со значением целевой функции – В16;
выбираем нахождение минимума целевой функции;
в поле Изменяя ячейки переменных указываем адреса ячеек со значениями искомых переменных B10:E13;
в списке Выберите метод решения указываем Поиск решения линейных задач симплекс-методом.
В область В соответствии и ограничениями введем ограничения
Задать вопрос
на новый заказ в Автор24.
