7. fejezet - Minimális költségű folyamfeladat

7.1. 7.1. A feladat megfogalmazása

Tegyük fel, hogy a élkapacitáson kívül minden élhez egy , egész értékű költséget rendeltünk, amely egységnyi mennyiségű folyam áramoltatásának költségét jelenti. A hálózaton átfolyó folyam költségét az alábbiak szerint értelmezzük:

azaz feltesszük, hogy a hálózat minden élen a költség arányos a folyammal és ezen élköltségek összegét értjük folyamköltség alatt.

Minimális költségű folyamfeladat (primál feladat):

Áramoltassunk át a hálózaton az s-ből a t-be irányuló, adott értékű folyamot úgy, hogy a folyam költsége minimális legyen. A feladat matematikai megfogalmazása a következő:

Meghatározandó a hálózat minden élére az folyam úgy, hogy a

mennyiség minimális legyen feltéve, hogy

Megfigyelhetjük, hogy a feladat egyenlőséges feltételeinek együtthatómátrixa a szomszédossági mátrix.

Minimális költségű folyamfeladat duál feladata:

A hálózat pontjaira vonatkozó egyenlőséges feltételekhez rendelt duál változók legyenek: .

A hálózat éleire vonatkozó kapacitáskorlátos egyenlőtlenséges feltételekhez rendelt duál változók legyenek: .

Ekkor a duál feladat a következő formában írható fel:

Megjegyzés:

Ha minden kapacitás és , akkor a minimális költségű folyamfeladat minimális út feladattá válik.