Rendszeroptimalizálás, 7. tétel

A VIK Wikiből
A lap korábbi változatát látod, amilyen (vitalap) 2012. október 22., 11:44-kor történt szerkesztése után volt. (Ú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…”)
(eltér) ← Régebbi változat | Aktuális változat (eltér) | Újabb változat→ (eltér)
Ugrás a navigációhoz Ugrás a kereséshez

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 (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: [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 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.