МАЂАРСКА МЕТОДА: ОД ЧЕГА СЕ САСТОЈИ, НА ПРИМЕР - ДУДАС - 2025

Мађарски метод је алгоритам који се користи у проблемима расподеле када желите да минимизира трошкове. Односно, користи се за проналажење минималних трошкова додељивањем више људи различитим активностима на основу најмањег трошка. Свака активност мора бити додељена другој особи.

Проблем са расподјелом је посебна врста проблема линеарног програмирања, гдје је циљ минимизирати трошкове или вријеме завршетка одређеног броја радних мјеста од стране више људи.

Извор: пикабаи.цом

Једна од важних карактеристика проблема са расподјелом је да је само један посао (или радник) додијељен машини (или пројекту).

Ову методу је развио мађарски математичар Д. Кониг. Из тог разлога је позната као мађарска метода за проблеме са задатком. Познат је и као алгоритам расподјеле Кухн-Мункрес-а.

Било који проблем са алокацијом може се лако решити применом ове методе која се састоји од две фазе:

- Са првом фазом врши се редукција и редукција ступаца.

- У другој фази се решење оптимизује на итеративној основи.

Шта је мађарска метода?

Мађарски метод састоји се од четири корака. Прва два корака се изводе само једном, док се кораци 3 и 4 понављају све док се не нађе оптимална алокација.

Квадратна матрица реда н према н сматра се улазним подацима који морају садржавати само негативне елементе.

За одређени проблем, ако број редова у матрици није једнак броју ступаца, мора се додати лучни редак или лутка ступац, зависно од случаја. Трошкови алокације за те лажне ћелије увек се расподељују као нула.

1. корак: одузмите минимум сваког реда

За сваки ред у низу бира се елемент с најнижом вриједношћу и одузима се од сваког елемента у том ретку.

2. корак: одузмите минимум од сваке колоне

Слично томе, ставка са најнижом вриједношћу одабрана је за сваки ступац и одузима се од сваке ставке у том ступцу.

Корак 3: прекријте све нуле са минималним бројем линија

Све нуле у матрици које потичу из корака 2 морају се прекрити кориштењем минималног броја хоризонталних и вертикалних линија, било редима или ступовима.

Ако је за покривање свих нула потребно укупно н линија, где је н једнак величини н пута н матрице, добиће се оптимална алокација између нула и због тога се алгоритам зауставља.

У супротном, ако је за покривање свих нула у низу потребно мање од н редака, пређите на корак 4.

4. корак: направите додатне нуле

Одабран је најмањи елемент матрице (зван к) који није покривен ниједном од линија направљених у кораку 3.

Вредност к се одузима од свих елемената који нису обухваћени линијама. Након тога, вриједност ка додаје се свим елементима који су прекривени сјециштем двију линија.

Ставке које су покривене једним редом остају као што су. Након извођења овог корака враћате се на корак 3.

Оптимална алокација

Након заустављања алгоритма у кораку 3, бира се скуп нула тако да сваки ред и сваки ступац имају само једну нулу.

Ако у овом процесу одабира не постоји ниједна нула у реду или ступцу, тада ће се одабрати једна од тих нула. Преостале нуле у том ступцу или реду уклањају се, понављајући исто као и за остале задатке.

Ако нема додељене једне нуле, постоји више решења. Међутим, трошкови ће остати исти за различите групе задатака.

Сви додани редови или ступци који се додају уклањају се. Нулте изабране у овој завршној матрици тако одговарају идеалном задатку који се тражи у оригиналној матрици.

Пример

Размотримо компанију у којој постоје четири активности (А1, А2, А3, А4) које морају обављати четири радника (Т1, Т2, Т3, Т4). По једном раднику се мора доделити једна активност.

Следећа матрица приказује трошкове придруживања одређеног радника одређеној активности. Циљ је да се минимизирају укупни трошкови задатка који се састоји од ове четири активности.

1. корак: одузмите минимум сваког реда

Започињете одузимањем елемента са минималном вриједношћу у сваком ретку од осталих елемената у том ретку. На пример, најмањи елемент у првом реду је 69. Стога се од сваког елемента у првом реду одузима 69. Резултирајућа матрица је:

2. корак: одузмите минимум од сваке колоне

На исти начин се елемент са најмањом вриједношћу сваког колона одузима од осталих елемената у том ступцу, добивајући сљедећу матрицу:

Корак 3: прекријте све нуле са минималним бројем линија

Сада ћемо одредити минимални број линија (хоризонталних или вертикалних) које су потребне да покрију све нуле у матрици. Све нуле могу се покрити помоћу 3 линије:

Пошто је потребан број линија три и мањи је од величине матрице (н = 4), настављамо са кораком 4.

4. корак: направите додатне нуле

Одабран је најмањи елемент који није обухваћен линијама, чија је вриједност 6. Ова се вриједност одузима од свих елемената који нису обухваћени и та иста вриједност додаје се свим елементима обухваћеним сјециштем двију линија. То резултира следећом матрицом:

Као што је назначено у мађарској методи, трећи корак мора бити изведен поново.

3. корак (поновите)

Поново се утврђује минималан број линија потребних за покривање свих нула у матрици. Овог пута су потребне четири линије:

Како је број потребних линија 4, једнак величини матрице (н = 4), имамо оптималну алокацију између нула у матрици. Стога се алгоритам зауставља.

Оптимална алокација

Као што метода указује, избор следећих нула одговара оптималном задатку:

Овај избор нула одговара следећем оптималном распореду у оригиналној матрици трошкова:

Дакле, радник 1 мора обављати активност 3, радник 2, активност 2, радник 3, активност 1, а радник 4 мора обављати активност 4. Укупни трошкови овог оптималног задатка су 69 + 37 + 11 + 23 = 140.

Референце

1. Мађарски алгоритам (2019). Мађарски алгоритам. Преузето са: Хунгарианалгоритхм.цом.
2. Студија (2019). Коришћење мађарског алгоритма за решавање задатака. Преузето са: студи.цом.
3. Висдом Јобс (2018). Мађарски метод решавања задатка - квантитативне технике управљања. Преузето са: висдомјобс.цом.
4. Геекс за Геекс (2019). Мађарски алгоритам за проблем задатка. Преузето са: геексфоргеекс.орг.
5. Карлеигх Мооре, Натхан Ландман (2019). Мађарски алгоритам максималног подударања. Сјајно. Преузето са: бриљант.орг.