0
e
Табл. 4 - один з можливих варіантів вирішення, при якому сумарне час очікування одно 62.5 години.
Залишилось 118 рішень. Щоб не перебирати їх все скористаємося алгоритмом угорського методу Кейнса.
Процес рішення розчленовується на кілька етапів.
Етап 1.
У табл. 3 вихідного рішення проведемо такі дії: з значень часу кожної колонки віднімемо мінімальний час в цій колонці (дивись табл. 5).
Табл. 5
1
2
3
4
5
13
7
0.5
0.5
6.5
1
11.5
8.5
2
0
5
2
7.5
7.5
6
6
0
3
0
0
5.5
12.5
7.5
4
8.5
1.5
0
7
12
5
У новій табл. 5 не всі колонки і рядки мають хоча б одне нульове рішення. Та, принаймні, три рішення однозначні. З двох альтернатив четвертого рядка залишимо тільки одну у колонці 1, оскільки час очікування 4.5 години менше ніж час очікування 8 годин. Таким чином ми маємо чотири рішення, близькі до оптимального рішення. Проблемними залишаються рядок 1 і колонка 2. p> Використовуючи той же принцип проведемо таку маніпуляцію: ми звертаємося до діям з рядком 1 і з колонкою 2, бо перетворити рядок 1 з мінімальним числом 0.5, простіше ніж рядок 2 з мінімальним значенням 1.5.
Складемо таблицю 6, яка буде наслідком таблиці 5, коли з усіх значень часу першого рядка віднімемо мінімальний час.
Табл. 6
1
2
3
4
5
12.5
6.5
0
0
6
1
11.5
8.5
2
0
5
2
7.5
7.5
6
6
0
3
0
0
3.5
12.5
7.5
4
8.5
1.5
0
7
12
5
Табл. 6 - другий етап - переміщення нулів і пошук нових. p> У кожному рядку і в кожній колонці має бути лише один нуль.
У колонці 4 залишаємо клітку 4:2.
У колонці 3 по логіці треба залишити нуль внизу, але в цьому випадку не буде вирішена проблема рядки один. Щоб одночасно закрити і рядок і колонку перевагу віддамо часу очікування 9 годин.
Коли вирішується питання рядка 4, то перевагу слід віддати значенням 4.5.
Табл. 7 - оптимальне рішення задачі
1
2
3
4
5
0
0
1
0
0
1
0
0
0
1
0
2
0
0
0
0
1
3
1
0
0
<...
