Розділ 3. Розв'язування задачі про призначення

Розв’язування задачі угорським методом

Розглянемо ситуацію, яку можна записати у вигляді задачі про призначення. Студент Тарас, у зв’язку зі станом здоров’я, пропустив майже цілий семестр. П’ятеро студентів вирішили йому допомогти у підготовці до іспитів. Кожен студент може допомогти в підготовці до одного іспиту. Ефективність допомоги виражена в балах, які студенти отримали за поточну успішність під час поточного семестру, представлена у таблиці 3.1.

Таблиця 3.1

Потрібно так закріпити предмети за студентами, щоб Тарас склав іспити з найкращим з можливих сумарним результатом.

Математична модель задачі

F=48×11+36×12+43×13+45×14+39×15+40×21+41×22+49×23+38×24+32×25+47×31+

+47×32+44×33+48×34+40×35+50×41+46×42+38×43+36×44+41×45+43×51+35×52+

+32×53+34×54+25×55>max

Поетапний розв’язок задачі

Таблиця вихідних умов (табл. 3.2).

Таблиця 3.2

У таблиці 3.2 n=m, тому її можна розв’язати угорським методом.

Попередній етап. Цільова функція задачі направлена на максимум, тому розшукують максимальний елемент в j-му стовпці й всі елементи цього стовпця послідовно віднімають із максимального. Отримаємо таблицю 3.3:

Таблиця 3.3

Далі розглядають i-тий рядок таблиці 3.3, розшукують в ній мінімальний елемент і з кожного елемента цього рядка віднімають мінімальний. Отримують таблицю 3.4, яка еквівалентна таблиці 3.2:

Таблиця 3.4

Відзначаємо систему незалежних нулів:

Таблиця 3.5

Якщо кількість 0* дорівнює n, тоді задачу можна вважити розв’язаною. У цій задачі 0*.

Зауваження. Перед початком кожної ітерації знаком '+' виділяють стовпці, які містять нулі із зірочками (табл. 3.6).

Таблиця 3.6

Перший етап. У таблиці 3.6 виділяють штрихом нуль, який знаходиться одночасно у невиділеному стовпці та у рядку з нулем із зірочкою. З нуля з зірочкою і з стовпця, в якому він знаходиться, знімають виділення. Відмічають рядок, в якому знаходиться нуль зі штрихом (табл. 3.7).

Таблиця 3.7

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

Третій етап. Серед невиділених елементів матриці вибирають мінімальний і позначають його h (h>0). Далі віднімають h із всіх елементів матриці, розташованих у невиділених рядках і додають до всіх елементів, розташованим у виділених стовпцях. У результаті одержують нову матрицю С'1(табл. 3.8), еквівалентну С1. У даній задачі h=1.

Таблиця 3.8

Перший етап. Знайшли такий невиділений нуль у рядку, де немає нуля із зірочкою. Тоді переходять до другого етапу, відзначивши цей нуль штрихом (табл. 3.9).

Таблиця 3.9

Другий етап. Будують ланцюжок з нулів матриці С1?: вихідний нуль зі штрихом, нуль із зірочкою, розташований в одному стовпці з першим нулем зі штрихом в одному рядку з попереднім нулем із зірочкою й т.д.

Далі над елементами ланцюжка, що знаходяться на непарних місцях (0') ставимо зірочки, знищуючи їх над парними елементами (0*). Потім знищуємо всі штрихи над елементами С1 і знаки виділення '+'. Перша ітерація закінчена. Отримали матрицю С2 (табл. 3.10).

Таблиця 3.10

Після цієї ітерації кількість незалежних нулів стало дорівнювати 5 (розмірності матриці 5) і тому алгоритм закінчує роботу. Шукані елементи призначення відповідають позиціям незалежних нулів матриці С2 (тобто 0*).

L (x) = 43+47+49+45+41=225.

Відповідь. Щоб Тарас склав іспити з максимально можливим результатом, одногрупники повинні допомагати йому в підготовці у такій відповідності:

Петро — ПСЕП;

Оля — маркетинг;

Юра — дискретний аналіз;

Юля — дослідження операцій;

Катя — СППР.