3.4. 3.4. Példamegoldás

Az eljárás illusztrálására tekintsük az alábbi hálózatot és ezen keressük meg a 2-ből az 5-be vezető minimális utat.

A hálózat struktúra táblázata ():

0. lépés:

Kezdeti potenciálok ill. a kezdeti értékek meghatározása:

1. lépés:

Útkeresés 2-ből 5-be az típusú éleken

Nem találtunk utat. A kiadódó (S,T) halmazok segítségével elvégezzük a lefedést. A címkézett oszlopokat és a címkézetlen sorokat fedjük le egy-egy vonallal.

A lefedés után meghatározzuk az értéket, amely a fedetlen elemek minimuma:

Ezután pedig az új táblázatot határozzuk meg, a fedetlen helyeken csökkentünk, a kétszer fedett helyeken növelünk értékkel. Ezután újabb útkeresés következik, amelyet a 2. lépésben mutatunk be. Megjegyezzük, hogy a továbbiakban nem rajzoljuk fel a táblázatot kétszer, hanem a címkézés után azonnal elvégezzük a lefedést. Reméljük ez a rövidítés nem zavarja a kezdő olvasót.

2. lépés

Útkeresés 2-ből 5-be az típusú éleken.

3. lépés:

Útkeresés 2-ből 5-be az típusú éleken.

4. lépés:

Útkeresés 2-ből 5-be az típusú éleken

Vége az algoritmusnak, mert utat találtunk. A primál és a duál feladat optimális értékeinek meghatározása:

Minimális út feladat optimális megoldása:

A P minimális út:

A P minimális út hossza:

Maximális potenciál feladat optimális megoldása:

, a duál feltétel miatt.

Az útban lévő első élre ((2,1) él) felírt egyenletben csak a az ismeretlen, amelynek értéke:

Az útban lévő második élre ((1,4) él) felírt egyenletben csak a az ismeretlen, amelynek értéke:

Az útban lévő harmadik élre ((4,5) él) felírt egyenletben csak a az ismeretlen, amelynek értéke:

A nem útba eső 3 pont potenciálját például meghatározhatjuk az (3,5) élre felírt egyenletből, amelyben csak a az ismeretlen, ennek értéke:

Természetesen más élet is választhattunk volna, például a (2,3) élen könnyebb lett volna a számolás.

Összefoglalva, a potenciálok optimális értékei a következők:

A duál célfüggvény optimál értéke, .

Látható, hogy optimális esetben a célfüggvények értékei megegyeznek.