7. 4. Задача о назначении
В данном разделе продемонстрируем, как средство Поиск решения позволяет решать задачу о назначении.
В нашем конкретном случае задача о назначении формулируется следующим образом. Имеются четыре рабочих и четыре вида работ. Стоимости Сij выполнения i-ым рабочим j-ой работы приведены в таблице, где под строкой понимается рабочий, а под столбцом – работа:
Стоимость выполнения работ
Рабочие |
1 |
4 |
6 |
3 |
9 |
10 |
7 |
9 |
|
4 |
5 |
11 |
7 |
|
8 |
7 |
8 |
5 |
|
Виды работ
|
||||
Необходимо составить план выполнения работ таким образом, чтобы все работы оказались выполненными, каждый рабочий был загружен только на одной работе, а суммарная стоимость выполнения всех работ была минимальной.
Замечание. Данная задача является сбалансированной, т. е. число работ совпадает с числом рабочих. Если задача несбалансированна, то перед началом решения ее необходимо сбалансировать, введя недостающее число фиктивных строчек или столбцов с достаточно большими штрафными стоимостями работ.
Для решения данной задачи сначала построим ее математическую модель. Обозначим символом Хij переменную, имеющую только два допустимых значения: 0 или 1. Такие переменные называются двоичными. Причем, будем считать, что:
Хij = 1, если i-ым рабочим выполняется j-ая работа;
Хij = 0, если i-ым рабочим не выполняется j-ая работа.
Тогда математическую модель задачи о назначении можно сформулировать следующим образом:
минимизировать
при ограничениях
Для решения этой задачи с помощью средства Поиск решения необходимо выполнить некоторые предварительные действия:
В ячейки диапазона А2: D5 введите стоимости работ.
Отведите ячейки диапазона F2:I5 под неизвестные.
Введите в ячейку J1 функцию цели, вычисляющую стоимость работ:
=СУММПРОИЗВ(А2:D5; F2:I5)
В ячейки диапазонов J2:J5 и F6:I6 введите формулы, задающие левые части ограничений и представленные в следующей ниже таблице.
Ячейка Формула Ячейка Формула
J2 =CYMM(F2:I2) F6 =CYMM(F2:F5)
J3 =СУMM(F3:I3) G6 =СУММ(G2:G5)
J4 =CYMM(F4:I4) H6 =СУММ(Н2:Н5)
J5 =CУMM(F5:I5) I6 =СУММ(12:15)
Рис. 7.10. исходные данные задачи о назначении и заполненное диалоговое окно Поиск решения
Рис. 7.11. Оптимальное решение задачи о назначении
Теперь все готово для поиска решения при помощи средства Поиск решения.
Выберите команду Сервис – Поиск решения и заполните диалоговое окно Поиск решения, как показано на рис. 7.10.
Нажмите кнопку Выполнить. Средство Поиск решения найдет оптимальный план назначений на работы (рис. 7.11).
7. 5. Расходы на маркетинг и рекламу
Условие задачи: какими должны быть расходы на маркетинг и рекламу, чтобы годовой бюджет стал равным 500000 долл. При стоимости каждого проекта 50000 долл.?
Создадим следующую таблицу:
|
Стоимость производства |
Накладные расходы |
Маркетинг |
Реклама |
Стоимость проекта |
Проект 1 |
21427 |
4000 |
5357 |
3214 |
33998 |
Проект 2 |
23747 |
4000 |
5937 |
3562 |
37246 |
Проект 3 |
23840 |
4000 |
5960 |
3576 |
37376 |
Проект 4 |
25555 |
4000 |
6389 |
3833 |
39777 |
Проект 5 |
24144 |
4000 |
6036 |
3622 |
37802 |
Проект 6 |
23162 |
4000 |
5790 |
3474 |
36426 |
Проект 7 |
28156 |
4000 |
7039 |
4223 |
43418 |
Проект 8 |
23413 |
4000 |
5853 |
3512 |
36778 |
Проект 9 |
21219 |
4000 |
5305 |
3183 |
33707 |
Проект 10 |
24875 |
4000 |
6219 |
3731 |
38825 |
Годовой бюджет |
375353 |
||||
Ограничения:
Стоимость проекта равна |
50000 |
Расходы на маркетинг (не менее, чем) |
6000 |
Годовой бюджет не должен превышать |
500000 |
Стоимость каждого проекта рассчитывается как сумма Стоимости производства, Накладных расходов, Маркетинга, Рекламы. Годовой бюджет равен сумме Стоимостей всех проектов.
Скопируем таблицу на другой лист книги и выполним команду Сервис – Поиск решения. В диалоговом окне установим ограничения, как показано на рис. 7.12. После этого нажмем кнопку Выполнить. Результат решения задачи приведен на рис. 7.13.
Рис. 7.12. Исходные данные к задаче и задание ограничений
Рис. 7.13. Решение задачи с помощью Поиска решения