---
tags: vaje, om, lp, simpleks, dualnost
hackmd: https://hackmd.io/RXwrSr3OTaOdeTE93MehNA
plugins: mathjax
---
# 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:

1. preveri, ali je $(x_1, x_2, x_3)$ dopustna rešitev
2. tam, kjer omejitve niso dosežene, spremenljivke dualnega problema nastavi na $0$
3. za vse spremenljivke $x_i$, različne od $0$, nastavi enačbo med spremenljivkami dualnega problema.
4. reši dobljene enačbe
5. 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.

----

1. Dokaži, da $15$kg čokoladnih in $2.5$kg maslenih piškotov ni optimalna rešitev.
2. 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!