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

A primál és a duál feladat között szoros kapcsolat van. Először a célfüggvények közötti kapcsolatra mutatunk rá. Ezt az összefüggést lemmában (segédtétel) mondjuk ki, amelyet a főtétel (a főtétel az optimális megoldások létezését és kapcsolatát mondja ki) bizonyításához használunk fel.

LEMMA:

Tetszőleges -ből -be vezető út és tetszőleges megengedett () potenciálrendszer esetén a úthossz nem lehet kisebb, mint a végponthoz tartozó potenciál, azaz a célfüggvények értékei között az alábbi összefüggés áll fenn:

Bizonyítás.

A duál feladat két feltételének felhasználásával és egyszerűsítéssel egyszerűen adódik, hogy

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

1. KÖVETKEZMÉNY:

Ha az -ből -be vezető út és a megengedett potenciálrendszer olyan, hogy a lemmában egyenlőség áll fenn, akkor a úthossz minimális értékű, a potenciál pedig maximális értékű, azaz az út és a potenciálrendszer optimális.

Bizonyítás.

Legyen a szóbanforgó út és a potenciálrendszer olyan, hogy .

Indirekte tegyük fel, hogy a út nem minimális, azaz létezik egy út, amelyre

Mivel a útra is igaz a lemma állítása, így

felhasználva a egyenlőséget, ebből adódik, hogy

ez pedig ellentmond a indirekt feltevésünknek, tehát nem létezik útnál jobb út, azaz a út optimális (minimális).

Most pedig indirekte tegyük fel, hogy a potenciálrendszer nem maximális, azaz létezik egy potenciálrendszer, amelyre

Mivel a potenciálrendszerre is igaz a lemma állítása, így

Az utóbbi két összefüggés ellentmond egymásnak, tehát a feltevésünk hamis volt, azaz nem létezik potenciálrendszernél jobb, tehát a potenciálrendszer optimális (maximális).

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 lemmában egyenlőség akkor és csak akkor áll fenn, ha a út minden élén

Bizonyítás.

Rendezzük át a lemma bizonyításában szereplő egyenlőtlenséget, ekkor a lemmabeli egyenlőség fennállásához azt kell megvizsgálnunk, hogy mikor lesz az alábbi összefüggés zérus

A duál feltétel szerint az összeg minden tagja nemnegatív, így az összeg akkor és csak akkor lehet zérus, ha minden tagja zérus. Ez pedig azt jelenti, hogy a lemmabeli egyenlőség szükséges és elégséges feltétele, hogy minden útbeli élen .

FORD tétel:

Ha van -et -vel összekötő út, akkor létezik olyan út és potenciálrendszer, hogy a lemmában egyenlőség áll fenn, azaz létezik minimális út és maximális potenciál; a minimális úthossz és a maximális potenciál egyenlő egymással, képletben:

Bizonyítás.

A bizonyítás konstruktív jellegű, az optimális megoldáspár (primál és duál) meghatározásának menetét (algoritmusát) is szolgáltatja.

Legyen a potenciálrendszer megengedett, amely tehát a duál feltételeket kielégíti. Ilyen potenciálrendszer biztosan létezik, hiszen a értékek nemnegativitása miatt a megengedett potenciálrendszer. Konstruáljunk a hálózat éleiből egy digráfot, amelynek E élhalmaza azon élekből álljon, amelyekre

Keressünk utat s-ből t-be az digráfon. A Minty tétel értelmében két eset lehetséges:

1. eset: van út

Ez azt jelenti, hogy ezen út minden élén . A két következmény alapján optimális megoldást kaptunk, azaz a megtalált út is és a potenciálrendszer is optimális.

2. eset: nincs út

MINTY tétel szerint van olyan vágás, amely üres. Ez azt jelenti, hogy a vágásban nincs olyan él, amelyre , tehát a hálózatban ezen vágásbeli éleken . Képezzük a vágásban levő éleken az

értéket, azaz számítsuk ki a hálózat vágásbeli élein a és a mennyiségek különbségének minimumát. Könnyen ellenőrizhető, hogy , hisz pozitív számok minimuma is pozitív. Most határozzunk meg egy új potenciálrendszert az alábbi módon:

Ez az új potenciálrendszer kielégíti a duál feltételeket, amelyet az alábbiakban igazolunk.

A , mert .

A feltételek teljesülését az élhalmaz partícióra bontásával igazolhatjuk legkönnyebben.

Az partíciókban az alábbiak szerint alakul a duál feltétel teljesülése:

  1. Ha , akkor ,

  2. Ha ,

  3. Ha , mivel ,

  4. Ha .

Ez utóbbi állítás az érték definíciója miatt igaz, ugyanis minden vágásbeli élre és az utolsó partíció éppen a vágás.

Az új potenciálrendszerre megismételjük a fent leírtakat. A duál célfüggvény értéke értékkel növekszik, mivel . Az alapadatok egészértékűsége miatt egész szám és a lemma alapján a duál célfüggvény felülről korlátos, ezért az eljárás véges sok lépésben végetér, azaz eljutunk az 1. esethez (optimális megoldáshoz).

A minimális út probléma megoldása FORD L.R. Jr. [ 4 ] és MINTY G.J. [ 11 ] munkáiban szerepel.