4 Задача о назначениях

Задана матрица затрат:

С =

С = =

Известны затраты с _{i j} , связанные с выполнением i-м кандидатом j - й работы. Предполагается, что каждый кандидат может быть назначен только на одну работу и каждая работа может быть выполнена только одним кандидатом.

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

Построение математической модели:

х_{i j} =1, если i -й кандидат назначен на j- ю работу

х_{i j} =0, в противном случае.

По условию:

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

Теперь можно воспользоваться функцией «Поиск решения». Для этого следует ввести данные платежной матрицы, в поле «Запасы» и «Заказы» следует ввести единицы в соответствии с заданной моделью в соответствии с рисунком 8.

Рисунок 8 – Исходные данные к задаче о назначениях

После обработки данных получены следующие результаты в соответствии с рисунком 9.

Рисунок 9 – Результат задачи о назначениях

Таким образом, оптимальная матрица назначений имеет следующий вид:

Минимальное значение целевой функции F_min = 72

Графически данную задачу можно представить в соответствии с рисунком 10.

Рисунок 10 – Результат задачи о назначениях

5 Решение игр

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

Решение: max{7,11,13)=13

min {19,14,19)=19

Пусть (р₁, р_2, р₃) – смешанная стратегия игрока А, (q₁, q₂, q₃) – смешанная стратегия игрока В.

Напомним, что суммы вероятностей равны 1.

Для игрока А:

18р₁ +19 р₂ +15 р₃≥ v

11р₁ +14 р₂ +13 р₃≥ v

7р₁ +11 р₂ +19 р₃≥ v

F = v → max

Преобразуем ограничения, разделив все члены неравенств на v (обозначим y₁ = р₁/v, y₂ = р₂/v, y₃ = р₃/v заметим, что v = 1/(y₁ + y₂₊ y₃)).

18y₁ +19 y₂ +15 y₃≥ 1

11y₁ +14 y₂ +13 y₃≥1

7y₁ +11y₂ +19 y₃≥ 1

F = y₁₊ y₂₊ y₃→ min

Для игрока B:

18q₁ + 11q₂ +7q₃ ≤ v

19q₁ + 14q₂ +11q₃ ≤ v

15q₁ + 13q₂ +19q₃ ≤ v

F = v → min

Преобразуем ограничения, разделив все члены неравенств на v (обозначим х₁ = q₁/v, х₂ = q₂/v, x₃= q₃/v, заметим, что

v= 1/(x₁ + x₂+x₃)).

Итак, задача принимает вид:

18x₁+11x₂+7x₃ ≤ 1

19x₁+14x₂+11x₃ ≤ 1

15x₁+13x₂+19x₃ ≤ 1

f = x₁+x₂+x₃ → max

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

Получено оптимальное решение в соответствии с рисунком 11.

х₁ = 0,05, х₂ =0, х₃= 0,01

v = 1/(x₁ + x₂ + x₃) = 0,06

q₁ = 0,0003, q₂ = 0, q₃ = 0,0006

Расчеты выполняются в среде EXCEL

Рисунок 11 – Результат задачи

Вывод: чтобы обеспечить гарантированный средний проигрыш 0,06 игроку В нужно с вероятностью 0,0003 выбрать первую стратегию и с вероятностью 0,0006 – третью стратегию (или так- чередовать стратегии 1 и 3 в соотношении 1:2).