Madžarska metoda, kaj je sestavljen, primer

On Madžarska metoda To je algoritem, ki se uporablja pri težavah z dodelitvijo, kadar želite zmanjšati stroške. To pomeni, da se uporablja za iskanje minimalnih stroškov z dodeljevanjem več ljudi različnim dejavnostim na podlagi najnižjih stroškov. Vsaka dejavnost mora biti dodeljena drugi osebi.

Problem dodelitve je posebna vrsta problema linearnega programiranja, kjer je cilj zmanjšati stroške ali čas dokončanja količine dela več ljudi.

Vir: Pixabay.com

Ena od pomembnih značilnosti problema dodelitve je, da je stroju dodeljena samo eno delo (ali delavec).

To metodo je razvil madžarski matematik D. Konig. Zaradi tega je znana kot madžarska metoda za težave z dodelitvijo. Znan je tudi kot algoritem dodelitve Kuhn-Munkres.

Vsako težavo z dodelitvijo je mogoče enostavno rešiti z uporabo te metode, ki je sestavljena iz dveh faz:

- S prvo fazo se znižajo vrstice in zmanjšanja stolpcev.

- V drugi fazi je optimizirana rešitev na iterativni bazi.

[TOC]

Kaj je madžarska metoda?

Madžarska metoda je sestavljena iz štirih korakov. Prva dva koraka se izvedeta samo enkrat, koraka 3 in 4 pa se ponavljata, dokler ne najdeta optimalne naloge.

Šteje se za vnosno dejstvo na kvadratno matrico reda n z n, ki mora vsebovati samo ne -negativne elemente.

Za dano težavo, če število vrstic v matriki ni enako številu stolpcev. Stroški dodelitve za te izmišljene celice so vedno dodeljeni kot nič.

1. korak: Odštejte minimalne podatke vsake vrstice

Za vsako vrstico matrice je element izbran z najnižjo vrednostjo in odštevanjem vsakega elementa v tej vrstici.

Vam lahko služi: kaj je trenutno sredstvo? (S primeri)

2. korak: Odštejte minimalne podatke vsakega stolpca

Podobno je za vsak stolpec izbran element z najnižjo vrednostjo in ga odštejemo iz vsakega elementa v tem stolpcu.

3. korak: pokrijte vse ničle z minimalnim številom vrstic

Vse ničle morajo biti prekrite v matrico, ki je posledica koraka 2 z uporabo minimalnega števila vodoravnih in navpičnih črt, bodisi po vrsticah ali stolpcih.

Če so za pokritje vseh ničla potrebne skupne črte, saj je n enak velikosti n na n matrice, bo med ničli optimalna dodelitev in zato se algoritem ustavi.

V nasprotnem primeru, če je za pokritje vseh ničlic v matriki potrebno manj linij, se nadaljuje s 4. korakom.

4. korak: Ustvari dodatne ničle

Izbran je najmanj elementa matrice (imenovan k), ki ga ne zajema ena od vrstic, narejenih v koraku 3.

Vrednost k vseh elementov, ki jih ne zajemajo črte, se odšteje. Kasneje se vrednost K doda vsem elementom, ki jih pokriva presečišče dveh vrstic.

Elementi, ki jih pokriva ena črta. Po izvedbi tega koraka se vrnete v 3. korak.

Optimalna naloga

Ko je algoritem ustavljen v 3. koraku, je izbran niz ničla, tako da ima vsaka vrstica in vsak stolpec samo eno izbrano ničlo.

Če v tem izbirnem postopku ni nobene ničle v vrstici ali stolpcu, bo izbrana ena od teh ničle. Preostale ničle se izločijo v tem stolpcu ali vrstici, kar ponavlja isto tudi za druge naloge.

Lahko vam služi: makrolokalizacija

Če ni niti ene dodelitve ničle, pomeni, da obstaja več rešitev. Vendar bodo stroški ostali enaki za različne nabore dodelitve.

Odpravljena je vsaka izmišljena vrstica ali stolpec, ki je bila dodana. Zero, izbrane v tej končni matriki, ustrezajo idealni dodelitvi, ki je potrebna v originalni matriki.

Primer

Razmislite o podjetju, kjer so štiri dejavnosti (A1, A2, A3, A4), ki ga morajo izvesti štirje delavci (T1, T2, T3, T4). Določi mora dejavnost na delavca.

Naslednja matrica prikazuje stroške dodeljevanja določenega delavca določeni dejavnosti. Cilj, ki si ga prizadevamo, je zmanjšati skupne stroške naloge, sestavljene iz teh štirih dejavnosti.

1. korak: Odštejte minimalne podatke vsake vrstice

Element se začne z minimalno vrednostjo vsake vrstice druge elemente te vrstice. Na primer, najmanjši element v prvi vrsti je 69. Zato se v prvi vrsti odšteje 69 vsakega elementa. Nastala matrika je:

2. korak: Odštejte minimalne podatke vsakega stolpca

Na enak način se element odšteje z minimalno vrednostjo vsakega stolpca drugih elementov tega stolpca in pridobi naslednjo matrico:

3. korak: pokrijte vse ničle z minimalnim številom vrstic

Zdaj bo določeno minimalno število črt (vodoravnih ali navpičnih), ki so potrebne za prekrivanje vseh ničla v matrici. Vse ničle je mogoče pokriti s 3 vrsticami:

Ker je število potrebnih vrstic tri in je manjše od velikosti matrice (n = 4), se nadaljuje s korakom 4.

Lahko vam služi: Upravljanje projektov: kaj je, faze, cilji, primeri

4. korak: Ustvari dodatne ničle

Izbran je najnižji element, ki ga ne zajemajo črte, katerega vrednost je 6. Ta vrednost vseh neobveščenih elementov se odšteje in ta ista vrednost je dodana vsem elementom, ki jih zajema preseči dve vrstici. To ima za posledico naslednjo matrico:

Kot je navedeno v madžarski metodi, je treba korak številka tri ponovno izvesti.

3. korak (ponovitev)

Ponovno je določeno minimalno število vrstic, potrebnih za prekrivanje vseh ničla v matriki. Tokrat so potrebne štiri vrstice:

Ker je število potrebnih vrstic 4, enako velikosti matrice (n = 4), obstaja optimalna dodelitev med ničli v matrici. Zato se algoritem ustavi.

Optimalna naloga

Kot je navedeno po metodi, izbira, narejena iz naslednjih ničle, ustreza optimalni dodelitvi:

Ta izbor ničle ustreza naslednji optimalni dodelitvi v prvotni matriki stroškov:

Zato mora delavec 1 izvajati dejavnost 3, delavec 2, dejavnost 2, delavec 3, dejavnost 1 in delavec 4 morajo opraviti dejavnost 4. Skupni stroški te optimalne dodelitve so 69+37+11+23 = 140.

Reference

1. Madžarski algoritem (2019). Madžarski algoritem. Vzet iz: madgaranalgoritem.com.
2. Študija (2019). Uporaba madžarskega algoritma za reševanje težav z dodelitvijo. Vzeto iz: Študij.com.
3. Wisdom Jobs (2018). Madžarska metoda za reševanje problema dodelitve - kvantitativne tehnike za upravljanje. Vzet iz: WisdomJobs.com.
4. Geeks za geeks (2019). Madžarski algoritem za problem dodelitve. Vzet od: geeksforgeeks.org.
5. Karleight Moore, Nathan Landman (2019). Madžarski algoritem za največjo ujemanje. Briljantno. Vzeto od: briljantno.org.