« nazaj
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}\]