 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Рассмотрим пример задачи о назначениях
Институт получил гранты на выполнение пяти исследовательских проектов (столбцы). В качестве научных руководителей проектов рассматриваются кандидатуры шестерых ученых (строки), обладающих различным опытом и способностями. Каждый ученый оценил время, необходимое ему для реализации проектов в месяцах. Требуется выбрать научного руководителя для выполнения каждого проекта так, чтобы суммарное время выполнения всех проектов было минимальным.
Т.к. матрица "стоимостей назначений" не является квадратной, решение задачи в исходном виде невозможно. Необходимо добавить фиктивный ресурс - дополнительный, шестой, проект. Исходя из того, что задача на минимум, в дополнительном столбце со стоимостями назначений необходимо проставить какие-либо большие числа.
| Проекты | ||||||
| Ученые | 6* | |||||
На листе Excel организовываем две таблицы (рис. 2.206)
Рис. 2.206
В первой занесены условия задачи, а во второй на месте нулей (ячейки с М14 по R19) с помощью надстройки Поиск решения получим матрицу назначений (ответ задачи).
Кроме этого, необходимо завести целевую ячейку – ячейка, где вычислена общее время выполнения всех проектов с помощью функции СУММПРОИЗВ (рис. 2.206).
В ячейках, выделенных красным цветом, введены функции суммы по строчкам (ячейки S14:S19) с помощью функции СУММ, и аналогично, суммы по столбцам (ячейки М20:R20).
После этого можно запускать надстройку Поиск решения (вкладка Данные). (рис. 2.207)
Рис. 2.207 Диалоговое окно Поиск решения
В диалоговом окне выставлены следующие параметры поиска решения:
| Оптимизировать целевую функцию | S20 | Общее время выполнение всех проектов должно быть минимально |
| Изменяемые ячейки переменных | M14:R19 | Двоичная переменная: 1 - ученый назначен на проект, 0 - в противном случае |
| Ограничения | M14:R19=двоич | Изменяемые переменные могут принимать значения 0 или 1 |
| M20:R20=1 | На каждый проект должен быть назначен только 1 ученый | |
| S14:S19=1 | Каждый ученый должен быть назначен только на 1 проект |
После нажатия кнопки Найти решение, в изменяемых ячейках увидим назначение:
И соответствующий ответ на задачу сформулируем следующим образом:
Научным руководителем для выполнения 1-го проекта необходимо выбрать 1-го ученого;
Научным руководителем для выполнения 2-го проекта необходимо выбрать 2-го ученого;
Научным руководителем для выполнения 3-го проекта необходимо выбрать 5-го ученого;
Научным руководителем для выполнения 4-го проекта необходимо выбрать 3-го ученого;
Научным руководителем для выполнения 5-го проекта необходимо выбрать 6-го ученого;
Т.к. 6* проект является фиктивным, 4-й ученый не будет привлечен.
Суммарное время выполнения всех проектов составит 20-10=10 месяцев.
Поиск по сайту: