logo
макет(пр)_2

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

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

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

Пример 1.

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

Пример 2.

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

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

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

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

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

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

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

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

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

Таблица 36