15. fejezet - Trans-shipment feladat

15.1. 15.1. A feladat megfogalmazása

Tekintsünk egy hálózatot, több forrással és több nyelővel. A hálózat minden élén a kapacitások mellett értelmezzünk egy szállítási egységköltséget, jelölje ezeket A hálózatban az élek kapacitása és egységköltsége mellett adottak a forrásokból kifolyó folyamok és a nyelőkbe befolyó folyamok mennyiségei. Jelölje ezeket az adott mennyiségeket ill. . Tegyük fel, hogy a forrásokból kifolyó mennyiségek összege megegyezik a nyelőkbe befolyó mennyiségek összegével, azaz

A hálózat olyan pontját, amely sem nem forrás, sem nem nyelő, közbülső pontnak nevezzük. Ezeket a pontokat átrakodó pontoknak is szokás nevezni, innen a feladat elnevezése, például ezekben a pontokban egyik hajóról a másik hajóra történik a beérkező áru átrakodása és innen a továbbszállítása. A trans-shipment feladatot sokféleképpen elképzelhetjük. Egy olyan szállítási feladatként is, amelyben a termelőkön és a fogyasztókon kívül ún. átrakodópontok is vannak, tehát nem közvetlenül történik a szállítás a termelő és a fogyasztó között. Az ilyen módon megfogalmazott feladatot általános szállítási feladatnak is nevezik. A szállítási feladatban termelő-termelő és fogyasztó-fogyasztó között nincs kapcsolat. A trans-shipment feladatban ilyen kapcsolatok is lehetnek.

A trans-shipment feladat megfogalmazása:

Határozzuk meg a hálózatban a minimális költségű folyamot úgy, hogy teljesüljenek az alábbiak:

  • az éleken a folyam nem lehet nagyobb az él kapacitásánál,

  • a forráspontokból az adott mennyiség áramlik ki,

  • a nyelőpontokba az adott mennyiség áramlik be,

  • a közbülső pontokban a beáramló és a kiáramló mennyiség azonos legyen.

A trans-shipment feladat matematikai megfogalmazása:

Vezessük be a folyamproblémánál megismert jelölést egy pontból kifolyó ill. befolyó folyamok összegére:

Meghatározandók az folyamkomponensek úgy, hogy