9.4. 9.4. Példamegoldás

1. Példa :

Oldjuk meg az alábbi általános Kőnig feladatot!

0. lépés: Kezdeti szállítás meghatározása.

Célszerű azzal kezdeni a megoldást, hogy a tiltott helyeket „-” jellel bejelöljük és ekkor az üres helyeket kell kitölteni.

Mint említettük az ún. Észak-Nyugati sarok módszerrel szokás egy induló szállítást előállítani. Az Észak-Nyugati sarok módszer lényege az, hogy a táblázat bal felső (É-Ny-i irányú) sarkából kiindulva balról jobbra és fentről lefelé haladva írjuk be a szabad helyekre a szállítási mennyiségeket. Mivel célunk a legtöbb árú elszállítása, ezért mindig a lehető legnagyobb szállítási értékkel töltjük fel a táblát.

Az Észak-Nyugati sarok módszer néhány lépését az alábbiakban közöljük:

A -ből az -be szállíthatunk (szabad hely), de legfeljebb 18-at (a 18 és a 32 minimumát) és ezt a 18-at írjuk a táblázatba, a kínálatát és az keresletét 18-al csökkentve. A -ből az -ba is szállíthatunk, de már csak zérus mennyiséget. Hasonlóan zérussal kell kitöltenünk a táblázat első sorának utolsó szabad helyét is. Most a második termelő következik. A -ből az -be szállíthatunk (szabad hely), de legfeljebb 14-et (a 22 és a 14 minimumát) és ezt a 14-et írjuk a táblázatba, a kínálatát és az keresletét 14-el csökkentve. A táblázat többi szabad helyét hasonlóan kell kitölteni, tehát az eredeti táblázat és a szállítási táblázat egyidejű figyelésével. Párhuzamosan töltjük ki a táblázat szegélyeit is, ahová mindig a megmaradó kínálatot ill. a kielégítetlen igényt írjuk. Nyilvánvalóan mindig igaz az, hogy a táblázat (szegélyeket is figyelembe véve) soraiban lévő számok összege a termelők kínálatát, az oszlopaiban lévő számok összege pedig a fogyasztók keresletét adja. A következő táblázat az induló szállítást mutatja.

Elvileg bármely módszerrel meghatározható egy lehetséges induló szállítás, sőt a szabad helyeket zérussal is feltölthetnénk. Láthatjuk, hogy a 86 kínálatból minden erőfeszítés nélkül 80-at sikerült indulásként elszállítani. Az is megállapítható, hogy még a és a termelőtől kellene szállítani az -be. Ezt egy út megkeresésével végezzük.

1. lépés: Útkeresés s -ből t -be címkézéssel.

A címkézés eredménye az alábbi táblázatban látható. Ahhoz, hogy könnyebben megértsük a címkézés lényegét, a címkézést lépésenként közöljük, ezt mutatja a fenti táblázat. A termelők címkéit a táblázat jobb, a fogyasztók címkéit pedig az alsó szegélyen tüntetjük fel.

0. lépés: A és címkéje induláskor „-s”, mert innen kell elszállítani árut és addig kell címkézni, amíg az -be nem érkezünk vagy azt kapjuk, hogy nincs út.

Most megnézzük, hogy a és termelőtől mely fogyasztókhoz mehetünk.

1.1. lépés: A -ból az -be és az -ba, mehetünk, így ezen fogyasztók címkéjeként beírjuk a -t.

1.2. lépés: A címkéjét „+s”-re változtatjuk.

2.1. lépés: A -ből az és -be mehetünk. Mivel -nek már van címkéje, így csak az -et címkézzük, mégpedig -el.

2.2. lépés: A címkéjét „+s”-re változtatjuk.

Mivel a kérdéses -be nem jutottunk el, ezért most a fogyasztóktól próbálunk a termelőkhöz szabad kapacitású úton visszamenni.

3.1. lépés: Az -ből -be haladhatunk, mivel a viszonylatban van szállítás, amit visszaszállíthatunk. A -t címkézzük -vel.

3.2. lépés: Az címkéjét „+” előjelűre változtatjuk.

4.1. lépés: Az -ból nem tudunk továbbhaladni, mivel nem szállítottunk hozzá, nem címkézünk.

4.2. lépés: Az címkéjét „+” előjelűre változtatjuk.

5.1. lépés: Az -ből nem tudunk továbbhaladni, mivel nem szállítottunk hozzá, nem címkézünk.

5.2. lépés: Az címkéjét „+” előjelűre változtatjuk.

Most újra termelőktől próbálunk a fogyasztókhoz menni szabad kapacitású úton. A címkézésnél tehát felváltva címkézünk termelőtől fogyasztóhoz és fogyasztótól termelőhöz. Szisztematikusan címkézzünk, tehát amíg van negatív címke a függőleges ill. a vízszintes címkemezőkben, addig ne váltsunk a másik irányra.

6.1. lépés: A -ből az és -be mehetünk. Mivel -nek már van címkéje, így csak az -et címkézzük, mégpedig -vel.

6.2. lépés: A címkéjét „+” előjelűre változtatjuk.

Most újra fogyasztótól címkézünk.

7.1. lépés: Az -ből -be haladhatunk, mivel a viszonylatban van szállítás, amit visszaszállíthatunk. Az -et címkézzük -el.

7.2. lépés: Az címkéjét „+” előjelűre változtatjuk.

Most újra termelőtől címkézünk.

8.1. lépés: A -ből az , és -be mehetünk. Mivel az , már címkézett, így csak az -be mehetünk és az -öt címkézzük -el.

Ezzel a lépéssel be is fejeztük a címkézést, hiszen olyan fogyasztóhoz jutottunk, amelyiknek még van igénye.

Az alábbi táblázat a címkézés eredményét mutatja, de nem lépésenkénti bontásban.

A címkézés eredményeképpen az alábbi út adódott. Az utat mint ismeretes a címkéken visszafelé haladva határozhatjuk meg.

Az út éleinek szabad kapacitását az út élei alatt tüntettük fel. A típusú élen a szabad kapacitás , mivel a kapacitás is az. Az típusú élen pedig a szabad kapacitás a megfelelő típusú él szállítása. Az út mentén a szállítás a szabad kapacitások minimumával () növelhető. Példában az út kapacitása . Észrevehető, hogy az első és utolsó élnek, valamint minden második élnek van véges szabad kapacitása. Jelöljük az út éleit és szimbólumokkal, mégpedig úgy, hogy -el az út azon éleit, amelyek közrejátszanak meghatározásában, -el pedig az út többi élét. Az út tehát -el kezdődik (ill. végződik) és felváltva és jeleket tartalmaz. Az utat a későbbiekben nem érdemes külön leírni, hanem az út felgöngyölítése során a táblázatba és jelekkel bejelöljük az út éleit. Ily módon a -t a szimbólummal jelölt számok minimumaként határozhatjuk meg, példánkban

A ismeretében folyamnövelést kell végrehajtani az út mentén. A jelöléseink segítségével ezt az alábbi egyszerű módon végezhetjük el:

A jobb érthetőség kedvéért az út megfelelő jelekkel való jelölésével mégegyszer megismételjük az előző táblázatot. A táblázatba bejelöltük félkövéren az út vonalát is. Ez mindig egy törtvonalnak adódik, amely vízszintes és függőleges vonalain is az egyik végpont -el, a másik pedig -el van jelölve.

Az alábbi ábra is az utat mutatja, de most az általános Kőnig feladat kétrészes gráfján:

A táblázatos útjelölésnél tehát minden vizszintes ill. függőleges vonal mentén egy növelést és egy csökkentést hajtunk végre. Azoknál a termelőknél ill. fogyasztóknál, ahol nincs elszállítandó árú ill. kielégítetlen igény ott egyszerűen átrendeződik a szállítás. Amennyivel egyik helyen többet szállítottunk, a másik helyen ugyanannyival kevesebbet. Kivételt csak az út első és utolsó éle képez, mert itt a szállítás növekszik. A gráfon látható utat alternáló útnak nevezzük, mert minden második éle és ezeken növelést ill. minden második éle típusú és ezeken csökkenést eszközlünk.

2. lépés: Folyamnövelés és útkeresés címkézéssel.

3. lépés: Folyamnövelés és útkeresés címkézéssel.

Vége az algoritmusnak, útkeresésre már nincs szükség, mert a termelőktől a kínálatuknak megfelelő mennyiségű árut elszállítottuk. Az eldöntendő kérdésre tehát a válasz igen, azaz az összes árú elszállítható a termelőktől. Azt is megkaptuk egyben, hogy milyen módon kell végrehajtani a szállítást. Az szállításokat a fenti szállítási táblázat mutatja. A -ből az -be 12 egységet, -ből az -be 6 egységet, stb. kell szállítani.

2. Példa:

Oldjuk meg az alábbi általános Kőnig feladatot!

1. lépés: Induló szállítás meghatározása Észak-Nyugati sarok módszerrel és útkeresés címkézéssel

2. lépés: Folyamnövelés és útkeresés címkézéssel.

Vége az algoritmusnak, mert nincs út, így nem tudjuk tovább növelni a szállítást. Arra az eldöntendő kérdésre, hogy az összes árú elszállítható-e, nem a válasz, mivel 2 mennyiséget semmiképpen nem lehet elszállítani. Arra a kérdésre, hogy maximálisan mennyi árú szállítható el a termelőktől, szintén megkaptuk a választ, 2 híján az összeset, azaz 87-et. Az algoritmus azt is megmutatja, hogy a maximális mennyiséget milyen módon kell elszállítani. A fenti szállítási táblából olvashatók ki az szállítások. Mivel az összes árut nem lehet elszállítani, így a KŐNIG tétel értelmében meghatározhatók a termelők és fogyasztók P és R halmazai. A P ill. R halmazba a megcímkézett termelők ill. fogyasztók tartoznak, azaz

A P-beli termelők összkínálata és az R-beli fogyasztók összkereslete pedig az alábbi

Tehát , ahogy ezt a KŐNIG tétel állította. Valóban nem lehet az összes terméket elszállítani, hiszen már a P-beli termelőktől sem tudjuk a kínálatuknak megfelelő 46 mennyiséget elszállítani, mert csupán 44-et képesek fogadni azok a fogyasztók, amelyekhez a P-beliek szállíthatnak.

Végezetül a lefedést is elvégezhetjük a szállítási táblázaton, 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 mindenhol tiltás van, így minden szabad hely lefedett. A kétszer fedett helyeken a szállítás zérus, így pozitív szállítás csak egyszer fedett helyen lehet. A fedővonalrendszer súlyszáma: 87, amely a lefedett sorokhoz és oszlopokhoz tartozó kínálatok és keresletek összege. A fedővonalrendszer olyan, hogy az összes szabad helyet (*-ot) lefedi és a súlyszáma a lehető legkisebb. Az elszállítható maximális árúmennyiség egyenlő a fedővonalrendszer súlyszámával. Ez a FORD-FULKERSON tételből következik.