7.3. 7.3. Példamegoldás

Határozzuk meg az alábbi hálózaton az 1-ből a 4-be irányuló, 7 folyamértékű minimális költségű folyamot! A hálózat élein két számot tüntettünk fel, az első a kapacitást, a második (zárójelben lévő) pedig a költséget jelenti.

0. lépés

Induló adatok: , , , ,

Az induló szabad kapacitás táblázat és költségtáblázat:

A minimális út (P):

Az út minimális költsége:

Az úton a minimális kapacitás:

A folyamnövelés értéke:

A folyamérték:

A hiányzó folyamérték:

A folyamköltség:

1. lépés

Az új szabad kapacitás táblázat és költségtáblázat:

A minimális út (P):

Az út minimális költsége:

Az úton a minimális kapacitás:

A folyamnövelés értéke:

A folyamérték:

A hiányzó folyamérték:

A folyamköltség:

2. lépés

Az új szabad kapacitás táblázat és költségtáblázat:

A minimális út (P):

Az út minimális költsége:

Az úton a minimális kapacitás:

A folyamnövelés értéke:

A folyamérték:

A hiányzó folyamérték:

A folyamköltség:

Vége az algoritmusnak, mert elértük az adott folyamértéket.

Megoldás:

Az eredeti hálózat élein a folyamok:

Az összes szállítási költség: , amelyet az algoritmus során is meghatároztunk.