Як вирішити задачу про призначення. Як знайти мінімальний елемент кожного рядка.

Завдання про призначеннях є окремим випадком транспортної задачі, в якій число пунктів виробництва та пунктів призначення однаково. У цьому випадку матриця транспортної таблиці буде мати квадратну форму. Природно, що для кожного пункту призначення обсяг потреби буде дорівнює 1, а для кожного пункту виробництва величина пропозиції також буде дорівнює 1. Щоб вирішити задачу про призначеннях , скористайтеся угорським методом.
Інструкція
1
Вирішуйте задачу про призначеннях аналогічно будь-якої транспортної задачі і формалізує її у вигляді транспортної таблиці, в рядках якої відображаються призначення, а в шпальтах - відстані до споживачів. У кожному стовпчику таблиці знайдіть мінімальне значення і відніміть його з кожного елемента цього рядка, потім виконайте цю ж операцію для стовпців. Виходить, що тепер в кожному стовпці і кожному рядку ви маєте, принаймні, по одному нульового значення.
2
Знайдіть рядок, яка містить тільки одне нульове значення вартості, і помістіть в цей осередок один елемент. Якщо немає такого рядка, то допускається почати вирішення задачі про призначення з будь-якої комірки, що має нульову вартість.
3
Закреслюйте залишилися нульові значення осередках даного шпальти і повторіть дві останні дії до тих пір, поки продовжувати їх стане вже неможливо.
4
У тому випадку, якщо в рядках залишаться нульові осередки, що залишилися незачеркнутимі, яким не відповідатимуть призначення, то знайдіть стовпець з єдиним нульовим значенням і помістіть у відповідний осередок один елемент. Що залишилися в цьому рядку нульові значення вартості закресліть. Повторіть останні дві дії до тих пір, поки це можливо.
5
Якщо всі елементи розподілені в осередку, яким відповідає нульова вартість, то дане рішення про призначеннях є оптимальним. У тому випадку, якщо воно виявилося неприпустимим, проведіть мінімальна кількість вертикальних і горизонтальних прямих через стовпці і рядки таблиці таким чином, щоб вони пройшли через всі осередки з нульовою вартістю.
6
Визначте мінімальний елемент серед тих, через які не пройшли прямі. Додайте цей елемент до всіх значень елементів матриці, які лежать на перетині проведених прямих. Ті значення елементів, в яких немає перетину прямих, залиште без змін. Після даного перетворення у вас в таблиці з'явиться, принаймні, ще одне нульове значення. Поверніться до кроку 2 і повторіть оптимізацію, поки не отримаєте потрібний результат.
Корисна порада
Суть угорського методу полягає в оптимізації та приведення матриці до такого виду, коли всі підлягають розподілу елементи повинні потрапити в осередки таблиці з нульовою вартістю. При цьому розподіл елементів в клітини з нульовою вартістю дозволить отримати мінімальне значення цільової функції.