Magyar módszer

Mire használjuk a Magyar módszert?

• Hozzárendelési problémák megoldására

• Vállalatelhelyezési problémák megoldására

• Én semmire

• Maximális párosítások megtalálására egy súlyozott gráfban

Mi a jelentése a hozzárendelési feladat modelljében az x váltzóknak?

• mennyi munkát végez valaki

• mennyi az értéke az adott munkának

• hozzárendeljük-e valakihez az adott feladatot

• mesterséges változó

Milyen feltételeknek kell teljesülnie a feladat modelljében?

• Minden oszlopban csupa 1-es kell legyen

• Minden sorban csupa 1-es kell legyen

• A főátlőban a változók összegének 1-nek kell lenniük

• Az sor- és oszlopösszegeknek mindenhol 1-nek kell lennie

Mikor kiegyensúlyozott egy költségmátrix?

• Ha ugyanannyi sor van benne mint oszlop

• Ha van benne csupa 0 oszlop

• Ha van benne csupa 0 sor

• Ha ugyanannyi oszlop van benne mint sor

Hogyan állítjuk elő a Magyar módszer során az első redukált költségmátrixot?

• Kivonjuk minden oszlopból az oszlopminimumot

• Kivonjuk minden sorból a sorminimumot

• Kivonjuk minden oszlopból a sorminimumot és minden sorból az oszlopminimumot

• Kivonjuk minden sorból a sorminimumot és minden oszlopból az oszlopminimumot

Hogy néz ki az alábbi feladat költségmátrixa CSAK A SORMINIMUMOK KIVONÁSA UTÁN?

• 
• 
• 

Melyik a helyes redukált költségmátrix, az oszlopminimumok kivonása után?

• 
• 

Kiegyensúlyozott-e az alábbi feladat?

• Igen

• Nem

Mikor létezik független 0 rendszer?

• Ha ugyanannyi 0 van, mint ahány sor

• Ha egy m*m-es redukált költségmátrixban m vonal szükséges az összes 0 lefedéséhez

• Ha egy m*m-es redukált költségmátrixban a nullák száma > 2*m

Találtunk-e független 0 rendszert?

• Igen, mert ugyanannyi a vonal mint a sorok/oszlopok száma

• Nem

• Igen, mert lefedtük az összes 0-t