12.5. 12.5. Példamegoldás

1. példa.

Oldjuk meg az alábbi „házasság” feladatot!

0. lépés: Kezdeti hozzárendelés meghatározása É-Ny-i sarok módszerrel.

1. lépés: Útkeresés címkézéssel

Találtunk utat, az út a címkéken visszafelé haladva a következő:

Az út élei alatti sorokban a szabad kapacitást és az élek megszokott jelöléseit is megadtunk.

Az út mentén értéke nyilvánvalóan csak 1 lehet. A szokásos módon a -el jelölt cellákon csökkentjük, a -el jelölteken pedig növeljük a folyamot. A csökkentés azt jelenti, hogy ott a létező hozzárendelést megszüntetjük, a növelés pedig új hozzárendelést jelent. A továbbiakban nem írjuk le külön az utat és nem is jelöljük be a táblázatba a megszokott és szimbólumokat, hanem az út (címkék segítségével való) meghatározása során azonnal elvégezzük a régi hozzárendelés megszüntetését ill. az új hozzárendelés felvételét. Itt is igaz, hogy az út egy törtvonal és végpontjain felváltva történik hozzárendelés felvétel és megszüntetés, felvétellel kezdve és befejezve is. A hozzárendelés javítását a következő táblázat mutatja:

Vége az algoritmusnak, mert az összes személyt hozzárendeltük a munkákhoz. A hozzárendelés a táblázatból kiolvasható.

2. példa:

Oldjuk meg az alábbi „házasság” feladatot!

0. lépés: Kezdeti hozzárendelés meghatározása.

Most nem az Észak-Nyugati sarok módszerrel végezzük az induló hozzárendelést, hanem a kevés *-ot tartalmazó sorokban és oszlopokban kezdjük az induló hozzárendelés meghatározását. Először a 3. személy hozzárendelését végeztük el, mivel az csak egy munkához rendelhető, másodszor az 5. személy hozzárendelése következik, mert már az előző hozzárendelést figyelembevéve szintén csak egy munkához rendelhető, utána a 6. személy következett, mert ő a többi személyhez képest kevesebb munkához rendelhető, ezekután a 2., majd a 4. személy következett.

1. lépés: Útkeresés címkézéssel

Vége az algoritmusnak, mert nem találtunk utat, így nem tudjuk tovább javítani a hozzárendelést. Arra az eldöntendő kérdésre, hogy az összes személy hozzárendelhető-e a munkákhoz, a válasz nem, mivel 1 személyt semmiképpen sem lehet hozzárendelni. Arra a kérdésre, hogy maximálisan hány személy rendelhető a munkákhoz szintén megkaptuk a választ, 1 híján az összeset, tehát 5 személyt. Az algoritmus azt is megmutatja, hogy a lehető legtöbb személy hozzárendelését milyen módon biztosíthatjuk. Ez a fenti táblából kiolvasható. Elképzelhető természetesen más hozzárendelés is, azonban 5-nél több személy semmiképpen nem rendelhető a munkákhoz. Mivel az összes személyt nem lehet hozzárendelni, így a „házasság” feladatra vonatkozó KŐNIG tétel értelmében meghatározhatók a személyek és munkák P és R halmazai. A P és R halmazba a megcímkézett személyek ill. munkák tartoznak, azaz

A P-beli személyek és az R-beli munkák száma pedig

Tehát , ahogy ezt a KŐNIG tétel állította. Valóban nem lehet az összes személyt hozzárendelni a munkákhoz, hiszen már a P-beli 3 személy mindegyikét sem tudjuk hozzárendelni, mert csupán 2 olyan munka van, amelyekhez a P-beliek hozzárendelhetők.

Végezetül a lefedést is elvégezhetjük, mégpedig a nem P-beli (címkézetlen) sorokat és az R-beli (címkézett) oszlopokat fedjük le. Látható, hogy a fedetlen helyeken nincs *, így minden * le lett fedve. A kétszer fedett helyeken nincs hozzárendelés, vagyis hozzárendelés csak egyszer fedett helyen lehet.