Продовження прикладу розв’язування задачі про призначення

Надалі виділені стовпці та рядки будемо помічати символом “+”. Згідно з наведеним алгоритмом результат виконання першого кроку має такий вигляд

+ + +

0^* 3 2 2

2 0^* 0 2

0 1 4 3

3 2 0^* 0

Далі, виконуючи кроки 2, 3, 4, помічаємо штрихом нуль, розташований у четвертому рядку та четвертому стовпчику, помічаємо четвертий рядок як зайнятий, а також знімаємо мітку з третього стовпця.

+ +

0^* 3 2 2

2 0^* 0 2

0 1 4 3

3 2 0^* 0^’ +

Наступне виконання кроків 3, 4 призводить до матриці

+

0^* 3 2 2

2 0^* 0^’ 2 +

0 1 4 3

3 2 0^* 0^’ +

Оскільки отримана матриця не містить вільних нулів, далі від кроку 3 переходимо до кроку 7, на якому віднімаємо від першого та другого рядків мінімальний вільний елемент (одиницю у третьому рядку та у другому стовпчику) і додаємо цей елемент до першого стовпчика

+

0^* 2 1 1

3 0^* 0^’ 2 +

0 0 3 2

4 2 0^* 0^’ +

Тепер на кроці 4 помічаємо штрихом нуль у третьому рядку та у другому стовпчику і переходимо до кроку 5, на якому отримуємо почерговий ланцюжок

+

0^* 2 1 1

3 0^* 0^’ 2 +

0 0^’ 3 2 +

4 2 0^* 0^’ +

Далі, на кроці 6 отримуємо збільшену кількість виділених нулів, а на наступному кроці 2 алгоритм зупиняється.

+ + + +

0^* 2 1 1

3 0 0^* 2

0 0^* 3 2

4 2 0 0^*

В результаті отримуємо розв’язок: x₁₁ = 1, x₂₃ = 1, x₃₂ = 1, x₄₄ = 1, усі інші змінні дорівнюють нулю, а минимальне значення витрат становить

F_min = c₁₁ + c₂₃ + c₃₂ + c₄₄ = 1 + 10 + 5 + 5 = 21.

Дата добавления: 2014-01-13