Linearni program $\Pi = \Pi’’$:
\[\begin{aligned} \max \ c^\top x \\ A x &\le b \\ x &\ge 0 \end{aligned}\]Dualni linearni program $\Pi’$:
\[\begin{aligned} \min \ b^\top y \\ A^\top y &\ge c \\ y &\ge 0 \end{aligned}\]Šibki izrek o dualnosti:
\[Ax \le b \land A^\top y \ge c \land x, y \ge 0 \Rightarrow c^\top x \le b^\top y\]Krepki izrek o dualnosti: če je $x^{*}$ optimalna rešitev $\Pi$ in $y^{*}$ optimalna rešitev $\Pi’$, potem velja $c^\top x^{*}$ $=$ $b^\top y^{*}$
Pričakovana časovna zahtevnost simpleksne metode za LP z $m$ omejitvami in $n$ spremenljivkami: $O(m \log n)$
S pomočjo dualnega programa reši naslednji problem:
\[\begin{aligned} \max \quad - x_1 - 2 x_2 \\[1ex] -3 x_1 + x_2 &\le -1 \\ x_1 - x_2 &\le 1 \\ -2 x_1 + 7 x_2 &\le 6 \\ 9 x_1 + 4 x_2 &\le 6 \\ -5 x_1 + 2 x_2 &\le -3 \\ 7 x_1 - 3 x_2 &\le 6 \\[1ex] x_1, x_2 &\ge 0 \end{aligned}\]Dualni LP:
\[\begin{aligned} \min \quad -y_3 + y_4 + 6 y_5 + 6 y_6 - 3 y_7 + 6 y_8 \\[1ex] -3 y_3 + y_4 - 2 y_5 + 9 y_6 - 5 y_7 + 7 y_8 &\ge -1 \\ y_3 - y_4 + 7 y_5 + 4 y_6 + 2 y_7 - 3 y_8 &\ge -2 \\[1ex] y_3, y_4, y_5, y_6, y_7, y_8 &\ge 0 \end{aligned}\]V standardni obliki:
\[\begin{aligned} \max \quad y_3 - y_4 - 6 y_5 - 6 y_6 + 3 y_7 - 6 y_8 \\[1ex] 3 y_3 - y_4 + 2 y_5 - 9 y_6 + 5 y_7 - 7 y_8 &\le 1 \\ -y_3 + y_4 - 7 y_5 - 4 y_6 - 2 y_7 + 3 y_8 &\le 2 \\[1ex] y_3, y_4, y_5, y_6, y_7, y_8 &\ge 0 \end{aligned}\]Začetni slovar:
\[\begin{aligned} y_1 &= 1 - 3 y_3 + y_4 - 2 y_5 + 9 y_6 - 5 y_7 + 7 y_8 \\ y_2 &= 2 + y_3 - y_4 + 7 y_5 + 4 y_6 + 2 y_7 - 3 y_8 \\ -z &= y_3 - y_4 - 6 y_5 - 6 y_6 + 3 y_7 - 6 y_8 \end{aligned}\]Drugi slovar:
\[\begin{aligned} y_7 &= 1/5 - 1/5 y_1 - 3/5 y_3 + 1/5 y_4 - 2/5 y_5 + 9/5 y_6 + 7/5 y_8 \\ y_2 &= 12/5 - 2/5 y_1 - 1/5 y_3 - 3/5 y_4 + 31/5 y_5 + 38/5 y_6 - 1/5 y_8 \\ -z &= 3/5 - 3/5 y_1 - 4/5 y_3 - 2/5 y_4 - 36/5 y_5 - 3/5 y_6 - 9/5 y_8 \end{aligned}\]Optimalna rešitev dualnega programa:
Optimalna rešitev originalnega programa:
V mizarski delavnici izdelujejo stole, mize in omare. Proizvodni proces ima dve fazi: struženje in lakiranje. Stol stružijo 18 minut, lakirajo 6 minut, dobiček pri enem prodanem stolu pa je 200 evrov. Mizo stružijo 24 minut, lakirajo 12 minut, z njo pa zaslužijo 500 evrov. Omare ne stružijo, lakirajo jo pol ure, z njo pa zaslužijo 800 evrov.
Koliko posameznih izdelkov naj izdelajo, da bodo imeli največji možen dobiček, če je čas struženja omejen s 120 minutami, čas lakiranja pa je največ 150 minut? Zapiši tudi dualni program ter razmisli o pomenu spremenljivk in omejitev!
Linearni program:
\[\begin{aligned} \max \quad 200 x_1 + 500 x_2 + 800 x_3 \\[1ex] 18 x_1 + 24 x_2 &\le 120 \\ 6 x_1 + 12 x_2 + 30 x_3 &\le 150 \\[1ex] x_1, x_2, x_3 &\ge 0 \end{aligned}\]Dualni linearni program:
\[\begin{aligned} \min \quad 120 y_4 + 150 y_5 \\[1ex] 18 y_4 + 6 y_5 &\ge 200 \\ 24 y_4 + 12 y_5 &\ge 500 \\ 30 y_5 &\ge 800 \\[1ex] y_3, y_4, y_5 &\ge 0 \end{aligned}\]S simpleksno metodo rešujemo originalni LP:
\[\begin{aligned} x_4 &= 120 - 18 x_1 - 24 x_2 \\ x_5 &= 150 - 6 x_1 - 12 x_2 - 30 x_3 \\ z &= 200 x_1 + 500 x_2 + 800 x_3 \end{aligned}\]Optimalna rešitev originalnega LP:
Optimalna rešitev dualnega LP:
Ali je ${x_1} = 7, {x_2} = 1, {x_3} = 3$ optimalna rešitev linearnega programa:
\[\begin{aligned} \max \quad 2 x_1 + 3 x_2 - x_3 \\[1ex] x_1 - x_2 - x_3 &\le 3 \\ x_1 + 2 x_2 + 3 x_3 &\le 18 \\ x_1 + 3 x_2 - 2 x_3 &\le 4 \\[1ex] x_1, x_2, x_3 &\ge 0 \end{aligned}\]Pomagaj si z dualnim dopolnjevanjem:
Izrek o dualnem dopolnjevanju: če sta $x^{*}$ in $y^{*}$ optimalni rešitvi $\Pi$ in $\Pi’$, potem:
Dualni LP:
\[\begin{aligned} \min \quad 3 y_4 + 18 y_5 + 4 y_6 \\[1ex] y_4 + y_5 + y_6 &\ge 2 \\ -y_4 + 2y_5 + 3y_6 &\ge 3 \\ -y_4 + 3y_5 - 2y_6 &\ge -1 \\[1ex] y_4, y_5, y_6 &\ge 0 \end{aligned}\]Dopustnost rešitve:
\[\begin{aligned} 7 - 1 - 3 &= 3 \\ 7 + 2 \cdot 1 + 3 \cdot 3 &= 18 \\ 7 + 3 \cdot 1 - 2 \cdot 3 &= 4 \\[1ex] 7, 1, 3 &\ge 0 \end{aligned}\]Rešitev je dopustna.
Vse omejitve so dosežene.
Nastavimo sistem enačb:
\[\begin{aligned} y_4 + y_5 + y_6 &= 2 \\ -y_4 + 2y_5 + 3y_6 &= 3 \\ -y_4 + 3y_5 - 2y_6 &= -1 \\[1ex] \end{aligned}\]Rešimo sistem enačb:
\[\begin{aligned} y_4 + y_5 + y_6 &= 2 \\ 19y_5 &= 9 \\ 4y_5 - y_6 &= 1 \\[1ex] \end{aligned}\]Imamo dopustno rešitev dualnega LP, torej imamo optimalno rešitev.
Stara mama Tilka ljubi peko piškotov in zna speči kar tri vrste piškotov: čokoladne, jajčne in maslene. Za kilogram vsakih najprej potrebuje pol kilograma moke in 200g sladkorja. Nato za čokoladne piškote potebuje še 200g čokolade in 100g masla, za jajčne piškote 100g masla in 4 jajca, za maslene pa 200g masla in 2 jajci.
V soboto se poroči njena vnukinja Slavka, zato so ji sorodniki povedali, da v petek zvečer pridejo po piškote, nato pa odhiteli po opravkih in jo brez prevoza pustili doma. K sreči ima na zalogi 50kg moke, 5kg sladkorja, 3kg čokolade, 2kg masla in 40 jajc.
Linearni program:
\[\begin{aligned} \max \quad x_1 + x_2 + x_3 \\[1ex] 5 x_1 + 5 x_2 + 5 x_3 &\le 500 \\ 2 x_1 + 2 x_2 + 2 x_3 &\le 50 \\ 2 x_1 &\le 30 \\ x_1 + x_2 + 2 x_3 &\le 20 \\ 4 x_2 + 2 x_3 &\le 40 \\[1ex] x_1, x_2, x_3 &\ge 0 \end{aligned}\]Dual:
\[\begin{aligned} \min \quad 500 y_4 + 50 y_5 + 30 y_6 + 20 y_7 + 40 y_8 \\[1ex] 5 y_4 + 2 y_5 + 2 y_6 + y_7 &\ge 1 \\ 5 y_4 + 2 y_5 + y_7 + 4 y_8 &\ge 1 \\ 5 y_4 + 2 y_5 + 2 y_7 + 2 y_8 &\ge 1 \\[1ex] y_4, y_5, y_6, y_7, y_8 &\ge 0 \end{aligned}\]Preverjamo optimalnost rešitve $x = (15, 0, 2.5)$.
\[\begin{aligned} 5 \cdot 15 + 5 \cdot 2.5 &< 500 &&\Rightarrow y_4 = 0 \\ 2 \cdot 15 + 2 \cdot 2.5 &< 50 &&\Rightarrow y_5 = 0 \\ 2 \cdot 15 &= 30 \\ 15 + 2 \cdot 2.5 &= 20 \\ 2 \cdot 2.5 &< 40 &&\Rightarrow y_8 = 0 \\ 15, 0, 2.5 &\ge 0 \end{aligned}\] \[\begin{aligned} 2 y_6 + y_7 &= 1 \\ 2 y_7 &= 1 \end{aligned}\]Preverjamo optimalnost rešitve $x = (10, 10, 0)$.
\[\begin{aligned} 5 \cdot 10 + 5 \cdot 10 &< 500 &&\Rightarrow y_4 = 0 \\ 2 \cdot 10 + 2 \cdot 10 &< 50 &&\Rightarrow y_5 = 0 \\ 2 \cdot 10 &< 30 &&\Rightarrow y_6 = 0 \\ 10 + 10 &= 20 \\ 4 \cdot 10 &= 40 \\ 10, 10, 0 &\ge 0 \end{aligned}\] \[\begin{aligned} y_7 &= 1 \\ y_7 + 4 y_8 &= 1 \\ \end{aligned}\]Reklamna agencija želi s svojimi oglasi doseči vsaj 50000 potrošnikov, pri čemer ima na voljo 20000 evrov sredstev. Oglašujemo na sledečih medijih:
| Medij | Doseg | Cena | Vpliv | Max. št. oglasov |
|---|---|---|---|---|
| TV SLO | 2000 | 1200 | 65 | 12 |
| POP TV | 3000 | 1500 | 90 | 15 |
| Val 202 | 2500 | 200 | 5 | 30 |
| Dnevnik | 1500 | 800 | 35 | 10 |
| Večer | 1200 | 750 | 30 | 5 |
Na televiziji želimo imeti vsaj 10 oglasov, vendar zanje lahko porabimo največ 3/4 sredstev. Oglase želimo razporediti tako, da bomo dosegli čimvečji vpliv. Dokaži, da je $(0, 10, 5, 5, 0)$ optimalna rešitev!
Dual:
\[\begin{aligned} \min \quad -500 y_6 + 2000 y_7 - 10 y_8 + 150 y_9 + 12 y_{10} + 15 y_{11} + 30 y_{12} + 10 y_{13} + 5 y_{14} \\[1ex] -20 y_6 + 120 y_7 - y_8 + 12 y_9 + y_{10} &\ge 65 \\ -30 y_6 + 150 y_7 - y_8 + 15 y_9 + y_{11} &\ge 90 \\ -25 y_6 + 20 y_7 + y_{12} &\ge 5 \\ -15 y_6 + 80 y_7 + y_{13} &\ge 35 \\ -12 y_6 + 75 y_7 + y_{14} &\ge 30 \\[1ex] y_7, y_8, y_9, y_{10}, y_{11}, y_{12}, y_{13}, y_{14} &\ge 0 \end{aligned}\]