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

Завдання про призначеннях є окремим випадком транспортної задачі, в якій число пунктів виробництва та пунктів призначення однаково. У цьому випадку матриця транспортної таблиці буде мати квадратну форму. Природно, що для кожного пункту призначення обсяг потреби буде дорівнює 1, а для кожного пункту виробництва величина пропозиції також буде дорівнює 1. Щоб вирішити задачу про призначеннях, скористайтеся угорським методом.

Інструкція

Вирішуйте задачу про призначеннях аналогічно будь-якої транспортної задачі і формалізує її у вигляді транспортної таблиці, в рядках якої відображаються призначення, а в шпальтах - відстані до споживачів. У кожному стовпчику таблиці знайдіть мінімальне значення і відніміть його з кожного елемента цього рядка, потім виконайте цю ж операцію для стовпців. Виходить, що тепер в кожному стовпці і кожному рядку ви маєте, принаймні, по одному нульового значення.

Знайдіть рядок, яка містить тільки одне нульове значення вартості, і помістіть в цей осередок один елемент. Якщо немає такого рядка, то допускається почати вирішення задачі про призначення з будь-якої комірки, що має нульову вартість.

Закресліть залишилися нульові значення осередках даного шпальти і повторіть дві останні дії до тих пір, поки продовжувати їх стане вже неможливо.

У тому випадку, якщо в рядках залишаться нульові осередки, що залишилися незачеркнутимі, яким не відповідатимуть призначення, то знайдіть стовпець з єдиним нульовим значенням і помістіть у відповідний осередок один елемент. Що залишилися в цьому рядку нульові значення вартості закресліть. Повторіть останні дві дії до тих пір, поки це можливо.

Якщо всі елементи розподілені в осередку, яким відповідає нульова вартість, то дане рішення про призначеннях є оптимальним. У тому випадку, якщо воно виявилося неприпустимим, проведіть мінімальна кількість вертикальних і горизонтальних прямих через стовпці і рядки таблиці таким чином, щоб вони пройшли через всі осередки з нульовою вартістю.

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