14.3. 14.3. Algoritmus a szállítási feladat megoldására. A „magyar módszer”

Az algoritmus a fenti tétel konstruktív bizonyításából kiolvasható. Két dolgot kell csupán megbeszélnünk, egyik az algoritmus indításával, másik az általános Kőnig feladattal kapcsolatos. Az algoritmus indításához lehetséges duál változókat kell meghatározni. A kezdeti lehetséges duál változókat sokféleképpen meghatározhatjuk. Arra kell csupán ügyelnünk, hogy az és duál változók olyanok legyenek, hogy a belőlük számított redukált költség legyen. Jó lenne olyan redukált költségekből kiindulni, amelyek egyrészt egyszerűen számolhatók, másrészt sok zérus van közöttük. Ez utóbbi azért fontos, mert akkor már az induló Kőnig feladatban sok szabad hely lesz. Alakítsuk át -t az alábbi formára:

Ha a értékeket olyanra választjuk, hogy azokat a -ből levonva nemnegatív eredményt kapunk és a értékeket pedig olyanra választjuk, hogy azokat a -ből levonva szintén nemnegatív eredményt kapunk, akkor az redukált költség nemnegatív marad. Elvileg nagyon sok ilyen , választás lehetséges. A legjobb ilyen választás az, amikor a redukált költségeket úgy kapjuk meg, hogy a költségmátrix minden sorából a sor legkisebb elemét vonjuk ki és az eredménymátrix minden oszlopából pedig az oszlop legkisebb elemét vonjuk ki. A redukált költségek ilyen módon való meghatározásánál a sorokon végrehajtott műveletet sorredukciónak, az oszlopokon végrehajtott műveletet pedig oszlopredukciónak nevezzük. Ezzel a sor- és oszlopredukcióval olyan megengedett induló redukált költségmátrixot kapunk, amely azzal a jó tulajdonsággal bír, hogy minden sorában és oszlopában van legalább egy zérus.

Természetesen elfogadható más induló redukált költségmátrix is. Például végezhetünk csak sorredukciót vagy csak oszlopredukciót vagy először oszlopredukciót, majd utána sorredukciót vagy az is elképzelhető, hogy nem redukáljuk a költségmátrixot. Javasoljuk az olvasónak, hogy a „magyar módszer” begyakorlásánál egy feladatot többféle indulással is végezzen el.

Az általános Kőnig feladatban ott szabad szállítani, ahol a redukált költség zérus. Az általános Kőnig feladat megoldási algoritmusa az előzőekből már ismert, így az nem jelent különösebb problémát. Induló szállítást kell meghatározni majd a szállítást javítani útkeresésekkel. Ha nem sikerült elszállítani az összes árut a termelőktől, akkor a kiadódó P, R halmazok alapján elvégezzük a lefedéseket és ezek segítségével egy számot határozunk meg, amely a fedetlen helyeken lévő redukált költségek minimuma. Ezután, mint ahogy ezt a bizonyításnál láttuk ezzel az számmal az alábbiak szerint módosítjuk a redukált költségeket:

Megjegyezzük, hogy az algoritmus során valójában a duál változókat nem használjuk, nem érdemes ugyanis kiszámítani őket, mivel csak az redukált költségekre van szükségünk. A duál változók egyébként burkoltan benne vannak a redukált költségekben.

Az új redukált költségekkel újra megoldunk egy általános Kőnig feladatot. Ennek megoldása szintén egy induló szállítás meghatározásával kezdődik. A Kőnig feladatnál elmondottakból tudjuk, hogy szállítás csak egyszer fedett helyeken lehet és az előzőekből pedig azt tudjuk, hogy az egyszer fedett helyeken nem változott a redukált költség, így az előző általános Kőnig feladatban kapott szállítás egyben az új Kőnig feladat induló szállítása lehet. Természetesen minden egyes általános Kőnig feladat induló szállítását az Észak-Nyugati sarok módszerrel is meghatározhatjuk, de az előbb említett lehetőség lehetővé teszi ennek mellőzését.

Ne feledkezzünk meg azonban arról, hogy a fent ismertetett „magyar módszer” csak standard szállítási feladat megoldására szolgál, azaz csak akkor alkalmazható, ha az összkínálat és az összkereslet egyenlő egymással. Ezért a megoldás 0. lépésében ellenőrizni kell a kereslet-kínálat egyensúlyát. Amennyiben nem standard szállítási feladattal van dolgunk, akkor először standard szállítási feladattá kell alakítani, ennek megvalósítására egy külön szakaszban visszatérünk.

A következő folyamatábrán a szállítási feladat „magyar módszerrel” történő megoldásának menetét vázoljuk fel: