Optimizacijske metode

Primer. $$ a = \begin{bmatrix} 2 \\ 1 \end{bmatrix} \qquad U = \begin{bmatrix} 2 & 2 \\ 1 & 2 \end{bmatrix} $$ S Karush-Kuhn-Tuckerjevimi pogoji dobimo sledečo rešitev: $$ p = \begin{bmatrix} {3 \over 2} \\ {3 \over 2} \end{bmatrix} \qquad X = \begin{bmatrix} 1 & {1 \over 3} \\ 0 & {2 \over 3} \end{bmatrix} $$ Trdimo, da so tudi $p' = \begin{bmatrix} 1 \\ 2 \end{bmatrix}$ ravnovesne cene. $$ \begin{alignedat}{4} x'_{11} + 2 x'_{12} &= 2 &&& x'_{12} &= 1 \,-\, {1 \over 2} & x'_{11} \\ x'_{21} + 2 x'_{22} &= 1 &&& x'_{22} &= {1 \over 2} - {1 \over 2} & x'_{21} &= {1 \over 2} x'_{11} \\ x'_{11} + x'_{21} &= 1 &&& x'_{21} &= 1 - x'_{11} \\ x'_{12} + x'_{22} &= 1 &&& 0 &\le x'_{11} \le 1 \\ u_1(X') &= 2 x'_{11} &{} + 2 x'_{12} &= x'_{11} + 2 &\qquad u_2(X') &= x'_{21} + 2 & x'_{22} &= 1 \\ x'_{11} &= 1 & x'_{12} &= {1 \over 2} & x'_{21} &= 0 & x'_{22} &= {1 \over 2} \\ u_1(X') &= 3 &&& u_2(X') &= 1 \\ z'_1 &= 2 & S'_1 &= \{1\} & z'_2 &= 1 & S'_2 &= \{1, 2\} \end{alignedat} $$ Ravnovesne cene torej niso enolične! V tem primeru prvi kupec kupuje tudi izven svojega optimalnega svežnja. Izkaže se, da so pri teh podatkih vse možne ravnovesne cene $$ \tilde{p} = \begin{bmatrix} \lambda \\ 3 - \lambda \end{bmatrix} \qquad \tilde{X} = \begin{bmatrix} 1 & {2 - \lambda \over 3 - \lambda} \\ 0 & {1 \over 3 - \lambda} \end{bmatrix} \qquad \left(\lambda \in \left[1, {3 \over 2}\right]\right) \\ u_1(\tilde{X}) = 4 - {2 \over 3 - \lambda} \qquad u_2(\tilde{X}) = {2 \over 3 - \lambda} $$

Lokalna optimizacija

Lokalna optimizacija je pristop, ki ga običajno uporabimo pri reševanju "težkih" problemov, npr. problema potujočega trgovca.

Primer.

graph G {
    rankdir=LR
    nodesep=0.5
    ranksep=1
    splines=false
    node [label=""]

    u -- x [label=5]
    u -- y [label=5]
    x -- v [xlabel=5]
    y -- w [label=5]
    v -- w [label=5, constraint=false]
    u -- v [xlabel="  1"]
    u -- w [xlabel="1   "]
    x -- y [xlabel="  10", constraint=false]
    x -- w [label=10, constraint=false]
    y -- v [label=10, constraint=false]
}

Za graf z $n$ vozlišči imamo $(n-1)!$ dopustnih rešitev.

Ideja: iščemo "lokalne optimume" in upamo, da so tudi globalni optimumi.

Definicija. Naj bo $X$ množica. Relacija $S \subseteq X \times X$ je relacija sosednosti, če je refleksivna ($\forall x \in X: \ x \, S \, x$) in simetrična ($\forall x, y \in S: (x \, S \, y \Rightarrow y \, S \, x)$).

Za element $x \in X$ je množica $S[x] := \{y \in X \mid x \, S \, y\}$ soseščina elementa $x$. Element $x \in X$ je $S$-lokalni minimum ($S$-lokalni maksimum) funkcije $f: X \to \mathbb{R}$, če velja $\forall y \in S[x]: \ f(y) \ge f(x)$ ($\forall y \in S[x]: \ f(y) \le f(x)$).

Metoda za iskanje globalnih minimumov: izberemo naključen $x_0 \in X$, in nastavimo $i := 0$. Preverimo, če je $x_i$ $S$-lokalni minimum - če je, postopek končamo, sicer pa obstaja $x_{i+1} \in S[x_i]$, da $f(x_{i+1}) < f(x_i)$. Postavimo $i := i+1$ in ponavljamo. Če se postopek konča, smo našli $S$-lokalni minimum.

Postopek večkrat ponovimo in izberemo najboljšega izmed dobljenih $S$-lokalnih minimumov.

Definicija. Relacija $S$ je natančna za $f$, če je $S$-lokalni minimum tudi globalni minimum.

Primeri.

1. $X = \mathbb{R}^n$, izberemo $\epsilon > 0$. Naj bo $x \, S \, y \Leftrightarrow \Vert x - y \Vert < \epsilon$. Relacija $S$ ni natančna za splošne $f$, je pa natančna za konveksne $f$.
2. Množica dopustnih rešitev $D$ linearnega programa $\Pi$ je politop (angl. polytope). Globalni minimum in maksimum sta dosežena na ekstremni točki, torej na oglišču. Naj bo torej $X$ množica oglišč $D$ in definirajmo relacijo $S$ tako, da velja $x \, S \, y$ natanko tedaj, ko sta $x$ in $y$ na istem robu. Zgoraj opisana metoda za $S$ je ravno simpleksna metoda. Relacija $S$ je natančna za ciljno funkcijo $\Pi$.
3. $G = (V, E)$ povezan graf, $c : E \to \mathbb{R}$ uteži povezav. Naj bo $X$ množica (množic povezav $E' \subseteq E$) vpetih dreves $T = (V, E')$ v $G$ in $f(E') = \sum_{e \in E'} c(e)$ funkcija cene vpetega drevesa. To je problem najcenejšega vpetega drevesa - za reševanje lahko uporabimo Primov ali Kruskalov algoritem. Definiramo relacijo $S$, tako da velja $E'_1 \, S \, E'_2 \Leftrightarrow |E'_1 \oplus E'_2| \le 2$. Relacija $S$ je natančna za $f$ (brez dokaza).

4. Problem potujočega trgovca: $G = (V, E)$ povezan graf, $c : E \to \mathbb{R}$ uteži povezav. Naj bo $S$ množica Hamiltonovih ciklov v $G$ in $f(C) = \sum_{e \in C} c(e)$ funkcija cene Hamiltonovega cikla. Relacijo $S$ definiramo tako, da sta dva Hamiltonova cikla sosedna, če lahko "prevežemo" dve povezavi na ciklu.

   graph G {
     rankdir=LR
     nodesep=0.5
     ranksep=0.7
     node [label=""]
   
     a1 -- b1
     a1 -- c1
     b1 -- d1 [color=red]
     c1 -- e1 [color=red]
     d1 -- f1
     e1 -- f1
   
     f1 -- S -- a2 [style=invis]
   
     a2 -- b2
     a2 -- c2
     b2 -- d2 [style=invis]
     b2 -- e2
     c2 -- d2
     c2 -- e2 [style=invis]
     d2 -- f2
     e2 -- f2
   
     S [label=S,color=none,fontsize="20pt"]
   }
   

   Relacija $S$ ni natančna. Naj bo $G = K_n = (V, {V \choose 2})$, $u, v, w, x, y \in V$ in $C$ Hamiltonov cikel z $uv, uw, xy \not\in C$, $vw, ux, uy \in C$ ter $$ \begin{aligned} \forall e \in C: \ c(e) &= 5 \\ c(uv) = c(uw) &= 1 \\ \forall e \not\in C \cup \{uv, uw\}: \ c(e) &= 10 \end{aligned} $$ Potem velja: $$ \begin{aligned} f(C) &= 5n \\ \forall C' \in S[C]: f(C') &= 5(n-2) + 2 \cdot 10 \lor f(C') = 5(n-2) + 10 + 1 \\ \forall C' \in S[C]: f(C') &> f(C) \\ f(C \oplus \{ux, uy, vw, uv, uw, xy\}) &= 5(n-3) + 10 + 2 \cdot 1 = 5n - 3 < f(C) \end{aligned} $$ $C$ je torej $S$-lokalni minimum, ni pa tudi globalni minimum.

   graph G {
     rankdir=LR
     nodesep=0.5
     ranksep=1
     splines=false
   
     u -- x [label=5, color=red, fontcolor=red]
     u -- y [label=5, color=red, fontcolor=red]
     x -- v [xlabel=5, color=red, fontcolor=red]
     y -- w [label=5, color=red, fontcolor=red]
     v -- w [label=5, color=red, fontcolor=red, constraint=false]
     u -- v [xlabel="  1"]
     u -- w [xlabel="1   "]
     x -- y [xlabel="  10", constraint=false]
     x -- w [label=10, constraint=false]
     y -- v [label=10, constraint=false]
   }
   

   graph G {
     rankdir=LR
     nodesep=0.5
     ranksep=1
     splines=false
   
     u -- x [label=5, color=red, fontcolor=red]
     u -- y [label=5, color=red, fontcolor=red]
     x -- v [xlabel=5]
     y -- w [label=5]
     v -- w [label=5, color=red, fontcolor=red, constraint=false]
     u -- v [xlabel="  1"]
     u -- w [xlabel="1   "]
     x -- y [xlabel="  10", constraint=false]
     x -- w [label=10, color=red, fontcolor=red, constraint=false]
     y -- v [label=10, color=red, fontcolor=red, constraint=false]
   }
   

   graph G {
     rankdir=LR
     nodesep=0.5
     ranksep=1
     splines=false
   
     u -- x [label=5]
     u -- y [label=5, color=red, fontcolor=red]
     x -- v [xlabel=5, color=red, fontcolor=red]
     y -- w [label=5, color=red, fontcolor=red]
     v -- w [label=5, constraint=false]
     u -- v [xlabel="  1", color=red, fontcolor=red]
     u -- w [xlabel="1   "]
     x -- y [xlabel="  10", constraint=false]
     x -- w [label=10, color=red, fontcolor=red, constraint=false]
     y -- v [label=10, constraint=false]
   }
   

   graph G {
     rankdir=LR
     nodesep=0.5
     ranksep=1
     splines=false
   
     u -- x [label=5]
     u -- y [label=5]
     x -- v [xlabel=5, color=red, fontcolor=red]
     y -- w [label=5, color=red, fontcolor=red]
     v -- w [label=5, constraint=false]
     u -- v [xlabel="  1", color=red, fontcolor=red]
     u -- w [xlabel="1   ", color=red, fontcolor=red]
     x -- y [xlabel="  10", color=red, fontcolor=red, constraint=false]
     x -- w [label=10, constraint=false]
     y -- v [label=10, constraint=false]
   }