5. fejezet - Maximális folyam - minimális vágás feladatpár

Mint ahogy az előző fejezetekben is láttuk a hálózatokon többféle optimalizálási feladatot értelmezhetünk. A következő fejezetekben az ún. folyamproblémákkal fogunk foglalkozni, látni fogjuk, hogy ezek szorosan kapcsolódnak a vágással. Ezek a feladatok olyan lineáris programozási feladatok, amelyek speciális szerkezetüknél fogva sok hasznos tulajdonsággal rendelkeznek és egészértékű optimális megoldásuk van. Számos érdekes és a gyakorlatban fontos kombinatorikai feladat is megfogalmazható és megoldható folyamfeladatként. Némely esetben kevéssé kézenfekvő a kapcsolat a folyamok fizikai valóságával. Ebben a fejezetben a folyamproblémák standard modelljét a maximális folyam-minimális vágás feladatpárt és e feladatpárra vonatkozó ismereteket közöljük. A további fejezetekben röviden vázolunk további folyam modelleket is. A folyamfeladatokat követő fejezetek modelljeinek alapját is a maximális folyam - minimális vágás feladatpár fogja alkotni.

5.1. 5.1. A feladatpár megfogalmazása

Legyen adott egy hálózat. A hálózat éleihez rendelt nemnegatív számot az él kapacitásának nevezzük. Ezt a kapacitást különbözőképpen foghatjuk fel attól függően, hogy milyen konkrét problémát fogalmazunk meg: valamely termékből egységnyi idő alatt legfeljebb mennyi tud az útszakaszon folyamatosan áthaladni vagy elektromos hálózat esetén a vezetékeken átfolyó áram maximális erőssége, stb. Legyen két pont kitüntetve, az egyik a forrás, amelyet jelöljünk -el, másik a nyelő, jele legyen . A folyamproblémát nagyon vázlatosan úgy fogalmazhatjuk meg, hogy keressük a forrásból a nyelőbe vezető maximális mennyiségű folyamot. Jelölje az élen átmenő folyam nagyságát. Általánosan folyamról beszélünk, amely egy konkrét feladat kapcsán lehet termékmennyiség, áramerősség, stb. A folyam a forrásból ered, a nyelőben elnyelődik és a hálózat éleire a kapacitáskorlátozásnak, a pontjaira pedig Kirchoff csomóponti törvényének kell teljesedni. Az utóbbi feltételt megmaradási szabályként is említhetnénk, amely azt fejezi ki, hogy a hálózat mindegyik közbülső (forrástól és nyelőtől különböző) pontjára érvényes, hogy egy adott pontba befolyó folyamok értéke azonos az onnan kifolyó folyamok értékével. Egy adott pontból kifolyó folyam mennyiségét az pontbeli folyamértéknek nevezzük és a összegzéssel írhatjuk le. Hasonlóan írható le a befolyó folyam is. A forráspontból kifolyó mennyiséget pedig a folyam értékének nevezzük. Ezekután a folyamprobléma matematikai megfogalmazása a következő:

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

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

A folyamprobléma tehát a forrásból a nyelőbe irányuló legnagyobb értékű folyam meghatározása. A célfüggvényt a forrásból kifolyó folyam mennyiségeként fogalmaztuk meg, de nyilvánvalóan használhattuk volna a megmaradási törvény miatt a nyelőbe befolyó folyam mennyiséget is. Általában folyam alatt a feltételeknek eleget tevő értékek összességét értjük, de nem követünk el nagy hibát, ha az egyes éleken értelmezett értékeket (folyamkomponenseket) is egyszerűen folyamnak nevezzük. A legnagyobb értékű folyamot maximális folyamnak nevezzük.

Példa a folyamfeladat matematikai megfogalmazására:

Tekintsük az alábbi ábrán látható hálózatot és fogalmazzuk meg az 1-ből a 6-ba irányuló maximális folyam feladatot matematikai formában!

Maximális folyam feladat (Primál feladat)

Legyenek a feladat döntési változói az értékek, amelyek az i pontból a j pontba mutató élen a folyam mennyiségét jelentik. Ezek darabszáma a hálózat éleinek számával azonos, a feladat döntési változói tehát rendre:

A döntési változókra vonatkozó kapacitáskorlátozás azt írja elő, hogy a folyam egyik élen sem lehet negatív és nem lehet nagyobb, mint az él kapacitása, ezek a feltételek a következők:

A közbülső pontokra (nem forrás, nem nyelő) érvényesnek kell lenni a Kirchoff csomóponti törvényének, azaz minden közbülső pontból a kifelé mutató élen a folyamok összegének azonosnak kell lenni a pontba befelé mutató élen lévő folyamok összegével. Négy közbülső pont van, ezekre a feltételek rendre a következők:

A célfüggvény pedig a forráspontból kifolyó folyamok összege, azaz

Mint ahogy látható a folyamprobléma is egy lineáris programozási feladat, amelyet szimplex módszerrel meg tudunk oldani. A megoldáshoz célszerű az egyedi felsőkorlátos szimplex módszert használni, de még így is elég nagyméretű feladatot kell megoldani. A folyamprobléma minden feltételében és a célfüggvényben is 0 és 1 együtthatók szerepelnek, ez a speciális szerkezet indokolja, hogy a hálózaton működő megoldási módszert alkalmazzunk. A folyamproblémának, mint lineáris programozási feladatnak létezik a duál feladata is. A következőkben ezt határozzuk meg. A fenti primál lineáris programozási feladatnak felírjuk a duál feladatát és egy kis transzformáció után azt fogjuk tapasztalni, hogy a duál feladat a vágással hozható kapcsolatba.

A duál feladat egyszerűbb meghatározásához alakítsuk át a folyamfeladatot oly módon, hogy bevezetünk egy v-vel jelölt új változót, amely a folyam értékét jelentse. A feltételek közé vegyük fel a forrásra és a nyelőre vonatkozó előírásokat is, a célfüggvény pedig legyen a v folyamérték, amelynek maximumát keressük. A v változóra elvben nincs előjel megkötés, tudjuk ugyan, hogy a folyam nemnegativitása miatt szükségképpen pozitív, de ezt az előírást nem szerepeltetjük a modellben, mert nem előírás, hanem következmény. A feladat alakja a következő:

A fenti lineáris programozási feladat duál változói legyenek a következők:

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:

Ennek a duál feladatnak minden lehetséges megoldása és az optimális megoldása is megfeleltethető egy (S,T) vágásnak a következő módon. Legyen

Érdemes megfigyelni az átalakított folyamfeladatban a hálózat pontjaira felírt egyenleteket. Az ismeretlenek együtthatóiból képzett mátrix nem más mint a hálózat alapját képező digráf szomszédossági mátrixa. Az egyenlőséges feltételek mátrixos formában tehát így is írhatók:

ahol S a szomszédossági mátrix, az egységvektorok, az x pedig a döntési változókat magába foglaló vektor.

Ezekután a folyamfeladat duál feladata általánosan a következőképpen fogalmazható meg.

A folyamprobléma duál feladata:

Meghatározandó a forrást (s) a nyelőtől (t) elválasztó vágások közül az, amelyben a vágásbeli élekre írt kapacitás értékek összege, azaz a

mennyiség minimális.

A mennyiséget általánosan az vágás kapacitásának vagy a vágás átbocsátóképességének nevezzünk. A legkisebb átbocsátóképességű vágást egyszerűen minimális vágásnak nevezzük. A két szorosan összekapcsolódó feladat (primál – duál) együttesét maximális folyam-minimális vágás feladatpár néven szoktuk emlegetni.

Mielőtt rátérnénk a feladatok matematikai vizsgálatára, röviden szólunk a folyamfeladat megoldásáról. Egy nagyon kézenfekvőnek tűnő algoritmus lehet a következő: Legyen adott egy megengedett folyam, amely lehet az azonosan zérus is. Meghatározzuk minden élen, hogy mekkora az él szabad kapacitása. Egy él szabad kapacitása () alatt az élen még átfolyatható mennyiséget, azaz az mennyiséget értjük. Ha egy él szabad kapacitása zérus, akkor azt az élet telített élnek, ha pedig szabad kapacitása pozitív, akkor azt az élet telítetlen élnek nevezzük. Tekintsük csak a telítetlen éleket és csak ezeken a telítetlen éleken keressünk utat a forrásból a nyelőbe. Ha találtunk utat, akkor ezen út minden élén az élre előírt kapacitáskorlátozás miatt az él szabad kapacitásának megfelelő mértékben a folyam növelhető. Az út minden élén azonban csak egyforma mértékben növelhetjük a folyamot, mert egyébként az új folyam megsértené a csomóponti törvényt. Könnyen belátható, hogy az út szűk keresztmetszete dönti el a növelés maximális mértékét. Tehát meghatározzuk az út mentén a legkisebb szabad kapacitást, amelynél nagyobb mértékben nem javítható a folyam. Mivel a maximális folyam elérése a fő célunk, ezért ezzel a legkisebb szabad kapacitással érdemes növelni a folyamot. Jelöljük ezt a szabad kapacitást -val. A folyamnövelés után az eljárásunkat megismételjük. Tehát az algoritmus egy-egy lépésében három feladatot kell kell elvégeznünk:

  1. Útkeresés s-ből t-be a telítetlen éleken.

  2. Az út mentén a legkisebb szabad kapacitás () meghatározása.

  3. A legkisebb szabad kapacitással az út minden élén növeljük a folyamot.

A gyakorlati kivitelezés során nem érdemes az új folyamot kiszámítani, mivel az (1) és a ( 2) feladatban csupán a szabad kapacitás ismerete szükséges, így a (3) feladatban a folyamnövelés helyett a szabad kapacitásokat csökkentjük az út mentén. Akkor fejezzük be az algoritmust, ha már nem találunk utat. Az elmondottakra nézzünk egy példát. A példával az algoritmusra szeretnénk rámutatni, ezért az útkeresést most nem címkézéssel oldjuk meg.

Példa a kézenfekvő algoritmus bemutatására:

Tekintsük az alábbi hálózatot! Határozzuk meg az s-ből t-be irányuló maximális folyamot!

A probléma egyszerűsége miatt azonnal látható, hogy a maximális folyam értéke 7. Nézzük a megoldást lépésenként. A hálózat szabad kapacitásait a baloldali ábrán (a telített éleket szaggatottan jelöljük), az utat és az út mentén a folyamnövelés mértékét a jobb oldali ábrán tüntetjük fel. Induljunk ki az azonosan zérus folyamból. Ekkor az élek szabad kapacitása megegyezik az él kapacitásával.

1. útkeresés

2. útkeresés

3. útkeresés

4. útkeresés

A 4. útkeresés során nem tudtunk telítetlen éleken a forrásból a nyelőbe eljutni, így az algoritmus befejeződött. Az élek kapacitásának és szabad kapacitásának a különbsége a folyamot adja, amelyet az alábbi hálózaton szemléltetünk.

A fenti hálózatból kiolvasható, hogy a forrásból a nyelőbe vezető folyam értéke 6. E példán tapasztaltuk, hogy a kézenfekvő algoritmusunk nem jól működik, mert maximális folyamra a 7-et kellett volna eredményezni. Ha az útkeresések során először a felső két él által, utána pedig az alsó két él által meghatározott utat találjuk meg, akkor az algoritmus jól működik. Hol lehet a hiba az algoritmusban, amely egyszer működik, egyszer nem? A nem megfelelő működés az algoritmus merevségében van, ugyanis egy élen a folyamot csak növelni tudjuk. Amennyiben lehetőséget adtunk volna arra, hogy ha egy élen már átfolyattunk valamennyit, akkor szükség esetén legfeljebb ennyit vissza is folyathatunk, úgy az algoritmus minden esetben jól működik. Ahhoz, hogy a fenti algoritmust minden esetben sikerrel tudjuk alkalmazni az eredeti folyamfeladatot módosítani kell, természetesen az alapprobléma érintése nélkül.

A folyamprobléma módosítása az alábbiak szerint történik. Egészítsük ki a hálózatot teljes hálózattá. Az eredetileg nem létező éleket is vegyük fel és azok kapacitását zérusnak vegyük. A teljes hálózat élein az folyamra a nemnegativitást elvetjük, helyette a ferdeszimmetricitást írjuk elő, amely az alábbit jelenti:

Ez a matematikai előírás fogja megoldani a gondunkat. Hogy jobban megértsük, számítsuk ki a szabad kapacitásokat. Az élen , a élen pedig . A folyam ferdeszimmetricitása miatt azonban . Tehát ha egy élen a folyam nő, pl. -ről megváltozik -ra, akkor az élen a szabad kapacitás -val csökken. A „visszélen” pedig ugyanannyival, -val nő. Ez fordítva is igaz. A negatív folyam természetesen az optimális megoldásban nem fog érdekelni bennünket, csak a pozitív folyamok lesznek számunkra érdekesek. A módosított folyamra vonatkozó csomóponti törvény a ferdeszimmetricitás miatt úgy fogalmazható meg, hogy a közbülső pontokban a kilépő (vagy belépő) folyamok előjeles összege zérus legyen. A folyam értékét a továbbiakban jelöljük -el, amelynek értéke: . Matematikai értelemben folyamfeladat alatt a továbbiakban mindig e módosított folyamfeladatot értjük, amelynek matematikai megfogalmazása a következő:

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

maximális legyen, feltéve, hogy

Nem nehéz kitalálni, hogy a duál feladat változatlan marad, csupán a teljes hálózatra vonatkozóan kell a minimális vágást keresni.

Mielőtt belekezdenénk a vizsgálatokba, bevezetünk néhány jelölést .

Legyen részhalmazok és az éleken értelmezett függvény (folyam esetén: vagy kapacitás esetén: ), továbbá jelölje az alábbi mennyiséget:

Könnyen ellenőrizhető, hogy fennállnak az alábbi addíciós összefüggések:

Ezen addíciós összefüggések figyelembevételével a folyamfeladatra felírt korlátozottsági előírások az

alakban, míg a ferdeszimmetricitási előírások az

alakban írhatók. A folyamfeladat megfogalmazására a fenti jelölésmód természetes, ugyanis az értéke a B ponthalmaz pontjaiból a C ponthalmaz pontjaiba irányuló folyam értékét, a értéke pedig a B ponthalmaz pontjaiból a C ponthalmaz pontjaiba irányuló élek teljes átbocsátóképessége.

A fentebb bevezetett jelölések alapján legyen:

amelyet az pontból kilépő folyamok összegének nevezünk. Az pont a folyamra nézve akkor forrás, ha , a pont pedig akkor nyelő, ha .

Az teljes hálózat egy folyamát s-ből t-be irányuló folyamnak nevezzük, ha , és minden (közbülső pont) esetén . Szemléletesen nyilvánvaló, de algebrailag is könnyen igazolható, hogy az s-ből t-be irányuló folyam esetén

az feltételből ugyanis levezethető, hogy

ebből pedig

Az hálózat s-ből t-be irányuló folyamánál az számot a folyam értékének nevezzük. A legnagyobb értékű folyamot maximális folyamnak nevezzük.

Ezekután a maximális folyam feladat a következő módon fogalmazható meg matematikai formában.

Maximális folyam feladat ( primál feladat ):

Meghatározandó a teljes hálózaton az s-ből t-be irányuló folyam úgy, hogy a folyam értéke az

maximális legyen, feltéve, hogy

Minimális vágás feladat ( duál feladat ):

Meghatározandó az s-et t-től elválasztó vágás úgy, hogy a vágás átbocsátó képessége a

minimális legyen.