Задачи о назначении

Рассматриваемую задачу «о назначении», отнесем, также как и ОЗЛП, к так называемым, «распределительным задачам».

Рассмотрим пример.

Как правило, рассматривается ограниченная величина ресурсов, которых недостаточно для выполнения всех работ наилучшим образом, чтобы достичь максимального эффекта.

В этих условиях необходимо ресурсы распределить так, чтобы поставленная цель была достигнута и получен максимально возможный эффект. Например, минимум затрат, минимальное время на изготовление или проектирование какой-либо системы и т.д.

Распределительные задачи можно разделить на группы:

· по виду целевой функции – на линейные и нелинейные. Линейные, если целевая функция линейно зависит от переменных (фазовых координат). Нелинейная – в противном случае.

· в зависимости от объемов необходимых ресурсов – на сбалансированные и несбалансированные.

· по характеру изменения фазовых координат – с непрерывными фазовыми координатами, целочисленными ФК

· по количеству экстремумов целевой функции

· по характеру изменения ресурсов во времени – на статические и динамические

В конструкторском бюро требуется разработать проект системы управления, включая датчики информации и исполнительные устройства. Примем, что система состоит из n блоков Б(j), к их проектированию может быть привлечено n групп конструкторов К(i). Будем считать, что нам известно время, затрачиваемое i-ой группой конструкторов на разработку j-ого блока (i=1,2,..,n и j=1,2,..,n). Требуется определить какие группы конструкторов должны разрабатывать тот или иной блок, чтобы суммарное время проектирования (подготовки эскизного проекта системы управления) было минимальным. Исходной информацией является матрица затрат (матрица – задание).

За основу принимается матрица задачи-примера (см. рис. 3.2.1)

а₁₁ а₁₂ а₁₃ 50 30 20

а₂₁ а₂₂ а₂₃ = 20 40 40

а₃₁ а₃₂ а₃₃ 40 70 50

Элементы матрицы-задания

а₁₁ – две последние цифры шифра студента

а₂₂ =40+первая из двух последних цифр шифра

а₃₃ =50+вторая из двух последних цифр шифра

Остальные цифры остаются без изменения

Матрица-задание

Решение задачи состоит из следующих основных этапов: