Predavanje 15.3.
V našem primeru: $$ \min \ x_{ab} + 3 x_{ac} + x_{bc} + 6 x_{cb} \\[1ex] \begin{aligned} \text{p.p.} && -x_{ab} - x_{ac} &= -7 \\ && x_{ab} + x_{cb} - x_{bc} &= 4 \\ && x_{ac} + x_{bc} - x_{cb} &= 3 \\ && x_{ab}, x_{ac}, x_{bc}, x_{cb} &\ge 0 \end{aligned} $$
To je linearni program, lahko ga rešimo z dvofazno simpleksno metodo. Spoznali bomo prilagojen algoritem: simpleksna metoda na omrežjih.
Naj bo $A \in \mathbb{R}^{V \times E}$ incidenčna matrika usmerjenega grafa $G = (V, E)$, tj., $A = (a_{ve})_{v \in V, e \in E}$, kjer je $$ a_{ve} = \begin{cases} 1 & \operatorname{konec}(e) = v, \\ -1 & \operatorname{začetek}(e) = v, \text{in} \\ 0 & \text{sicer,} \end{cases} $$ ter $b \in \mathbb{R}^V$ in $c \in \mathbb{R}^E$ vektorja uteži vozlišč in povezav. Potem lahko problem razvoza $\Pi$ zapišemo kot $$ \begin{aligned} \min \ c^\top x \\[1ex] \text{p.p.} \quad A x &= b \\ x &\ge 0 \end{aligned} $$ ali ekvivalentno kot $$ \begin{aligned} \max \ -c^\top x \\[1ex] \text{p.p.} \quad -A x &= -b \\ x &\ge 0 \end{aligned} $$
Dual $\Pi'$ problema razvoza $\Pi$ je potem $$ \min \ -b^\top y \\[1ex] \text{p.p.} \quad -A^\top y \ge -c $$ in ga ekvivalentno lahko zapišemo kot $$ \max \ b^\top y \\[1ex] \text{p.p.} \quad A^\top y \le c $$ Ker ima matrika $A$ vrednosti v stolpcu, ki ustreza povezavi $uv$, vrednosti $-1$ in $1$ v vrsticah, ki ustrezata vozliščema $u$ oziroma $v$, in $0$ drugod, lahko dual problema razvoza zapišemo tudi kot $$ \max \ \sum_{v \in V} b_v y_v \\[1ex] \text{p.p.} \quad \forall uv \in E: \ y_u + c_{uv} \ge y_v $$
Opazimo, da če je $y$ dopustna (optimalna) rešitev $\Pi'$, potem je tudi $y + \epsilon$ ($\epsilon \in \mathbb{R}$) dopustna (optimalna) rešitev $\Pi'$, saj velja $$ \sum_{v \in V} b_v (y_v + \epsilon) = \sum_{v \in V} b_v y_v + \epsilon \sum_{v \in V} b_v = \sum_{v \in V} b_v y_v. $$
Vemo tudi (dualno dopolnjevanje): če sta $x$ in $y$ dopustni rešitvi za $\Pi$ oziroma $\Pi'$, potem sta $x, y$ tudi optimalni natanko tedaj, ko velja $$ \forall uv \in E: \ (x_{uv} = 0 \ \lor \ y_u + c_{uv} = y_v) $$
Rešitev 1 je dopustna, ni pa optimalna: $$ \begin{aligned} y_a &= 0 \\ y_b = y_a + 1 &= 1 \\ y_c = y_a + 3 &= 3 \\ y_b + 1 &\not\ge y_c \\ y_c + 6 &\ge y_b \end{aligned} $$
Rešitev 2 je dopustna in tudi optimalna: $$ \begin{aligned} y_a &= 0 \\ y_b = y_a + 1 &= 1 \\ y_c = y_b + 1 &= 2 \\ y_a + 3 &\ge y_c \\ y_c + 6 &\ge y_b \end{aligned} $$
Kdaj je sistem $\forall uv \in E: \ y_u + c_{uv} = y_v$ rešljiv?
digraph G {
rankdir=LR
nodesep=0.5
ranksep=1
node [label=""]
a [xlabel=a]
b [xlabel=b]
c [xlabel=c]
a -> b [taillabel=" 2\n\n", tailport=ne]
a -> c [taillabel="\n 1", tailport=se]
b -> c [headlabel=" 5", label=" ", tailport=se, constraint=false]
}
$$ \begin{aligned} y_a &= 0 \\ y_b = y_a + 2 &= 2 \\ y_c = y_a + 1 &= 1 \\ y_c \ne y_b + 5 &= 7 \end{aligned} $$
digraph G {
rankdir=LR
nodesep=0.5
ranksep=1
node [label=""]
a [xlabel=a]
b [xlabel=b]
c [xlabel=c]
d [xlabel=d]
e [xlabel=e]
f [xlabel=f]
a -> c [taillabel=5]
b -> c [taillabel=1]
c -> e [taillabel=2]
d -> e [taillabel=-3]
e -> f [taillabel=4]
}
$$ \begin{alignedat}{3} &&&& y_a &= 0 \\ && y_c &=& y_a + 5 &= 5 \\ y_c &= y_b + 1 &&\Rightarrow&\ y_b &= 4 \\ && y_e &=& y_c + 2 &= 7 \\ y_e &= y_d + (-3) &&\Rightarrow&\ y_d &= 10 \\ && y_f &=& y_e + 4 &= 11 \end{alignedat} $$
Problem so cikli! Tak sistem enačb je vedno rešljiv na drevesu (tj., povezanem grafu brez ciklov). V drevesu je med vsakima vozliščema natanko ena pot.
Definicija. $x$ je drevesna dopustna rešitev za problem razvoza $\Pi$ na grafu $G = (V, E)$, če v njem obstaja vpeto drevo $T = (V, E')$, da velja $x_e = 0$ za vsak $e \in E \setminus E'$.
digraph G {
rankdir=LR
nodesep=0.5
ranksep=1
edge [fontcolor=red]
node [label=""]
a [xlabel=a]
b [xlabel=b]
c [xlabel=c]
d [xlabel=d]
e [xlabel=e]
f [xlabel=f]
a -> b [color=red]
a -> c [label=0]
b -> c [label=0, constraint=false]
d -> b [color=red, constraint=false]
c -> d [color=red]
c -> e [color=red]
d -> e [label=0, constraint=false]
d -> f [label=0]
f -> d [color=red, constraint=false]
f -> e [label=0, constraint=false, tailport=s]
}
Trditev. Če ima problem razvoza $\Pi$ dopustno rešitev, ima tudi drevesno dopustno rešitev.
Definicija. Naj bo $G$ usmerjen graf in $C$ cikel v $G$, ki vsebuje povezavo $f$. Potem je povezava $e$ v ciklu $C$ (glede na povezavo $f$) prema, če kaže v isto smer kot $f$, in obratna sicer.
digraph G {
rankdir=LR
nodesep=0.5
ranksep=1
node [label=""]
a -> b [label=obratna]
a -> c [label=prema]
d -> b [label=prema,constraint=false]
c -> d [style=invis]
c -> e [color=red,label=f,fontcolor=red]
d -> e [label="obratna ",constraint=false]
}
Dokaz. Naj bo $x$ dopustna rešitev za problem razvoza $\Pi$ na grafu $G = (V, E)$. Naj bo $E^{(0)} = E$ in $x^{(0)} = x$. Definirali bomo zaporedje ${(E^{(i)}, x^{(i)})}_{i=0}^k$, tako da v $i$-tem koraku dobimo $E^{(i)}$ tako, da iz $E^{(i-1)}$ odstranimo eno povezavo in določimo novo dopustno rešitev $x^{(i)}$ tako, da velja $x_e^{(i)} = 0$ za vsako povezavo $e \in E \setminus E^{(i)}$, dokler ne dobimo vpetega drevesa $T = (V, E^{(k)})$.
Denimo, da ima graf $G^{(i-1)} = (V, E^{(i-1)})$ cikel $C$, in naj bo $f$ povezava na $C$ z najmanjšo vrednostjo $x_f^{(i-1)}$. Določimo novo dopustno rešitev $$ x_e^{(i)} = \begin{cases} x_e^{(i-1)} - x_f^{(i-1)} & \text{$e$ prema v $C$ glede na $f$,} \\ x_e^{(i-1)} + x_f^{(i-1)} & \text{$e$ obratna v $C$ glede na $f$,} \\ x_e^{(i-1)} & \text{sicer} \end{cases} $$ in novo množico povezav $E^{(i)} = E^{(i-1)} \setminus \{f\}$. Opazimo, da velja $x^{(i)} \ge 0$, $x_f^{(i)} = 0$ in $x_e^{(i)} = 0$ za vsako povezavo $e \in E \setminus E^{(i-1)}$, torej rešitev ustreza pogojem in je dopustna, saj še vedno velja Kirchhoffov zakon:
digraph G {
rankdir=TD
node [label=""]
xu [style=invis]
x [style=invis]
xd [style=invis]
au [style=invis]
ad [style=invis]
bu [style=invis]
bd [style=invis]
cu [style=invis]
cd [style=invis]
du [style=invis]
dd [style=invis]
xu -> x -> xd [style=invis]
xd -> xu [constraint=false]
au -> a -> ad [label=" +p"]
bu -> b -> bd [style=invis]
bd -> b -> bu [label=" -p", constraint=false]
cu -> c [label=" +p"]
c -> cd [style=invis]
cd -> c [label=" -p", constraint=false]
du -> d [style=invis]
d -> du [label=" -p", constraint=false]
d -> dd [label=" +p"]
}
Primer.
digraph G {
rankdir=LR
nodesep=0.5
ranksep=1
edge [fontcolor=red]
node [label=""]
a -> b [label=<<font color="black"><s>6</s></font>>, xlabel=7]
a -> c [label=<<font color="black"><s>3</s></font>>, xlabel=2]
d -> b [label=<<font color="black"><s>5</s></font>>, xlabel=4, constraint=false]
c -> d [style=invis]
c -> e [label=<<font color="black"><s>1</s></font>>, xlabel=0, color=red]
d -> e [label=<<font color="black"><s>4</s></font>>, xlabel=" 5", constraint=false]
}
Opomba. Drevo določa dopustno rešitev, če ta obstaja. Naj bo $u$ list v drevesu $T$ in $e$ povezava v $T$ s krajiščem $u$. Potem je $x_e$ enolično določen. Postopek ponovimo za drevo $T - u$, dokler imamo še kakšno povezavo.
digraph G {
rankdir=LR
nodesep=0.5
ranksep=1
edge [fontcolor=red,labelfontcolor=black]
a [label=-3,xlabel=a]
b [label=-5,xlabel=b]
c [label="",xlabel=c]
d [label=-2,xlabel=d]
e [label=6,xlabel=e]
f [label=4,xlabel=f]
a -> c [taillabel=5, label=3]
b -> c [taillabel=1, label=5]
c -> e [taillabel=2, label=8]
d -> e [taillabel=-3, label=2]
e -> f [taillabel=4, label=4]
}
Simpleksna metoda na omrežjih.
- Začnemo z neko drevesno dopustno rešitvijo $x$ (jo uganemo; kasneje sistematično) na vpetem drevesu $T = (V, E')$: $x_e = 0$ za vsako povezavo $e \in E \setminus E'$.
- Rešimo sistem $\forall uv \in E': \ y_u + c_{uv} = y_v$ (vrednosti $y_v$, $v \in V$ so razvozne cene).
- Preverimo, ali velja $y_u + c_{uv} \ge y_v$ za vsako povezavo $uv \in E \setminus E'$. Če velja, je $x$ optimalna rešitev (po dualnem dopolnjevanju).
- Sicer obstaja povezava $e = uv \in E \setminus E'$, za katero velja $y_u + c_e < y_v$. Ta povezava (vstopna povezava) je v natanko enem (edinem) ciklu $C$ v grafu $H = (V, E' \cup \{e\})$. Naj bo $f$ obratna povezava v $C$ glede na $e$ z najmanjšo vrednostjo $x_f$ (izstopna povezava). Razvoz povečamo za $x_f$ na premih povezavah na $C$ glede na $e$ (obratnih glede na $f$) in zmanjšamo za $x_f$ na obratnih povezavah na $C$ glede na $e$ (premih glede na $f$). V novi rešitvi ima povezava $f$ ničeln razvoz in jo odstranimo iz drevesa.
- Če obratne povezave na $C$ ni, potem je problem neomejen.
- Ponavljamo, dokler ne pridemo do optimalne rešitve (ali ugotovimo, da je problem neomejen).