Optimizacijske metode

Ekvivalentna formulacija izreka o dualnem dopolnjevanju: dopustni rešitvi $x$ in $y$ sta optimalni rešitvi za $\Pi$ oziroma $\Pi'$ natanko tedaj, ko velja $$ \begin{aligned} \forall i &\in \{1, \dots, m\}: & \Big(\sum_{j=1}^n a_{ij} x_j &< b_i &&\Rightarrow& y_{n+i} &= 0\Big) \quad \text{in} \\ \forall j &\in \{1, \dots, n\}: & \Big(x_j &> 0 &&\Rightarrow& \sum_{i=1}^m a_{ij} y_{n+i} &= c_j\Big). \end{aligned} $$

Dokaz. $$ L = \sum_{j=1}^n c_j x_j \le \sum_{j=1}^n \left(\sum_{i=1}^m a_{ij} y_{n+i}\right) x_j = \sum_{i=1}^m \left(\sum_{j=1}^n a_{ij} x_j\right) y_{n+i} \le \sum_{i=1}^m b_i y_{n+i} = D $$

Po Posledici 1 in KID sta $x, y$ optimalni za $\Pi, \Pi'$, natanko tedaj, ko velja $L = D$, kar je enakovredno $$ \begin{aligned} \forall j: c_j x_j = \left(\sum_{i=1}^m a_{ij} y_{n+i}\right) x_j &\ \land \ \forall i: \left(\sum_{j=1}^n a_{ij} x_j\right) y_{n+i} = b_i y_{n+i} \\ \Leftrightarrow \quad \forall j: \left(c_j - \sum_{i=1}^m a_{ij} y_{n+i}\right) x_j = 0 &\ \land \ \forall i: \left(b_i - \sum_{j=1}^n a_{ij} x_j\right) y_{n+i} = 0 \end{aligned} $$

Primer. Pokaži, da je $x = (0, 50, 0)$ optimalna rešitev problema kmetije.

1. korak: preverimo, da je ponujena rešitev dopustna. $$ \begin{aligned} 0 + 50 + 0 &= 50 \\ 3 \cdot 0 + 4 \cdot 50 + 5 \cdot 0 &< 250 \\ 3 \cdot 0 + 5 \cdot 50 + 4 \cdot 0 &< 300 \end{aligned} $$

2. korak: za vsako neenakost, ki je izpolnjena z $<$, pripadajoči dualni spremenljivki dodelimo vrednost $0$. $$ y_5 = y_6 = 0 $$

3. korak: za vsako pozitivno vrednost v rešitvi postavimo enačaj v pripadajoči neenakosti. $$ y_4 + 4 y_5 + 5 y_6 = 15 $$

4. korak: rešimo sistem iz korakov 2 in 3 in preverimo dopustnost rešitve.

   • Če je rešitev več (parametrična rešitev), zadostuje, da poiščemo tako vrednost parametrov, da bo dobljena rešitev dopustna. $$ y_4 = 15 \qquad y_5 = 0 \qquad y_6 = 0 \\[1ex] \begin{aligned} 15 + 3 \cdot 0 + 3 \cdot 0 &\ge 10 \\ 15 + 5 \cdot 0 + 4 \cdot 0 &\ge 12 \end{aligned} $$

Ekonomski pomen dualnih spremenljivk

Primer. Problem kmetije: $$ x_1^\ast = 0 \qquad x_2^\ast = 50 \qquad x_3^\ast = 0 $$

$$ \begin{aligned} z^\ast = 10 \cdot 0 + 15 \cdot 50 + 12 \cdot 0 &= 750 & \text{(zaslužek v 40 €)} \\[1ex] 0 + 50 + 0 &= 50 & \text{(zemlja v ha)} \\ 3 \cdot 0 + 4 \cdot 50 + 5 \cdot 0 &< 250 & \text{(delovna sila v 20 človek-urah)} \\ 3 \cdot 0 + 5 \cdot 50 + 4 \cdot 0 &< 300 & \text{(kapital v 80 €)} \end{aligned} $$ Ne izplača se nam najeti več delovne sile ali vzeti kredita. Morda se nam izplača dokupiti dodatno zemljo. $$ y_4^\ast = 15 \qquad y_5^\ast = 0 \qquad y_6^\ast = 0 $$

Izrek. Naj bo $\Pi$ prvotni linearni program kot zgoraj z neizrojeno bazno optimalno rešitvijo (tj., v pripadajočem slovarju so vsi konstantni členi pri baznih spremenljivkah pozitivni), in $\Pi'$ njegov dual. Potem obstaja $\epsilon > 0$, da velja $$ |\Delta b| < \epsilon \ \Rightarrow \ \Delta z^\ast = \sum_{i=1}^m y_{n+i}^\ast \Delta b_i, $$ kjer je $y^\ast$ optimalna rešitev $\Pi'$ in sta $\Delta b$ in $\Delta z^\ast$ spremembi desne strani in optimalne vrednosti.

V našem primeru: $z^\ast = 15 \, \Delta b_1$ za $|\Delta b| < \epsilon$. Zemljo se nam splača kupiti po ceni največ $15 \cdot 40$ €/ha = $600$ €/ha.

Torej: optimalne vrednosti duala nam dajo "tržno"/"pošteno"/sprejemljivo ceno surovin.

Dual splošnega linearnega programa

Izrek. Naj bo $\Pi$ linearni program v spodnji obliki. Potem je njegov dual $\Pi'$:

Izrek o dualnem dopolnjevanju za $\Pi$ in $\Pi'$ kot zgoraj.
Naj bosta $x$ in $y$ dopustni rešitvi za $\Pi$ oziroma $\Pi'$. Potem sta $x$ in $y$ optimalni rešitvi za $\Pi$ oziroma $\Pi'$ natanko tedaj, ko velja $$ \begin{aligned} \forall i &\in \{1, \dots, m'\}: & \Big(\sum_{j=1}^n a_{ij} x_j &= b_i &&\lor& y_{n+i} &= 0\Big) \quad \text{in} \\ \forall j &\in \{1, \dots, n'\}: & \Big(x_j &= 0 &&\lor& \sum_{i=1}^m a_{ij} y_{n+i} &= c_j\Big). \end{aligned} $$

Torej:

• neenakost $\le \quad \leftrightarrow \quad$ nenegativna spremenljivka
• enakost $\quad \leftrightarrow \quad$ neomejena spremenljivka

Primer.

Dokaz. Pretvorimo $\Pi$ v standardno obliko: $$ \begin{aligned} \max \ \sum_{j=1}^{n'} c_j x_j + \sum_{j=n'+1}^n c_j x_j^+ - \sum_{j=n'+1}^n c_j x_j^- \\[1ex] \text{p.p.} \quad \sum_{j=1}^{n'} a_{ij} x_j + \sum_{j=n'+1}^n a_{ij} x_j^+ - \sum_{j=n'+1}^n a_{ij} x_j^- &\le b_i & (1 &\le i \le m') \\ \sum_{j=1}^{n'} a_{ij} x_j + \sum_{j=n'+1}^n a_{ij} x_j^+ - \sum_{j=n'+1}^n a_{ij} x_j^- &\le b_i & (m'+1 &\le i \le m) \\ -\sum_{j=1}^{n'} a_{ij} x_j - \sum_{j=n'+1}^n a_{ij} x_j^+ + \sum_{j=n'+1}^n a_{ij} x_j^- &\le -b_i & (m'+1 &\le i \le m) \\ x_j &\ge 0 & (1 &\le j \le n') \\ x_j^+, x_j^- &\ge 0 & (n'+1 &\le j \le n) \end{aligned} $$

Zapišimo še dual: $$ \begin{aligned} \min \ \sum_{i=1}^{m'} b_i y_{n+i} + \sum_{i=m'+1}^m b_i y_{n+i}^+ - \sum_{i=m'+1}^m b_i y_{n+i}^- \\[1ex] \text{p.p.} \quad \sum_{i=1}^{m'} a_{ij} y_{n+i} + \sum_{i=m'+1}^m a_{ij} y_{n+i}^+ - \sum_{i=m'+1}^m a_{ij} y_{n+i}^- &\ge c_j & (1 &\le j \le n') \\ \sum_{i=1}^{m'} a_{ij} y_{n+i} + \sum_{i=m'+1}^m a_{ij} y_{n+i}^+ - \sum_{i=m'+1}^m a_{ij} y_{n+i}^- &\ge c_j & (n'+1 &\le j \le n) \\ -\sum_{i=1}^{m'} a_{ij} y_{n+i} - \sum_{i=m'+1}^m a_{ij} y_{n+i}^+ + \sum_{i=m'+1}^m a_{ij} y_{n+i}^- &\ge c_j & (n'+1 &\le j \le n) \\ y_{n+i} &\ge 0 & (1 &\le i \le m') \\ y_{n+i}^+, y_{n+i}^- &\ge 0 & (m'+1 &\le i \le m) \end{aligned} $$ Vidimo, da je dobljeni dual enakovreden našemu zapisu $\Pi'$.

Problem razvoza

(angl. transshipment problem)

Primer. Imamo 3 mesta, v mestu $a$ proizvedejo 7 enot mleka, v $b$ ga porabijo 4 enote, v $c$ pa ga porabijo 3 enote. Prevoz po cesti ima določeno ceno na enoto:

• $a \to b: 1$
• $a \to c: 3$
• $b \to c: 1$
• $c \to b: 6$

Kako najceneje prenesti mleko od proizvajalcev do porabnikov?

digraph G {
  rankdir=LR
  nodesep=0.5
  ranksep=1

  a [label=-7,xlabel=a]
  b [label=4,xlabel=b]
  c [label=3,xlabel=c]

  a -> b [taillabel="  1\n\n", tailport=ne]
  a -> c [taillabel="\n   3", tailport=se]
  b -> c [headlabel="   1", label=" ", tailport=se, constraint=false]
  c -> b [headlabel="6   ", tailport=nw, constraint=false]
}

Možni rešitvi:

• Rešitev 1:

  digraph G {
  rankdir=LR
  nodesep=0.5
  ranksep=1
  edge [fontcolor=red, labelfontcolor=black]
  
  a [label=-7,xlabel=a]
  b [label=4,xlabel=b]
  c [label=3,xlabel=c]
  
  a -> b [taillabel="  1\n\n", label=4, tailport=ne, color=red]
  a -> c [taillabel="\n   3", label=3, tailport=se, color=red]
  b -> c [headlabel="   1", label=" ", tailport=se, constraint=false]
  c -> b [headlabel="6   ", tailport=nw, constraint=false]
  }
  

  Cena: $4 \cdot 1 + 3 \cdot 3 = 13$

• Rešitev 2:

  digraph G {
  rankdir=LR
  nodesep=0.5
  ranksep=1
  edge [fontcolor=red, labelfontcolor=black]
  
  a [label=-7,xlabel=a]
  b [label=4,xlabel=b]
  c [label=3,xlabel=c]
  
  a -> b [taillabel="  1\n\n", label=7, tailport=ne, color=red]
  a -> c [taillabel="\n   3", tailport=se]
  b -> c [headlabel="   1", label=" 3", tailport=se, constraint=false, color=red]
  c -> b [headlabel="6   ", tailport=nw, constraint=false]
  }
  

  Cena: $7 \cdot 1 + 3 \cdot 1 = 10$

Imamo usmerjen utežen graf $G = (V, E)$, kjer je $V$ množica vozlišč in $E$ množica usmerjenih povezav, ter uteži na vozliščih $b_v \in \mathbb{R}$ ($v \in V$) in uteži na povezavah $c_{uv} \in \mathbb{R}$ ($uv \in E$), kjer:

• $b_v \ge 0$, če je v vozlišču $v$ poraba $b_v$, in
• $b_v < 0$, če je v vozlišču $v$ proizvodnja $-b_v$.

Predpostavimo $\sum_{v \in V} b_v = 0$.

Iščemo $x_{uv} \ge 0$ za vsako povezavo $uv \in E$, tako da velja Kirchhoffov zakon: $$ \forall v \in V: \sum_{uv \in E} x_{uv} - \sum_{vu \in E} x_{vu} = b_v. $$ Radi bi minimizirali ceno $\sum_{uv \in E} c_{uv} x_{uv}$.