7.2. 7.2. Algoritmus a minimális költségű folyamfeladat megoldására

A feladatok matematikai vizsgálatával most nem foglalkozunk, csupán egy kézenfekvő algoritmust közlünk, amely segítségül hívja a minimális út feladat megoldását.

Az algoritmus leírásában a következő jelöléseket használjuk:

Jelölje a tényleges folyamértéket. Jelölje a hiányzó folyamértéket, amely megmutatja, hogy a megadott folyamérték () eléréséhez még mekkora folyamérték hiányzik, képlete: . Jelölje C a folyamköltséget, azaz a célfüggvény értékét.

  1. A hálózat kiegészítése teljes hálózattá, zérus kapacitású és végtelen költségű élekkel.

  2. Az induló folyam legyen a zérus folyam, azaz minden élen. Az induló szabad kapacitás: . Az induló folyamérték: . Az induló hiányzó folyamérték: . Az induló folyamköltség: .

  3. Minimális út meghatározása s-ből t-be a költségadatokon. A minimális út feladat célfüggvényének optimális értéke az út mentén lévő költségek összege, amelyet úgy is felfoghatjuk, mint egységnyi mennyiségű folyam úton való áramoltatásának folyamköltsége. Jelölje ezt .

  4. A minimális út kapacitásának a meghatározása (), amely az út mentén a szabad kapacitások minimuma.

    A hiányzó folyamérték meghatározása: .

    Az út kapacitásának tényleges értéke a és a értékek minimum, azaz . Ezzel az értékkel növelhetjük meg az út mentén a folyamot.

    A folyamérték meghatározása: .

    A folyamköltség meghatározása: Az út minden élén növeltük a folyamot -val, így a mennyiségű folyam áramoltatásának költsége , az új folyamköltség:

  5. A folyam ill. a szabad kapacitás módosítása:

    Az út kapacitásával az út minden élén növeljük a folyamot, a visszút mentén pedig csökkentjük. Ehelyett azonban a szabad kapacitásokat () módosítjuk az alábbiak szerint:

    Ha , vagy ami ugyanazt jeleni, hogy , akkor megállunk, mert ezzel a folyamnöveléssel a folyam értéke elérte az előírt értéket, hisz pontosan a hiányzó folyamértékkel javítottunk a folyamon. A szabad kapacitások segítségével meghatározhatjuk a minimális költségű folyamot a hálózat élein. A minimális folyamköltséget pedig C értéke adja.

    Ha , vagy , akkor újabb minimális út keresésére van szükség, de előtte módosítani kell a költségeket. A (6) pontban folytatjuk az eljárást.

  6. A költségek módosítása:

    A módosítás szemléletes, hisz, ha egy élen még van szabad kapacitás, akkor ott nem változtatunk a költségen. Ha egy él szabad kapacitása zérus, akkor azon már nem lehet további folyamot áramoltatni, így az útkeresésnél ezt az élet nem szabad figyelembe venni. Ezt úgy valósíthatjuk meg, hogy az él költségét végtelen nagyra választjuk, így ez az él biztosan nem kerül bele a minimális útba. Az út visszélein a szabad kapacitás nőtt, így ott lehet további folyamnövelés, viszont ha ezeken az éleken növeljük a folyamot, az azt jelenti, hogy az ellentétes élen csökken a folyam, így a folyamköltség is. Ezért ezeknek az éleknek negatív költséget adunk, mégpedig az ellentétes irányú él költségének (-1)-szeresét.

  7. Visszatérés a (3) ponthoz, azaz újabb minimális út feladatot kell megoldanunk.

Megjegyzés:

Az algoritmus során minden lépésben minimális utat kell meghatározni. A költségek között viszont lehetnek negatív számok is. A minimális út megkeresésének algoritmusának ismertetésekor feltettük, hogy a költségadatok nemnegatívok. Ezért a soron következő példamegoldásban a megoldási lépéseket csak vázlatosan hajtjuk végre, a minimális utat csupán közöljük. Fontos megjegyeznünk, hogy a feladat duálisának segítségével hatékony primál-duál algoritmus dolgozható ki, amelyet out-of-kilter néven ismerünk.