Рішення завдання про призначення угорським методом. Приклад.
Завдання: Вирішити задачу про призначення на максимум.
Не будемо наводити будь-яку словесне умова, вони можуть бути різні, наприклад «На роботу влаштовуються 6 кандидатів на 6 вакансій і вони отримали відповідні оцінки при співбесіді на кожну вакансію, провести набір кандидатів на шість вакансій так, щоб сумарна оцінка кандидатів була максимальною» або «шість верстатів виконують шість робіт за час, заданий в таблиці, скласти виробничий план ...». Будемо вважати, що перед нами матриця (платіжна, тимчасова і т.д.) і потрібно вирішити задачу про призначення угорським методом на максимум, тобто вибрати по одній клітці в рядку і стовпцю так, щоб з сума була максимальна.
Рішення:
Крок 1:
Зауваження: перший крок потрібно тільки для вирішення завдання на максимум, якщо вам потрібно розв'язати цю проблему на мінімум, то пропустіть його.
Перетворимо матрицю, замінивши кожен елемент матриці різницею максимального елемента цього рядка і самого елемента.
Потрібно забрати нулі в кожному рядку і в кожному стовпці. У третьому, п'ятому та шостому стовпчиках нулів немає, віднімемо з елементів цих стовпців мінімальний елемент відповідного стовпця.
Отримали матрицю, в якій в кожного рядка і кожному стовпці є нуль. Нашою метою є відзначити по одній клітинці в кожному рядку і кожному стовпці так, щоб вони були нульові. У цій матриці тільки перші чотири рядки і стовпці задовольняють цій вимозі. Відзначимо відповідні осередки рамкою.
Відзначимо як «незадоволену рядок», 5-ю, в якій ми такий нуль відзначити не змогли, і другий стовпець, він містить нуль в п'ятому рядку. Але другий стовпець також містить нуль в першому рядку, відзначимо і її як «незадоволену». Перший рядок нулів більше не містить, тобто процес відзначення незадоволених рядків закінчений, і ми отримали ситуацію під назвою «вузьке місце».
У таблиці будемо відзначати незадоволені рядки і стовпці зірочками, а число поруч із зірочкою означатиме порядок відзначення (для кращого розуміння процесу).
Виберемо мінімальний елемент в помічених рядках поза зазначених рядків. Це 3, що стоїть в п'ятому стовпці і п'ятому стовпці.
Віднімемо цей елемент із зазначених рядків і додамо в отриманих шпальтах.
Виконаємо дії, зауважимо, що тепер можна відзначити нуль в п'ятому рядку і п'ятому стовпці.
Бракує ще нуля в 6-му рядку. Відзначимо її як незадоволену, вона має нуль в першому стовпці, відзначимо його як незадоволений, він, в свою чергу, містить нуль у другому рядку, відзначимо її, але вона більш нулів не містить, процес відзначення законний.
Виберемо мінімальний елемент у зазначених рядках поза зазначених стовпців. Це елемент 2 в шостому рядку і шостому стовпці. Віднімемо двійку з другої та шостої стік і додамо її в першому стовпці.
Виконаємо дії. Зауважимо, що тепер можна відзначити ще один нуль.
Отримали матрицю з шістьма нулями, по одному в кожному рядку і стовпці, отже, можна провести призначення (розподіл робіт і т.д.) по матриці:
І вартість (раціональність, час робіт і т.д.) такого призначення складе: