Rendszeroptimalizálás, 7. tétel

A VIK Wikiből

Ez az oldal a korábbi SCH wikiről lett áthozva.

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):

Értelmezés sikertelen (ismeretlen „\begin{array}” függvény): {\displaystyle \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} }

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:

Értelmezés sikertelen (ismeretlen „\begin{array}” függvény): {\displaystyle 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} }

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 (mDLP) megegyezik a minimális vágás (mC) értékével.
  • Biz*:
  1. 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.
  2. 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: Értelmezés sikertelen (ismeretlen „\begin{array}” függvény): {\displaystyle \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. }
    • Á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 mC ≤ ∑w'(e)c(e) = ∑w(e)c(e) = mDLP.

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.