Двухиндексные задачи линейного программирования. Задача о назначениях

ЛАБОРАТОРНАЯ РАБОТА № 4

ДВУХИНДЕКСНЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. ЗАДАЧА О НАЗНАЧЕНИЯХ

ЦЕЛЬ РАБОТЫ

Приобретение навыков построения математических моделей задач о назначении и решения этих задач в Microsoft Excel.

ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ

1. Согласно номеру своего варианта выберите условие задачи.
2. Постройте модель задачи, включая транспортную таблицу.
3. Найдите оптимальное решение задачи с помощью Excel и представьте его преподавателю.
4. Оформите отчет по лабораторной работе, который должен содержать:

• титульный лист (см. рис. 2.1);
• транспортную таблицу и модель задачи с указанием всех единиц

измерения;

• результат решения задачи с указанием единиц измерения.

ЗАДАЧА О НАЗНАЧЕНИЯХ. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ [1,3, 6, 7]

Задача о назначениях — это РЗ, в которой для выполнения каждой работы требуется один и только один ресурс (один человек, одна автомашина и т.д.), а каждый ресурс может быть использован на одной и только одной работе. То есть ресурсы не делимы между работами, а работы не делимы между ресурсами. Таким образом, задача о назначениях является частным случаем ТЗ. Задача о назначениях имеет место при назначении людей на должности или работы, автомашин на маршруты, водителей на машины, при распределении групп по аудиториям, научных тем по научно-исследовательским лабораториям и т.п.

Исходные параметры модели задачи о назначениях
 

Искомые параметры

ПОСТАНОВКА ЗАДАЧИ О НАЗНАЧЕНИЯХ

Отдел кадров предприятия устроил конкурсный набор специалистов на две вакантные должности. На эти новые места (НМ) претендуют 3 прежних сотрудника (ПС), уже работающие в других отделах, и 4 новых сотрудника (НС). Номера новых сотрудников, новых и прежних мест выбираются по вариантам из табл. 5.2. Номера прежних мест являются номерами прежних сотрудников.

Отдел кадров оценил по десятибалльной шкале компетентность новых сотрудников (табл. 5.3) и прежних сотрудников (табл. 5.4) для работы и на новых местах, и на прежних местах (ПМ), то есть занимаемых прежними сотрудниками. Необходимо учесть, что руководство предприятия, во-первых, предпочитает, чтобы прежние сотрудники не претендовали на места друг друга, и, во-вторых, не намерено увольнять прежних сотрудников.

Необходимо распределить сотрудников по должностям наилучшим образом.

РЕКОМЕНДАЦИИ К РЕШЕНИЮ ЗАДАЧИ О НАЗНАЧЕНИЯХ

1. Процесс приведения защиты о назначениях к сбалансированному виду имеет свои особенности по сравнению с ТЗ. Если условие сбалансированности задачи (4.2) не выполняется из-за нехватки работ или исполнителей в количестве kab, то для создания баланса надо ввести такое же количество kab фиктивных строк или столбцов. 
2. Особенностью решения данной задачи является моделирование системы предпочтений, сложившейся у руководства предприятия по описанному в условии задачи кадровому вопросу.
3. В задаче о назначениях увольнение прежнего сотрудника или неприятие на работу нового сотрудника моделируется попаданием единицы в фиктивный столбец матрицы решений задачи, поэтому для запрещения или разрешения таких ситуаций необходимо использовать соответствующие «тарифы».
4. Значения «тарифов» cij выбираются в зависимости от направления оптимизации ЦФ задачи о назначениях (L(X) – max или L(X)-min). При этом руководствуются принципом «невыгодности» запрещенных назначений. Так, если L(X) – это общая компетентность работников, то в качестве запрещающих надо выбирать нулевые компетентности cij. А если L(X) – это общее время прохождения машинами транспортных маршрутов, то в качестве запрещающих надо выбирать значения cij превосходящее по величине максимальные реальные значения cij. 
5. При решении задач о назначении в Excel необходимо учитывать, что переменные xij являются булевыми.

ВАРИАНТЫ

Таблица 5.2

Номера сотрудников и мест их работы для конкретного варианта

Таблица 5.3

Компетентность новых сотрудников

Таблица 5.4

Компетентность прежних сотрудников

ПРИМЕРНЫЕ ВОПРОСЫ НА ЗАЩИТЕ РАБОТЫ

1. Какова постановка задачи о назначениях?
2. В чем отличие модели задачи о назначениях от модели ТЗ?
3. Каковы исходные и искомые параметры задачи о назначениях?
4. Запишите математическую модель задачи о назначениях.
5. Как записать модель задачи о назначениях, подразумевающую максимизацию ЦФ, в виде (5.1)?
6. Каким образом в модели задачи о назначениях можно запретить конкретное назначение?
7. В чем особенности процесса приведения задачи о назначениях к сбалансированному виду?
8. Поясните модель задачи о назначениях, построенную по заданному варианту.