Rendszeroptimalizálás, 7. tétel

Ez az oldal a korábbi SCH wiki-ről lett áthozva. Az eredeti változata itt érhető el.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor kérlek javíts rajta egy rövid szerkesztéssel.

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót

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

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 ⇔ π(v)≤π(u)+w(e),
• π(t)-π(s)≥1 ⇔ π(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 (m_DLP) megegyezik a minimális vágás (m_C) értékével.
  
• Biz*:

1. m_DLP ≤ m_C: 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 m_DLP ≤ ∑w(e)c(e) = m_C.
2. m_DLP ≥ m_C: 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) ⇒ ∑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 m_C ≤ ∑w'(e)c(e) = ∑w(e)c(e) = m_DLP.

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.

-- Peti - 2007.01.01.