2. Алгоритм угорського методу
Приклад 1
У проектну фірму надійшло замовлення на складання проектів перебудови трьох споруд. Виконати кожен з цих проектів може один з трьох проектантів фірми, однак час виконання роботи кожним робітником буде різним (див. табл. 1.). Розподілити роботи між проектантами таким чином, щоб замовленя було виконано якомога раніше.
|
1 проект |
2 проект |
3 проект |
1-й робітник |
15 діб |
10 діб |
9 діб |
2-й робітник |
9 діб |
15 діб |
10 діб |
3-й робітник |
10 діб |
12 діб |
8 діб |
В кожному рядку знаходимо мінімальний елемент і віднімаємо його від йнших елементів рядка.
|
1 проект |
2 проект |
3 проект |
min |
1-й робітник |
15 |
10 |
9 |
9 |
2-й робітник |
9 |
15 |
10 |
9 |
3-й робітник |
10 |
12 |
8 |
8 |
|
1 проект |
2 проект |
3 проект |
1-й робітник |
6 |
1 |
0 |
2-й робітник |
0 |
6 |
1 |
3-й робітник |
2 |
4 |
0 |
В отриманій матриці в кожному стовпчику знайдемо мінімальний елемент і віднімемо його від інших елементів відповідних стовпчиків.
|
1 проект |
2 проект |
3 проект |
1-й робітник |
6 |
4 |
0 |
2-й робітник |
0 |
6 |
1 |
3-й робітник |
2 |
4 |
0 |
min |
0 |
1 |
0 |
|
1 проект |
2 проект |
3 проект |
1-й робітник |
6 |
0 |
0 |
2-й робітник |
0 |
5 |
1 |
3-й робітник |
2 |
3 |
0 |
В
останній таблиці нульові елементи, що
підкреслені, визначають оптимальний
розв’язок: перший проект виконає 2-й
робітник, 2-й проект – 1-й робітник, 3-й
проект – 3-й робітник. Всі ці проекти
виконаються в мінімально можливий
термін
діб.
В деяких випадках нульові елементи, що отимані на першому та другому кроках алгоритму угорського методу не дозволяють безпосередньо отримати припустимий розв’язок. В таких випадках застосовують додаткові кроки для отримання оптимального розв’зку.
Приклад 2
Припустимо, що в попередньому прикладі представлено чотири робітники та замовлення на виконання чотирьох проектів
|
1 проект |
2 проект |
3 проект |
4 проект |
1-й робітник |
1 діб |
4 діб |
6 діб |
3 доби |
2-й робітник |
9 діб |
7 діб |
10 діб |
9 діб |
3-й робітник |
4 діб |
5 діб |
11 діб |
7 діб |
4-й робітник |
8 діб |
7 діб |
8 діб |
5 діб |
Виконання перших двох кроків алгоритму угорського методу призводить до такої таблиці:
|
1 проект |
2 проект |
3 проект |
4 проект |
1-й робітник |
0 |
3 |
2 |
2 |
2-й робітник |
2 |
0 |
0 |
2 |
3-й робітник |
0 |
1 |
4 |
3 |
4-й робітник |
3 |
2 |
0 |
0 |
Нульові елементи даної таблиці не дозволяють призначити кожному робітнику певний проект. Так, наприклад, якщо ми призначимо першому виконавцю роботу 1, з подальшогу розгляду виключається перший стовпчик, і тоді в рядку для третього робитника не залишиться нульових елементів. В таких випадках виконують такі додаткові кроки:
В останній таблиці проводять мінімальну кількість горизонтальних і вертикальних по рядках прямих з метою викреслення всіх нульових елементів.
|
1 проект |
2 проект |
3 проект |
4 проект |
1-й робітник |
0 |
3 |
2 |
2 |
2-й робітник |
2 |
0 |
0 |
2 |
3-й робітник |
0 |
1 |
4 |
3 |
4-й робітник |
3 |
2 |
0 |
0 |
Знаходять найменший невикреслений елемент і віднімають його від інших невикреслених елментів і додають до елементів, що знаходяться на перетині проведених на попередньому кроці прямих.
В нашому прикладі це елемент 1 (перетин 3-го робітника і 2-го проекту). Результатом описаних вище дій є таблиця:
|
1 проект |
2 проект |
3 проект |
4 проект |
1-й робітник |
0 |
2 |
1 |
1 |
2-й робітник |
3 |
0 |
0 |
2 |
3-й робітник |
0 |
0 |
3 |
2 |
4-й робітник |
4 |
2 |
0 |
0 |
Оптимальний розв’язок показаний підкресленими нулями. Отже, ми отримали таке розподілення робіт між працівниками (табл. 1):
Таблиця 1
Оптимальне розподілення робіт між працівниками
№ проекту |
виконавець |
1 |
1 |
2 |
3 |
3 |
2 |
4 |
4 |
Якщо нова отримана таблиця не дозволяє побудувати припустимий розв’язок, повторюють крок 1 додаткового алгоритму.