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!

Ta stran je odprtokodna. Izboljšaj to stran.

Ta zapisek je dostopen tudi na HackMD.