Як вирішити задачу про призначення


 

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



Інструкція

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

Корисні поради

Суть угорського методу полягає в оптимізації та приведенні матриці до такого виду, коли всі підлягають розподілу елементи повинні потрапити в осередки таблиці з нульовою вартістю. При цьому розподіл елементів в клітини з нульовою вартістю дозволить отримати мінімальне значення цільової функції.