---
tags: vaje, om, problemi, lp
hackmd: https://hackmd.io/1zJnwqZPT7qZzaUQ2ECR3A
plugins: mathjax
---
# Optimizacijske metode - vaje 19.2.2021

---

## Optimizacijske naloge

Zapišite naslednje probleme kot optimizacijsko nalogo $(D, f, \mathrm{opt})$.

* $D$ ... množica dopustnih rešitev (domena)
* $f : D \to \mathbb{R}$ ... ciljna funkcija
* $\mathrm{opt} \in \lbrace \min, \max \rbrace$

---

### Ekstrem

Poiščite minimum funkcije $f(x) = -x^2 + 2x + 5$.

----

* $D = \mathbb{R}$
* $f(x) = -x^2 + 2x + 5$
* $\mathrm{opt} = \min$

Imamo kvadratno funkcijo z negativnim vodilnim členom, nima minimuma - problem je neomejen!

Maksimum poiščemo z odvajanjem:

* $f'(x) = -2x + 2 = 0$
* $x = 1$
* vrednost ciljne funkcije $f(1) = 6$

---

### Vezani ekstrem

Poiščite valj z največjim volumnom pri dani površini $P$.

----

* $D = \lbrace (r, v) \in {\mathbb{R}_+}^2 \mid 2 \pi r (r + v) = P \rbrace$
* $f(r, v) = \pi r^2 v$
* $\mathrm{opt} = \max$

Rešitev:
- $v = {P \over 2 \pi r} - r$
- $V(r) = {r P \over 2} - \pi r^3$
- $V'(r) = {P \over 2} - 3 \pi r^2 = 0$
- $r = \sqrt{P \over 6 \pi}$
- $v = 2\sqrt{P \over 6\pi}$

---

### Preprosti nahrbtnik

Imamo nahrbtnik s prostornino $V$ ter $n$ predmetov s prostorninami ${V_1}, \dots, {V_n}$ in cenami ${c_1}, \dots, {c_n}$. Katere predmete in s kakšnim deležem (predmete lahko režemo) naj vzamemo, da bo skupna cena čim večja?

----

* $D = \lbrace x \in [0, 1]^n \mid {\sum_{i=1}^n} {x_i} {V_i} \le V \rbrace$
* $f(x) = {\sum_{i=1}^n} {x_i} {c_i}$
* $\mathrm{opt} = \max$

Rešitev:
* razvrstimo padajoče glede na ${c_i}/{V_i}$
* vzamemo toliko predmetov, kolikor jih stoji v nahrbtniku, in še delež naslednjega, kolikor stoji

---

### 0-1 nahrbtnik

Enak problem kot preprosti nahrbtnik, le da predmetov ne smemo rezati.

----

* $D = \lbrace x \in \lbrace 0, 1 \rbrace^n \mid {\sum_{i=1}^n} {x_i} {V_i} \le V \rbrace$
* $f(x) = {\sum_{i=1}^n} {x_i} {c_i}$
* $\mathrm{opt} = \max$

Primer: $V = 4$, ${V_1} = 3$, ${V_2} = {V_3} = 2$, ${c_1} = 7$, ${c_2} = {c_3} = 4$.
* po prejšnjem postopku: vzamemo prvi predmet, $f(x) = 7$
* optimalna rešitev: vzamemo drugi in tretji predmet, $f(x) = 8$

Težek problem! Ne poznamo učinkovite rešitve.

---

### Problem particije

Imamo $2 n$ jabolk s težami ${t_1}, \dots, {t_{2n}}$. Kako jih razdelimo v dve košari s po $n$ jabolki, da bo v obeh košarah čim bolj podobna teža?

----

* $D = \lbrace x \in \lbrace -1, 1 \rbrace^{2n} \mid {\sum_{i=1}^{2n}} {x_i} = 0 \rbrace$
* $f(x) = \vert {\sum_{i=1}^{2n}} {x_i} {t_i} \vert$
* $\mathrm{opt} = \min$

Težek problem! Ne poznamo učinkovite rešitve.

---

### Najmanjša krogla

Imamo množico točk $A = \lbrace {x_1}, \dots, {x_k} \rbrace \subset \mathbb{R}^n$. Poiščite najmanjšo kroglo, ki vsebuje vse točke v $A$.

----

* $D = \lbrace (s, r) \in \mathbb{R}^n \times {\mathbb{R}_+} \mid \forall x \in A: \Vert x - s \Vert \le r \rbrace$
* $f(s, r) = r$
* $\mathrm{opt} = \min$

Rešitev:
* preverimo ${k \choose n+1} = {k! \over (n+1)! (k-n-1)!}$ $(n+1)$-teric točk in za vsako preverimo, če so ostale točke iz A v notranjosti "očrtane" krogle
* število korakov: $O(k^{n+1})$ - polinomsko v $k$, eksponentno v $n$
* učinkovita rešitev, če je $n$ konstanta
* ni učinkovita, če $n$ ni konstanten

---

### Kovanci

Imamo $n$ centov. Kako jih lahko razdelimo na kovance po $1, 2, 5, 10, 20, 50$, da bodo kovanci čim bolj enakomerno zastopani? (Kaj to pomeni?)

----

* $S = \lbrace 1, 2, 5, 10, 20, 50 \rbrace$
* $D = \lbrace x \in {\mathbb{N}_0^S} \mid {\sum_{s \in S}} s {x_s} = n \rbrace$
* $f(x) = {\max_{s \in S}} {x_s} - {\min_{s \in S}} {x_s}$
* $\mathrm{opt} = \min$

Rešitev:
* vsak kovanec vzamemo $\lfloor n/88 \rfloor$-krat, za ostanek dodamo optimalno rešitev iz tabele:

| $n$ | 1 | 2 | 5 | 10 | 20 | 50 |
| --- | - | - | - | -- | -- | -- |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 | 0 | 0 |
| 2 | 0 | 1 | 0 | 0 | 0 | 0 |
| 3 | 1 | 1 | 0 | 0 | 0 | 0 |
| 4 | 2 | 1 | 0 | 0 | 0 | 0 |
| 5 | 0 | 0 | 1 | 0 | 0 | 0 |
| ...
| 87 | 0 | 1 | 1 | 1 | 1 | 1 |

---

### Maksimalni prerez

Imamo neusmerjen enostaven graf $G = (V, E)$. Iščemo razdelitev $V = A \cup B$, $A \cap B = \emptyset$, da bo število povezav med $A$ in $B$ čim večje.

----

* $D = \mathcal{P}V$
* $f(X) = \vert \lbrace \lbrace u, v \rbrace \in E \mid u \in X \land v \not\in X \rbrace \vert$
* $\mathrm{opt} = \max$

Težek problem!

---

### Problem trgovskega potnika

Dano imamo množico $M = \lbrace {m_i} \mid 1 \le i \le n \rbrace$ mest in funkcijo $d : M^2 \rightarrow \mathbb{R}$ razdalj med njimi. Iščemo najkrajši cikel, ki bo obiskal vsako mesto natanko enkrat.

----

* $D = {S_n}$ (množica permutacij množice z $n$ elementi)
* $f(\pi) = {\sum_{i=1}^n} d({m_{\pi(i-1)}}, {m_{\pi(i)}})$ (predpostavljamo $\pi(0) = \pi(n)$)
* $\mathrm{opt} = \min$

Težek problem!

---

### Minimalno vpeto drevo

Imamo enostaven neusmerjen graf $G = (V, E)$ in funkcijo cene povezave $c : E \rightarrow \mathbb{R}$. Iščemo vpeto drevo z najmanjšo ceno.

----

$T$ vpeto drevo v $G = (V, E)$: $T = (V, E')$, $E' \subseteq E$, $T$ drevo

* $D = \lbrace E' \subseteq E \mid T = (V, E') \text{ je drevo} \rbrace$
* $f(E') = {\sum_{e \in E'}} c(e)$
* $\mathrm{opt} = \min$

Rešujemo s Primovim ali Kruskalovim algoritmom.

---

## Linearni programi

Linearni program v standardni obliki:
* $D = \lbrace x \in \mathbb{R}^n \mid Ax \le b, x \ge 0 \rbrace$, kjer $A \in \mathbb{R}^{m \times n}$ in $b \in \mathbb{R}^m$
* $f(x) = c^\top x$, kjer $c \in \mathbb{R}^n$
* $\mathrm{opt} = \max$

Pretvorba v standardno obliko:

$$
\begin{aligned}
\min c^\top x &\quad \to \quad \max -c^\top x \\
{a_i} x \ge {b_i} &\quad \to \quad -{a_i} x \le -{b_i} \\
{a_i} x = {b_i} &\quad \to \quad {a_i} x \le {b_i}, \ -{a_i} x \le -{b_i} \\
{x_i} \le 0 &\quad \to \quad {x_i} = -{x'_i}, \ {x'_i} \ge 0 \\
{x_i} \text{ neomejena} &\quad \to \quad {x_i} = {x^+_i} - {x^-_i}, \ {x^+_i}, {x^-_i} \ge 0
\end{aligned}
$$