Решить задачи о назначениях с индивидуальными предпочтениями

Решить минимаксные и максиминные задачи о назначениях.

Задача 5.1.

J(i)/R(i)	R(1)	R(2)	R(3)	R(4)	R(5)
J(1)
J(2)
J(3)
J(4)
J(5)

Задача 5.2.

J(i)/R(i)	R(1)	R(2)	R(3)	R(4)	R(5)
J(1)
J(2)
J(3)
J(4)
J(5)

Задача 5.3.

J(i)/R(i)	R(1)	R(2)	R(3)	R(4)	R(5)
J(1)
J(2)
J(3)
J(4)
J(5)

Задача 5.4.

J(i)/R(i)	R(1)	R(2)	R(3)	R(4)	R(5)
J(1)
J(2)
J(3)
J(4)
J(5)

Задача 5.5.

J(i)/R(i)	R(1)	R(2)	R(3)	R(4)	R(5)
J(1)
J(2)
J(3)
J(4)
J(5)

Задача 5.6.

J(i)/R(i)	R(1)	R(2)	R(3)	R(4)	R(5)
J(1)
J(2)
J(3)
J(4)
J(5)

Задача 5.7.

J(i)/R(i)	R(1)	R(2)	R(3)	R(4)	R(5)
J(1)
J(2)
J(3)
J(4)
J(5)

Задача 5.8.

J(i)/R(i)	R(1)	R(2)	R(3)	R(4)	R(5)
J(1)
J(2)
J(3)
J(4)
J(5)

Задача 5.9.

J(i)/R(i)	R(1)	R(2)	R(3)	R(4)	R(5)
J(1)
J(2)
J(3)
J(4)
J(5)

Задача 5.10.

J(i)/R(i)	R(1)	R(2)	R(3)	R(4)	R(5)
J(1)
J(2)
J(3)
J(4)
J(5)

Рассмотрим задачу о назначении 4 исполнителей по 4 работам при условиях, что исполнителями на множестве работ заданы предпочтения, т.е., каждый исполнитель упорядочивает все работы в порядке своих индивидуальных предпочтений независимо от производительностей.

Пусть матрица производительностей R (размера 5x5) имеет вид:

J(i)/R(i)	R(1)	R(2)	R(3)	R(4)
J(1)
J(2)
J(3)
J(4)

Матрица предпочтений пусть имеет вид:

R(2)	R(2)	R(1)	R(1)
R(4)	R(1)	R(2)	R(4)
R(1)	R(3)	R(4)	R(3)
R(3)	R(4)	R(3)	R(2)
J(1)	J(2)	J(3)	J(4)

Здесь первый столбец определяет предпочтения исполнителя J(1) на множестве работ, причем самой “лучшей” для него является работа R(3), следующей по предпочтению R(1), затем R(4) и “наихудшей” R(2).

Решение задачи о назначениях называется некомпроментируемым, если не существует другого решения задачи о назначениях, при котором ни одному из исполнителей не будет назначена работа “худшая” по его предпочтениям, а хотя бы одному - “лучшая”.

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

Для решения этой задачи применим схему метода ветвей и границ.

Процедуры оценок.

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

назначаем очередного исполнителя на “лучшую” для него (в смысле его индивидуальных предпочтений) работу, еще не назначенную другим исполнителям.

Для нашего примера получаем

J(1) - R(3), J(2) - R(4), J(3) - R(2), J(4) - R(1).

Тогда H=12.

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

Оптимальное решение канонической задачи определяется следующими назначениями:

J(1) - R(3), J(2) - R(2), J(3) - R(1), J(4) - R(4), отсюда V=20.

Процедура ветвления.

Из начальной вершины осуществляем ветвление по 4 направлениям, причем i -ое направление соответствует назначению исполнителя с номером i на работу, “лучшую” по его индивидуальным предпочтениям.

Направление 1. J(1) - R(3).

Направление 2. J(2) - R(4).

Направление 3. J(3) - R(3).

Направление 4. J(4) - R(2).

В направлении 1 “некомпроментируемое” решение определяется назначениями:

J(1) - R(3), J(2) - R(4), J(3) - R(2), J(4) - R(1).

Тогда H=12.

Решение канонической задачи о назначениях определяется назначениями:

J(1) - R(3), J(2) - R(2), J(3) - R(1), J(4) - R(4), отсюда V=20.

В направлении 2 “некомпроментируемое” решение определяется назначениями:

J(1) - R(3), J(2) - R(4), J(3) - R(2), J(4) - R(1).

Тогда H=12.

Решение канонической задачи о назначениях определяется назначениями:

J(1) - R(3), J(2) - R(4), J(3) - R(1), J(4) - R(2), отсюда V=18.

В направлении 3 “некомпроментируемое” решение определяется назначениями:

J(1) - R(1), J(2) - R(4), J(3) - R(3), J(4) - R(2).

Тогда H=12.

Решение канонической задачи о назначениях определяется назначениями:

J(1) - R(1), J(2) - R(2), J(3) - R(3), J(4) - R(4), отсюда V=14.

В направлении 4 “некомпроментируемое” решение определяется назначениями:

J(1) - R(3), J(2) - R(4), J(3) - R(2), J(4) - R(2).

Тогда H=12.

Решение канонической задачи о назначениях определяется назначениями:

J(1) - R(3), J(2) - R(4), J(3) - R(1), J(4) - R(2), отсюда V=15.

В направлении 1 есть 3 варианта:

Вариант 1. J(1) - R(3), J(2) - R(4).

“Некомпроментируемое” решение: J(3) - R(2), J(4) - R(1), определяет H=12.

Оптимальное решение канонической задачи определяется решением:

J(3) - R(1), J(4) - R(2), отсюда V=15.

Вариант 2. J(1) - R(3), J(3) - R(4).

“Некомпроментируемое” решение: J(2) - R(1), J(4) - R(2), определяет H=14.

Оптимальное решение канонической задачи определяется решением:

J(2) - R(1), J(4) - R(2), отсюда V=14.

Вариант 3. J(1) - R(3), J(4) - R(2).

“Некомпроментируемое” решение: J(2) - R(1), J(3) - R(4), определяет H=14.

Оптимальное решение канонической задачи определяется решением:

J(2) - R(4), J(3) - R(1), отсюда V=15.

Процедура отбрасывания неперспективных направлений позволяет отбросить направление 3, так как в этом направлении V=14, а вариант 3 имеет значение нижней оценки H=14.

Продолжаем зондирование в направлении 1, вариант 1.

Случай 1. J(1) - R(3), J(2) - R(4), J(3) - R(2), J(4) - R(1).

Верхняя оценка совпадает с нижней V=H=12.

Случай 2. J(1) - R(3), J(2) - R(4), J(4) - R(2), J(3) - R(1). Верхняя оценка совпадает с нижней V=H=15.

Результаты, полученные в случае 2 (есть решение со значением критерия 15) позволяют отбросить вариант 2 (лучшее возможное решение имеет значение критерия 14), вариант 3 (лучшее возможное значение критерия равно 15), случай 1 (значение критерия 12) и направление 4 (лучшее возможное значение критерия 15).

Осталось провести зондирование в направлении 2.

В направлении 2 есть три варианта.

Вариант 1. J(2) - R(4), J(1) - R(3).

“Некомпроментируемое” решение: J(3) - R(2), J(4) - R(1), определяет H=12.

Оптимальное решение канонической задачи определяется решением:

J(3) - R(1), J(4) - R(2), отсюда V=15.

Вариант 2. J(2) - R(4), J(3) - R(3).

“Некомпроментируемое” решение: J(1) - R(1), J(4) - R(2), определяет H=9.

Оптимальное решение канонической задачи определяется решением:

J(1) - R(), J(4) - R(2), отсюда V=9.

Вариант 3. J(2) - R(4), J(4) - R(2).

“Некомпроментируемое” решение: J(1) - R(3), J(3) - R(1), определяет H=15.

Оптимальное решение канонической задачи определяется решением:

J(1) - R(3), J(3) - R(1), отсюда V=15.

Варианты 1,2 и 3 могут быть отброшены, так как в вышеописанном случае 2 есть решение со значением критерия 15.

Таким образом, оптимальное решение исходной задачи определяется назначениями (случай 2)

J(1) - R(3), J(2) - R(4), J(4) - R(2), J(3) - R(1).

Эти назначения являются “некомпроментируемые”, так как исполнители J(1), J(2) и J(4) назначены на лучшие (в смысле их индивидуальных предпочтений) работы и среди “некомпроментируемых” дают максимальное значение суммарной производительности.

Оптимальное решение исходной задачи имеет вид:

x’(1,3)=1, x’(2,4)=1, x’(3,1)=1, x’(4,2)=1, значения остальных переменных в оптимальном решении нули. Оптимум задачи F(X’)=15.

Дата добавления: 2017-02-01