- Какъв е унгарският метод?
- Стъпка 1: извадете минимумите на всеки ред
- Стъпка 2: извадете минимумите от всяка колона
- Стъпка 3: покрийте всички нули с минимален брой линии
- Стъпка 4: създайте допълнителни нули
- Оптимално разпределение
- пример
- Стъпка 1: извадете минимумите на всеки ред
- Стъпка 2: извадете минимумите от всяка колона
- Стъпка 3: покрийте всички нули с минимален брой линии
- Стъпка 4: създайте допълнителни нули
- Стъпка 3 (повторение)
- Оптимално разпределение
- Препратки
На унгарски метод е алгоритъм, който се използва при проблеми разпределение, когато искате да намалите разходите. Тоест, той се използва за намиране на минималните разходи чрез присвояване на множество хора на различни дейности на базата на най-малко разходи. Всяка дейност трябва да бъде възложена на различен човек.
Проблемът с разпределението е специален тип проблем с линейното програмиране, при който целта е да се минимизират разходите или времето за завършване на редица работни места от множество хора.
Източник: pixabay.com
Една от важните характеристики на проблема с разпределението е, че само една работа (или работник) е назначена на машина (или проект).
Този метод е разработен от унгарския математик Д. Кониг. Поради тази причина той е известен като унгарски метод за задачи за задачи. Известен е и като алгоритъм за разпределение на Кун-Мункрес.
Всеки проблем с разпределението може да бъде лесно разрешен чрез прилагане на този метод, който се състои от две фази:
- С първата фаза се извършват редукции и редукции на колони.
- Във втората фаза решението се оптимизира на итеративна основа.
Какъв е унгарският метод?
Унгарският метод се състои от четири стъпки. Първите две стъпки се изпълняват само веднъж, докато стъпки 3 и 4 се повтарят, докато не се намери оптимално разпределение.
Квадратна матрица от ред n по n се счита за входни данни, които трябва да съдържат само отрицателни елементи.
За даден проблем, ако броят на редовете в матрицата не е равен на броя на колоните, трябва да се добави манекен ред или манекен колона, в зависимост от случая. Разходите за разпределение на тези фиктивни клетки винаги се разпределят като нула.
Стъпка 1: извадете минимумите на всеки ред
За всеки ред в масива се избира елементът с най-ниската стойност и се изважда от всеки елемент в този ред.
Стъпка 2: извадете минимумите от всяка колона
По същия начин елементът с най-ниска стойност се избира за всяка колона и се изважда от всеки елемент в тази колона.
Стъпка 3: покрийте всички нули с минимален брой линии
Всички нули в матрицата, получени от стъпка 2, трябва да бъдат покрити, като се използва минимален брой хоризонтални и вертикални линии, или чрез редове или колони.
Ако са нужни общо n линии, за да покрият всички нули, където n е равно на размера n пъти n на матрицата, ще има оптимално разпределение между нулите и следователно алгоритъмът спира.
В противен случай, ако са необходими по-малко от n реда, за да покрият всички нули в масива, преминете към стъпка 4.
Стъпка 4: създайте допълнителни нули
Избран е най-малкият елемент от матрицата (наречен k), който не е покрит от една от линиите, направени в стъпка 3.
Стойността на k се изважда от всички елементи, които не са обхванати от линии. Впоследствие стойността на ka се добавя към всички елементи, които са обхванати от пресичането на две линии.
Елементите, които са обхванати от един ред, се оставят така, както е. След като извършите тази стъпка, се връщате към стъпка 3.
Оптимално разпределение
След спиране на алгоритъма в стъпка 3 се избира набор от нули, така че всеки ред и всяка колона да са избрани само една нула.
Ако в този процес на подбор няма нито една нула в ред или колона, тогава ще бъде избрана една от тези нули. Останалите нули в тази колона или ред се премахват, повтаряйки същото и за останалите задачи.
Ако няма еднозначно присвояване, има множество решения. Разходите обаче ще останат същите за различните групи задания.
Всички добавени редове или колони, които са добавени, се премахват. По този начин нулите, избрани в тази крайна матрица, съответстват на идеалното задание, изисквано в оригиналната матрица.
пример
Нека разгледаме компания, в която има четири дейности (A1, A2, A3, A4), които трябва да се извършват от четирима работници (T1, T2, T3, T4). На един работник трябва да се назначи една дейност.
Следващата матрица показва разходите за приписване на определен работник към определена дейност. Целта е да се сведе до минимум общата стойност на задачата, съставена от тези четири дейности.
Стъпка 1: извадете минимумите на всеки ред
Започвате с изваждане на елемента с минималната стойност на всеки ред от останалите елементи в този ред. Например, най-малкият елемент в първия ред е 69. Следователно, 69 се изважда от всеки елемент от първия ред. Получената матрица е:
Стъпка 2: извадете минимумите от всяка колона
По същия начин елементът с минималната стойност на всяка колона се изважда от останалите елементи на тази колона, получавайки следната матрица:
Стъпка 3: покрийте всички нули с минимален брой линии
Сега ще определим минималния брой линии (хоризонтални или вертикални), необходими за покриване на всички нули в матрицата. Всички нули могат да бъдат покрити с помощта на 3 реда:
Тъй като броят на необходимите линии е три и е по-малък от размера на матрицата (n = 4), продължаваме с стъпка 4.
Стъпка 4: създайте допълнителни нули
Избира се най-малкият елемент, който не е обхванат от линиите, чиято стойност е 6. Тази стойност се изважда от всички елементи, които не са обхванати, и същата стойност се добавя към всички елементи, обхванати от пресичането на две линии. Това води до следната матрица:
Както е посочено в унгарския метод, стъпка трета трябва да се извърши отново.
Стъпка 3 (повторение)
Отново се определя минималният брой линии, необходими за покриване на всички нули в матрицата. Този път са необходими четири реда:
Тъй като броят на необходимите линии е 4, равен на размера на матрицата (n = 4), имаме оптимално разпределение между нулите в матрицата. Следователно алгоритъмът спира.
Оптимално разпределение
Както показва методът, изборът, направен от следните нули, отговаря на оптимално задание:
Този избор на нули съответства на следното оптимално разпределение в оригиналната матрица на разходите:
Следователно работник 1 трябва да изпълнява дейност 3, работник 2, дейност 2, работник 3, дейност 1, а работник 4 трябва да извършва дейност 4. Общата стойност на това оптимално задание е 69 + 37 + 11 + 23 = 140.
Препратки
- Унгарски алгоритъм (2019). Унгарският алгоритъм. Взета от: Hungarianalgorithm.com.
- Проучване (2019). Използване на унгарския алгоритъм за решаване на задачи. Взета от: study.com.
- Wisdom Jobs (2018). Унгарски метод за решаване на задача за назначаване - количествени техники за управление. Взета от: wisdomjobs.com.
- Geeks за Geeks (2019). Унгарски алгоритъм за задача на задание. Взета от: geeksforgeeks.org.
- Karleigh Moore, Nathan Landman (2019). Унгарски максимален съвпадащ алгоритъм. Брилянтно. Взета от: bril.org.