Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Алгоритм решения задачи о назначениях

Читайте также:
  1. I. Возможности пакета GeoScape и решаемые задачи.
  2. I. Цели и задачи
  3. I. ЦЕЛИ И ЗАДАЧИ ОЛИМПИАДЫ
  4. II. Цели, задачи и основные направления деятельности Совета
  5. III. Обучающие тестовые задачи.
  6. IV стадия - стадия разрешения или фаза об­ ратного развития. 1 страница
  7. IV стадия - стадия разрешения или фаза об­ ратного развития. 10 страница

РЕШЕНИЕ ЗАДАЧИ О НАЗНАЧЕНИЯХ

Задачу о назначениях можно сформулировать следующим образом: имеется n исполнителей и n работ, задана - эффективность выполнения каждой работы каждым исполнителем (таблица, в которой содержатся n 2 чисел, характеризующих эффективность, называется n x n - или n 2 -матрицей). Задача заключается в том, чтобы назначить каждому исполнителю одну и только одну работу таким образом, чтобы оптимизировать заданную функцию эффективности. Математическая модель выглядит следующим образом:

Алгоритм решения задачи о назначениях

(венгерский метод)

В венгерском методе используется следующий принцип: оптимальность решения задачи о назначениях не нарушается при уменьшении (увеличении) элементов строки (столбца) на одну и ту же величину.

Решение считается оптимальным, если все измененные таким образом затраты , () и можно отыскать такой набор , что .

Шаг 1. Получение нулей в каждой строке

Выберем в каждой строке минимальный элемент и запишем его значение в правом столбце. Вычтем минимальные элементы из соответствующих строк. Переход к шагу 2.

Шаг 2. Получение нулей в каждом столбце.

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

Шаг 3. Поиск оптимального решения

Сделаем назначения. Для этого просматривают строку, содержащую наименьшее число нулей. Отмечают один из нулей этой строки и зачеркивают все остальные нули этой строки и того столбца, в котором находится отмеченный нуль. Аналогичные операции последовательно проводят для всех строк. Если назначение, которое получено при всех отмеченных нулях, является полным (число отмеченных нулей равно n), то решение является оптимальным. В противном случае переходят к шагу 4.

Шаг 4. Поиск минимального набора строк и столбцов, содержащих все нули.

Для этого необходимо отметить:

  1. Все строки, в которых не имеется ни одного отмеченного нуля;
  2. Все столбцы, содержащие перечеркнутый нуль хотя бы в одной из отмеченных строк;
  3. Все строки, содержащие отмеченные нули хотя бы в одном из отмеченных столбцов.

Действия 2) и 3) повторяются поочередно до тех пор, пока есть что отмечать. После этого необходимо зачеркнуть каждую непомеченную строку и каждый помеченный столбец.

Цель этого шага – провести минимальное число горизонтальных и вертикальных прямых, пересекающих по крайней мере один раз все нули.

Шаг 5. Перестановка некоторых нулей.

Взять наименьшее число из тех клеток, через которые не проведены прямые. Вычесть его из каждого числа, стоящего в невычеркнутых столбцах и прибавить к каждому числу, стоящему в вычеркнутых строках. Эта операция не изменяет оптимального решения, после чего весь цикл расчета повторить, начиная с шага 3.

 

ПРИМЕР

 

Научный руководитель, i Время выполнения i -м научным руководителем j -го исследовательского проекта
       
         
         
         
         

 

В венгерском методе используется следующий принцип: оптимальность решения задачи о назначениях не нарушается при уменьшении (увеличении) элементов строки (столбца) на одну и ту же величину.

Решение считается оптимальным, если все измененные таким образом затраты , () и можно отыскать такой набор , что .

Выберем в каждой строке минимальный элемент и запишем его значение в правом столбце.

 

Научный руководитель, i Время выполнения i -м научным руководителем j -го исследовательского проекта Минимальное время по строке
       
           
           
           
           

 

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

 

Научный руководитель, i аij
       
         
         
         
         
Минимальное время по графе        

 


Вычтем минимальные элементы из соответствующих столбцов.

Сделаем назначения

 

Научный руководитель, i аij
       
         
         
         
         

 

Научный руководитель, i аij
       
         
         
         
         

 

Научный руководитель, i аij
       
         
         
         
         

 

Число отмеченных (желтым цветом) нулей равно 3, т.е. назначение не является полным (3<4).

Найдем минимальный набор строк и столбцов, содержащий все нули.

 

Научный руководитель, i аij
       
         
         
         
         

 

Научный руководитель, i аij
       
         
         
         
         

 


 

Научный руководитель, i аij
       
         
         
         
         

 

В оставшихся клетках минимальный элемент равен 2.

 

Научный руководитель, i аij
       
         
         
         
         

 

Вычтем минимальный элемент равный 2 из каждого числа (каждой клетки) невычеркнутых (1,2,4) столбцов. Получим таблицу.

 

Научный руководитель, i аij
       
  -2      
  -2 -2   -2
         
         

 

Прибавим минимальный элемент равный 2 к каждому числу вычеркнутых строк в преобразованной таблице. Получим таблицу.

 

Научный руководитель, i аij
       
         
         
         
         

 


Вновь сделаем назначение, отметив по порядку нули в таблице.

 

Научный руководитель, i аij
       
         
         
         
         

 

Это назначение является полным, так как число отмеченных (желтым цветом) нулей равно 4.

Время выполнения всех (четырех) проектов:

Т =3х1+4х1+2х1+8х1=17.

Данное назначение не единственное. Если во второй строке сначала отметить не второй, а четвертый нуль, получим следующее назначение.

 

Научный руководитель, i аij
       
         
         
         
         

 

Время на выполнение всех проектов не изменилось:

Т =3х1+5х1+2х1+7х1=17.

Таким образом, получены два оптимальных назначения, которым соответствует минимальное время выполнения проектов равное 17 месяцам.

Дата добавления: 2015-08-09; просмотров: 205 | Нарушение авторских прав

<== предыдущая страница | следующая страница ==>
Шаг 3. Определение множества дуг для дальнейшего ветвления.| А. Нова гра
mybiblioteka.su - 2015-2024 год. (0.012 сек.)