5. ЛАБОРАТОРНАЯ РАБОТА №4 “ДВУХИНДЕКСНЫЕ
ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. ЗАДАЧА О НАЗНАЧЕНИЯХ”
5.1.
ЦЕЛЬ РАБОТЫ
Приобретение
навыков построения математических моделей задач о назначении и решения этих
задач в Microsoft Excel.
5.2.
ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ
Постройте
модель задачи, включая транспортную таблицу.
Найдите
оптимальное решение задачи с помощью Excel и представьте его преподавателю.
5.3.
ЗАДАЧА О НАЗНАЧЕНИЯХ. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ
Задача о назначениях
– это РЗ, в которой для выполнения каждой работы требуется один и только
один ресурс (один человек, одна автомашина и т.д.), а каждый ресурс может быть
использован на одной и только одной работе. То есть ресурсы не делимы между
работами, а работы не делимы между ресурсами. Таким образом, задача о
назначениях является частным случаем ТЗ. Задача о назначениях имеет место при
назначении людей на должности или работы, автомашин на маршруты, водителей на
машины, при распределении групп по аудиториям, научных тем по
научно-исследовательским лабораториям и т.п.
Исходные
параметры модели задачи о назначениях
1. n – количество ресурсов,
m – количество
работ.
2. – единичное количество ресурса (), например: один работник; одн транспортное средство; одна
научная тема и т.д.
3. – единичное количество работы (), например: одна должность; один маршрут; одна лаборатория.
4. – характеристика качества выполнения работы с помощью ресурса . Например, компетентность i-го работника при работе на j-й должности; время, за которое i-е транспортное средство перевезет груз
по j-му маршруту;
степень квалификации i-й
лаборатории при работе над j-й
научной темой.
Искомые
параметры
1. – факт назначения или неназначения ресурса на работу :
2. – общая (суммарная) характеристика качества
распределения ресурсов по работам.
Таблица 5.1
Общий вид транспортной матрицы задачи о
назначениях
Ресурсы,
|
Работы,
|
Количество ресурсов
|
|
|
…
|
|
|
|
|
…
|
|
1
|
|
|
|
…
|
|
1
|
…
|
…
|
…
|
…
|
…
|
…
|
|
|
|
…
|
|
1
|
Количество работ
|
1
|
1
|
…
|
1
|
|
Модель задачи о назначениях
;
|
(5.1)
|
Специфическая
структура задачи о назначениях позволила разработать так называемый "Венгерский метод" ее
решения. Поэтому, хотя в Excel
такие задачи решаются обычным симплекс-методом, в лабораторной работе требуется
построить модель задачи о назначениях вида (5.1). В некоторых случаях, например,
когда – это компетентность, опыт работы, или квалификация
работников, условие задачи может требовать максимизации ЦФ, в отличие от (5.1).
В этом случае ЦФ заменяют на и решают задачу с ЦФ , что равносильно решению задачи с ЦФ .
5.4.
ПОСТАНОВКА ЗАДАЧИ О НАЗНАЧЕНИЯХ
Отдел
кадров предприятия устроил конкурсный набор специалистов на две вакантные
должности. На эти новые места (НМ) претендуют 3 прежних сотрудника (ПС), уже работающие
в других отделах, и 4 новых сотрудника (НС). Номера новых сотрудников, новых и
прежних мест выбираются по вариантам из табл.5.2. Номера прежних мест являются
номерами прежних сотрудников.
Отдел
кадров оценил по десятибалльной шкале компетентность новых сотрудников
(табл.5.3) и прежних сотрудников (табл.5.4) для работы и на новых местах, и на
прежних местах (ПМ), то есть занимаемых прежними сотрудниками. Необходимо
учесть, что руководство предприятия, во-первых, предпочитает, чтобы прежние
сотрудники не претендовали на места друг друга, и, во-вторых, не намерено
увольнять прежних сотрудников.
Необходимо
распределить сотрудников по должностям наилучшим образом.
5.5.
РЕКОМЕНДАЦИИ К РЕШЕНИЮ ЗАДАЧИ О НАЗНАЧЕНИЯХ
1. Процесс
приведения задачи о назначениях к сбалансированному виду имеет свои особенности
по сравнению с ТЗ. Если условие сбалансированности задачи (4.2) не выполняется
из-за нехватки работ или исполнителей в количестве , то для создания баланса надо ввести такое же количество фиктивных строк или
столбцов.
2.
Особенностью решения данной задачи является моделирование системы предпочтений,
сложившейся у руководства предприятия по описанному в условии задачи кадровому
вопросу.
3. В задаче о
назначениях увольнение прежнего сотрудника или непринятие на работу нового
сотрудника моделируется попаданием единицы в фиктивный столбец матрицы решений
задачи, поэтому для запрещения или разрешения таких ситуации необходимо
использовать соответствующие "тарифы".
4. Значения
"тарифов" выбираются в
зависимости от направления оптимизации ЦФ задачи о назначениях ( или ). При этом руководствуются принципом
"невыгодности" запрещенных назначений. Так, если – это общая компетентность работников, то в качестве
запрещающих надо выбирать нулевые компетентности . А если – это общее время прохождения машинами транспортных
маршрутов, то в качестве запрещающих надо выбирать значения , превосходящие по величине максимальные реальные значения .
5. При решении
задач о назначении в Excel
необходимо учитывать, что переменные являются булевыми.
|