9.2. 9.2. A feladat matematikai vizsgálata

Az általános Kőnig feladat megoldhatóságára (egzisztencia formára) vonatkozik az alábbi tétel.

KŐNIG tétel:

Adott kvalifikációs táblázat esetén

Más szavakkal megfogalmazva: vagy elszállítható az összes árú, vagy ha nem, akkor megadható a termelőknek olyan részhalmaza, hogy ezen termelők összkínálata meghaladja azon fogyasztók összkeresletét, amelyekhez a kiválasztott termelők együttesen szállíthatnak.

A következőkben a tétel bizonyítását közöljük. A tétel bizonyítására konstruktív bizonyítást adunk, ami azt jelenti, hogy a bizonyítással a feladat megoldásának módját is megadjuk.

Bizonyítás.

A tétel bizonyítása a maximális folyam-minimális vágás feladatpár alaptételén (FORD-FULKERSON tétel) alapszik.

Konstruáljunk egy hálózatot, amelynek csúcspontjai a termelők és a fogyasztók, ezenfelül vegyünk fel egy forrást (s) és egy nyelőt (t). Minden termelőhöz vezessen él az s forrásból, minden fogyasztótól vezessen él a t nyelőhöz. A többi él termelők és fogyasztók közötti, mégpedig olyan viszonylatban, ahol megengedett a szállítás. A hálózat éleit és a kapacitásait az alábbi ábra mutatja. Az ábrába berajzoltunk egy vágást és a P, R ponthalmazokat is, amelyek a bizonyítás során lesznek meghatározva.

Legyen az típusú él kapacitása a termelő kínálata, az típusú él kapacitása az fogyasztó kereslete és a típusú él kapacitása végtelen .

Az általános Kőnig feladatot ezáltal egy folyamatfeladatra vezettük vissza. A folyamfeladat megoldási algoritmusával a folyamproblémát megoldjuk. A maximális folyam megoldása a Kőnig feladattal kapcsolatban az alábbiakat jelenti:

Az a -ből elszállított összmennyiséget, az az -be szállított összmennyiséget, az pedig a -ből az -be szállított árúmennyiséget jelenti. Ha például valamely , akkor ez a csomóponti megmaradási törvény alapján azt jelenti, hogy a -ből az összes árut elszállítottuk a fogyasztókhoz. Két esetet különböztetünk meg attól függően, hogy az folyamérték maximális értékére milyen eredményt kapunk.

1. eset: A maximális folyam értéke .

Ez azt jelenti, hogy az s-ből kiinduló élek mindegyike telített, ugyanis csak így lehet a folyam értéke .

A csomóponti megmaradási törvény szerint pedig ekkor mindegyik termelőtől pontosan a kínálatának megfelelő mennyiségű árut szállítunk el. Tehát ebben az esetben az összes árú elszállítható a termelőktől. A folyamfeladat megoldásai adják meg azt, hogyan lehet elszállítani az árukat.

2. eset: A maximális folyam értéke .

Ez azt jelenti, hogy az s-ből kiinduló élek nem mindegyike telített, tehát az összes árút nem lehet elszállítani. A folyamprobléma tárgyalásakor megismertük, hogy a maximális folyamhoz tartozik egy minimális vágás, amelyet a fenti ábrában tüntettünk fel. A vágás S ponthalmazába tartozó termelők halmazát P-vel, a fogyasztók halmazát pedig R-el jelöltük. A vágás T ponthalmazába tartozó termelők ill. fogyasztók halmazát -vel ill. -el jelöljük. Az, hogy ez a vágás minimális, a következőket jelenti.

Ezekután meghatározhatjuk az (S,T) vágás minimális átbocsátóképességét. Az vágásban lévő élek kapacitásait kell összeadni, amely az ábráről leolvasva az alábbi:

A FORD-FULKERSON tétel értelmében . Viszont a maximális folyam esetünkben , ezért az alábbi egyenlőtlenség írható

amelyet átrendezve

adódik. Ezt a bevezetett jelölésekkel felírva a

bizonyítandó összefüggést kaptuk.

Végül néhány megjegyzést fűzünk a 2. esethez, amikor az összes árú nem szállítható el. Mint tudjuk, a folyamprobléma meghatározása során kiadódó minimális vágást lefedéssel is szemléltethetjük. Fedjük le a -beli termelőkhöz tartozó sorokat ill. az R-beli fogyasztókhoz tartozó oszlopokat. Rendezzük át a táblázatot sorok és oszlopok cseréjével úgy, hogy az első sorokban a P-beli termelők, az első oszlopokban R-beli fogyasztók legyenek. Ekkor az alábbi táblázat adódik. Megjegyezzük, hogy a gyakorlati példákban a sorok és oszlopok cseréjére nincs szükség, itt azért tettük meg, hogy szemléletesebben lássuk az alábbi megjegyzéseket.

Megjegyzések:

  1. A fedetlen helyen nincs *, azaz ezeken a helyeken az általános Kőnig feladatban tiltott a szállítás. Ez egyben azt is jelenti, hogy a fedővonalrendszer az összes *-ot lefedi.

  2. A kétszer fedett helyeken nincs szállítás. A szállítási lehetőség (*) nincs kizárva ezeken a helyeken, de a szállítás zérus.

  3. Minden -beli termelőtől elszállítottuk a kínálatuknak megfelelő mennyiségű árut.

  4. Minden R-beli fogyasztó igényét kielégítettük.

  5. A lehető legtöbb mennyiségű árú lett elszállítva a termelőktől a fogyasztókhoz.

Az első négy megjegyzés abból következik, hogy a minimális vágás minden éle telített. Az első két megjegyzés szerint szállítás csak az egyszer fedett helyeken lehet.

Felhívjuk a figyelmet arra, hogy a Kőnig feladat egzisztencia formájára mondtuk ki a KŐNIG tételt. Ezt a tételt át is fogalmazhatjuk a következőképpen:

KŐNIG tétel (más formában):

Adott kvalifikációs táblázat esetén az összes árú elszállíthatóságának szükséges és elégséges feltétele az, hogy minden termelő esetén

Természetesen a két egzisztencia tétel ekvivalens egymással, az először megfogalmazott viszont az alaptételünkhöz, a MINTY tételhez hasonló szerkezetű.

Az (1) megjegyzést mélyebben vizsgálva a következőket mondhatjuk. Legyen adott egy táblázatunk, amelyben *-ok szerepelnek. Minden sornak ill. oszlopnak adjunk egy súlyszámot. Fedővonalrendszer alatt a táblázat bizonyos sorainak ill. oszlopainak egy-egy vonallal való lefedését értjük. A fedővonalrendszer súlyszámát pedig a lefedett sorok ill. oszlopok súlyszámainak összegével definiáljuk.

Lefedési feladat:

Fedjük le a táblázatban szereplő összes *-ot a legkisebb súlyszámú fedővonalrendszerrel!

Ez az optimalizálási feladat a folyamfeladat duálisának, vagyis a minimális vágás feladatnak felel meg. A fedővonalak a vágásnak, a fedővonalak súlyszáma pedig a vágás átbocsátóképességének felel meg. Tehát ezen lefedési probléma megoldására is a Kőnig feladat megoldási módszere szolgál.