Пример 3.7.1

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

Матрица времен приведена ниже

В -й строке -м столбце матрицы стоит время на выполнение -м ученым -го проекта.

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

Решение.

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

Введем переменные .

Целевая функция задачи имеет вид

Решим задачу венгерским методом, используя приведенную ниже таблицу. В -й строке -м столбце этой таблицы стоит время на выполнение -го проекта -м ученым, ; . Выберем в каждой строке минимальный элемент и запишем его в правом столбце табл. 3.6.2.

Таблица 3.6.2

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

Таблица 3.6.3

Отнимем минимальные элементы из соответствующих столбцов. Перейдем к табл. 3.6.4.

Таблица 3.6.4

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

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

Число отмеченных нулей равно 3, т.е. назначение не является полным. Перейдем к шагу 4 алгоритма.

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

Таблица 3.6.5

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

Таблица 3.6.6

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

Таблица 3.6.7

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

Это назначение является полным, так как число отмеченных нулей равно 4. Получено следующее назначение:

- первый ученый назначается научным руководителем первого проекта: ;

- второй ученый – научный руководитель второго проекта: ;

- третий ученый – научный руководитель третьего проекта: ;

- четвертый ученый – научный руководитель четвертого проекта: .

Время выполнения четырех проектов: С=3+4+2+8 =17.

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

Таблица 3.6.8

- первый ученый руководит первым проектом: ;

- второй ученый руководит четвертым проектом: ;

- третий ученый руководит третьим проектом: ;

- четвертый ученый руководит вторым проектом:

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

С=3*1+5*1+2*1+7*1=17

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

Дата добавления: 2014-01-04