9.3. 9.3. Algoritmus az általános Kőnig feladat megoldására

A KŐNIG tétel bizonyítása egyúttal módszert is adott mind az egzisztencia formájú, mind az optimalizációs formájú Kőnig feladat megoldására. Mivel a problémát a maximális folyam-minimális vágás feladatra vezettük vissza, így annak megoldási algoritmusát fogjuk használjuk.

Két lényeges észrevétel azonban megkönnyítheti a megoldást.

  1. A folyamprobléma kiinduló lépése egy lehetséges folyam (szállítás) meghatározása. Általában a zérus folyamból szoktunk kiindulni. Az általános Kőnig feladathoz konstruált folyamprobléma a kétrészes digráf szerkezet miatt nagyon speciális, így egyszerűen nyerhető az azonosan zérus szállítástól különböző induló szállítás is. Ezt az induló szállítást sokféleképpen meghatározhatjuk, azonban javasoljuk az ún. Észak-Nyugati sarok módszer szerint elvégezni. Ezt az egyszerű módszert majd a példamegoldás során fogjuk ismertetni.

  2. A megoldandó csúcspontú folyamfeladatot mint tudjuk egy méretű táblázaton kell megoldani. A folyamfeladat speciális szerkezetét azonban nemcsak az induláskor, hanem a megoldás során is kihasználhatjuk. Mivel bármely két termelő és bármely két fogyasztó között a kapacitás zérus, ezért ezeken az éleken nem folyhat folyam, így az eredeti méretű táblázaton is megoldhatjuk a feladatot, hisz a folyamprobléma címkézése során szükséges szabad kapacitású éleket ezen a kisebb méreten is tudjuk tárolni. Az alábbi ábra mutatja a megoldáshoz használt táblázatot.

    • Az típusú él szabad kapacitását a táblázat (i) részén tároljuk. Ez a szabad kapacitás tulajdonképpen a termelőtől még elszállítandó árúmennyiséget jelenti.

    • Az típusú él szabad kapacitását a táblázat (ii) részén tároljuk. Ez a szabad kapacitás az fogyasztó kielégítetlen igényét jelenti.

    • A tábla belsejében a szállítást tároljuk, itt a szabad kapacitás tárolása a kapacitás miatt értelmetlen lenne. Azokat a cellákat, ahol a szállítás nincs megengedve (tiltott hely) „-” jellel jelöljük.

    • Mivel a folyamproblémát teljes hálózaton oldjuk meg, így az élek is szerepelnek a hálózaton, amelyek szabad kapacitása nem más mint a él szállítása, hisz legfeljebb ennyit szállíthatunk vissza, más szóval legfeljebb ennyivel csökkenthetjük az él szállítását.

Ezekután a címkézésnek a csökkentett méretű táblázatra történő adaptálásáról kell szólnunk röviden.

A címkézéssel mindig a forrásból (s) a nyelőbe (t) keressük a szabad kapacitású utat, vagyis olyan utat, amelyen a folyam növelhető. Tehát a kínálattal rendelkező valamelyik termelőtől kell a kielégítetlen igénnyel rendelkező valamelyik fogyasztóhoz eljutni. Így „-s”-el azokat a fogyasztókat kell megcímkézni, amelyek még rendelkeznek elszállítandó áruval, vagyis amelyeknél az (i) részben pozitív szám áll. Az útkeresés végpontja azon fogyasztók valamelyike, amelynél az (ii) részben pozitív szám áll.

A hálózat többi éle és típusú. Az útkeresés során termelőtől minden olyan fogyasztóhoz mehetünk, ahol nincs tiltva a szállítás, azaz ahol a táblázatban zérus vagy pozitív szám áll. Viszont fogyasztótól termelőhöz csak olyan cellán mehetünk, amelyben pozitív szám áll.