Optimizacijske metode, 1. del

--- tags: om --- # Optimizacijske metode, 1. del 1. del \| [2. del](https://hackmd.io/@jaanos/By-Edfw75) --- ## Optimizacijski problemi **_Primer._** Od doma do fakultete iščemo pot, ki je * najkrajša * najhitrejša * najcenejša * najbolj udobna * ... **_Definicija._** _Optimizacijski problem_ je trojica $(\Omega, f, \operatorname{opt})$, kjer je * $\Omega$ ... množica dopustnih (angl. _feasible_) rešitev * $f : \Omega \to \mathbb{R}$ ... ciljna (kriterijska) funkcija * $\operatorname{opt} \in \{\min, \max, \inf, \sup\}$ ... tip ekstrema Če velja $\Omega = \emptyset$, je problem _nedopusten_, sicer pa je _dopusten_. --- ### Primeri 1. * $\Omega = [0, 3]$ * $f(x) = x^2 - 3x + 2$ * $\operatorname{opt} = \max$ Metoda reševanja: kandidati za maksimum so ničle odvoda in krajišča dopustnega intervala. Pišemo: $$ \begin{aligned} \max &\quad x^2 - 3x + 2 \\[1ex] \text{p.p.} &\quad 0 \le x \le 3 \end{aligned} $$ * p.p. ... pri pogojih * angl. _s.t._ (_subject to_, tudi _so that_, _such that_) ---- 2. * $\Omega = [0, 2] \times [0, 3]$ * $f(x, y) = x^2 - y^2$ * $\operatorname{opt} = \min$ Metoda reševanja: kandidati za minimum so ničle parcialnih odvodov in rob dopustnega območja. --- **_Definicija._** _Optimalna rešitev_ $(\Omega, f, \max)$ je $x^\ast \in \Omega$, da velja $\forall x \in \Omega: f(x) \le f(x^\ast)$. Vrednosti $f(x^\ast)$ pravimo _optimalna vrednost_. * Podobno, če $\operatorname{opt} = \min$. **Pozor!** ~~"bolj optimalna rešitev"~~ --- 3. Na kmetiji velikosti 50 ha želimo gojiti pšenico, koruzo in krompir. Na voljo imamo 5000 človek-ur dela in 24000 € kapitala ter sledeče podatke | | delo (človek-ur/ha) | stroški (€/ha) | dobiček (€/ha) | | ------- | ------------------- | -------------- | -------------- | | pšenica | 60 | 240 | 400 | | koruza | 80 | 400 | 600 | | krompir | 100 | 320 | 480 | Koliko ha posameznega pridelka naj posadimo, da bo dobiček čim večji? $$ \begin{aligned} \max &\ & 400 x_1 + 600 x_2 + 480 x_3 \\[1ex] \text{p.p.} && x_1 + x_2 + x_3 &\le 50 \\ && 60 x_1 + 80 x_2 + 100 x_3 &\le 5000 \\ && 240 x_1 + 400 x_2 + 320 x_3 &\le 24000 \\ && x_1, x_2, x_3 &\ge 0 \end{aligned} $$ Taki nalogi rečemo _linearni program_ (LP). --- 4. Imamo $2n$ jabolk z masami $w_1, w_2, \dots, w_{2n}$. Jabolka bi radi razdelili v dve košari tako, da je v vsaki košari $n$ jabolk in da sta masi obeh košar čim bliže. * $\Omega = \{A \subseteq \{1, 2, \dots, 2n\} \mid |A| = n\}$ * $f(A) = |\sum_{i \in A} w_i - \sum_{i \in A^c} w_i|$ * $\operatorname{opt} = \min$ Drugače zapisano: $$ \begin{aligned} \Omega &= \{-1, 1\}^{2n} \\ x_i &= \begin{cases} 1 & \text{$i$-to jabolko v levi košari} \\ -1 & \text{$i$-to jabolko v desni košari} \\ \end{cases} \end{aligned} $$ $$ \begin{aligned} && \min \ \left|\sum_{i=1}^{2n} w_i x_i \right| \\ \text{p.p.} && \sum_{i=1}^{2n} x_i &= 0 \\ && x_1, x_2, \dots, x_{2n} &\in \{-1, 1\} \end{aligned} $$ ---- 5. Ana, Barbara, Cvetka in Darja želijo prečkati most. Naenkrat lahko most prečkata le dve od njiju, imajo pa eno samo svetilko. Za prečkanje mostu A, B, C, D potrebujejo 1, 2, 5 oziroma 10 minut - pri skupnem prečkanju seveda potrebujejo toliko časa kot počasnejša od njiju. Kako naj prečkajo most, da bodo čim hitrejše? * Definiramo graf z množico vozlišč $V = \mathcal{P}\{A, B, C, D, s\}$ - vsako vozlišče predstavlja stanje na eni strani mostu. * Vozlišči $u$ in $v$ sta sosedni, če lahko z enim prečkanjem pridemo od stanja $u$ do stanja $v$ (tj., $s \in u \oplus v$, $2 \le |u \oplus v| \le 3$ in $u \subset v$ ali $v \subset u$). * Uteži povezav so porabljeni časi. * Iščemo najkrajšo pot med $\emptyset$ in $\{A, B, C, D, s\}$. * Rešujemo z Dijkstrovim algoritmom - spoznali ga bomo pri predmetu Operacijske raziskave. ---- 6. Sestaviti želimo čim hitrejšo štafeto. | | prsno | hrbtno | delfin | prosto | | - | ----- | ------ | ------ | ------ | | 1 | 65 | 73 | 63 | 57 | | 2 | 67 | 76 | 65 | 58 | | 3 | 68 | 72 | 69 | 55 | | 4 | 67 | 75 | 70 | 59 | | 5 | 71 | 69 | 75 | 57 | | 6 | 69 | 71 | 66 | 59 | Primer rešitve (ne nujno optimalne!): * prsno 3 (68) * hrbtno 5 (69) * delfin 1 (63) * prosto 6 (59) ```graphviz graph G { rankdir=LR edge [color=gray] prsno -- 1 prsno -- 2 prsno -- 3 [penwidth=2,color=red,label=68] prsno -- 4 prsno -- 5 prsno -- 6 hrbtno -- 1 hrbtno -- 2 hrbtno -- 3 hrbtno -- 4 hrbtno -- 5 [penwidth=2,color=red,label=69] hrbtno -- 6 delfin -- 1 [penwidth=2,color=red,label=63] delfin -- 2 delfin -- 3 delfin -- 4 delfin -- 5 delfin -- 6 prosto -- 1 prosto -- 2 prosto -- 3 prosto -- 4 prosto -- 5 prosto -- 6 [penwidth=2,color=red,label=59] } ``` ---- 7. Potujoči trgovec iz Ljubljane želi obiskati London, Pariz, Madrid, Berlin. | | Lj | Lo | P | M | B | | -- | -- | -- | -- | -- | -- | | Lj | / | 5 | 10 | 5 | 10 | | Lo | 5 | / | 10 | 1 | 5 | | P | 10 | 10 | / | 5 | 5 | | M | 5 | 1 | 5 | / | 1 | | B | 10 | 5 | 5 | 1 | / | * Primer poti: Lj - B - P - Lo - M - Lj, cena 10+5+10+1+5 = 31 Iščemo najcenejšo pot, torej najcenejši Hamiltonov cikel. To je **problem potujočega trgovca** - učinkovit algoritem ni znan! --- ```mermaid graph TD op["Optimizacijski problemi"] op --- Nedopustni op --- Dopustni Dopustni --- Neomejeni Dopustni --- Omejeni Omejeni --- Optimalni Omejeni --- Neoptimalni ``` * Nedopustni problemi: $\Omega = \emptyset$ $$ \begin{aligned} \max \ 2x - y^2 \\ \text{p.p.} \quad x - y &\le 1 \\ -x + y &\le -2 \end{aligned} $$ * Dopustni problemi: $\Omega \ne \emptyset$ - Neomejeni problemi $$ \begin{aligned} \max \ 2x - y^2 \\ \text{p.p.} \quad x &\ge 0 \\ y &\le 5 \end{aligned} $$ - Omejeni problemi + Optimalni problemi $$ \begin{aligned} \max \ x^2 + y^2 \\ \text{p.p.} \quad 0 \le x &\le 2 \\ 0 \le y &\le 1 \end{aligned} $$ + Neoptimalni problemi $$ \begin{aligned} \max \ x^2 + y^2 \\ \text{p.p.} \quad 0 \le x &< 2 \\ 0 \le y &< 1 \end{aligned} $$ --- ## Linearno programiranje **_Definicija._** _Linearni program_ (LP) je optimizacijski problem, kjer so ciljna funkcija in vsi pogoji linearni. **_Primer._** $$ \begin{aligned} \min \ 2x_1 - 3x_2 + 2x_3 \\[1ex] \text{p.p.} \quad x_1 + 2x_2 - x_3 &\le 4 \\ x_1 + 5x_2 + 2x_3 &\ge 2 \\ 2x_1 - 3x_2 - 4x_3 &= 1 \\ x_1 &\ge 0 \\ x_3 &\le 0 \end{aligned} $$ **_Definicija._** Linearni program je v _standardni obliki_, če * iščemo $\max$ * so vsi pogoji $\le$ * so vse spremenljivke $\ge 0$ **_Trditev._** Vsak linearni program lahko ekvivalentno zapišemo v standardni obliki. _Dokaz._ * $\min f(x) \to \max -f(x)$ * $g_j(x) \ge b \to -g_j(x) \le -b$ * $g_j(x) = b \to g_j(x) \le b$; $-g_j(x) \le -b$ * $x_i \le 0 \to x_i = -x'_i$; $x'_i \ge 0$ * $x_i$ neomejena $\to x_i = x^+_i - x^-_i$; $x^+_i, x^-_i \ge 0$ **_Primer._** Zapišimo prejšnji primer v standardni obliki. $$ \begin{aligned} \max \ -2x_1 + 3x^+_2 - 3x^-_2 + 2x'_3 \\[1ex] \text{p.p.} \quad x_1 + 2x^+_2 - 2x^-_2 + x'_3 &\le 4 \\ -x_1 - 5x^+_2 + 5x^-_2 + 2x'_3 &\le -2 \\ 2x_1 - 3x^+_2 + 3x^-_2 + 4x'_3 &\le 1 \\ -2x_1 + 3x^+_2 - 3x^-_2 - 4x'_3 &\le -1 \\ x_1, x^+_2, x^-_2, x'_3 &\ge 0 \end{aligned} $$ ---- V splošnem lahko zapišemo linearni program v standardni obliki kot $$ \begin{aligned} \max \ c_1 x_1 + c_2 x_2 + \dots + c_n x_n \\[1ex] \text{p.p.} \quad a_{11} x_1 + a_{12} x_2 + \dots + a_{1n} x_n &\le b_1 \\ a_{21} x_1 + a_{22} x_2 + \dots + a_{2n} x_n &\le b_2 \\ &\ \ \vdots \\ a_{m1} x_1 + a_{m2} x_2 + \dots + a_{mn} x_n &\le b_m \\ x_1, x_2, \dots, x_n &\ge 0 \end{aligned} $$ **Matrična oblika:** $$ x = \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{bmatrix}, \quad c = \begin{bmatrix} c_1 \\ c_2 \\ \vdots \\ c_n \end{bmatrix} \in \mathbb{R}^n, \quad b = \begin{bmatrix} b_1 \\ b_2 \\ \vdots \\ b_m \end{bmatrix} \in \mathbb{R}^m, \quad A = [a_{ij}]_{i,j=1}^{m,n} \in \mathbb{R}^{m \times n} $$ $$ \begin{aligned} \max \ c^\top x \\[1ex] \text{p.p.} \quad A x &\le b \\ x &\ge 0 \end{aligned} $$ **_Definicija._** Množica $A \subseteq \mathbb{R}^n$ je _konveksna_, če za vsaka $x, y \in A$ in vsak $\lambda \in [0, 1]$ velja $(1 - \lambda) x + \lambda y \in A$. * $\sum_{i=1}^k \alpha_i x_i$ z $\sum_{i=1}^k \alpha_i = 1$ je _afina kombinacija_ točk $x_i$ ($1 \le i \le k$). - Afin prostor: "premaknjen" linearen prostor = afina kombinacija točk neke množice * $\sum_{i=1}^k \alpha_i x_i$ z $\sum_{i=1}^k \alpha_i = 1$ in $\alpha_i \ge 0$ ($1 \le i \le k$) je _konveksna kombinacija_ točk $x_i$ ($1 \le i \le k$). Torej: množica $A$ je konveksna, če je vsaka daljica s krajišči v množici $A$ v celoti vsebovana v $A$. **_Primer._** * Konveksne množice v $\mathbb{R}$: intervali * Krogla v $\mathbb{R}^n$ je konveksna, sfera pa ne * Polprostor v $\mathbb{R}^n$ je konveksen: $$ \begin{aligned} a_1 x_1 + a_2 x_2 + \dots + a_n x_n &\le b &&/ \cdot (1 - \lambda) \\ a_1 y_1 + a_2 y_2 + \dots + a_n y_n &\le b &&/ \cdot \lambda \\ a_1 ((1-\lambda) x_1 + \lambda y_1) + \dots + a_n ((1-\lambda) x_n + \lambda y_n) &\le (1-\lambda) b + \lambda b = b \end{aligned} $$ $\Rightarrow$ $(1-\lambda) x + \lambda y$ je tudi v polprostoru. **_Trditev._** Presek konveksnih množic je konveksen: $A_i$ ($i \in I$) konveksne $\Rightarrow \bigcap_{i \in I} A_i$ konveksna. _Dokaz._ Preveriti moramo: za vsaka $x, y \in \bigcap_{i \in I} A_i$ in vsak $\lambda \in [0, 1]$ velja $\forall i \in I: (1-\lambda) x + \lambda y \in A_i$. To je res, ker so množice $A_i$ ($i \in I$) konveksne. Unija konveksnih množic **ni nujno konveksna**! **_Trditev._** Naj bo $\Pi = (\Omega, f, \max)$ linearni program. Potem velja: 1. $\Omega$ je konveksna množica. 2. Množica optimalnih rešitev $\Pi$ je konveksna množica. _Dokaz._ 1. $\Omega$ je presek polprostorov (in hiperravnin), torej je konveksna množica. 2. Če optimalnih rešitev ni, potem je množica optimalnih rešitev prazna, torej konveksna. Sicer naj bo $c$ optimalna vrednost. Potem je množica optimalnih rešitev enaka $$ \{x \in \Omega \mid f(x) = c\} $$ in je zato konveksna množica. --- ### Grafično reševanje LP z dvema spremenljivkama **_Primer._** $$ \begin{aligned} \max \ x + y \\[1ex] \text{p.p.} \quad x + 2y &\le 6 \\ 5x + 4y &\le 20 \\ x, y &\ge 0 \end{aligned} $$ ![](https://i.imgur.com/4BSJuiC.png) $$ \begin{aligned} x + 2y &= 6 &&/ \cdot (-2) \\ 5x + 4y &= 20 \\ 3x &= 8 \\ x &= {8 \over 3} \\ 2y &= 6 - {8 \over 3} = {10 \over 3} \\ y &= {5 \over 3} \end{aligned} $$ $(x^\ast, y^\ast) = ({8 \over 3}, {5 \over 3})$ je optimalna rešitev, $z^\ast = {13 \over 3}$ je optimalna vrednost. --- Množica dopustnih rešitev $\Omega$ je **politop** (lahko neomejen). Množica optimalnih rešitev je **lice** tega politopa (oglišče, stranica, stranska ploskev, itd.). Optimalna vrednost (če obstaja) je vedno dosežena (tudi) v oglišču. --- ### Simpleksna metoda Denimo, da imamo linearni program v standardni obliki $$ \begin{aligned} \max \ c^\top x \\[1ex] \text{p.p.} \quad A x &\le b \\ x &\ge 0 \end{aligned} $$ kjer velja * $A \in \mathbb{R}^{m \times n}$, $b \in \mathbb{R}^m$, $c \in \mathbb{R}^n$ * $b \ge 0$ (če velja $b \not\ge 0$, uporabimo dvofazno simpleksno metodo, ki jo bomo spoznali kasneje) **_Primer._** Kmetija: $$ \begin{aligned} \max &\ & 400 x_1 + 600 x_2 + 480 x_3 \\[1ex] \text{p.p.} && x_1 + x_2 + x_3 &\le 50 \\ && 60 x_1 + 80 x_2 + 100 x_3 &\le 5000 \\ && 240 x_1 + 400 x_2 + 320 x_3 &\le 24000 \\ && x_1, x_2, x_3 &\ge 0 \end{aligned} $$ Ciljno funkcijo in omejitve lahko skaliramo brez vpliva na pomen spremenljivk: $$ \begin{aligned} \max &\ & 10 x_1 + 15 x_2 + 12 x_3 \\[1ex] \text{p.p.} && x_1 + x_2 + x_3 &\le 50 \\ && 3 x_1 + 4 x_2 + 5 x_3 &\le 250 \\ && 3 x_1 + 5 x_2 + 4 x_3 &\le 300 \\ && x_1, x_2, x_3 &\ge 0 \end{aligned} $$ Neenakosti spremenimo v enakosti z uvedbo novih **nenegativnih** spremenljivk. Prvi slovar: $$ \begin{aligned} x_4 &= 50 - x_1 - x_2 - x_3 \\ x_5 &= 250 - 3 x_1 - 4 x_2 - 5 x_3 \\ x_6 &= 300 - 3 x_1 - 5 x_2 - 4 x_3 \\ \hline z &= 10 x_1 + 15 x_2 + 12 x_3 \end{aligned} $$ V zgornjem sistemu enačb nastopajo sledeče spremenljivke: * _prvotne spremenljivke_: $x_1, x_2, \dots, x_n$ * _dopolnilne spremenljivke_: $x_{n+1}, x_{n+2}, \dots, x_{n+m}$ * _funkcional_ $z$ _Slovar_ je izražava $m$ izmed spremenljivk $x_1, x_2, \dots, x_{n+m}$ (_bazne spremenljivke_) in funkcionala $z$ z ostalimi izmed spremenljivk (_nebazne spremenljivke_). V _prvem slovarju_ velja: * nebazne spremenljivke so prvotne spremenljivke, in * bazne spremenljivke so dopolnilne spremenljivke. Slovar je _dopusten_, če so konstantni koeficienti baznih spremenljivk nenegativni. Prvi slovar je dopusten zaradi predpostavke $b \ge 0$. Dopusten slovar nam da bazno dopustno rešitev, ki jo dobimo tako, da nebaznim spremenljivkam dodelimo vrednost $0$. $$ \begin{aligned} x_4 &= 50 - x_1 - x_2 - x_3 & \leftarrow x_2 &\le 50 \\ x_5 &= 250 - 3 x_1 - 4 x_2 - 5 x_3 & x_2 &\le {250 \over 4} = {125 \over 2} \\ x_6 &= 300 - 3 x_1 - 5 x_2 - 4 x_3 & x_2 &\le {300 \over 5} = 60 \\ \hline z &= 10 x_1 + 15 \underline{x_2} + 12 x_3 \end{aligned} $$ Izberemo **nebazno** spremenljivko s **pozitivnim** koeficientom pri funkcionalu $z$. Če je kandidatov več, izberemo **poljubnega**. Pogosto uporabljamo: * pravilo največjega koeficienta * pravilo najmanjšega indeksa * pravilo največjega povečanja Izbrani spremenljivki pravimo _vstopna_ spremenljivka. V našem primeru smo izbrali $x_2$ (sta pa tudi $x_1$ in $x_3$ kandidata). Vrstici, ki izbrano vstopno spremenljivko **najbolj omejuje**, pravimo _pivotna_ vrstica, pripadajoči bazni spremenljivki pa _izstopna_ spremenljivka. Če imamo več pivotnih vrstic (tj., več baznih spremenljivk najbolj omejuje vstopno spremenljivko), potem za izstopno spremenljivko izberemo **poljubno** izmed njih. Vstopna spremenljivka vstopi v bazo, izstopna iz nje izstopi. Rešimo enačbo za vstopno spremenljivko in vstavimo v enačbe za ostale bazne spremenljivke in funkcional $z$: $$ \begin{aligned} x_2 &= 50 - x_1 - x_3 - x_4 \\ x_5 &= 250 - 3 x_1 - 4 (50 - x_1 - x_3 - x_4) - 5 x_3 \\ &= 50 + x_1 - x_3 + 4 x_4 \\ x_6 &= 300 - 3 x_1 - 5 (50 - x_1 - x_3 - x_4) - 4 x_3 \\ &= 50 + 2 x_1 + x_3 + 5 x_4 \\ \hline z &= 10 x_1 + 15 (50 - x_1 - x_3 - x_4) + 12 x_3 = \\ &= 750 - 5 x_1 - 3 x_3 - 15 x_4 \end{aligned} $$ Če so vsi koeficienti pri funkcionalu $z$ **nepozitivni**, smo našli **optimalno rešitev** in se simpleksna metoda ustavi. V nasprotnem primeru ponavljamo postopek. Vsi slovarji, ki smo jih dobili tekom reševanja, so **dopustni**. Če smo dobili kak nedopusten slovar, smo se zmotili (npr. izbrali napačno izstopno spremenljivko ali naredili računsko napako). Kaj se lahko še zgodi? * Konstantni koeficient bazne spremenljivke je enak $0$: $$ \begin{aligned} &\vdots \\ x_j &= 0 + \ldots - 3 x_i + \ldots & \leftarrow x_i \le 0 \\ &\vdots \\ \hline z &= 10 + \ldots + 4 \underline{x_i} + \ldots \end{aligned} $$ Vrednost v bazni dopustni rešitvi se **ne** poveča - _izrojen_ korak. * Nobena vrstica na omejuje vstopne spremenljivke: $$ \begin{aligned} &\vdots \\ x_j &= \ldots + 3 x_i + \ldots & x_i \le \infty \\ &\vdots \\ \hline z &= \ldots + 4 \underline{x_i} + \ldots \end{aligned} $$ Tedaj je linearni program **neomejen** - končamo simpleksno metodo. **Neomejeno družino** dopustnih rešitev dobimo tako, da vstopno spremenljivko pustimo kot nenegativen parameter brez zgornje meje, ostalim nebaznim spremenljivkam pa dodelimo vrednost $0$. Kako iz zadnjega slovarja za optimalni problem dobimo **vse** optimalne rešitve? * Nebaznim spremenljivkam z negativnim koeficientom dodelimo vrednost $0$. * Nebazne spremenljivke z **ničelnim koeficientom** pustimo kot parametre (tj., jim ne dodelimo nujno vrednosti $0$). * Upoštevamo, da so vse bazne spremenljivke nenegativne. **_Primer._** Denimo, da imamo sledeči zadnji slovar. $$ \begin{aligned} x_2 &= 40 - {2 \over 3} x_1 - {4 \over 5} x_3 - {1 \over 15} x_6 \\ x_4 &= 10 - {1 \over 3} x_1 - {1 \over 5} x_3 + {1 \over 15} x_6 \\ x_5 &= 90 - {1 \over 3} x_1 - {9 \over 5} x_3 + {4 \over 15} x_6 \\ \hline z &= 200 - {1 \over 3} x_1 - {1 \over 3} x_6 \end{aligned} $$ Potem velja: * $x_1^\ast = x_6^\ast = 0$ * $x_2^\ast = 40 - {4 \over 5} x_3^\ast \ge 0$, torej $x_3^\ast \le 50$ * $x_4^\ast = 10 - {1 \over 5} x_3^\ast \ge 0$, torej $x_3^\ast \le 50$ * $x_5^\ast = 90 - {9 \over 5} x_3^\ast \ge 0$, torej $x_3^\ast \le 50$ Optimalne rešitve so torej oblike $x_1^\ast = 0$, $x_2^\ast = 40 - {4 \over 5} x_3^\ast$, $0 \le x_3^\ast \le 50$, $z^\ast = 200$. --- Ali se simpleksna metoda vedno ustavi? **NE.** Možnih slovarjev je ${n+m \choose m}$. Če se simpleksna metoda ne ustavi, pomeni, da je prišlo do "ciklanja". V tem primeru so vsi koraki v ciklu izrojeni. Ciklanje je izjemno redko. Dokazati se da, da do ciklanja ne bo prišlo, če za vstopne in izstopne spremenljivke uporabimo pravilo najmanjšega indeksa (_Blandovo pravilo_). Časovne zahtevnosti algoritmov: * "Hitri" algoritmi: uporabijo polinomsko mnogo operacij. * "Počasni" algoritmi: uporabijo eksponentno mnogo operacij. Ali je simpleksna metoda hitra? * Tipično: $\approx m \log n$ korakov * Najslabši primer: simpleksna metoda **ni** polinomska **_Primer._** (Klee-Minty) Za $n = 3$: $$ \begin{aligned} \max &\ & 100 x_1 + 10 x_2 + x_3 \\[1ex] \text{p.p.} && x_1 &\le 1 \\ && 20 x_1 + x_2 &\le 100 \\ && 200 x_1 + 20 x_2 + x_3 &\le 10000 \\ && x_1, x_2, x_3 &\ge 0 \end{aligned} $$ * Če uporabimo metodo največjega koeficienta, potrebujemo $2^n - 1$ korakov. * Če uporabimo pravilo največjega povečanja, potrebujemo $1$ korak. Obstajajo algoritmi za reševanje linearnih programov, ki so dokazljivo polinomski. --- ### Dvofazna simpleksna metoda Uporabljamo jo za linearne programe v standardni obliki, za katere ne velja $b \ge 0$. 1. faza: ugotovi, ali je linearni program dopusten - če je, nam prva faza da dopusten začetni slovar za drugo fazo. 2. faza: identična simpleksni metodi. --- **_Primer._** Imamo dve vitaminski tableti, Polivit in Oligovit, ki vsebujejo različne količine vitaminov A, B in C. | | A | B | C | cena za tableto | | -------------- | - | -- | - | --------------- | | Polivit | 1 | 4 | 1 | 12 | | Oligovit | 1 | 1 | 2 | 10 | | dnevne potrebe | 7 | 13 | 8 | Kako najceneje zadostiti dnevnim potrebam? $$ \begin{aligned} \min &\ & 12 x_1 + 10 x_2 \\[1ex] \text{p.p.} && x_1 + x_2 &\ge 7 \\ && 4 x_1 + x_2 &\ge 13 \\ && x_1 + 2 x_2 &\ge 8 \\ && x_1, x_2 &\ge 0 \end{aligned} $$ Zapišimo ekvivalentni linearni program v standardni obliki. $$ \begin{aligned} \max &\ & -12 x_1 - 10 x_2 \\[1ex] \text{p.p.} && -x_1 - x_2 &\le -7 \\ && -4 x_1 - x_2 &\le -13 \\ && -x_1 - 2 x_2 &\le -8 \\ && x_1, x_2 &\ge 0 \end{aligned} $$ Ker v zgornjem linearnem programu velja $b \not\ge 0$, zapišimo še pomožni problem prve faze: $$ \begin{aligned} && \min \ x_0 \\[1ex] \text{p.p.} && -x_1 - x_2 &\le -7 + x_0 \\ && -4 x_1 - x_2 &\le -13 + x_0 \\ && -x_1 - 2 x_2 &\le -8 + x_0 \\ && x_0, x_1, x_2 &\ge 0 \end{aligned} $$ Pomožni problem je vedno dopusten ($x_0$ mora biti dovolj velik). Pomožni problem ima optimalno vrednost $0$ **natanko tedaj**, ko je prvotni problem dopusten. Zapišimo začetni slovar za prvo fazo - ta slovar **ni dopusten**: $$ \begin{aligned} x_3 &= -7 + x_0 + x_1 + x_2 \\ x_4 &= -13 + x_0 + 4 x_1 + x_2 \\ x_5 &= -8 + x_0 + x_1 + 2 x_2 \\ \hline w &= -x_0 \end{aligned} $$ V prvem koraku prve faze v bazo vstopi $x_0$, izstopi pa spremenljivka z najmanjšim (najbolj negativnim) konstantnim členom - v našem primeru $x_4$: $$ \begin{aligned} x_0 &= 13 - 4 x_1 - x_2 + x_4 & \leftarrow x_2 &\le 13 \\ x_3 &= 6 - 3 x_1 + x_4 & x_2 &\le \infty \\ x_5 &= 5 - 3 x_1 + x_2 + x_4 & x_2 &\le \infty \\ \hline w &= -13 + 4 x_1 + \underline{x_2} - x_4 \end{aligned} $$ Nadaljujemo enako kot pri osnovni simpleksni metodi. V našem primeru po metodi največjega povečanja izberemo $x_2$ za vstopno spremenljivko in $x_0$ za izstopno spremenljivko. $$ \begin{aligned} x_2 &= 13 - x_0 - 4 x_1 + x_4 \\ x_3 &= 6 - 3 x_1 + x_4 \\ x_5 &= 18 - x_0 - 7 x_1 + 2 x_4 \\ \hline w &= -x_0 \end{aligned} $$ Optimalna vrednost pomožnega problema je $0$ - prvotni problem je torej dopusten. Začetni slovar druge faze dobimo tako, da v zadnjem slovarju prve faze vzamemo $x_0 = 0$ in vstavimo prvotne bazne spremenljivke v funkcional $z$: $$ \begin{aligned} x_2 &= 13 - 4 x_1 + x_4 \\ x_3 &= 6 - 3 x_1 + x_4 \\ x_5 &= 18 - 7 x_1 + 2 x_4 \\ \hline z &= -12 x_1 - 10 (13 - 4 x_1 + x_4) \\ &= -130 + 28 x_1 - 10 x_4 \end{aligned} $$ $x_1$ vstopi, $x_3$ izstopi: $$ \begin{aligned} x_1 &= 2 - {1 \over 3} x_3 + {1 \over 3} x_4 \\ x_2 &= 13 - 4 \left(2 - {1 \over 3} x_3 + {1 \over 3} x_4\right) + x_4 \\ &= 5 + {4 \over 3} x_3 - {1 \over 3} x_4 \\ x_5 &= 18 - 7 \left(2 - {1 \over 3} x_3 + {1 \over 3} x_4\right) + 2 x_4 \\ &= 4 + {7 \over 3} x_3 - {1 \over 3} x_4 \\ \hline z &= -130 + 28 \left(2 - {1 \over 3} x_3 + {1 \over 3} x_4\right) - 10 x_4 \\ &= -74 - {28 \over 3} x_3 - {2 \over 3} x_4 \end{aligned} $$ Imamo zadnji slovar druge faze, preberemo optimalno rešitev: * $x_1^\ast = 2$ tableti Polivit * $x_2^\ast = 5$ tablet Oligovit * cena: $-z^\ast = 74$ ---- Prva faza se vedno konča, ko ne moremo več izbrati vstopne spremenljivke (ker je problem omejen). * $w^\ast < 0$: prvotni problem je nedopusten, končamo. * $w^\ast = 0$, $x_0$ je nebazna spremenljivka v zadnjem slovarju prve faze: nadaljujemo z drugo fazo * $w^\ast = 0$, $x_0$ je bazna spremenljivka v zadnjem slovarju prve faze: temu se izognemo s pravilom, da če $x_0$ lahko izstopi iz baze, jo izberemo za izstopno spremenljivko (ali pa naredimo izrojen korak, da $x_0$ izstopi) ```mermaid graph TD LP[LP Π] -- "b ≱ 0" --- dvofazna[dvofazna simpleksna metoda] LP -- "b ≥ 0" --- enofazna[simpleksna metoda] dvofazna -- "w* < 0" --- nedopusten[Π nedopusten] dvofazna -- "w* = 0" --- dopusten[Π dopusten] --- enofazna enofazna --- neomejen[Π neomejen] enofazna --- optimalen[Π optimalen] ``` **_Osnovni izrek linearnega programiranja._** 1. Če ima linearni program dopustno rešitev, ima bazno dopustno rešitev. 2. Če ima linearni program optimalno rešitev, ima bazno optimalno rešitev. 3. Za linearni program velja natanko ena od možnosti: * linearni program je nedopusten, * linearni program je neomejen, ali * linearni program je optimalen. --- ### Dualnost pri linearnem programiranju Naj bo $\Pi$ linearni program $$ \begin{aligned} \max &\ & 10 x_1 + 15 x_2 + 12 x_3 \\[1ex] \text{p.p.} && x_1 + x_2 + x_3 &\le 50 &/ \cdot y_4 \ge 0 \\ && 3 x_1 + 4 x_2 + 5 x_3 &\le 250 &/ \cdot y_5 \ge 0 \\ && 3 x_1 + 5 x_2 + 4 x_3 &\le 300 &/ \cdot y_6 \ge 0 \\ && x_1, x_2, x_3 &\ge 0 \end{aligned} $$ Iščemo zgornje meje za ciljno funkcijo: $$ (y_4 + 3 y_5 + 3 y_6) x_1 + (y_4 + 4 y_5 + 5 y_6) x_2 + (y_4 + 5 y_5 + 4 y_6) x_3 \le 50 y_4 + 250 y_5 + 300 y_6 $$ Če velja $$ \begin{aligned} y_4 + 3 y_5 + 3 y_6 &\ge 10, \\ y_4 + 4 y_5 + 5 y_6 &\ge 15, \\ y_4 + 5 y_5 + 4 y_6 &\ge 12, \end{aligned} $$ potem $$ 10 x_1 + 15 x_2 + 12 x_3 \le 50 y_4 + 250 y_5 + 300 y_6. $$ Hočemo čim manjšo zgornjo mejo. _Prvotnemu_ linearnemu programu $\Pi$ dodelimo _dualni_ linearni program $\Pi'$: $$ \begin{aligned} \min &\ & 50 y_4 + 250 y_5 + 300 y_6 \\[1ex] \text{p.p.} && y_4 + 3 y_5 + 3 y_6 &\ge 10 \\ && y_4 + 4 y_5 + 5 y_6 &\ge 15 \\ && y_4 + 5 y_5 + 4 y_6 &\ge 12 \\ && y_4, y_5, y_6 &\ge 0 \end{aligned} $$ **_Definicija._** Za prvotni linearni program $\Pi$ je njegov dualni linearni program $\Pi'$, kjer je | prvotni LP $\Pi$ | dualni LP $\Pi'$ | | ---------------- | ---------------- | | $$\begin{aligned} \max \ c^\top x \\[1ex] \text{p.p.} \quad A x &\le b \\ x &\ge 0 \end{aligned}$$ | $$\begin{aligned} \min \ b^\top y \\[1ex] \text{p.p.} \quad A^\top y &\ge c \\ y &\ge 0 \end{aligned}$$ | | $$\begin{aligned} \max \ \sum_{j=1}^n c_j x_j \\[1ex] \text{p.p.} \quad \sum_{j=1}^n a_{ij} x_j &\le b_i & (1 &\le i \le m) \\ x_j &\ge 0 & (1 &\le j \le n) \end{aligned}$$ | $$\begin{aligned} \min \ \sum_{i=1}^m b_i y_{n+i} \\[1ex] \text{p.p.} \quad \sum_{i=1}^m a_{ij} y_{n+i} &\ge c_j & (1 &\le j \le n) \\ y_{n+i} &\ge 0 & (1 &\le i \le m) \end{aligned}$$ | **_Trditev._** $\Pi'' = \Pi$. _Dokaz._ Zapišimo $\Pi'$ v standardni obliki. $$ \begin{aligned} \max \ -b^\top y \\[1ex] \text{p.p.} \quad -A^\top y &\le -c \\ y &\ge 0 \end{aligned} $$ Potem je $\Pi''$ sledeči linearni program: $$ \begin{aligned} \min \ -c^\top x \\[1ex] \text{p.p.} \quad -A x &\ge -b \\ x &\ge 0 \end{aligned} $$ Pretvorba v standardno obliko nam pokaže, da je $\Pi'' = \Pi$. --- **_Šibki izrek o dualnosti (ŠID)._** Naj bo $\Pi$ prvotni linearni program kot zgoraj in $\Pi'$ njegov dual. Če je $x$ dopustna rešitev za $\Pi$ in $y$ dopustna rešitev za $\Pi'$, potem velja $c^\top x \le b^\top y$. _Dokaz._ 1. varianta: $$ \begin{aligned} c^\top x &\le (A^\top y)^\top x & (A^\top y &\ge c, x \ge 0) \\ &= y^\top A x \\ &\le y^\top b & (Ax &\le b, y \ge 0) \\ &= b^\top y \end{aligned} $$ 2. varianta: $$ \begin{aligned} \sum_{j=1}^n c_j x_j &\le \sum_{j=1}^n \left(\sum_{i=1}^m a_{ij} y_{n+i}\right) x_j & \Big(\forall j: \sum_{i=1}^m a_{ij} y_{n+i} &\ge c_j, x_j \ge 0\Big) \\ &= \sum_{i=1}^m \left(\sum_{j=1}^n a_{ij} x_j\right) y_{n+i} \\ &\le \sum_{i=1}^m b_i y_{n+i} & \Big(\forall i: \sum_{j=1}^n a_{ij} x_j &\le b_i, y_{n+i} \ge 0\Big) \\ \end{aligned} $$ **_Posledica 1._** Če sta $x$ in $y$ dopustni rešitvi za $\Pi$ oziroma $\Pi'$, za kateri velja $c^\top x = b^\top y$, potem sta $x$ in $y$ optimalni rešitvi za $\Pi$ oziroma $\Pi'$. _Dokaz._ $b^\top y$ je zgornja meja za $c^\top x$, to zgornjo mejo dosežemo. $c^\top x$ je spodnja meja za $b^\top y$, to spodnjo mejo dosežemo. **Opomba.** S to posledico lahko preverimo optimalnost ponujenih dopustnih rešitev $x$, $y$, za kateri velja $c^\top x = b^\top y$. **_Posledica 2._** Če je $\Pi$ neomejen problem, je $\Pi'$ nedopusten problem. _Dokaz._ Če je $\Pi'$ dopusten, imamo zgornjo mejo za ciljno funkcijo $\Pi$, protislovje. --- **_Krepki izrek o dualnosti (KID)._** Naj bo $\Pi$ prvotni linearni program kot zgoraj in $\Pi'$ njegov dual. Če je $x^\ast$ optimalna rešitev za $\Pi$, potem obstaja optimalna rešitev $y^\ast$ za $\Pi'$ in velja $c^\top x^\ast = b^\top y^\ast$. ---- Zadnji slovar za problem kmetije: $$ \begin{aligned} x_2 &= 50 - x_1 - x_3 - x_4 \\ x_5 &= 50 + x_1 - x_3 + 4 x_4 \\ x_6 &= 50 + 2 x_1 + x_3 + 5 x_4 \\ \hline z &= 750 - 5 x_1 - 0 x_2 - 3 x_3 - 15 x_4 - 0 x_5 - 0 x_6 \end{aligned} $$ Zadnji slovar za dual problema kmetije: $$ \begin{aligned} y_1 &= 5 + y_2 - y_5 - 2 y_6 \\ y_3 &= 3 + y_2 + y_5 - y_6 \\ y_4 &= 15 + y_2 - 4 y_5 - 5 y_6 \\ \hline z &= -750 - 0 y_1 - 50 y_2 - 0 y_3 - 0 y_4 - 50 y_5 - 50 y_6 \end{aligned} $$ Videti je, da so koeficienti dopolnilnih spremenljivk v zadnjem slovarju ravno negacija optimalne rešitve dualnega problema. ---- _Dokaz KID._ Simpleksna metoda za $\Pi$ se konča z zadnjim slovarjem z $$ z = z^\ast + \sum_{j=1}^{n+m} c^\ast_j x_j = \sum_{j=1}^n c_j x^\ast_j + \sum_{j=1}^n c^\ast_j x_j + \sum_{i=1}^m c^\ast_{n+i} x_{n+i}, $$ kjer velja $c^\ast_j \le 0$ ($1 \le j \le n+m$) in $c^\ast_j = 0$, če je $x_j$ bazna spremenljivka. Naj bo $y^\ast_{n+i} = -c^\ast_{n+i}$ ($1 \le i \le m$). Pokazali bomo, da je $y^\ast$ optimalna rešitev $\Pi'$. Velja $$ \begin{aligned} z &= \sum_{j=1}^n c_j x^\ast_j + \sum_{j=1}^n c^\ast_j x_j + \sum_{i=1}^m (-y^\ast_{n+i}) \left(b_i - \sum_{j=1}^n a_{ij} x_j\right) \\ &= \left(\sum_{j=1}^n c_j x^\ast_j - \sum_{i=1}^m b_i y^\ast_{n+i}\right) + \sum_{j=1}^n c^\ast_j x_j + \sum_{j=1}^n \left(\sum_{i=1}^m a_{ij} y^\ast_{n+i}\right) x_j \\ &= \left(\sum_{j=1}^n c_j x^\ast_j - \sum_{i=1}^m b_i y^\ast_{n+i}\right) + \sum_{j=1}^n \left(c^\ast_j + \sum_{i=1}^m a_{ij} y^\ast_{n+i}\right) x_j \\ \end{aligned} $$ Ker velja $z = \sum_{j=1}^n c_j x_j$, sledi $$ \begin{aligned} \sum_{j=1}^n c_j x^\ast_j - \sum_{i=1}^m b_i y^\ast_{n+i} &= 0, \\ c^\ast_j + \sum_{i=1}^m a_{ij} y^\ast_{n+i} &= c_j & (1 \le j \le n). \end{aligned} $$ Ker velja $y^\ast_{n+i} = -c^\ast_{n+i} \ge 0$ ($1 \le i \le m$) in $\sum_{i=1}^m a_{ij} y^\ast_{n+i} = c_j - c^\ast_j \ge c_j$ ($1 \le j \le n$), je $y^\ast$ dopustna rešitev za $\Pi'$. Ker velja $c^\top x^\ast = b^\top y^\ast$, je po Posledici 1 $y^\ast$ optimalna rešitev za $\Pi'$. --- Če povzamemo: * **_ŠID:_** $x, y$ dopustni za $\Pi, \Pi' \Rightarrow c^\top x \le b^\top y$ * **_KID:_** $\Pi$ optimalen $\Rightarrow \Pi'$ optimalen z isto optimalno vrednostjo Imamo torej sledeče možnosti: | $\Pi$ \ $\Pi'$ | nedopusten | neomejen | optimalen | | -------------- | ---------- | ----------- | ----------- | | nedopusten | ✔ | ✔ | ✗ (KID) | | neomejen | ✔ | ✗ (ŠID) | ✗ (KID/ŠID) | | optimalen | ✗ (KID) | ✗ (KID/ŠID) | ✔ | **_Primer_** nedopustnih $\Pi$ in $\Pi'$: | $\Pi$ | $\Pi'$ | | ----- | ------ | | $$\begin{aligned} \max &\ & 2x_1 - x_2 \\ \text{p.p.} && -x_1 + x_2 &\le -2 \\ && x_1 - x_2 &\le 1 \\ && x_1, x_2 &\ge 0 \end{aligned}$$ | $$\begin{aligned} \min &\ & -2y_3 + y_4 \\ \text{p.p.} && -y_3 + y_4 &\ge 2 \\ && y_3 - y_4 &\ge -1 \\ && y_3, y_4 &\ge 0 \end{aligned}$$ | **_Izrek._** Za linearna programa $\Pi$ in $\Pi'$ velja natanko ena od sledečih možnosti: * oba sta optimalna, * oba sta nedopustna, ali * eden je neomejen, drugi pa nedopusten. --- **_Izrek o dualnem dopolnjevanju_** (angl. _complementary slackness_). Naj bo $\Pi$ prvotni linearni program kot zgoraj in $\Pi'$ njegov dual, ter naj bosta $x$ in $y$ dopustni rešitvi za $\Pi$ oziroma $\Pi'$. Potem sta $x$ in $y$ optimalni rešitvi za $\Pi$ oziroma $\Pi'$ natanko tedaj, ko velja $$ \begin{aligned} \forall i &\in \{1, \dots, m\}: & \Big(\sum_{j=1}^n a_{ij} x_j &= b_i &&\lor& y_{n+i} &= 0\Big) \quad \text{in} \\ \forall j &\in \{1, \dots, n\}: & \Big(x_j &= 0 &&\lor& \sum_{i=1}^m a_{ij} y_{n+i} &= c_j\Big). \end{aligned} $$ Ekvivalentno: potem sta $x$ in $y$ optimalni rešitvi za $\Pi$ oziroma $\Pi'$ natanko tedaj, ko velja $$ \begin{aligned} \forall i &\in \{1, \dots, m\}: & \Big(\sum_{j=1}^n a_{ij} x_j &< b_i &&\Rightarrow& y_{n+i} &= 0\Big) \quad \text{in} \\ \forall j &\in \{1, \dots, n\}: & \Big(x_j &> 0 &&\Rightarrow& \sum_{i=1}^m a_{ij} y_{n+i} &= c_j\Big). \end{aligned} $$ _Dokaz._ $$ L = \sum_{j=1}^n c_j x_j \le \sum_{j=1}^n \left(\sum_{i=1}^m a_{ij} y_{n+i}\right) x_j = \sum_{i=1}^m \left(\sum_{j=1}^n a_{ij} x_j\right) y_{n+i} \le \sum_{i=1}^m b_i y_{n+i} = D $$ Po Posledici 1 in KID sta $x, y$ optimalni za $\Pi, \Pi'$ natanko tedaj, ko velja $L = D$, kar je enakovredno $$ \begin{aligned} \forall j: c_j x_j = \left(\sum_{i=1}^m a_{ij} y_{n+i}\right) x_j &\ \land \ \forall i: \left(\sum_{j=1}^n a_{ij} x_j\right) y_{n+i} = b_i y_{n+i} \\ \Leftrightarrow \quad \forall j: \left(c_j - \sum_{i=1}^m a_{ij} y_{n+i}\right) x_j = 0 &\ \land \ \forall i: \left(b_i - \sum_{j=1}^n a_{ij} x_j\right) y_{n+i} = 0 \end{aligned} $$ **_Primer._** Pokaži, da je $x = (0, 50, 0)$ optimalna rešitev problema kmetije. 1. korak: preverimo, da je ponujena rešitev dopustna. $$ \begin{aligned} 0 + 50 + 0 &= 50 \\ 3 \cdot 0 + 4 \cdot 50 + 5 \cdot 0 &< 250 \\ 3 \cdot 0 + 5 \cdot 50 + 4 \cdot 0 &< 300 \end{aligned} $$ 2. korak: za vsako neenakost, ki je izpolnjena z $<$, pripadajoči dualni spremenljivki dodelimo vrednost $0$. $$ y_5 = y_6 = 0 $$ 3. korak: za vsako pozitivno vrednost v rešitvi postavimo enačaj v pripadajoči neenakosti. $$ y_4 + 4 y_5 + 5 y_6 = 15 $$ 4. korak: rešimo sistem iz korakov 2 in 3 ter preverimo dopustnost rešitve. * Če je rešitev več (parametrična rešitev), zadostuje, da poiščemo tako vrednost parametrov, da bo dobljena rešitev dopustna. $$ \begin{aligned} y_4 = 15 \qquad y_5 &= 0 \qquad y_6 = 0 \\[1ex] 15 + 3 \cdot 0 + 3 \cdot 0 &\ge 10 \\ 15 + 5 \cdot 0 + 4 \cdot 0 &\ge 12 \end{aligned} $$ --- ### Ekonomski pomen dualnih spremenljivk **_Primer._** Problem kmetije: $$ \begin{aligned} x_1^\ast = 0 \qquad x_2^\ast = 50 \qquad x_3^\ast &= 0 \\[1ex] z^\ast = 10 \cdot 0 + 15 \cdot 50 + 12 \cdot 0 &= 750 & \text{(zaslužek v 40 €)} \\[1ex] 0 + 50 + 0 &= 50 & \text{(zemlja v ha)} \\ 3 \cdot 0 + 4 \cdot 50 + 5 \cdot 0 &< 250 & \text{(delovna sila v 20 človek-urah)} \\ 3 \cdot 0 + 5 \cdot 50 + 4 \cdot 0 &< 300 & \text{(kapital v 80 €)} \end{aligned} $$ Ne izplača se nam najeti več delovne sile ali vzeti kredita. Morda se nam izplača dokupiti dodatno zemljo. $$ y_4^\ast = 15 \qquad y_5^\ast = 0 \qquad y_6^\ast = 0 $$ **_Izrek._** Naj bo $\Pi$ prvotni linearni program kot zgoraj z neizrojeno bazno optimalno rešitvijo (tj., v pripadajočem slovarju so vsi konstantni členi pri baznih spremenljivkah pozitivni), in $\Pi'$ njegov dual. Potem obstaja $\epsilon > 0$, da velja $$ |\Delta b| < \epsilon \ \Rightarrow \ \Delta z^\ast = \sum_{i=1}^m y_{n+i}^\ast \Delta b_i, $$ kjer je $y^\ast$ optimalna rešitev $\Pi'$ ter sta $\Delta b$ in $\Delta z^\ast$ spremembi desne strani in optimalne vrednosti. V našem primeru: $\Delta z^\ast = 15 \, \Delta b_1$ za $|\Delta b| < \epsilon$. Zemljo se nam splača kupiti po ceni največ $15 \cdot 40$ €/ha = $600$ €/ha. Torej: optimalne vrednosti duala nam dajo "tržno"/"pošteno"/sprejemljivo ceno surovin. --- ### Dual splošnega linearnega programa **_Izrek._** Naj bo $\Pi$ linearni program v spodnji obliki. Potem je njegov dual $\Pi'$: | prvotni LP $\Pi$ | dualni LP $\Pi'$ | | ---------------- | ---------------- | | $$\begin{aligned} \max \ \sum_{j=1}^n c_j x_j \\[1ex] \text{p.p.} \quad \sum_{j=1}^n a_{ij} x_j &\le b_i & (1 &\le i \le m') \\ \sum_{j=1}^n a_{ij} x_j &= b_i & (m'+1 &\le i \le m) \\ x_j &\ge 0 & (1 &\le j \le n') \end{aligned}$$ | $$\begin{aligned} \min \ \sum_{i=1}^m b_i y_{n+i} \\[1ex] \text{p.p.} \quad \sum_{i=1}^m a_{ij} y_{n+i} &\ge c_j & (1 &\le j \le n') \\ \sum_{i=1}^m a_{ij} y_{n+i} &= c_j & (n'+1 &\le j \le n) \\ y_{n+i} &\ge 0 & (1 &\le i \le m') \end{aligned}$$ | **_Izrek o dualnem dopolnjevanju_** za $\Pi$ in $\Pi'$ kot zgoraj. Naj bosta $x$ in $y$ dopustni rešitvi za $\Pi$ oziroma $\Pi'$. Potem sta $x$ in $y$ optimalni rešitvi za $\Pi$ oziroma $\Pi'$ natanko tedaj, ko velja $$ \begin{aligned} \forall i &\in \{1, \dots, m'\}: & \Big(\sum_{j=1}^n a_{ij} x_j &= b_i &&\lor& y_{n+i} &= 0\Big) \quad \text{in} \\ \forall j &\in \{1, \dots, n'\}: & \Big(x_j &= 0 &&\lor& \sum_{i=1}^m a_{ij} y_{n+i} &= c_j\Big). \end{aligned} $$ Torej: * neenakost $\le \quad \leftrightarrow \quad$ nenegativna spremenljivka * enakost $\quad \leftrightarrow \quad$ neomejena spremenljivka **_Primer._** | prvotni LP $\Pi$ | dualni LP $\Pi'$ | | ---------------- | ---------------- | | $$\begin{aligned} \max \ 3 x_1 - 2 x_2 \\[1ex] \text{p.p.} \quad x_1 + 4 x_2 &\le 5 \\ 3 x_1 + x_2 &= 4 \\ x_1 &\ge 0 \end{aligned}$$ | $$\begin{aligned} \min \ 5 y_3 + 4 y_4 \\[1ex] \text{p.p.} \quad y_3 + 3 y_4 &\ge 3 \\ 4 y_3 + y_4 &= -2 \\ y_3 &\ge 0 \end{aligned}$$ | _Dokaz._ Pretvorimo $\Pi$ v standardno obliko: $$ \begin{aligned} \max \ \sum_{j=1}^{n'} c_j x_j + \sum_{j=n'+1}^n c_j x^+_j - \sum_{j=n'+1}^n c_j x^-_j \\[1ex] \text{p.p.} \quad \sum_{j=1}^{n'} a_{ij} x_j + \sum_{j=n'+1}^n a_{ij} x^+_j - \sum_{j=n'+1}^n a_{ij} x^-_j &\le b_i & (1 &\le i \le m') \\ \sum_{j=1}^{n'} a_{ij} x_j + \sum_{j=n'+1}^n a_{ij} x^+_j - \sum_{j=n'+1}^n a_{ij} x^-_j &\le b_i & (m'+1 &\le i \le m) \\ -\sum_{j=1}^{n'} a_{ij} x_j - \sum_{j=n'+1}^n a_{ij} x^+_j + \sum_{j=n'+1}^n a_{ij} x^-_j &\le -b_i & (m'+1 &\le i \le m) \\ x_j &\ge 0 & (1 &\le j \le n') \\ x^+_j, x^-_j &\ge 0 & (n'+1 &\le j \le n) \end{aligned} $$ Zapišimo še dual: $$ \begin{aligned} \min \ \sum_{i=1}^{m'} b_i y_{n+i} + \sum_{i=m'+1}^m b_i y^+_{n+i} - \sum_{i=m'+1}^m b_i y^-_{n+i} \\[1ex] \text{p.p.} \quad \sum_{i=1}^{m'} a_{ij} y_{n+i} + \sum_{i=m'+1}^m a_{ij} y^+_{n+i} - \sum_{i=m'+1}^m a_{ij} y^-_{n+i} &\ge c_j & (1 &\le j \le n') \\ \sum_{i=1}^{m'} a_{ij} y_{n+i} + \sum_{i=m'+1}^m a_{ij} y^+_{n+i} - \sum_{i=m'+1}^m a_{ij} y^-_{n+i} &\ge c_j & (n'+1 &\le j \le n) \\ -\sum_{i=1}^{m'} a_{ij} y_{n+i} - \sum_{i=m'+1}^m a_{ij} y^+_{n+i} + \sum_{i=m'+1}^m a_{ij} y^-_{n+i} &\ge -c_j & (n'+1 &\le j \le n) \\ y_{n+i} &\ge 0 & (1 &\le i \le m') \\ y^+_{n+i}, y^-_{n+i} &\ge 0 & (m'+1 &\le i \le m) \end{aligned} $$ Vidimo, da je dobljeni dual enakovreden našemu zapisu $\Pi'$. --- ## Problem razvoza (angl. _transshipment problem_) **_Primer._** Imamo 3 mesta, v mestu $a$ proizvedejo 7 enot mleka, v $b$ ga porabijo 4 enote, v $c$ pa ga porabijo 3 enote. Prevoz po cesti ima določeno ceno na enoto: * $a \to b: 1$ * $a \to c: 3$ * $b \to c: 1$ * $c \to b: 6$ Kako najceneje prenesti mleko od proizvajalcev do porabnikov? ```graphviz digraph G { rankdir=LR nodesep=0.5 ranksep=1 a [label=-7,xlabel=a] b [label=4,xlabel=b] c [label=3,xlabel=c] a -> b [taillabel=" 1\n\n", tailport=ne] a -> c [taillabel="\n 3", tailport=se] b -> c [headlabel=" 1", label=" ", tailport=se, constraint=false] c -> b [headlabel="6 ", tailport=nw, constraint=false] } ``` Možni rešitvi: * Rešitev 1: ```graphviz digraph G { rankdir=LR nodesep=0.5 ranksep=1 edge [fontcolor=red, labelfontcolor=black] a [label=-7,xlabel=a] b [label=4,xlabel=b] c [label=3,xlabel=c] a -> b [taillabel=" 1\n\n", label=4, tailport=ne, color=red] a -> c [taillabel="\n 3", label=3, tailport=se, color=red] b -> c [headlabel=" 1", label=" ", tailport=se, constraint=false] c -> b [headlabel="6 ", tailport=nw, constraint=false] } ``` Cena: $4 \cdot 1 + 3 \cdot 3 = 13$ * Rešitev 2: ```graphviz digraph G { rankdir=LR nodesep=0.5 ranksep=1 edge [fontcolor=red, labelfontcolor=black] a [label=-7,xlabel=a] b [label=4,xlabel=b] c [label=3,xlabel=c] a -> b [taillabel=" 1\n\n", label=7, tailport=ne, color=red] a -> c [taillabel="\n 3", tailport=se] b -> c [headlabel=" 1", label=" 3", tailport=se, constraint=false, color=red] c -> b [headlabel="6 ", tailport=nw, constraint=false] } ``` Cena: $7 \cdot 1 + 3 \cdot 1 = 10$ ---- 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$) in uteži na povezavah $c_{uv} \in \mathbb{R}$ ($uv \in E$), kjer: * $b_v \ge 0$, če je v vozlišču $v$ poraba $b_v$, in * $b_v < 0$, če je v vozlišču $v$ proizvodnja $-b_v$. Predpostavimo $\sum_{v \in V} b_v = 0$. Iščemo $x_{uv} \ge 0$ za vsako povezavo $uv \in E$, tako da velja **_Kirchhoffov zakon_**: $$ \forall v \in V: \sum_{uv \in E} x_{uv} - \sum_{vu \in E} x_{vu} = b_v. $$ Radi bi minimizirali ceno $\sum_{uv \in E} c_{uv} x_{uv}$. ---- V našem primeru: $$ \begin{aligned} \min &\ & x_{ab} + 3 x_{ac} + x_{bc} + 6 x_{cb} \\[1ex] \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 $$ \begin{aligned} \min \ -b^\top y \\[1ex] \text{p.p.} \quad -A^\top y &\ge -c \end{aligned} $$ in ga ekvivalentno lahko zapišemo kot $$ \begin{aligned} \max \ b^\top y \\[1ex] \text{p.p.} \quad A^\top y &\le c \end{aligned} $$ 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 $$ \begin{aligned} \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 \end{aligned} $$ 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$ ($E' \subseteq E$) rešljiv? ```graphviz 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} $$ ```graphviz 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._** Dopustna rešitev $x$ za problem razvoza $\Pi$ na grafu $G = (V, E)$ je _drevesna dopustna rešitev_, če v grafu $G$ obstaja vpeto drevo $T = (V, E')$, da velja $x_e = 0$ za vsak $e \in E \setminus E'$. ```graphviz 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. ```graphviz 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: ```graphviz 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._** ```graphviz digraph G { rankdir=LR nodesep=0.5 ranksep=1 edge [fontcolor=red] node [label=""] a -> b [label=<<s>6</s>>, xlabel=7] a -> c [label=<<s>3</s>>, xlabel=2] d -> b [label=<<s>5</s>>, xlabel=4, constraint=false] c -> d [style=invis] c -> e [label=<<s>1</s>>, xlabel=0, color=red] d -> e [label=<<s>4</s>>, 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. ```graphviz 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.** 1. 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'$. 2. 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. 3. Ponavljamo, dokler ne pridemo do optimalne rešitve (ali ugotovimo, da je problem neomejen). ---- **_Primer._** ```graphviz digraph G { rankdir=LR nodesep=0.5 ranksep=1 splines=false edge [fontcolor=red,labelfontcolor=black] a [label=5, xlabel=<20>] b [label=-5, xlabel=<15>] c [label=-3, xlabel=<0>] d [label=-2, xlabel=<21>] e [label="", xlabel=<27>] f [label=2, xlabel=<26 >] g [label=3, xlabel=<28>] a -> b [style=invis] a -> c [style=invis] b -> a [taillabel=5, xlabel=2, color=red, constraint=false] c -> a [taillabel=20, label=3, color=red, constraint=false] c -> b [taillabel=5, label="0+5 < 15", color=green, fontcolor=black constraint=false] b -> d [taillabel=6, xlabel=<f>, label=3, color=red, style=dashed] c -> e [taillabel=11, label="0+11 < 27", xlabel=<e>, color=blue, fontcolor=black] d -> e [taillabel=1, label="21+1 < 27", color=green, fontcolor=black, constraint=false] d -> f [taillabel=5, label=5, color=red] e -> g [taillabel=1, label=3, color=red] f -> e [taillabel="1 ", xlabel="3 ", color=red, constraint=false] g -> f [taillabel=1, constraint=false] } ``` Povezavam na ciklu spremenimo razvoz za $3$: ```graphviz digraph G { rankdir=LR nodesep=0.5 ranksep=1 splines=false edge [fontcolor=red,labelfontcolor=black] a [label=5, xlabel=<36>] b [label=-5, xlabel=<31>] c [label=-3, xlabel=<16>] d [label=-2, xlabel=<21>] e [label="", xlabel=<27>] f [label=2, xlabel=<26 >] g [label=3, xlabel=<28>] a -> b [style=invis] a -> c [style=invis] b -> a [taillabel=5, xlabel=5, color=red, constraint=false] c -> a [taillabel=20, label=0, xlabel=<f>, color=red, style=dashed, constraint=false] c -> b [taillabel=5, label="16+5 < 31", xlabel=< e>, color=blue, fontcolor=black, constraint=false] b -> d [taillabel=6] c -> e [taillabel=11, label=3, color=red] d -> e [taillabel=1, label="21+1 < 27", color=green, fontcolor=black, constraint=false] d -> f [taillabel=5, label=2, color=red] e -> g [taillabel=1, label=3, color=red] f -> e [taillabel="1 ", xlabel="0 ", color=red, constraint=false] g -> f [taillabel=1, constraint=false] } ``` Izstopna povezava je imela razvoz $0$ - razvozi se ne spremenijo, spremeni se le drevo in razvozne cene (_izrojen korak_): ```graphviz digraph G { rankdir=LR nodesep=0.5 ranksep=1 splines=false edge [fontcolor=red,labelfontcolor=black] a [label=5, xlabel=<26>] b [label=-5, xlabel=<21>] c [label=-3, xlabel=<16>] d [label=-2, xlabel=<21>] e [label="", xlabel=<27>] f [label=2, xlabel=<26 >] g [label=3, xlabel=<28>] a -> b [style=invis] a -> c [style=invis] b -> a [taillabel=5, xlabel=5, color=red, constraint=false] c -> a [taillabel="20 ", constraint=false] c -> b [taillabel=5, label=0, color=red, constraint=false] b -> d [taillabel=6] c -> e [taillabel=11, label=3, color=red] d -> e [taillabel=1, label="21+1 < 27", xlabel=< e>, color=blue, fontcolor=black, constraint=false] d -> f [taillabel=5, label=2, color=red] e -> g [taillabel=1, label=3, color=red] f -> e [taillabel="1 ", xlabel=<0 f>, color=red, style=dashed, constraint=false] g -> f [taillabel=1, constraint=false] } ``` Še en izrojen korak: ```graphviz digraph G { rankdir=LR nodesep=0.5 ranksep=1 splines=false edge [fontcolor=red,labelfontcolor=black] a [label=5, xlabel=<26>] b [label=-5, xlabel=<21>] c [label=-3, xlabel=<16>] d [label=-2, xlabel=<26>] e [label="", xlabel=<27>] f [label=2, xlabel=<31 >] g [label=3, xlabel=<28>] a -> b [style=invis] a -> c [style=invis] b -> a [taillabel=5, xlabel=5, color=red, constraint=false] c -> a [taillabel="20 ", constraint=false] c -> b [taillabel=5, label=0, color=red, constraint=false] b -> d [taillabel=6] c -> e [taillabel=11, label=3, color=red] d -> e [taillabel=1, label=0, color=red, constraint=false] d -> f [taillabel=5, label=2, xlabel=<f>, color=red, style=dashed] e -> g [taillabel=1, label=3, color=red] f -> e [taillabel="1 ", constraint=false] g -> f [taillabel=1, label="28+1 < 31", xlabel=< e>, color=blue, fontcolor=black, constraint=false] } ``` Povezavam na ciklu spremenimo razvoz za $2$: ```graphviz digraph G { rankdir=LR nodesep=0.5 ranksep=1 splines=false edge [fontcolor=red,labelfontcolor=black] a [label=5, xlabel=<26>] b [label=-5, xlabel=<21>] c [label=-3, xlabel=<16>] d [label=-2, xlabel=<26>] e [label="", xlabel=<27>] f [label=2, xlabel=<29 >] g [label=3, xlabel=<28>] a -> b [style=invis] a -> c [style=invis] b -> a [taillabel=5, xlabel=5, color=red, constraint=false] c -> a [taillabel=20, label="16+20 ≥ 26", fontcolor=black, constraint=false] c -> b [taillabel=5, label=0, color=red, constraint=false] b -> d [taillabel=6, label="21+6 ≥ 26", fontcolor=black] c -> e [taillabel=11, label=3, color=red] d -> e [taillabel=1, label=2, color=red, constraint=false] d -> f [taillabel=5, label="26+5 ≥ 29", fontcolor=black] e -> g [taillabel=1, label=5, color=red] f -> e [taillabel="1 ", xlabel="29+1 ≥ 27 ", fontcolor=black, constraint=false] g -> f [taillabel=1, label=2, color=red, constraint=false] } ``` Ni več kandidatov za vstop - dobili smo optimalno rešitev s ceno $$ \sum_{e \in E} c_e x_e = 5 \cdot 5 + 5 \cdot 0 + 11 \cdot 3 + 1 \cdot 2 + 1 \cdot 5 + 1 \cdot 2 = 67. $$ Preverimo še optimalno vrednost dualnega problema: $$ \sum_{v \in V} b_v y_v = 5 \cdot 26 + (-5) \cdot 21 + (-3) \cdot 16 + (-2) \cdot 26 + 0 \cdot 27 + 2 \cdot 29 + 3 \cdot 28 = 67 $$ ---- **Opomba.** Če je $y_u + c_{uv} < y_v$ in je $C$ cikel v $H$, ki vsebuje $uv$, to pomeni, da je $$ \sum_{e \in C \text{ prema}} c_e - \sum_{e \in C \text{ obratna}} c_e < 0. $$ ```graphviz 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] a -> b a -> c [style=dashed, color=blue] d -> b [constraint=false] c -> d [style=invis] c -> e d -> e [constraint=false] } ``` $$ \begin{aligned} y_b &= y_a + c_{ab} \\ y_d &= y_b - c_{db} \\ &= y_a + c_{ab} - c_{db} \\ y_e &= y_d + c_{de} \\ &= y_a + c_{ab} - c_{db} + c_{de} \\ y_c &= y_e - c_{ce} \\ &= y_a + c_{ab} - c_{db} + c_{de} - c_{ce} \\[1ex] y_a + c_{ac} &< y_a + c_{ab} - c_{db} + c_{de} - c_{ce} \\ 0 &> c_{ac} + c_{ce} - c_{de} + c_{db} - c_{ab} \end{aligned} $$ Ko razvoz na premih povezavah povečamo za $p$ in ga na obratnih povezavah zmanjšamo za $p$, se cena poveča za $$ p (c_{ac} + c_{ce} - c_{de} + c_{db} - c_{ab}) $$ oziroma v splošnem za $$ p \left(\sum_{e \in C \text{ prema}} c_e - \sum_{e \in C \text{ obratna}} c_e\right). $$ Če je $p > 0$, se cena torej zmanjša. **Opomba.** Če ne moremo izbrati izstopne povezave, so vse povezave na $C$ preme in velja $\sum_{e \in C} c_e < 0$. Našli smo negativen cikel, problem razvoza je torej neomejen. **_Trditev._** Če velja $\forall uv \in E: \ y_u + c_{uv} \ge y_v$ (z enakostjo pri vseh povezavah $uv \in E'$ vpetega drevesa $T = (V, E')$), je rešitev optimalna. _Dokaz._ Naj bo $x'$ še ena dopustna rešitev. Potem velja $$ \forall uv \in E: \ (y_u + c_{uv} - y_v) x_{uv}' \ge (y_u + c_{uv} - y_v) x_{uv} = 0, $$ saj * če $uv \in E'$, potem $y_u + c_{uv} - y_v = 0$, in * če $uv \not\in E'$, potem $x_{uv} = 0$, $(y_u + c_{uv} - y_v) x_{uv}' \ge 0$. Če seštejemo za vse povezave, dobimo $$ \begin{aligned} 0 &\le \sum_{uv \in E} c_{uv} (x_{uv}' - x_{uv}) - \sum_{uv \in E} (y_v - y_u) (x_{uv}' - x_{uv}) = c^\top (x' - x) - (A^\top y)^\top (x' - x) = \\ &= c^\top x' - c^\top x - y^\top A x' + y^\top A x = c^\top x' - c^\top x - y^\top b + y^\top b . \end{aligned} $$ Velja torej $c^\top x' \ge c^\top x$. **Opomba.** Tudi pri simpleksni metodi za omrežja lahko pride do ciklanja. Temu se lahko izognemo z uporabo _Cunninghamovega pravila_: * 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 kandidata na $C$ od $z$ naprej v smeri $uv$. ```graphviz digraph G { rankdir=LR nodesep=0.5 ranksep=1 node [label=""] r -> a a -> b [style=invis] b -> a [constraint=false] b -> z z -> c [color=green] z -> d c -> e [style=invis] e -> c [constraint=false] d -> f [label=e, color=blue, fontcolor=blue] e -> g [color=green] g -> f [label=f, fontcolor=blue, color=green, style=dashed, constraint=false] r [xlabel=r] z [xlabel=z] d [xlabel=u] f [xlabel=v] } ``` --- Kako pridemo do začetne dopustne rešitve oziroma dokažemo, da je problem nedopusten? Uporabimo **dvofazno simpleksno metodo na omrežjih**. 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 $b_v < 0$ in povezava $vr$ ne obstaja, jo dodamo. * 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$. Ta problem je vedno dopusten: * $x_{rv} = b_v$ za vse $v \in V \setminus \{r\}$ z $b_v \ge 0$, * $x_{vr} = -b_v$ za vse $v \in V \setminus \{r\}$ z $b_v < 0$, * $x_e = 0$ za vse ostale povezave $e \in \tilde{E}$. Kirchhofovi zakoni: * $v \ne r$, $b_v \ge 0$: $x_{rv} = b_v$ * $v \ne r$, $b_v < 0$: $-x_{vr} = b_v$ * $v = r$: $-\sum_{\substack{u \ne r \\ b_u \ge 0}} x_{ru} + \sum_{\substack{u \ne r \\ b_u < 0}} x_{ur} = -\sum_{\substack{u \ne r \\ b_u \ge 0}} b_u + \sum_{\substack{u \ne r \\ b_u < 0}} (-b_u) = -\sum_{u \ne r} b_u = b_r$ Prvotni problem je dopusten natanko tedaj, ko je optimalna vrednost pomožnega problema enaka $0$. Ker so vse cene v pomožnem problemu nenegativne, je problem omejen. **_Primer._** Dokaži, da je problem nedopusten. ```graphviz digraph G { rankdir=TD nodesep=1 ranksep=1 a [label=1] b [label=-3] c [label=-2] r [label=0, xlabel="r "] d [label=4] a -> c [style=invis] a -> r [taillabel=" 1"] b -> a [taillabel=3, constraint=false] b -> r [taillabel="4 "] b -> d [taillabel=2] c -> a [taillabel=" 1", headport=sw, constraint=false] c -> r [taillabel=2, constraint=false] d -> r [taillabel=1, constraint=false] } ``` Narišimo graf za pomožni problem in določimo začetno drevesno rešitev. ```graphviz digraph G { rankdir=TD nodesep=0.5 ranksep=1 edge [fontcolor=red,labelfontcolor=black] a [label=1, xlabel=<1>] b [label=-3, xlabel=<0>] c [label=-2, xlabel=<0>] r [label=0, xlabel=<0>] d [label=4, xlabel=<1>] a -> c [style=invis] a -> r [taillabel="\n 0"] b -> a [taillabel=0, xlabel=<e>, color=blue, constraint=false] b -> r [taillabel="0 ", label=3, color=red] b -> d [taillabel=0, color=green] c -> a [taillabel=" 0", color=green, constraint=false] c -> r [taillabel=0, label=2, color=red, constraint=false] d -> r [taillabel=" 0", constraint=false] r -> a [taillabel="1 ", label=1, xlabel=<f >, style=dashed, color=red, constraint=false] r -> d [taillabel=1, label=4, color=red, constraint=false] } ``` ```graphviz digraph G { rankdir=TD nodesep=0.5 ranksep=1 edge [fontcolor=red,labelfontcolor=black] a [label=1, xlabel=<0>] b [label=-3, xlabel=<0>] c [label=-2, xlabel=<0>] r [label=0, xlabel=<0>] d [label=4, xlabel=<1>] a -> c [style=invis] a -> r [taillabel="\n 0"] b -> a [taillabel=0, label=1, color=red, constraint=false] b -> r [taillabel="0 ", label=2, xlabel=<f>, style=dashed, color=red] b -> d [taillabel=0, xlabel=<e >, color=blue] c -> a [taillabel=0, constraint=false] c -> r [taillabel=0, label=2, color=red, constraint=false] d -> r [taillabel=" 0", constraint=false] r -> a [taillabel="1 ", constraint=false] r -> d [taillabel=1, label=4, color=red, constraint=false] } ``` ```graphviz digraph G { rankdir=TD nodesep=0.5 ranksep=1 edge [fontcolor=red,labelfontcolor=black] a [label=1, xlabel=<1>] b [label=-3, xlabel=<1>] c [label=-2, xlabel=<0>] r [label=0, xlabel=<0>] d [label=4, xlabel=<1>] a -> c [style=invis] a -> r [taillabel="\n 0"] b -> a [taillabel=0, label=1, xlabel=<f>, style=dashed, color=red, constraint=false] b -> r [taillabel="0 "] b -> d [taillabel=0, label=2, color=red] c -> a [taillabel=0, xlabel=<e>, color=blue, constraint=false] c -> r [taillabel=0, label=2, color=red, constraint=false] d -> r [taillabel=" 0", constraint=false] r -> a [taillabel="1 ", constraint=false] r -> d [taillabel=1, label=2, color=red, constraint=false] } ``` ```graphviz digraph G { rankdir=TD nodesep=0.5 ranksep=1 edge [fontcolor=red,labelfontcolor=black] a [label=1, xlabel=<0>] b [label=-3, xlabel=<1>] c [label=-2, xlabel=<0>] r [label=0, xlabel=< 0>] d [label=4, xlabel=<1>] a -> c [style=invis] a -> r [taillabel="\n0"] b -> a [taillabel=0, constraint=false] b -> r [taillabel="0 "] b -> d [taillabel=0, label=3, color=red] c -> a [taillabel=0, xlabel=1, color=red, constraint=false] c -> r [taillabel=0, label=1, color=red, constraint=false] d -> r [taillabel=" 0", constraint=false] r -> a [taillabel="1 ", constraint=false] r -> d [taillabel=1, label=1, color=red, constraint=false] } ``` Ni več kandidatov za vstop - imamo optimalno rešitev pomožnega problema. Ker ta vključuje umetno povezavo s pozitivnim razvozom, je prvotni problem nedopusten. ---- **Opomba.** Če je $\sum_{v \in V} b_v > 0$, ne moremo zadostiti vsem potrebam. Če je $\sum_{v \in V} b_v < 0$, dodamo umetno vozlišče $s \not\in V$ ("skladišče") in povezavo od vseh izvorov (vozlišč $v \in V$ z $b_v < 0$) do $s$ s ceno $0$ ter določimo $b_s = -\sum_{v \in V} b_v$. **_Izrek o celoštevilskih rešitvah._** Dan je problem razvoza s celoštevilskimi vrednostmi $b_v$ ($v \in V$). 1. Če obstaja dopustna rešitev, obstaja tudi celoštevilska dopustna rešitev. 2. Če obstaja optimalna rešitev, obstaja tudi celoštevilska optimalna rešitev. _Dokaz._ Naredimo dvofazno simpleksno metodo na omrežjih. Na vsakem koraku imamo celoštevilsko rešitev; če je problem dopusten, dobimo celoštevilsko dopustno rešitev. Tedaj naredimo še drugo fazo, na vsakem koraku imamo celoštevilsko rešitev. Če pridemo do optimalne rešitve, bo ta celoštevilska. --- **_Definicija._** Matrika $A = (a_{ij})_{i,j=1}^n \in \mathbb{R}^{n \times n}$ je _dvojno stohastična_, če velja $a_{ij} \ge 0$ ($1 \le i, j \le n$) ter $\sum_{j=1}^n a_{ij} = 1$ ($1 \le i \le n$) in $\sum_{i=1}^n a_{ij} = 1$ ($1 \le j \le n$). **_Primer_** dvojno stohastične matrike: $$ \begin{bmatrix} 0 & 0.9 & 0.1 \\ 0.4 & 0.1 & 0.5 \\ 0.6 & 0 & 0.4 \end{bmatrix} $$ **_Definicija._** Matrika $P = (p_{ij})_{i,j=1}^n \in \{0, 1\}^{n \times n}$ je _permutacijska matrika_, če je v vsaki vrstici in v vsakem stolpcu natanko ena enica. **_Primeri_** za $n = 3$: $$ \begin{array}{cccccc} \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}, & \begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix}, & \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}, & \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{bmatrix}, & \begin{bmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix}, & \begin{bmatrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{bmatrix} \\ 123 & 132 & 213 & 231 & 312 & 321 \end{array} $$ Imamo $n!$ permutacijskih matrik velikosti $n \times n$. Permutacijske matrike so dvojno stohastične. **_Trditev._** Naj bo $A \in \mathbb{R}^{n \times n}$ dvojno stohastična matrika. Potem obstaja permutacijska matrika $P \in \{0, 1\}^{n \times n}$, tako da velja $p_{ij} = 1 \Rightarrow a_{ij} > 0$ ($1 \le i, j \le n$). _Dokaz._ Naj bo $G = (V, E)$ usmerjen graf z množico vozlišč $V = \{v_i, s_i \mid 1 \le i \le n\}$ in množico povezav $E = \{v_i s_j \mid a_{ij} > 0\}$. Postavimo še $b_{v_i} = -1$, $b_{s_i} = 1$ ($1 \le i \le n$) in $c_{v_i s_j} = 0$ ($v_i s_j \in E$). Dobljeni problem razvoza je dopusten, saj obstaja dopustna rešitev z $x_{v_i s_j} = a_{ij}$ ($v_i s_j \in E$): $$ \begin{alignedat}{4} v_i&:& -\sum_{v_i s_j \in E} x_{v_i s_j} &=& -\sum_{j=1}^n a_{ij} &=& -1 &= b_{v_i} \\ s_j&:& \sum_{v_i s_j \in E} x_{v_i s_j} &=& \sum_{i=1}^n a_{ij} &=& 1 &= b_{s_j} \end{alignedat} $$ Ker obstaja dopustna rešitev $x$, obstaja tudi celoštevilska dopustna rešitev $x'$: $$ \begin{alignedat}{3} v_i&:& -\sum_{v_i s_j \in E} x_{v_i s_j}' &=& -1 &= b_{v_j}, \\ s_j&:& \sum_{v_i s_j \in E} x_{v_i s_j}' &=& 1 &= b_{s_j}, \end{alignedat} $$ kjer je v zgornjih vsotah natanko eden od $x_{v_i s_j}'$ enak $1$, ostali pa so enaki $0$. Tako lahko dobimo permutacijsko matriko $P$, kjer je $p_{ij} = 1$, če je $x_{v_i s_j}' = 1$, in $p_{ij} = 0$ sicer. Očitno potem velja $p_{ij} = 1 \Rightarrow a_{ij} > 0$ ($1 \le i, j \le n$). Tako permutacijsko matriko lahko najdemo z dvofazno simpleksno metodo na omrežjih. V našem primeru: ```graphviz digraph G { rankdir=TD nodesep=0.5 ranksep=1 edge [fontcolor=red] v1 [label=-1] v2 [label=-1] v3 [label=-1] s1 [label=1] s2 [label=1] s3 [label=1] v1 -> s2 [label=0.9] v1 -> s3 [label=0.1] v2 -> s1 [label=0.4] v2 -> s2 [label=0.1] v2 -> s3 [label=" 0.5"] v3 -> s1 [label=" 0.6"] v3 -> s3 [label=0.4] } ``` **_Definicija._** Naj bo $G = (V, E)$ neusmerjen graf. Množici $M \subseteq E$ pravimo _prirejanje_, če nobeni dve povezavi iz $M$ nimata skupnega krajišča (tj., $\forall e, f \in M: (e \ne f \Rightarrow e \cap f = \emptyset)$). Prirejanje $M$ je _popolno prirejanje_, če je vsako vozlišče grafa $G$ krajišče povezave iz $M$ (tj., $\forall v \in V \ \exists e \in M: v \in e$). **_Kőnigov izrek o plesnih parih._** Naj bo $G = (V, E)$ dvodelen regularen graf (tj., lahko zapišemo $V = X + Y$, tako da $\forall xy \in E: (x \in X \land y \in Y)$, ter $\exists r \in \mathbb{N} \ \forall v \in V: \deg(v) = r$). Potem obstaja popolno prirejanje $M \subseteq E$ v grafu $G$. **Opomba.** Če imamo $n$ deklet in $n$ fantov ter vsako dekle pozna $r$ fantov in vsak fant pozna $r$ deklet, potem lahko vsako dekle pleše s fantom, ki ga pozna. ```graphviz graph G { rankdir=TD nodesep=0.5 ranksep=1 node [label=""] d1 -- f1 [color=red] d1 -- f2 [style=invis] d1 -- f3 d1 -- f4 [style=invis] d2 -- f1 [style=invis] d2 -- f2 [style=invis] d2 -- f3 [color=red] d2 -- f4 d3 -- f1 d3 -- f2 [color=red] d3 -- f3 [style=invis] d3 -- f4 [style=invis] d4 -- f1 [style=invis] d4 -- f2 d1 -- f3 [style=invis] d4 -- f4 [color=red] } ``` _Dokaz._ Naj bo $X = \{x_1, x_2, \dots x_n\}$ in $Y = \{y_1, y_2, \dots y_n\}$. Definirajmo matriko $A = (a_{ij})_{i,j=1}^n$ z $$ a_{ij} = \begin{cases} {1 \over r} & x_i \sim y_j, \\ 0 & \text{sicer.} \end{cases} $$ Matrika $A$ je dvojno stohastična, saj velja $$ \begin{aligned} \sum_{j=1}^n a_{ij} &= {1 \over r} \cdot r = 1 & (1 \le i \le n) \\ \sum_{i=1}^n a_{ij} &= {1 \over r} \cdot r = 1 & (1 \le j \le n) \end{aligned} $$ Po prejšnji trditvi obstaja permutacijska matrika $P = (p_{ij})_{i,j=1}^n$, tako da $$ p_{ij} = 1 \ \Rightarrow\ a_{ij} > 0 \ \Rightarrow\ a_{ij} = {1 \over r} \ \Rightarrow\ x_i \sim y_j \quad (1 \le i, j \le n) $$ Matrika $P$ določa popolno prirejanje $M$: $$ p_{ij} = 1 \ \Leftrightarrow\ x_i y_j \in M \quad (1 \le i, j \le n) $$ --- ### 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}{3} \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.** 1. 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'$. 2. 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 prejšnji trditvi). * 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. 3. Ponavljamo, dokler ne pridemo do optimalne rešitve (ali ugotovimo, da je problem neomejen). **_Primer._** ```graphviz digraph G { rankdir=LR nodesep=0.5 ranksep=1 edge [fontcolor=red,labelfontcolor=black] a [label=-8, xlabel=<0>] b [label=2, xlabel=<3>] c [label=3, xlabel=<    1>] d [label=3, xlabel=<7>] a -> b [taillabel=3, label=<8 ≤ 9>, color=red, constraint=false] a -> c [taillabel=1, label=<0 ≤ 2>, color=red, style=dashed, xlabel=<f>] b -> c [taillabel=2, label=<3 ≤ 3>, style=bold, color=blue, xlabel=< e 3+2 > 1>, fontcolor=black] b -> d [taillabel=4, label=<3 ≤ 4>, color=red] c -> d [taillabel=1, label=< ≤ 5>, 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. ```graphviz digraph G { rankdir=LR nodesep=0.5 ranksep=1 edge [fontcolor=red,labelfontcolor=black] a [label=-8, xlabel=<0>] b [label=2, xlabel=<3>] c [label=3, xlabel=<    5>] d [label=3, xlabel=<7>] a -> b [taillabel=3, label=<6 ≤ 9>, color=red, constraint=false] a -> c [taillabel=1, label=<2 ≤ 2>, style=bold] b -> c [taillabel=2, label=<1 ≤ 3>, color=red, style=dashed, xlabel=<f>] b -> d [taillabel=4, label=<3 ≤ 4>, color=red] c -> d [taillabel=1, label=< ≤ 5>, xlabel=<e 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. ```graphviz digraph G { rankdir=LR nodesep=0.5 ranksep=1 edge [fontcolor=red,labelfontcolor=black] a [label=-8, xlabel=<0>] b [label=2, xlabel=<3>] c [label=3, xlabel=<    6>] d [label=3, xlabel=<7>] a -> b [taillabel=3, label=<6 ≤ 9>, color=red, constraint=false] a -> c [taillabel=1, label=<2 ≤ 2>, style=bold, xlabel="0+1 < 6 ", fontcolor=black] b -> c [taillabel=2, label=<3 ≤ 3>, style=bold, xlabel="3+2 < 6 ", fontcolor=black] b -> d [taillabel=4, label=<1 ≤ 4>, color=red] c -> d [taillabel=1, label=<2 ≤ 5>, 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. ```graphviz digraph G { rankdir=LR nodesep=0.5 ranksep=1 edge [fontcolor=red] node [label=""] a -> b [label=<2 ≤ 3>, color=red] a -> c [label=<≤ 1>, xlabel=<e = f>, color=blue, style=dashed] c -> b [label=<1 ≤ 5>, 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. ```graphviz digraph G { rankdir=LR nodesep=0.5 ranksep=1 edge [fontcolor=red] node [label=""] a -> b [label=<1 ≤ 3>, color=red] a -> c [label=<1 ≤ 1>, style=bold] c -> b [label=<2 ≤ 5>, 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. --- ## Pretoki in prerezi **_Primer._** Letalo iz San Francisca v New York je polno. Imamo pa proste sedeže na drugih letih: * San Francisco - Denver: 5 mest * San Francisco - Houston: 6 mest * Denver - Atlanta: 2 mesti * Denver - Chicago: 5 mest * Houston - Atlanta: 5 mest * Atlanta - New York: 7 mest * Chicago - New York: 4 mesta Koliko dodatnih potnikov lahko prepeljejo? ```graphviz digraph G { rankdir=LR nodesep=0.5 ranksep=1 SFO [xlabel=s] JFK [xlabel=t] SFO -> DEN [headlabel=" 5 "] SFO -> IAH [headlabel=" 6 "] DEN -> ATL [headlabel="2 "] DEN -> ORD [headlabel=5] IAH -> ATL [headlabel=5] ATL -> JFK [headlabel=7] ORD -> JFK [headlabel=4] } ``` Imamo usmerjen graf $G = (V, E)$ in pretočnosti $d_e$ za vsako povezavo $e \in E$. Iščemo maksimalni pretok: $$ \forall e \in E: \ 0 \le x_e \le d_e $$ Imamo dve posebni vozlišči: * začetno vozlišče $s$ (angl. _source_) * končno vozlišče $t$ (angl. _terminal_) Predpostavimo, da v $s$ in iz $t$ ne gre nobena povezava. Za ostala vozlišča veljajo Kirchhoffovi zakoni: $$ \forall w \in V \setminus \{s, t\}: \ \sum_{uw \in E} x_{uw} = \sum_{wv \in E} x_{wv} $$ Seštejmo Kirchhoffove zakone po vseh $w \in V \setminus \{s, t\}$: $$ \begin{aligned} \sum_{w \in V \setminus \{s, t\}} \sum_{uw \in E} x_{uw} &= \sum_{w \in V \setminus \{s, t\}} \sum_{wv \in E} x_{wv} \\ \sum_{\substack{e \in E \\ \operatorname{konec}(e) \ne t}} x_e &= \sum_{\substack{e \in E \\ \operatorname{začetek}(e) \ne s}} x_e \end{aligned} $$ _Prostornina pretoka_ je enaka $$ F \quad = \sum_{\substack{e \in E \\ \operatorname{konec}(e) = t}} x_e = \sum_{\substack{e \in E \\ \operatorname{začetek}(e) = s}} x_e $$ Iščemo _pretok_ z maksimalno prostornino: $$ \begin{alignedat}{2} \max &\ & \sum_{\substack{e \in E \\ \operatorname{začetek}(e) = s}} x_e \\[1ex] \text{p.p.} \quad \forall w \in V \setminus \{s, t\}&:& \ \sum_{uw \in E} x_{uw} &= \sum_{wv \in E} x_{wv} \\ \forall uv \in E&:& \ 0 \le x_{uv} &\le d_{uv}, \end{alignedat} $$ To je poseben primer problema razvoza z omejitvami: vzamemo $b_v = 0$ ($v \in V$), $c_e = 0$ ($e \in E$) ter dodamo povezavo $ts$ s $c_{ts} = -1$, $d_{ts} = \infty$. ```graphviz digraph G { rankdir=LR nodesep=0.5 ranksep=1 node [label=""] edge [taillabel=0] SFO [xlabel=s] JFK [xlabel="t "] SFO -> DEN [xlabel=<≤ 5>] SFO -> IAH [xlabel=<≤ 6>] DEN -> ATL [xlabel=<≤ 2>] DEN -> ORD [xlabel=<≤ 5>] IAH -> ATL [xlabel=<≤ 5>] ATL -> JFK [xlabel=<≤ 7>] ORD -> JFK [xlabel=<≤ 4>] JFK -> SFO [taillabel=-1, constraint=false] } ``` Ta problem lahko rešimo s simpleksno metodo na omrežjih za problem razvoza z omejitvami. ```graphviz digraph G { rankdir=LR nodesep=0.5 ranksep=1 edge [fontcolor=red,labelfontcolor=black] node [label="", fontcolor=blue] SFO [xlabel=0] DEN [xlabel=0] IAH [xlabel=0] ATL [xlabel=0] ORD [xlabel=0] JFK [xlabel=0] SFO -> DEN [taillabel=" 0 ", label=<0 ≤ 5>, color=red] SFO -> IAH [taillabel=0, label=<0 ≤ 6>, color=red] DEN -> ATL [taillabel=" 0", label=<≤ 2>] DEN -> ORD [taillabel=0, label=<0 ≤ 5>, color=red] IAH -> ATL [taillabel=0, label=<0 ≤ 5>, xlabel=<f>, color=red, style=dashed] ATL -> JFK [taillabel=0, label=<0 ≤ 7>, color=red] ORD -> JFK [taillabel=0, label=<≤ 4>] JFK -> SFO [taillabel=-1, xlabel=<e 0+(-1) < 0>, color=blue, fontcolor=blue, constraint=false] } ``` ```graphviz digraph G { rankdir=LR nodesep=0.5 ranksep=1 edge [fontcolor=red,labelfontcolor=black] node [label="", fontcolor=blue] SFO [xlabel=0] DEN [xlabel=0] IAH [xlabel=0] ATL [xlabel=1] ORD [xlabel=0] JFK [xlabel=1] SFO -> DEN [taillabel=" 0 ", label=<0 ≤ 5>, color=red] SFO -> IAH [taillabel=0, label=<5 ≤ 6>, color=red] DEN -> ATL [taillabel=" 0", label=<≤ 2>, color=green] DEN -> ORD [taillabel=0, label=<0 ≤ 5>, color=red] IAH -> ATL [taillabel=0, label=<5 ≤ 5>, style=bold] ATL -> JFK [taillabel=0, label=<5 ≤ 7>, color=red] ORD -> JFK [taillabel=0, label=<≤ 4>, xlabel="e = f", color=blue, fontcolor=blue, style=dashed] JFK -> SFO [taillabel=-1, label=5, color=red, constraint=false] } ``` ```graphviz digraph G { rankdir=LR nodesep=0.5 ranksep=1 edge [fontcolor=red,labelfontcolor=black] node [label="", fontcolor=blue] SFO [xlabel=0] DEN [xlabel=0] IAH [xlabel=0] ATL [xlabel=1] ORD [xlabel=0] JFK [xlabel=1] SFO -> DEN [taillabel=" 0 ", label=<4 ≤ 5>, xlabel=<f>, color=red, style=dashed] SFO -> IAH [taillabel=0, label=<5 ≤ 6>, color=red] DEN -> ATL [taillabel=" 0", label=<≤ 2>, xlabel=e, color=blue, fontcolor=blue] DEN -> ORD [taillabel=0, label=<4 ≤ 5>, color=red] IAH -> ATL [taillabel=0, label=<5 ≤ 5>, style=bold] ATL -> JFK [taillabel=0, label=<5 ≤ 7>, color=red] ORD -> JFK [taillabel=0, label=<4 ≤ 4>, style=bold] JFK -> SFO [taillabel=-1, label=9, color=red, constraint=false] } ``` ```graphviz digraph G { rankdir=LR nodesep=0.5 ranksep=1 edge [fontcolor=red,labelfontcolor=black] node [label=""] SFO [xlabel=<0>] DEN [xlabel=<1>] IAH [xlabel=<0>] ATL [xlabel=<1>] ORD [xlabel=<1>] JFK [xlabel=<1>] SFO -> DEN [taillabel=" 0 ", label=<5 ≤ 5>, style=bold] SFO -> IAH [taillabel=0, label=<5 ≤ 6>, color=red] DEN -> ATL [taillabel=" 0", label=<1 ≤ 2>, color=red] DEN -> ORD [taillabel=0, label=<4 ≤ 5>, color=red] IAH -> ATL [taillabel=0, label=<5 ≤ 5>, style=bold] ATL -> JFK [taillabel=0, label=<6 ≤ 7>, color=red] ORD -> JFK [taillabel=0, label=<4 ≤ 4>, style=bold] JFK -> SFO [taillabel=-1, label=10, color=red, constraint=false] } ``` V praksi uporabljamo **Ford-Fulkersonov algoritem**. **_Definicija._** Naj bo $x$ dopustna rešitev za problem maksimalnega pretoka na usmerjenem grafu $G = (V, E)$ s pretočnostmi $d_e$ ($e \in E$) ter začetnim vozliščem $s$ in končnim vozliščem $t$. Rečemo, da je $v_0 v_1 \dots v_k$ ($v_i \in V, 0 \le i \le k$) _povečujoča pot_, če je $v_0 = s$, $v_k = t$ ter, za $1 \le i \le k$, * $v_{i-1} v_i \in E$ in $x_{v_{i-1} v_i} < d_{v_{i-1} v_i}$ (_prema povezava_), ali * $v_i v_{i-1} \in E$ in $x_{v_i v_{i-1}} > 0$ (_obratna povezava_). Ideja: vzamemo povečujočo pot z množico povezav $P$. Pretok na tej poti povečamo za $$ p = \min(\{x_e \mid e \in P \text{ obratna}\} \cup \{d_e - x_e \mid e \in P \text{ prema}\}) $$ (tj., povečamo na premih in zmanjšamo na obratnih povezavah). ```graphviz digraph G { rankdir=LR node [label=""] au [style=invis] ad [style=invis] bu [style=invis] bd [style=invis] cu [style=invis] cd [style=invis] du [style=invis] dd [style=invis] s [xlabel=s] x [style=invis] t [xlabel=t] 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"] s -> x -> t [label="+p"] } ``` **_Primer._** ```graphviz digraph G { rankdir=LR nodesep=0.5 ranksep=1 node [label=""] SFO [xlabel=s] JFK [xlabel=t] SFO -> DEN [taillabel=1, headlabel=0, color=red] SFO -> IAH [taillabel=2, headlabel=0] DEN -> ATL [taillabel=2, headlabel=0, color=red] DEN -> ORD [taillabel=3, headlabel=0] IAH -> ATL [taillabel=3, headlabel=0] ATL -> JFK [taillabel=1, headlabel=0, color=red] ORD -> JFK [taillabel=2, headlabel=0] } ``` Povečamo pretok na izbrani poti za 1: ```graphviz digraph G { rankdir=LR nodesep=0.5 ranksep=1 SFO [label="", xlabel=s] DEN [label=""] IAH [label=""] ATL [label=""] ORD [label=""] JFK [label="", xlabel=t] SFO -> DEN [taillabel=0, headlabel=1, style=bold] SFO -> IAH [taillabel=2, headlabel=0, color=red] DEN -> ATL [taillabel=1, headlabel=1, color=red] DEN -> ORD [taillabel=3, headlabel=0, color=red] IAH -> ATL [taillabel=3, headlabel=0, color=red] ATL -> JFK [taillabel=0, headlabel=1, style=bold] ORD -> JFK [taillabel=2, headlabel=0, color=red] } ``` Najbolj nas omejuje obratna povezava - spet povečamo pretok za $1$: ```graphviz digraph G { rankdir=LR nodesep=0.5 ranksep=1 node [label=""] SFO [xlabel=s] JFK [xlabel=t] SFO -> DEN [taillabel=0, headlabel=1, style=bold] SFO -> IAH [taillabel=1, headlabel=1] DEN -> ATL [taillabel=2, headlabel=0] DEN -> ORD [taillabel=2, headlabel=1] IAH -> ATL [taillabel=2, headlabel=1] ATL -> JFK [taillabel=0, headlabel=1, style=bold] ORD -> JFK [taillabel=1, headlabel=1] } ``` Takih poti ni več - imamo optimalno rešitev. --- **_Definicija._** Za problem maksimalnega pretoka na usmerjenem grafu $G = (V, E)$ ter začetnim vozliščem $s$ in končnim vozliščem $t$ je množica $C \subseteq V$ je _prerez_, če velja $s \in C$, $t \not\in C$. Za vsaki vozlišči $u, v \in V$, tako da velja $uv \not\in E$, naj velja $x_{uv} = 0$. Potem lahko Kirchhoffove zakone pišemo kot $$ \forall w \in V \setminus \{s, t\}: \ \sum_{u \in V} x_{uw} = \sum_{v \in V} x_{wv} $$ Seštejmo za vsak $w \in C \setminus \{s\}$: $$ \sum_{\substack{u \in V \\ v \in C \setminus \{s\}}} x_{uv} = \sum_{\substack{u \in C \setminus \{s\} \\ v \in V}} x_{uv} $$ Členi $x_{uv}$, kjer $u, v \in C \setminus \{s\}$, se pojavijo na obeh straneh in se jih lahko znebimo: $$ \sum_{\substack{u \not\in C \setminus \{s\} \\ v \in C \setminus \{s\}}} x_{uv} = \sum_{\substack{u \in C \setminus \{s\} \\ v \not\in C \setminus \{s\}}} x_{uv} $$ Ker $s$ ni končno vozlišče nobene povezave, velja $$ \sum_{\substack{u \in C \\ v \not\in C}} x_{uv} - \sum_{\substack{u \not\in C \\ v \in C}} x_{uv} = \sum_{v \not\in C} x_{sv} + \sum_{\substack{u \in C \setminus \{s\} \\ v \not\in C \setminus \{s\}}} x_{uv} - \left(\sum_{\substack{u \not\in C \setminus \{s\} \\ v \in C \setminus \{s\}}} x_{uv} - \sum_{v \in C} x_{sv}\right) = \sum_{v \in V} x_{sv} = F $$ Prostornina pretoka torej zadošča enakosti $$ F = \sum_{\substack{u \in C \\ v \not\in C}} x_{uv} - \sum_{\substack{u \not\in C \\ v \in C}} x_{uv} $$ Definirajmo še _kapaciteto prereza_ $C$ kot $$ K = \sum_{\substack{u \in C \\ v \not\in C}} d_{uv} $$ **_Trditev_.** Naj bosta $x$ in $C$ pretok s prostornino $F$ in prerez s kapaciteto $K$ za problem maksimalnega pretoka. Potem velja $F \le K$. _Dokaz._ $$ F = \sum_{\substack{u \in C \\ v \not\in C}} x_{uv} - \sum_{\substack{u \not\in C \\ v \in C}} x_{uv} \le \sum_{\substack{u \in C \\ v \not\in C}} d_{uv} - \sum_{\substack{u \not\in C \\ v \in C}} 0 = K $$ **Opomba.** Primerjaj s šibkim izrekom o dualnosti! **_Posledica._** Če velja $F = K$, je $x$ maksimalen pretok, $C$ pa minimalen prerez. Govorimo torej o **problemu maksimalnega pretoka in minimalnega prereza** (angl. _maximal flow/minimal cut_). **_Izrek._** Za problem maksimalnega pretoka in minimalnega prereza velja natanko ena od sledečih možnosti. 1. Problem maksimalnega pretoka je neomejen, kapaciteta vsakega prereza je $\infty$. 2. Obstajata maksimalen pretok $x$ in minimalen prerez $C$, tako da je prostornina $x$ enaka kapaciteti $C$. **Opomba.** Primerjaj s krepkim izrekom o dualnosti! _Dokaz._ Problem maksimalnega pretoka na usmerjenem grafu $G = (V, E)$ s pretočnostmi $d_e$ ($e \in E$) ter začetnim vozliščem $s$ in končnim vozliščem $t$ je dopusten linearni program, saj je ničelni pretok dopustna rešitev. Če je neomejen, po zgornji trditvi ne obstaja prerez s končno kapaciteto (sicer bi imeli zgornjo mejo za prostornino). V nasprotnem primeru naj bo $x$ optimalna drevesna rešitev pridruženega problema razvoza z omejitvami za drevo $T = (V, E')$. Naj bodo $y$ razvozne cene. Ker velja $d_{ts} = \infty$, povezava $ts$ ni nasičena. Ker velja $c_{ts} = -1$, sledi $y_t \ge y_s + 1 > y_s$. Potem je $$ C = \{v \in V \mid y_v \le y_s\} $$ prerez, saj velja $s \in C$ in $t \not\in C$. Določimo prostornino pretoka $x$. * Če $u \in C$, $v \not\in C$, potem $y_u + c_{uv} \le y_s < y_v$, torej $uv \not\in E'$ in $x_{uv} = d_{uv}$ (nasičena povezava). * Če $u \not\in C$, $v \in C$, potem $y_u + c_{uv} > y_s \ge y_v$, torej $uv \not\in E'$ in $x_{uv} = 0$ (prazna povezava). Tako velja $$ F = \sum_{\substack{u \in C \\ v \not\in C}} x_{uv} - \sum_{\substack{u \not\in C \\ v \in C}} x_{uv} = \sum_{\substack{u \in C \\ v \not\in C}} d_{uv} = K $$ Sledi, da je $x$ maksimalni pretok in $C$ minimalni prerez. --- Spomnimo se: povečujoča pot sestoji iz premih povezav, ki niso nasičene, in obratnih povezav, ki niso prazne. Kako najdemo povečujočo pot? Začnemo s $C = \{s\}$, nato pa ponavljamo za vsak $v \in C$: ali obstaja $w \not \in C$, da velja $x_{vw} < d_{vw}$ ali $x_{wv} > 0$ - če obstaja, dodamo $w$ v $C$. * Če v nekem koraku dobimo $t \in C$, smo našli povečujočo pot od $s$ do $t$, tako da lahko povečamo pretok. * Če v nekem koraku tak $w$ ne obstaja, povečujoče poti ni - našli smo maksimalni pretok $x$ in minimalni prerez $C$. Običajno problem pretoka rešujemo na pridruženem grafu: ```graphviz digraph G { rankdir=LR nodesep=0.5 ranksep=1 u1 [label=u] v1 [label=v] x1 [style=invis] x2 [style=invis] u2 [label=u] v2 [label=v] u1 -> v1 [taillabel=<duv>] v1 -> x1 [style=invis] x1 -> x2 x2 -> u2 [style=invis] u2 -> v2 [taillabel=<duv - xuv>, headlabel=<xuv>, arrowhead=none] } ``` **_Primer._** ```graphviz digraph G { rankdir=LR nodesep=0.5 ranksep=1 node [label=""] SFO [xlabel=s] JFK [xlabel=t] SFO -> DEN [headlabel=" 0 ", taillabel=5] SFO -> IAH [headlabel=" 0 ", taillabel=6, color=red] DEN -> ATL [headlabel="0 ", taillabel=2] DEN -> ORD [headlabel=0, taillabel=5] IAH -> ATL [headlabel=0, taillabel=<5>, color=red] ATL -> JFK [headlabel=0, taillabel=7, color=red] ORD -> JFK [headlabel=0, taillabel=4] } ``` ```graphviz digraph G { rankdir=LR nodesep=0.5 ranksep=1 node [label=""] SFO [xlabel=s] JFK [xlabel=t] SFO -> DEN [headlabel="0 ", taillabel=5, color=red] SFO -> IAH [headlabel="5 ", taillabel=1] DEN -> ATL [headlabel="0 ", taillabel=2] DEN -> ORD [headlabel=0, taillabel=5, color=red] IAH -> ATL [headlabel=5, taillabel=0, style=bold] ATL -> JFK [headlabel=5, taillabel=2] ORD -> JFK [headlabel=0, taillabel=<4>, color=red] } ``` ```graphviz digraph G { rankdir=LR nodesep=0.5 ranksep=1 node [label=""] SFO [xlabel=s] JFK [xlabel=t] SFO -> DEN [headlabel=" 4 ", taillabel=<1>, color=red] SFO -> IAH [headlabel=" 5 ", taillabel=1] DEN -> ATL [headlabel="0 ", taillabel=2, color=red] DEN -> ORD [headlabel=4, taillabel=1] IAH -> ATL [headlabel=5, taillabel=0, style=bold] ATL -> JFK [headlabel=5, taillabel=2, color=red] ORD -> JFK [headlabel=4, taillabel=0, style=bold] } ``` ```graphviz digraph G { rankdir=LR nodesep=0.5 ranksep=1 node [label=""] SFO [xlabel=s, style=filled] IAH [style=filled] JFK [xlabel=t] SFO -> DEN [headlabel=" 5 ", taillabel=0, style=bold, color=blue] SFO -> IAH [headlabel=" 5 ", taillabel=1] DEN -> ATL [headlabel="1 ", taillabel=1] DEN -> ORD [headlabel=4, taillabel=1] IAH -> ATL [headlabel=5, taillabel=0, style=bold, color=blue] ATL -> JFK [headlabel=6, taillabel=1] ORD -> JFK [headlabel=4, taillabel=0, style=bold] } ``` * Prostornina pretoka: $F = 5 + 5 = 6 + 4 = 10$ * Kapaciteta prereza: $K = 5 + 5 = 10$ Optimalna rešitev: ```graphviz digraph G { rankdir=LR nodesep=0.5 ranksep=1 node [label=""] SFO [xlabel=s, style=filled] IAH [style=filled] JFK [xlabel=t] SFO -> DEN [label=5, style=bold, color=blue] SFO -> IAH [label=5] DEN -> ATL [label=1] DEN -> ORD [label=4] IAH -> ATL [label=5, style=bold, color=blue] ATL -> JFK [label=6] ORD -> JFK [label=4, style=bold] } ``` **Opomba.** Ali se Ford-Fulkersonov algoritem vedno ustavi? **NE.** Obstajajo primeri, kjer lahko (če "nerodno" izbiramo povečujoče poti) v neskončno ponavljamo postopek (če so nekatere pretočnosti iracionalne), pri čemer prostornina pretoka konvergira proti številu, ki je manjše od prostornine maksimalnega pretoka. Da zagotovimo, da se algoritem ustavi, v vsakem koraku izberemo najkrajšo povečujočo pot (Edmonds-Karpov algoritem). **Opomba.** Disjunktne povečujoče poti (po povezavah) lahko obravnavamo hkrati, npr. ```graphviz digraph G { rankdir=LR nodesep=0.5 ranksep=1 node [label=""] SFO [xlabel=s] JFK [xlabel=t] SFO -> DEN [headlabel=" 0 ", taillabel=5, color=green] SFO -> IAH [headlabel=" 0 ", taillabel=6, color=red] DEN -> ATL [headlabel="0 ", taillabel=2] DEN -> ORD [headlabel=0, taillabel=5, color=green] IAH -> ATL [headlabel=0, taillabel=<5>, color=red] ATL -> JFK [headlabel=0, taillabel=7, color=red] ORD -> JFK [headlabel=0, taillabel=<4>, color=green] } ```