14.2. 14.2. A feladatpár matematikai vizsgálata

Először a szállítási feladat primál és duál feladatának célfüggvényértékei közötti kapcsolatot, majd az optimalitási kritériumot és végül a feladatpár megoldhatóságára vonatkozó dualitási tételt közöljük bizonyításaikkal együtt.

A SZÁLLÍTÁSI FELADATPÁR ALAPLEMMÁJA:

Ha az lehetséges szállítás (azaz kielégíti a primál feladat feltételeit) és lehetséges árrendszer (azaz kielégíti a duál feladat feltételeit), akkor

Bizonyítás.

Az egyébként egyszerű bizonyítás során először a duál feltételeket, majd sorra a primál feltételek használjuk fel:

Az első egyenlőtlenségnél felhasználtuk az nemnegativitását. A továbbiakban pedig az összeadandókat átrendeztük és kiemelést végeztünk, majd a többi primál feltételt használtuk fel.

A lemmából két fontos következményt olvashatunk ki.

1. KÖVETKEZMÉNY:

Ha az lehetséges szállítás és az lehetséges árrendszer olyan, hogy a hozzájuk tartozó primál és duál célfüggvényértékek megegyeznek, akkor ez a szállítás és ez az árrendszer egyben optimális megoldás is.

Bizonyítás.

Jelölje és azt a primál és duál lehetséges megoldást, amelyekre

Legyen tetszőleges, lehetséges szállítás. A lemma alapján

figyelembevéve a *-gal jelölt változókhoz tartozó célfüggvényértékek megegyezését, kapjuk, hogy

Ez utóbbi egyenlőtlenség éppen azt fejezi ki, hogy az primál lehetséges megoldás optimális megoldás. Hasonlóan igazolható, hogy az duál lehetséges megoldások szintén optimális megoldások. Ennek igazolását az olvasóra bízzuk.

A soron következő második következményt szokás optimalitási kritériumnak vagy egyensúlyi összefüggésnek is nevezni, mivel arra ad választ, hogy milyen feltételek esetén egyezik meg a két célfüggvény, azaz mikor optimálisak a megengedett megoldások.

2. KÖVETKEZMÉNY (Optimalitási kritérium):

A két feladat célfüggvényértéke akkor és csak akkor egyezik meg (azaz lemmában egyenlőség akkor és csak akkor áll fenn), ha minden indexpárra

Bizonyítás.

Ez a lemma bizonyításából egyszerűen kiolvasható, ugyanis a két oldal akkor és csak akkor lehet egyenlő, ha a bizonyításban szereplő egyenlőtlenség egyenlőséggel teljesül, azaz

amelyből átrendezéssel kapjuk, hogy

Mivel a fenti összeg minden tagjában mindkét tényező a primál és a duál feltételek miatt nemnegatív, ezért az összeg mindegyik tagja nemnegatív. Nemnegatív számok összege pedig akkor és csak akkor lehet zérus, ha mindegyik tagja zérus, azaz minden (i, j) indexpárra

A SZÁLLÍTÁSI FELADATPÁR DUALITÁSI TÉTELE:

Mind a primál, mind a duál feladatnak létezik optimális megoldása és a primál feladat célfüggvényértékének minimuma megegyezik a duál feladat célfüggvényértékének maximumával, azaz

Bizonyítás.

A tétel bizonyítása konstruktív bizonyítás, amely azt jelenti, hogy az optimális megoldásoknak nemcsak a létezését igazolja, hanem a bizonyítás menete egyben algoritmust is szolgáltat az optimális megoldások meghatározására. A bizonyításból kiolvasható algoritmus „magyar módszer” néven ismeretes. Az elnevezés H. W. KUHN-tól származik, aki ezzel kívánt emléket állítani két kiváló magyar matematikusnak. Az algoritmus „magyar” eredetére a későbbiekben még visszatérünk.

Legyenek adottak az lehetséges duál változók, amelyek kielégítik a feltételeket, azaz minden (i, j) indexpárra. A későbbiekben egyszerűsíti a jelöléseinket, ha bevezetjük az mennyiségeket. Ez az egyrészt a duál változók értékétől függő mennyiség, másrészt pedig a szállítási egységköltség módosított értéke, szokás ezért redukált szállítási egységköltségnek vagy röviden redukált költségnek is nevezni. Az optimalitási kritériumot, így az

összefüggéssel fogalmazhatjuk meg. Ez azt jelenti, hogy optimális esetben csak ott engedélyezett a szállítás, ahol . Kíséreljük meg az összes árut elszállítani a termelőktől a fogyasztókhoz úgy, hogy az optimalitási kritérium teljesüljön. Az csak akkor teljesedik, ha csak olyan cellákon engedélyezzük a szállítást, amelyekben . Tulajdonképpen egy általános Kőnig feladatot kell megoldanunk. Az ottani jelöléseknek megfelelően * ott van, ahol szabad a szállítás (), az cellákon pedig tiltás van.

Az általános Kőnig feladatot a vonatkozó algoritmus használatával megoldjuk és a KŐNIG tétel értelmében két esetet vizsgálunk.

1.eset:

Ha az általános Kőnig feladat megoldható, vagyis az összes árut el tudjuk szállítani, akkor ez a szállítás optimális is egyben, hisz az optimalitás követelménye teljesül. Vége az algoritmusnak.

2. eset:

Ha az általános Kőnig feladat nem oldható meg, akkor viszont a KŐNIG tétel értelmében megkapjuk a termelők P és a fogyasztók R halmazát, amelyekre mint tudjuk fennáll, hogy

Ha a P és az R halmazok segítségével elvégezzük a szokásos lefedést, akkor a KŐNIG tételből adódóan az alábbi táblázatban látható összefüggések is érvényesek:

A következő lépésben új és duál változókat határozunk meg, amelyek

  1. teljesítik a duál feltételeket és

  2. a duál célfüggvénynek az új értéke nagyobb az előzőnél.

Az új duál változók meghatározásához először határozzuk meg a fedetlen cellákban lévő redukált költségek minimumát, jelöljük ezt a számot -al:

Mivel az szám pozitív számok minimuma, így . Ennek az számnak és a P, R halmazoknak a segítségével az új és duál változókat az alábbiak szerint határozzuk meg:

Ezek az új duálváltozók az megfelelő választása miatt kielégítik a duál feltételeket. Másképpen fogalmazva az új duál változókkal számolt új redukált költségek is nemnegatívok, azaz

minden (i, j) indexre.

Vizsgáljuk meg, hogy ez valóban teljesedik-e. A P, R halmazokkal particionált tábla négy blokkjára blokkonként külön megvizsgáljuk:

  1. Ha és , akkor .

  2. Ha és , akkor .

  3. Ha és , akkor , az pozitivitása miatt.

  4. Ha és , akkor , az definíciója miatt.

A fentiekből kiolvasható, hogy az új redukált költségek számítása a lefedés segítségével nagyon egyszerűen elvégezhető, nevezetesen

Miután beláttuk, hogy az új duál változók valóban megengedettek, meghatározhatjuk a hozzájuk tartozó duál célfüggvény értékét:

Mivel és a KŐNIG tétel értelmében a kifejezésben az szorzója pozitív, ezért a duál célfüggvény új értéke valóban nagyobb, mint az előző célfüggvényérték. Az új duálváltozókkal megismételjük a fenti lépéseket, azaz megpróbáljuk megoldani az új általános Kőnig feladatot, ott megengedve a szállítást, ahol az új redukált költségek értéke zérus.

Mivel mindegyik , valamint az is egész szám, ezért a duál célfüggvény értéke egész számmal növekszik. A lemma alapján tudjuk, hogy a duál célfüggvény korlátos felülről, mindezekből következik, hogy az eljárás véges sok lépésben végetér.

A szállítási feladat először HITCHOCK F.L. munkájában [ 7 ] található, ezért szokás HITCHOCK feladatnak is nevezni. A szállítási feladat lineáris programozási módszerrel is megoldható. A folyamok segítségével történő megoldási módszert, a dualitási tétel konstruktív bizonyítását FORD L. R. Jr. és FULKERSON D.R. [ 5 ] adták meg.