Predavanje 29.3.
Problem razvoza z omejitvami
Imamo usmerjen utežen graf $G = (V, E)$, kjer je $V$ množica vozlišč in $E$ množica usmerjenih povezav, ter uteži na vozliščih $b_v \in \mathbb{R}$ ($v \in V$), tako da velja $\sum_{v \in V} b_v = 0$, uteži na povezavah $c_{uv} \in \mathbb{R}$ ($uv \in E$), in omejitve na povezavah $d_{uv} \in [0, \infty]$ ($uv \in E$).
Problem lahko zapišemo kot linearni program $$ \begin{aligned} \min \ c^\top x \\[1ex] \text{p.p.} \quad A x &= b \\ 0 \le x &\le d, \end{aligned} $$ kjer je $A \in \mathbb{R}^{V \times E}$ incidenčna matrika grafa $G$.
Uporabili bomo podoben algoritem kot pri problemu razvoza.
Definicija. Naj bo $x$ dopustna rešitev problema razvoza z omejitvami. Potem je (pri rešitvi $x$) povezava $e \in E$ prazna, če velja $x_e = 0$, in nasičena, če velja $x_e = d_e < \infty$.
Definicija. Naj bo $x$ dopustna rešitev problema razvoza z omejitvami. Rešitev $x$ je drevesna dopustna rešitev, če obstaja vpeto drevo $T = (V, E')$ v grafu $G = (V, E)$, da velja $\forall e \in E \setminus E': (x_e = 0 \lor x_e = d_e)$ (torej, povezave izven drevesa so prazne ali nasičene).
Trditev. Naj bo $x$ drevesna dopustna rešitev problema razvoza z omejitvami za vpeto drevo $T = (V, E')$ v grafu $G = (V, E)$ ter $y$ razvozne cene (tj., $\forall uv \in E': y_u + c_{uv} = y_v$). Če za vsako povezavo $uv \in E \setminus E'$ velja $$ (x_{uv} = 0 \land y_u + c_{uv} \ge y_v) \lor (x_{uv} = d_{uv} \land y_u + c_{uv} \le y_v), $$ potem je $x$ optimalna rešitev.
Dokaz. Naj bo $x'$ dopustna rešitev problema razvoza z omejitvami. Potem velja $$ \forall uv \in E: \ (y_u + c_{uv} - y_v) x_{uv}' \ge (y_u + c_{uv} - y_v) x_{uv}, $$ saj
- če $uv \in E'$, potem $y_u + c_{uv} - y_v = 0$,
- če $uv \not\in E'$ in $x_{uv} = 0$, potem $(y_u + c_{uv} - y_v) x_{uv}' \ge 0$, in
- če $uv \not\in E'$ in $x_{uv} = d_{uv}$, potem $x_{uv}' \le x_{uv}$ in $y_u + c_{uv} - y_v \le 0$.
Če seštejemo za vse povezave, dobimo $$ \begin{alignedat}{2} \sum_{uv \in E} c_{uv} x_{uv}' - \sum_{uv \in E} (y_v - y_u) x_{uv}' &= c^\top x' - (A^\top y)^\top x' &&= c^\top x' - y^\top A x' &&= c^\top x' - y^\top b \\ \sum_{uv \in E} c_{uv} x_{uv} - \sum_{uv \in E} (y_v - y_u) x_{uv} &= c^\top x - (A^\top y)^\top x &&= c^\top x - y^\top A x &&= c^\top x - y^\top b \end{alignedat} $$ Velja torej $c^\top x' \ge c^\top x$.
Simpleksna metoda na omrežjih za problem razvoza z omejitvami.
- Začnemo z neko drevesno dopustno rešitvijo $x$ na vpetem drevesu $T = (V, E')$: $x_e = 0$ ali $x_e = d_e$ za vsako povezavo $e \in E \setminus E'$.
- Rešimo sistem $\forall uv \in E': \ y_u + c_{uv} = y_v$ (tj., poiščemo razvozne cene).
- Preverimo, ali za vsako povezavo $uv \in E \setminus E'$ velja $x_{uv} = 0$ in $y_u + c_{uv} \ge y_v$ oziroma $x_{uv} = d_{uv}$ in $y_u + c_{uv} \le y_v$. Če velja, je $x$ optimalna rešitev (po dualnem dopolnjevanju).
- Sicer obstaja povezava $e = uv \in E \setminus E'$ (vstopna povezava - v edinem ciklu $C$ v grafu $H = (V, E' \cup \{e\})$), za katero velja:
- $x_{uv} = 0$ in $y_u + c_e < y_v$: nastavimo $p = \min(\{x_f \mid f \in C \text{ obratna}\} \cup \{d_f - x_f \mid f \in C \text{ prema}\})$ ter premim povezavam povečamo razvoz za $p$, obratnim pa zmanjšamo za $p$; ali
- $x_{uv} = d_{uv}$ in $y_u + c_e > y_v$: nastavimo $p = \min(\{x_f \mid f \in C \text{ prema}\} \cup \{d_f - x_f \mid f \in C \text{ obratna}\})$ ter premim povezavam zmanjšamo razvoz za $p$, obratnim pa povečamo za $p$.
- Naj bo $f$ povezava v $C$, za katero je dosežena vrednost $p$ (izstopna povezava). V novi rešitvi je $f$ prazna ali nasičena in jo odstranimo iz drevesa.
- Če je $p = \infty$, potem je problem neomejen.
- Ponavljamo, dokler ne pridemo do optimalne rešitve (ali ugotovimo, da je problem neomejen).
Primer.
digraph G {
rankdir=LR
nodesep=0.5
ranksep=1
edge [fontcolor=red,labelfontcolor=black]
a [label=-8, xlabel=<<font color="blue">0</font>>]
b [label=2, xlabel=<<font color="blue">3</font>>]
c [label=3, xlabel=<<font color="blue"> 1</font>>]
d [label=3, xlabel=<<font color="blue">7</font>>]
a -> b [taillabel=3, label=<8 <font color="black">≤ 9</font>>, color=red, constraint=false]
a -> c [taillabel=1, label=<0 <font color="black">≤ 2</font>>, color=red, style=dashed, xlabel=<<font color="blue">f</font>>]
b -> c [taillabel=2, label=<3 <font color="black">≤ 3</font>>, style=bold, color=blue, xlabel=<<font color="blue"> e </font><br></br> 3+2 > 1>, fontcolor=black]
b -> d [taillabel=4, label=<3 <font color="black">≤ 4</font>>, color=red]
c -> d [taillabel=1, label=<<font color="black"> ≤ 5</font>>, xlabel="\n1+1 < 7\n ", color=green, fontcolor=black, constraint=false]
}
Ker vstopi nasičena povezava, imamo $p = \min\{3, 2-0, 8\} = 2$. Izstopna povezava je obratna, tako da bomo na njej povečali razvoz na $2$ in jo tako zasitili.
digraph G {
rankdir=LR
nodesep=0.5
ranksep=1
edge [fontcolor=red,labelfontcolor=black]
a [label=-8, xlabel=<<font color="blue">0</font>>]
b [label=2, xlabel=<<font color="blue">3</font>>]
c [label=3, xlabel=<<font color="blue"> 5</font>>]
d [label=3, xlabel=<<font color="blue">7</font>>]
a -> b [taillabel=3, label=<6 <font color="black">≤ 9</font>>, color=red, constraint=false]
a -> c [taillabel=1, label=<2 <font color="black">≤ 2</font>>, style=bold]
b -> c [taillabel=2, label=<1 <font color="black">≤ 3</font>>, color=red, style=dashed, xlabel=<<font color="blue">f</font>>]
b -> d [taillabel=4, label=<3 <font color="black">≤ 4</font>>, color=red]
c -> d [taillabel=1, label=<<font color="black"> ≤ 5</font>>, xlabel=<<font color="blue">e</font><br></br> 5+1 < 7>, color=blue, fontcolor=black, constraint=false]
}
Ker vstopi prazna povezava, imamo $p = \min\{5-0, 3, 3-1\} = 2$. Izstopna povezava je prema, tako da bomo na njej povečali razvoz na $2$ in jo tako zasitili.
digraph G {
rankdir=LR
nodesep=0.5
ranksep=1
edge [fontcolor=red,labelfontcolor=black]
a [label=-8, xlabel=<<font color="blue">0</font>>]
b [label=2, xlabel=<<font color="blue">3</font>>]
c [label=3, xlabel=<<font color="blue"> 6</font>>]
d [label=3, xlabel=<<font color="blue">7</font>>]
a -> b [taillabel=3, label=<6 <font color="black">≤ 9</font>>, color=red, constraint=false]
a -> c [taillabel=1, label=<2 <font color="black">≤ 2</font>>, style=bold, xlabel="0+1 < 6 ", fontcolor=black]
b -> c [taillabel=2, label=<3 <font color="black">≤ 3</font>>, style=bold, xlabel="3+2 < 6 ", fontcolor=black]
b -> d [taillabel=4, label=<1 <font color="black">≤ 4</font>>, color=red]
c -> d [taillabel=1, label=<2 <font color="black">≤ 5</font>>, color=red, constraint=false]
}
Ni več kandidatov za vstop - dobili smo optimalno rešitev s ceno $$ \sum_{e \in E} c_e x_e = 3 \cdot 6 + 1 \cdot 2 + 2 \cdot 3 + 4 \cdot 1 + 1 \cdot 2 = 32 $$
Opomba. Lahko se zgodi, da je $e = f$, torej je ista povezava tako vstopna kot izstopna. Tedaj preide iz prazne v nasičeno povezavo ali obratno.
digraph G {
rankdir=LR
nodesep=0.5
ranksep=1
edge [fontcolor=red]
node [label=""]
a -> b [label=<2 <font color="black">≤ 3</font>>, color=red]
a -> c [label=<<font color="black">≤ 1</font>>, xlabel=<<font color="blue">e = f</font>>, color=blue, style=dashed]
c -> b [label=<1 <font color="black">≤ 5</font>>, color=red, constraint=false]
}
Ker vstopi prazna povezava, imamo $p = \min\{1-0, 5-1, 2\} = 1$. Imamo $e = f$, izstopna povezava je prema in jo tako zasitimo.
digraph G {
rankdir=LR
nodesep=0.5
ranksep=1
edge [fontcolor=red]
node [label=""]
a -> b [label=<1 <font color="black">≤ 3</font>>, color=red]
a -> c [label=<1 <font color="black">≤ 1</font>>, style=bold]
c -> b [label=<2 <font color="black">≤ 5</font>>, color=red, constraint=false]
}
Opomba. Cunninghamovo pravilo (preprečuje "ciklanje"):
- izberemo koren $r \in V$;
- ko izbiramo izstopno povezavo v ciklu $C$ z vstopno povezavo $e = uv$, določimo vozlišče $z$ na $C$, ki leži na poteh (v drevesu - brez $e$) od $r$ do $u$ oziroma $v$, in za izstopno povezavo izberemo prvega (zadnjega) kandidata na $C$ od $z$ naprej v smeri $uv$, če je ta prazna (nasičena).
Kako poiščemo začetno drevesno dopustno rešitev oziroma dokažemo, da je problem nedopusten? Uporabimo dvofazno simpleksno metodo na omrežjih za problem razvoza z omejitvami. Definiramo pomožni problem:
- Izberemo koren $r \in V$.
- Za vsako vozlišče $v \in V \setminus \{r\}$:
- če $b_v \ge 0$ in povezava $rv$ ne obstaja, jo dodamo; če obstaja in $d_{rv} < b_v$, dodamo še eno tako povezavo;
- če $b_v < 0$ in povezava $vr$ ne obstaja, jo dodamo; če obstaja in $d_{vr} < -b_v$, dodamo še eno tako povezavo.
- Dobimo nov graf $\tilde{G} = (V, \tilde{E})$. Dodanim povezavam (iz $\tilde{E} \setminus E$) pravimo umetne povezave, povezavam iz $E$ pa prvotne povezave.
- Definiramo nove cene $\tilde{c}$, in sicer
- prvotne povezave $e \in E$ imajo ceno $\tilde{c}_e = 0$, in
- umetne povezave $e \in \tilde{E} \setminus E$ imajo ceno $\tilde{c}_e = 1$.
- Definiramo nove omejitve $\tilde{d}$:
- prvotne povezave $e \in E$ imajo nespremenjene omejitve $\tilde{d}_e = d_e$, in
- umetne povezave $e \in \tilde{E} \setminus E$ niso omejene: $\tilde{d}_e = \infty$.
Pomožni problem je optimalen, optimalna vrednost je $0$ natanko tedaj, ko je prvotni problem dopusten.