Контрольні запитання:
Особливості постановці мережевій ТЗ (МТЗ)?
Які є методи вирішення МТЗ?
Які є обмеження на використання знайомих вам методів вирішення МТЗ?
Література [1, 5]
Практична робота 15. Розв’язання задачі о призначеннях
Мета: набути практичних навичок використання венгерського методу.
Задача
Для працівників і робіт, дана матриця nхn, що задає вартість виконання кожної роботи кожним працівником (викладач видає індивідуально).
Завдання
Знайти мінімальну вартість виконання робіт, таку що кожен працівник виконує рівно одну роботу, а кожну роботу виконує рівно один працівник.
Методичні вказівки
Надалі під призначенням розуміють відповідність між працівниками і роботами, що має нульову вартість, після того як зроблені трансформації, що впливають лише на загальну вартість робіт.
Н
асамперед
запишемо задачу в матричній формі:
де a, b, c, d - працівники, що повинні виконати роботи 1, 2, 3, 4.
Коефіцієнти a1, a2, a3, a4 позначають вартість виконання працівником "a" робіт 1, 2, 3, 4 відповідно. Аналогічний зміст мають інші символи. Матриця квадратна, тому кожен працівник може виконати тільки одну роботу.
Крок 1
Зменшуємо елементи построчно. Знаходимо найменший з елементів першого рядка (а1, а2, а3, а4), і віднімаємо його з всіх елементів першого рядка. При цьому хоча б один з елементів першого рядка обнулится. Те ж саме виконуємо і для всіх інших рядків. Тепер у кожнім рядку матриці є хоча б один нуль. Іноді нулів уже досить, щоб знайти призначення. Приклад показаний у таблиці. Червоні нулі позначають призначені роботи.
0 |
a2' |
0 |
a4' |
b1' |
b2' |
b3' |
0 |
0 |
c2' |
c3' |
c4' |
d1' |
0 |
d3' |
d4' |
При великій кількості нулів для пошуку призначення (нульової вартості) можна використовувати алгоритм перебування максимального паросочетания двочасткових графів, наприклад алгоритм Хопкрофта-Карпа. Крім того, якщо хоча б в одному стовпці немає нульових елементів, то призначення неможливе.
Крок 2
Часто на першому кроці немає призначення, як, наприклад, у наступному випадку:
0 |
a2' |
a3' |
a4' |
b1' |
b2' |
b3' |
0 |
0 |
c2' |
c3' |
c4' |
d1' |
0 |
d3' |
d4' |
Задача може бути ефективно (за нульову вартість) виконана як працівником a, так і працівником c, зате задача 3 не може бути ефективно виконана ніким.
У таких випадках ми повторюємо крок 1 для стовпців і знову перевіряємо, чи можливо призначення.
Крок 3
У багатьох випадках ми досягнемо бажаного результату вже після кроку 2. Але іноді це не так, наприклад:
0 |
a2' |
a3' |
a4' |
b1' |
b2' |
b3' |
0 |
0 |
c2' |
c3' |
c4' |
d1' |
0 |
0 |
d4' |
Якщо працівник d виконує роботу 2, комусь виконувати роботу 3, і навпаки.
У таких випадках ми виконуємо процедуру, описану нижче.
Спочатку, використовуючи будь-який алгоритм пошуку максимального паросочетания в двочастковому графі, призначаємо якнайбільше робіт тим працівникам, що можуть їх виконати за нульову вартість. Приклад показаний у таблиці, призначені роботи виділені червоними.
0 |
a2' |
a3' |
a4' |
b1' |
b2' |
b3' |
0 |
0 |
c2' |
c3' |
c4' |
d1' |
0 |
0 |
d4' |
Відзначимо всі рядки без призначень (рядок 1). Відзначимо всі стовпці з нулями в цих рядках (стовпець 1). Відзначимо всі рядки з нулями в цих стовпцях (рядок 3). Продовжуємо, поки нові рядки і стовпці не перестали відзначатися.
× |
|
|
|
|
0 |
a2' |
a3' |
a4' |
× |
b1' |
b2' |
b3' |
0 |
|
0 |
c2' |
c3' |
c4' |
× |
d1' |
0 |
0 |
d4' |
|
Тепер проводимо лінії через усі відзначені стовпці і невідмічені рядки.
× |
|
|
|
|
0 |
a2' |
a3' |
a4' |
× |
b1' |
b2' |
b3' |
0 |
|
0 |
c2' |
c3' |
c4' |
× |
d1' |
0 |
0 |
d4' |
|
Усі ці дії переслідували лише одну мету: провести найменша кількість ліній (вертикалей і горизонталей), щоб покрити всі червоні нулі. Можна було скористатися будь-як іншим методом замість описаного.
Крок 4
З непокритих лініями елементів матриці (у даному випадку це a2', a3', a4', c2', c3', c4') знайти найменший. Відняти його з усіх не відзначених рядків і додати до всіх перетинань відзначених рядків і стовпців. Так, наприклад, якщо найменший елемент із перерахованих дорівнює а2', ми одержимо
× |
|
|
|
|
0 |
0 |
a3'-а2' |
a4'-a2' |
× |
b1'+a2' |
b2' |
b3' |
0 |
|
0 |
c2'-а2' |
c3'-а2' |
c4'-а2' |
× |
d1'+a2' |
0 |
0 |
d4' |
|
Повторювати процедуру (кроки 1-4) доти, поки призначення не стане можливим.