16.5. 16.5. Példamegoldás

1. példa:

Oldjuk meg az alábbi hozzárendelési feladatot „magyar módszerrel”!

0. lépés: Ellenőrzés

Ellenőrizzük, hogy a sorok és oszlopok száma megegyezik-e, mert a „magyar módszer” erre a standard alakra lett kidolgozva.

1. lépés: A redukált időtáblázat meghatározása.

Sor- és oszlopredukcióval előállítjuk az redukált időtáblázatot.

2. lépés: A „házasság” feladat megkonstruálása és megoldása.

A kezdeti hozzárendelést az Észak-Nyugati sarok módszerrel végezzük. Itt nem érdemes külön az és a hozzárendelési (0 vagy 1 értékekből álló) táblázatot is tárolni, a hozzárendelés az táblázatban is megadható a „házasság” feladatnál ismertetett bekarikázással. Tehát ne feledjük, hogy csak cellákon lehetséges hozzárendelést végezni. A kezdeti hozzárendelés után címkézéssel megpróbáljuk javítani a hozzárendelést.

Találtunk utat, az út mentén a hozzárendelést eggyel javíthatjuk. Az útkeresés az és személyektől indult ki és vagy a vagy a munkákhoz szerettünk volna eljutnunk. Sikerült eljutnunk mindkettő munkához. Mivel minket csak egy út érdekel, ezért tetszőlegesen választottuk meg az út végpontját, legyen ez a munka. A címkéken visszafelé haladva a következő út adódott:

Az út mentén az típusú élen új hozzárendelést kapunk, a típusú élen pedig a régi hozzárendelés megszűnik, ezt jelöltük a és a szimbólumokkal. Mint ahogy a „házasság” feladat tárgyalásánál láttuk, az utat nem írjuk le, hanem amikor a címkéken visszafelé haladva felkutatjuk utat, egyszerre elvégezzük az új hozzárendelés berajzolását és a régi hozzárendelés törlését. Ezt mutatja az alábbi táblázat.

A régi hozzárendelés megszüntetését szaggatott körrel, az új hozzárendelést pedig vastagított körrel jelöltük. Ezt a táblázatot csupán azért közöltük, hogy az út mentén való módosítást könnyebben tudjuk nyomon követni. Természetesen az út megtalálása után azonnal a javított táblázatot írjuk fel, amelyen el is kezdjük az újabb útkeresést. Ezt mutatja a következő táblázat.

Nem találtunk utat, így az időtáblázatot fogjuk módosítani a lefedés segítségével. A táblázatba be is rajzoltuk a lefedést.

3. lépés: A redukált időtáblázat módosítása.

Mivel egyetlen táblázatot használunk, így a redukált időtáblázat által meghatározott „házasság” feladatot is azonnal elkezdjük megoldani. Tehát ellentétben a szállítási feladat megoldásával, itt elegendő egyetlen táblázat használata is. Ehhez a redukált időtáblázathoz az induló hozzárendelést vagy Észak-Nyugati sarok módszerrel vagy egyszerűen az előző hozzárendelés bemásolásával végezzük el. A példában az utóbbi szerint jártunk el.

4. lépés: A redukált időtáblázat meghatározása és a „házasság” feladat megoldása.

Találtunk utat, az út mentén a hozzárendelést javítjuk, ezt mutatja a következő táblázat.

Vége az algoritmusnak, mert sikerült az összes személyt a munkákhoz rendelni. A primál és a duál feladat optimális megoldása az alábbi:

A primál feladat optimális megoldása:

Az optimális hozzárendelést a fenti legutolsó táblázat tartalmazza bekarikázásokkal jelölve. Az optimális hozzárendelés tehát:

.

A minimális összidő számítása:

A duál feladat optimális megoldása:

A szállítási feladatnál látottakhoz hasonlóan határozzuk meg a hozzárendelési feladat duál változóinak optimális értékeit. Ha azt akarjuk, hogy a duál változók között ne legyen negatív, akkor adjunk mindegyikhez 3-at, ezt mutatja a jobboldali táblázatrész.

A duál feladat célfüggvényének maximális értéke:

2. Példa:

Az alábbi táblázat mutatja, hogy az egyes személyek (I) az egyes gépeken (G) dolgozva egy óra alatt hány darab terméket tudnak előállítani. Határozza meg a személyek gépekhez való hozzárendelését úgy, hogy a gépeken legfeljebb egy személy dolgozhat és a lehető legtöbb termék legyen előállítva egy óra alatt. Továbbá előírjuk, hogy az , , hozzárendelés nem lehetséges. Azt is megköveteljük, hogy a harmadik személy mindenképpen dolgozzon.

Megoldás:

A példa egy nem standard alakú hozzárendelési feladat, amelyben az egymáshoz hozzárendelendők száma nem azonos, a célfüggvény maximumát kell keresni és egyedi letiltások is vannak. Először a minimum feladatra történő visszavezetést végezzük el, azáltal, hogy a táblázat legnagyobb (esetleg annál nagyobb) eleméből kivonjuk a táblázat összes elemét. Másodszor egy fiktív gépet iktatunk be zérus adatokkal. Harmadszor pedig az egyedi tiltásokat egy M szimbólum használatával kezelhetjük. A fentieket elvégezve, az alábbi sémával adott hozzárendelési feladatot kell megoldani „magyar módszerrel”.

Mint ismeretes a „magyar módszer” első lépéseként sorredukciót majd oszlopredukciót szoktunk alkalmazni. A feladatban a sorredukció csak a 3. sor adatait változtatja meg, ezáltal a 3. sor elemei a többihez képest kisebbek lesznek és az oszlopredukció során általában ebben a sorban keletkeznek a zérusok. A zérusok jobb eloszlása miatt érdemes először az oszlopredukciót elvégezni. Az oszlopredukció elvégzése után következhet a sorredukció, amely jelen példában elmarad.

Ezután a kezdeti hozzárendelést készítjük el az Észak-Nyugati sarok módszerrel, majd a „magyar módszer” szokásos lépései (címkézés, lefedés, módosítás) következnek:

A lefedés segítségével az új táblázat elkészítése és az előző hozzárendelés bemásolása következik. A hozzárendelés triviális módon javítható az hozzárendeléssel.

A címkézés során találtunk utat, amely mentén tovább javítható a hozzárendelés. Az alábbi táblázat az új hozzárendelést tartalmazza.

Vége az algoritmusnak, mert az összes személyt hozzárendeltük a „gépek”-hez.

Az eredeti feladat optimális hozzárendelése is a fenti táblázatból olvasható ki. A megoldás szerint az személy lett a fiktív géphez rendelve, ami azt jelenti, hogy az optimális megoldásban az személyt nem érdemes foglalkoztatni, a többi személy pedig az alábbi módon lett a gépekhez rendelve:

Az egy óra alatt előállított termékek maximális száma: .

Megjegyezzük, hogy amennyiben a duál feladaton keresztül esetleges ellenőrzést szeretnénk végezni, úgy azt a standard alakú feladaton kell elvégeznünk.

3. Példa:

Adott az alábbi mátrix. Válasszunk ki a mátrix elemei közül ötöt úgy, hogy minden sorban és oszlopban legfeljebb egyet választhatunk és a kiválasztott elemek összege minél kisebb legyen! Továbbá vegyük figyelembe a kiválasztásnál, hogy a harmadik oszlopban mindenképpen válasszunk számot, az elemet pedig ne válasszuk.

Megoldás:

A példa egy nem standard alakú hozzárendelési feladat, amelyben az egymáshoz hozzárendelendők száma nem azonos és letiltások is vannak. Egy fiktív sort kell beiktatnunk zérus adatokkal. Az egyedi tiltásokat egy M szimbólum használatával kezelhetjük. A fentieket elvégezve, az alábbi sémával adott hozzárendelési feladatot kell megoldani „magyar módszerrel”:

Első lépésként elvégezzük a sorredukciót, majd az oszlopredukciót és utána Észak-Nyugati sarok módszerrel készítünk egy induló hozzárendelést. A következő lépésben pedig címkézéssel megpróbáljuk javítani a hozzárendelést. Ezt mutatja a következő táblázat.

Nem tudtunk javítani a hozzárendelésen, a címkézés alapján elvégezzük a lefedést és meghatározzuk értékét (). Elvégezzük a tábla adatainak módosítását és az új táblázaton újra címkézünk.

Most sem sikerült javítani a hozzárendelésen, a címkézés alapján elvégezzük a lefedést és meghatározzuk értékét (). Elvégezzük a tábla adatainak módosítását és az új táblázaton újra címkézünk. Ezt mutatja a következő táblázat:

A fenti táblán két címkézést is végeztünk a helytakarékosság miatt. Az első címkézésnél találtunk utat és javítottunk a hozzárendelésen. A szaggatott kör a régi hozzárendelés megszüntetését, a vastag kör pedig az új hozzárendelést mutatja. A második címkézés már a normál és a vastag körrel jelölt hozzárendelés javítását szolgálja. Nem sikerült javítani, így újabb lefedés, majd módosítás következik. Ezt mutatja a következő táblázat. El is kezdjük a címkézést és sikerült utat találni, a hozzárendelés javítható, amit végre is hajtottunk a táblázatban.

A fenti táblázatból kiolvasható a feladat optimális megoldása, amely szerint az és az mátrixelemeket kell kiválasztani. A kiválasztott öt elem összege = 36.

Megjegyezzük, hogy az egy táblázaton való többszöri címkézés helytakarékosság miatt hasznos lehet, de az eligazodás viszont nehézkesebb. Ezért ezt a lehetőséget a gyakorlottabb példamegoldóknak javasoljuk.