Optimizacijske metode
Optimizacijske metode - vaje 20.3.2020
| LP $\Pi$ | Dualni LP $\Pi’$ |
|---|---|
| \(\begin{aligned} \max c^\top x \\ A x &\le b \\ x &\ge 0\end{aligned}\) | \(\begin{aligned} \min b^\top y \\ A^\top y &\ge c \\ y &\ge 0\end{aligned}\) |
Pričakovana časovna zahtevnost simpleksne metode za LP z $m$ omejitvami in $n$ spremenljivkami je $O(m^\alpha \log^\beta n)$ za neka $\alpha, \beta > 0$.
Naloga 1
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}\]Spodaj smo videli: $x_1=3/5$, $x_2=0$.
Rešitev.
Damo v standardno obliko in rešujemo s simpleksno metodo:
\[\begin{aligned} y_7&=1-3 y_1 + y_2 -2y_3+9y_4-5y_5+7y_6 \\ y_8&=2+y_1 - y_2 +7y_3+4y_4 +2y_5-3y_6 \\[1ex] z&= y_1 - y_2 - 6 y_3 - 6 y_4 + 3y_5 - 6y_6\\ \end{aligned}\]Povečujemo $z$: vstopi $y_5$, izstopi $y_7$
\[\begin{aligned} y_5&=\frac{1}{5}-\frac{3}{5} y_1 + \frac{1}{5}y_2 -\frac{2}{5}y_3+\frac{9}{5}y_4+\frac{7}{5}y_6-\frac{1}{5}y_7 \\ y_8&=\frac{12}5-\frac15y_1 - \frac35y_2 +\frac{31}5y_3+\frac{38}5y_4 -\frac15y_6 -\frac25y_7\\[1ex] z&= \frac{3}{5}-\frac45 y_1 - \frac25 y_2 -\frac{36}{5} y_3 - \frac35 y_4 - \frac95y_6 -\frac{3}{5}y_7\\ \end{aligned}\]Imamo rešitev: $y_1=y_2=y_3=y_4=y_6=y_7=0$, $y_5=\frac{1}{5}$, $y_8=\frac{12}{5}$.
Rešitev osnovnega LP: $x_1=\frac{3}{5}$, $x_2=0$.
Naloga 2
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$ urami, čas lakiranja pa je največ $150$ ur? Zapiši tudi dualni program ter razmisli o pomenu spremenljivk in omejitev!
Rešitev. Količina stolov: $x_1$, količina miz $x_2$, količina omar: $x_3$.
\[\begin{aligned} \max \quad 200 x_1 +500 x_2 +800 x_3 \\[1ex] \frac{3}{10} x_1 + \frac{4}{10} x_2 + 0 x_3&\le 120 \\ \frac{1}{10} x_1 + \frac{2}{10} x_2 + \frac{5}{10} x_3 &\le 150 \\[1ex] x_1, x_2, x_3 &\ge 0 \end{aligned}\]Dual:
\[\begin{aligned} \min \quad 120y_1 +150 y_2 \\[1ex] \frac{3}{10} y_1 + \frac{1}{10} y_2 &\ge 200\\ \frac{4}{10} y_1 + \frac{2}{10} y_2 &\ge 500 \\ 0 y_1+\frac{5}{10} y_2 &\ge 800 \\[1ex] y_1, y_2 &\ge 0 \end{aligned}\]Naloga 3
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:
- preveri, ali je $(x_1, x_2, x_3)$ dopustna rešitev
- tam, kjer omejitve niso dosežene, spremenljivke dualnega problema nastavi na $0$
- za vse spremenljivke $x_i$, različne od $0$, nastavi enačbo med spremenljivkami dualnega problema.
- reši dobljene enačbe
- preveri, ali je dobljena rešitev dopustna.
Rešitev. Preverimo dopustnost:
\[\begin{aligned} 7 - 1 - 3 &\le 3 & (\text{OK}, &=)\\ 7 + 2 \cdot 1 + 3 \cdot 3 &\le 18 & (\text{OK}, &=)\\ 7 + 3 \cdot 1 - 2 \cdot 3 &\le 4 & (\text{OK}, &=)\\[1ex] x_1, x_2, x_3 &\ge 0 & (\text{OK})\\[1ex] z=2\cdot 7+3\cdot 1-3&=14 \end{aligned}\]Napišemo dual:
\[\begin{aligned} \min \quad 3 y_1 + 18 y_2 +4 y_3 \\[1ex] y_1 +y_2 +y_3 &\ge 2 \\ -y_1 + 2 y_2 + 3 y_3 &\ge 3 \\ -y_1 + 3 y_2 - 2 y_3 &\ge -1 \\[1ex] y_1, y_2, y_3 &\ge 0 \end{aligned}\]Ker je $x_1\not=0$, je $y_1 +y_2 +y_3 = 2$. (Če bi bila pa prva neenakost iz LP $<$, torej $x_1 - x_2 - x_3 < 3$, bi bil pa $y_1=0$.) Podobno zaradi $x_2\not=0$ in $x_3\not=0$ dobimo
\[\begin{aligned} y_1 +y_2 +y_3 &= 2 \\ -y_1 + 2 y_2 + 3 y_3 &= 3 \\ -y_1 + 3 y_2 - 2 y_3 &= -1 \end{aligned}\] \[\begin{aligned} 3y_2 +4y_3 &= 5 \\ 4 y_2 - y_3 &= 1 \end{aligned}\] \[\begin{aligned} 3y_2 +4y_3 &= 5 \\ 16 y_2 - 4y_3 &= 4 \end{aligned}\]Rešitev: $y_2=\frac{9}{19}$, $y_3=\frac{17}{19}$, $y_1=\frac{12}{19}$. Ker smo upoštevali vse (ne)enačbe, je rešitev dopustna (če kakšne neenačbe ne zapišete z $=$, je treba pogoj preveriti!).
Kaj pa vrednost funkcionala v dualu? $3 y_1 + 18 y_2 +4 y_3=\frac{36}{19}+\frac{162}{19}+\frac{68}{19}=14$
Naloga 4
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 $200$g sladkorja. Nato za čokoladne piškote potebuje še $200$g čokolade in $100$g masla, za jajčne piškote $100$g masla in $4$ jajca, za maslene pa $200$g 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 $50$kg moke, $5$kg sladkorja, $3$kg čokolade, $2$kg masla in $40$ jajc.
- Dokaži, da $15$kg čokoladnih in $2.5$kg maslenih piškotov ni optimalna rešitev.
- Dokaži, da bo največ piškotov spekla, če speče $10$kg čokoladnih in $10$kg jajčnih piškotov.
Naloga 5
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!
