Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel7}} ==!! A lineáris és egészértékű programozás alkalmazása hálózati folyamproblémákra.== TOC ===Maximális folyam…”

2012-10-22T09:44:39Z

Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel7}} ==!! A lineáris és egészértékű programozás alkalmazása hálózati folyamproblémákra.== __TOC__ ===Maximális folyam…”

Új lap

{{GlobalTemplate|Infoszak|RopiTetel7}}

==!! A lineáris és egészértékű programozás alkalmazása hálózati folyamproblémákra.==

__TOC__

===Maximális folyam felírása LP problémaként===

*Def*: δf(v) = v csúcsból kimenő folyam 
*Def*: ρf(v) = v csúcsba bemenő folyam 
*Def*: f(e) = az e élen átmenő folyam 
*Def*: c(e) = e él kapacitása 
*Def*: s a forrás, t a nyelő

* ∀v≠s,t: δf(v) ≤ ρf(v)
* δf(s) ≤ ρf(t)
* ∀e: 0 ≤ f(e) ≤ c(e)
* folyam értéke = (e* = t→s) pszeudoélen átmenő folyam

A δf ≤ ρf és az f(e) ≤ c(e) típusú egyenlőtlenségeket a következőképpen tudjuk felírni (B az illeszkedési mátrix, B* az e* éllel kiegészített gráf illeszkedési mátrixa és E az egységmátrix):

<math> \begin{array}{c} \\ \\ s \\ t \\ \\ \\ \\ \end{array} \overbrace{\begin{array}{|@{\hspace{1.5em}}c@{\hspace{1.5em}}|c|} \hline & \\ B & \\ & -1 \\ & 1 \\ \hline & \\ E & 0 \\ & \\ \hline \end{array}}^{B^*} \;\;\; \left. \begin{array}{|c|} \hline \\ x \\ \\ \hline \mu \\ \hline \end{array} \right\} x^* \le \begin{array}{|c|} \hline \\ 0 \\ \\ \\ \hline \\ c \\ \\ \hline \end{array} </math>

===Potenciál fogalma===

Jelöljük a fenti mátrixot M-mel. A max{(0,...,0,1)x*: Mx*=(0;...;0;c), x*≥0} feladat duálisa min{(y(0;...;0;c): yM≥(0,...,0,1), y≥0}. Az y vektort bontsuk szét két részre:

<math> y= \begin{array}{|@{\hspace{1.5em}}c@{\hspace{1.5em}}|@{\hspace{1.5em}}c@{\hspace{1.5em}}|} \hline \pi(v) & w(e) \\ \hline \end{array} </math>

A duális feladat az új jelölésekkel:
* ∀e=u→v: π(u)-π(v)+w(e)≥0 <big>⇔</big> π(v)≤π(u)+w(e),
* π(t)-π(s)≥1 <big>⇔</big> π(t)≥π(s)+1,
* π≥0, w≥0
* keressük ∑w(e)c(e) minimumát.
ahol a π(v) függvényt a csúcs potenciáljának hívjuk, w(e) pedig a szállítás költsége az e élen.

===Duális feladat megoldása és minimális vágás===

*Tétel*: a duális feladat minimuma (mDLP) megegyezik a minimális vágás (mC) értékével. 
*Biz*:
<ol style="margin-top:0px">
<li> mDLP ≤ mC: Egy s-t vágás S és T diszjunkt részhalmazokra osztja V-t. Legyen w=1 a vágás éleire, 0 a többi élre, π pedig 0 az S-beli csúcsokra és 1 a T-beli csúcsokra. Ekkor w és π kielégítik a duális feladat egyenlőtlenségeit, tehát mDLP ≤ ∑w(e)c(e) = mC.
<li> mDLP ≥ mC: legyen w,π a DLP feladat optimális megoldása. Mivel a feladat mátrixa totálisan unimoduláris és az LP feladat célfüggvénye egész együtthatós, a TU alaptétel szerint w és π választható egészértékűnek.

Vezessük be a következő két mennyiséget:

<math> \pi'(v) = \left\{ \begin{array}{l} \mbox{0, ha $\pi(v)\le\pi(s)$} \\ \mbox{1 egy\'ebk\'ent} \end{array} \right. \quad w'(e) = \left\{ \begin{array}{l} \mbox{0, ha $w(e)=0$} \\ \mbox{1 egy\'ebk\'ent} \end{array} \right. </math>

*Áll*: (π', w') megoldása a DLP feladatnak. 
*Biz*:
* π'(t)≥π'(s)+1 igaz, mert π'(t)=1 és π'(s)=0.
* π'(v)≤π'(u)+w(e) feltétel csak akkor sérülhet, ha π'(v)=1 és π'(u)=w(e)=0. Az egészértékűség miatt ∀e w'(e)≤w(e) <big>⇒</big> ∑w'(e)c(e)≤∑w(e)c(e), de mivel ∑w(e)c(e) minimális volt, ezért egyenlők. Azaz a duális minimuma nem változik, ha feltesszük, hogy π és w csak 0-t vagy 1-et vehetnek fel.

Legyen S azoknak a csúcsoknak a halmaza, amire π(v)=0 és T, amire π(v)=1. Egy S→T irányú e élre w'(e)≥π(v)-π(u), azaz w'(e) csak 1 lehet. A többi pozitív kapacitású élre w'(e)=0, különben w'(e) 1-ről 0-ra csökkentésével ∑w'(e)c(e) is csökkenne, azaz eredetileg nem volt optimális. w' tehát egy vágás éleinek az indikátora. Ezzel megmutattuk, hogy mC ≤ ∑w'(e)c(e) = ∑w(e)c(e) = mDLP.
</ol>

===Következmények===

* Beláttuk a Ford-Fulkerson tételt (maximális folyam értéke = a minimális vágás értéke).
* Beláttuk, hogy ha minden kapacitás egész, akkor a maximális folyam is választható egészértékűnek.
* A minimális költségű folyam probléma is könnyen megfogalmazható LP feladatként, és egész élkapacitások mellett a kapott folyam is egész lesz.
* A többtermékes folyam szintén LP feladat, de a mátrixa nem TU, az egész többtermékes probléma már NP-nehéz.

-- [[PallosPeter|Peti]] - 2007.01.01.

[[Category:Infoszak]]

Rendszeroptimalizálás, 7. tétel - Laptörténet

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel7}} ==!! A lineáris és egészértékű programozás alkalmazása hálózati folyamproblémákra.== __TOC__ ===Maximális folyam…”

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel7}} ==!! A lineáris és egészértékű programozás alkalmazása hálózati folyamproblémákra.== TOC ===Maximális folyam…”