Унгарски метод - какво е това, определение и понятие

Унгарският метод е алгоритъм, който позволява да се минимизират разходите при оптимизационен проблем, базиран на линейно програмиране.

Целта на унгарския метод е да се намерят минималните разходи за набор от задачи, които трябва да се изпълняват от най-подходящите хора.

Той използва линейно програмиране (PL) за извършване на поредица от стъпки, които могат да бъдат автоматизирани. По този начин инструменти като статистическия софтуер R (наред с други) имат няколко много полезни пакета за тези оптимизационни проблеми.

Произход на унгарския метод

Негов създател е унгарският математик (откъдето идва и името му) Харолд В. Кун през 1955 г. Друг математик, Джеймс Мункрес, го ревизира през 1957 г. С тази еволюция той е получил други имена като алгоритъма за разпределение на Мункрес или Кун-Мюнкрес.

От друга страна, този метод има прецедент при двама автори, Dénes König и Jenő Egerváry, както евреи, така и унгарци. Първият разработи теорията на графовете, на която се основава този алгоритъм. Втората обобщава теоремата на Кьониг и позволява на Кун да разработи метода.

Стъпки на унгарския метод

Следващите стъпки позволяват да се извърши унгарският метод по прост начин с помощта на електронна таблица. В допълнение, тази схема, която показваме, ще ни позволи да видим по глобален начин процеса, който ще разработим подробно в последния пример.

• Като предварителни стъпки трябва да назначите хора (редове) към поредица от проекти (колони). Освен това е необходимо да се изчислят различните разходи за всеки проект в зависимост от това кой го изпълнява и да се изгради матрица (C) с тази информация.
• В матрицата (C) търсим минималната стойност на всеки ред. Изваждаме това от всички елементи в реда и извършваме същата операция с колоните. Ще се появи нова матрица (C`) с резултатите от предишните операции.
• След това създаваме «графика на равенствата», която ни позволява да избираме задачите и проектите с най-ниска цена. Оптималното би било онези елементи, чийто резултат е нула. Ако е вярно, че няма елемент с нулева стойност, присвоена на повече от един ред, алгоритъмът завършва.
• В противен случай трябва да се направи ново задание. Направена е нова матрица, към която са приложени поредица от модификации, както ще видим в примера. Пресъздаваме графиката и продължаваме, докато имаме матрица, която има поне една нула във всеки ред и в неповтарящи се позиции.
• С тази информация вече имаме назначени хора и проекти (нулите), които оптимизират проблема. Ако дадена задача вече е зададена в предишен ред, тя се отхвърля в следващия. За да изчислим минималните разходи, добавяме разходите на първоначалната матрица, които се появяват в позицията на тези нули.

Пример за унгарски метод

Нека разгледаме един прост пример за унгарския метод на. Нека си представим, че имаме трима работници и те трябва да бъдат разпределени по три проекта. Създаваме първоначалната матрица (C) и стойностите на разходите във всяка клетка. За това трябва да използвате информацията, налична във фирмата. След като имаме всичко това, ние започваме процеса. Електронната таблица може да помогне.

Изчисляваме минимумите на всеки ред и ги изваждаме от елементите на този ред и правим същото с колоните (стъпки 1 и 2). В получената матрица (C`) чертаем линии по такъв начин, че те да покриват всички нули и на свой ред да се пресичат помежду си (стъпка 3). Виждаме, че има два реда, но най-голямата стойност на броя редове или колони е три. Трябва да продължим.

Сега избираме най-малкото от непокритите числа, в този пример е две (тъмно синьо). Изваждаме го от предишните и го добавяме към тези, които се намират там, където линиите се пресичат. В нашия случай това са още две (E3, T1). Остава ни нова матрица (стъпка 4). Пречертаваме линиите и броим. Има три реда, еднакви с броя на редовете или колоните. Алгоритъмът е завършен.

Започваме с реда или колоната с най-малко нули (E1, T1). Ако дадена задача вече е назначена, тя не може да бъде преназначена, например с E2 не можете да използвате първата нула на T1, тъй като тази задача е била назначена на E1. Общите разходи по унгарския метод ще бъдат сумата от разходите на оригиналната матрица (стъпка 1), разположена в същата позиция като избраните нули (стъпка 5).