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

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

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

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

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

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

 

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

 

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

 

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

 

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

 

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

 

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

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

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

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

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

см.рис 3.2.1.

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

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

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

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

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

 

 

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

Б К	Б(1)	Б(2)	Б(3)
К(1)	а11
К(2)		а22
К(3)			а33

 

 

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