Optimizacijske metode

Optimizacijski problemi

Primer. Od doma do fakultete iščemo pot, ki je

• najkrajša
• najhitrejša
• najcenejša
• najbolj udobna
• ...

Definicija. Optimizacijski problem je trojica $(\Omega, f, \operatorname{opt})$, kjer je

• $\Omega$ ... množica dopustnih (angl. feasible) rešitev
• $f$ ... ciljna (kriterijska) funkcija
• $\operatorname{opt} \in {\min, \max, \inf, \sup}$ ... tip ekstrema

Če velja $\Omega = \emptyset$, je problem nedopusten, sicer pa je dopusten.

Primeri

1. • $\Omega = [0, 3]$
   • $f(x) = x^2 - 3x + 2$
   • $\operatorname{opt} = \max$

   Metoda reševanja: kandidati za maksimum so ničle odvoda in krajišča dopustnega intervala.

   Pišemo: $$ \begin{aligned} \max &\quad x^2 - 3x + 2 \\[1ex] \text{p.p.} &\quad 0 \le x \le 3 \end{aligned} $$

• p.p. ... pri pogojih
• angl. s.t. (subject to, tudi so that, such that)

2. • $\Omega = [0, 2] \times [0, 3]$
   • $f(x, y) = x^2 - y^2$
   • $\operatorname{opt} = \min$

   Metoda reševanja: kandidati za minimum so ničle parcialnih odvodov in rob dopustnega območja.

Definicija. Optimalna rešitev $(\Omega, f, \max)$ je $x^\ast \in \Omega$, da velja $\forall x \in \Omega: f(x) \le f(x^\ast)$. Vrednosti $f(x^\ast)$ pravimo optimalna vrednost.

• Podobno, če $\operatorname{opt} = \min$.

Pozor! "bolj optimalna rešitev"

3. Na kmetiji velikosti 50 ha želimo gojiti pšenico, koruzo in krompir. Na voljo imamo 5000 človek-ur dela in 24000 € kapitala ter sledeče podatke

Koliko ha posameznega pridelka naj posadimo, da bo dobiček čim večji?

$$ \max \ 400 x_1 + 600 x_2 + 480 x_3 \\[1ex] \begin{aligned} \text{p.p.} && x_1 + x_2 + x_3 &\le 50 \\ && 60 x_1 + 80 x_2 + 100 x_3 &\le 5000 \\ && 240 x_1 + 400 x_2 + 320 x_3 &\le 24000 \\ && x_1, x_2, x_3 &\ge 0 \end{aligned} $$

Taki nalogi rečemo linearni program (LP).

4. Ana, Barbara, Cvetka in Darja želijo prečkati most. Naenkrat lahko most prečkata le dve od njiju, imajo pa eno samo svetilko. Za prečkanje mostu A, B, C, D potrebujejo 1, 2, 5 oziroma 10 minut - pri skupnem prečkanju seveda potrebujejo toliko časa kot počasnejša od njiju. Kako naj prečkajo most, da bodo čim hitrejše?

• Definiramo graf z množico vozlišč $V = \mathcal{P}{A, B, C, D, s}$ - vsako vozlišče predstavlja stanje na eni strani mostu.
• Vozlišči $u$ in $v$ sta sosedni, če lahko z enim prečkanjem pridemo od stanja $u$ do stanja $v$ (tj., $s \in u \oplus v$, $2 \le |u \oplus v| \le 3$ in $u \subset v$ ali $v \subset u$).
• Uteži povezav so porabljeni časi.
• Iščemo najkrajšo pot med $\emptyset$ in ${A, B, C, D, s}$.
• Rešujemo z Dijkstrovim algoritmom - spoznali ga bomo pri predmetu Operacijske raziskave.

5. Sestaviti želimo čim hitrejšo štafeto.

Primer rešitve (ne nujno optimalne!):

• prsno 3 (68)
• hrbtno 5 (69)
• delfin 1 (63)

• prosto 6 (59)

  graph G {
  rankdir=LR
  edge [color=gray]
  prsno -- 1
  prsno -- 2
  prsno -- 3 [penwidth=2,color=red,label=68]
  prsno -- 4
  prsno -- 5
  prsno -- 6
  hrbtno -- 1
  hrbtno -- 2
  hrbtno -- 3
  hrbtno -- 4
  hrbtno -- 5 [penwidth=2,color=red,label=69]
  hrbtno -- 6
  delfin -- 1 [penwidth=2,color=red,label=63]
  delfin -- 2
  delfin -- 3
  delfin -- 4
  delfin -- 5
  delfin -- 6
  prosto -- 1
  prosto -- 2
  prosto -- 3
  prosto -- 4
  prosto -- 5
  prosto -- 6 [penwidth=2,color=red,label=59]
  }
  

6. Potujoči trgovec iz Ljubljane želi obiskati London, Pariz, Madrid, Berlin.

• Primer poti: Lj - B - P - Lo - M - Lj, cena 10+5+10+1+5 = 31

  Iščemo najcenejšo pot, torej najcenejši Hamiltonov cikel. To je problem potujočega trgovca - učinkovit algoritem ni znan!

graph TD

op["Optimizacijski problemi"]
op --- Nedopustni
op --- Dopustni
Dopustni --- Neomejeni
Dopustni --- Omejeni
Omejeni --- Optimalni
Omejeni --- Neoptimalni

• Nedopustni problemi: $\Omega = \emptyset$ $$ \begin{aligned} \max \ 2x - y^2 \\ \text{p.p.} \quad x - y &\le 1 \\ -x + y &\le -2 \end{aligned} $$
• Dopustni problemi: $\Omega \ne \emptyset$
  • Neomejeni problemi $$ \begin{aligned} \max \ 2x - y^2 \\ \text{p.p.} \quad x &\ge 0 \\ y &\le 5 \end{aligned} $$
  • Optimalni problemi $$ \begin{aligned} \max \ x^2 + y^2 \\ \text{p.p.} \quad 0 \le x &\le 2 \\ 0 \le y &\le 1 \end{aligned} $$
  • Neoptimalni problemi $$ \begin{aligned} \max \ x^2 + y^2 \\ \text{p.p.} \quad 0 \le x &< 2 \\ 0 \le y &< 1 \end{aligned} $$

Linearno programiranje

Definicija. Linearni program (LP) je optimizacijski problem, kjer so ciljna funkcija in vsi pogoji linearni.

Primer. $$ \begin{aligned} \min \ 2x_1 - 3x_2 + 2x_3 \\[1ex] \text{p.p.} \quad x_1 + 2x_2 - x_3 &\le 4 \\ x_1 + 5x_2 + 2x_3 &\ge 2 \\ 2x_1 - 3x_2 - 4x_3 &= 1 \\ x_1 &\ge 0 \\ x_3 &\le 0 \end{aligned} $$

Definicija. Linearni program je v standardni obliki, če

• iščemo $\max$
• so vsi pogoji $\le$
• so vse spremenljivke $\ge 0$

Trditev. Vsak linearni program lahko ekvivalentno zapišemo v standardni obliki.

Dokaz.

• $\min f(x) \to \max -f(x)$
• $g_j(x) \ge b \to -g_j(x) \le -b$
• $g_j(x) = b \to g_j(x) \le b$; $-g_j(x) \le -b$
• $x_i \le 0 \to x_i = -x'_i$; $x'_i \ge 0$
• $x_i$ neomejena $\to x_i = x^+_i - x^-_i$; $x^+_i, x^-_i \ge 0$