Решение задачи о назначениях

Выполнив эту работу, Вы сможете:

· научиться строить математическую модель для задачи о назначениях;

· освоить технологию задач о назначениях в табличном редакторе Microsoft Excel.

Теоретическая часть

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

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

Пример 1.

Выпускники военной академии получают назначения на места службы. Каждый офицер имеет определенные пожелания относительно места службы. В свою очередь, в зависимости от места службы определенные требования предъявляются к офицеру. Желательно заполнить все вакантные места. Необходимо найти наилучшие (с точки зрения обеих сторон) назначения.

Пример 2.

Большая фирма переезжает в новое здание. Возникает необходимость распределить сотрудников по помещениям. С одной стороны, каждый сотрудник выдвигает определенные требования к своим соседям (например, предпочитает некурящих) и к расположению комнаты (например, вблизи от коллег по совместному проекту). С другой стороны, каждое помещение имеет определенные характеристики. Необходимо найти такой вариант распределения, при котором, по меньшей мере, не ухудшился бы психологический климат в коллективе.

Исходные параметры модели:

1. n – количество ресурсов, m – количество работ.

2.  – единичное количество ресурса  (), например: один работник; одно транспортное средство; одна научная тема и т.д.

3.  – единичное количество работы  (), например: одна должность; один маршрут; одна лаборатория.

4.  – характеристика качества выполнения работы  с помощью ресурса . Например, компетентность i-го работника при работе на j-й должности; время, за которое i-е транспортное средство перевезет груз по j-му маршруту; степень квалификации i-й лаборатории при работе над j-й научной темой.

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

1.  – факт назначения или неназначения ресурса  на работу :

2.  – общая (суммарная) характеристика качества распределения ресурсов по работам.

Таблица 36

Общий вид транспортной матрицы задачи о назначениях

	Ресурсы,	Работы,					Количество ресурсов
				…
				…			1
				…			1
	…	…	…	…	…		…
				…			1
	Количество работ	1	1	…	1

Модель задачи о назначениях

;

(22)

                   

В некоторых случаях, например, когда  – это компетентность, опыт работы, или квалификация работников, условие задачи может требовать максимизации ЦФ, в отличие от (22).