Optimizacijske metode

Začetni slovar druge faze dobimo tako, da v zadnjem slovarju prve faze vzamemo $x_0 = 0$ in vstavimo prvotne bazne spremenljivke v funkcional $z$: $$ \begin{aligned} x_2 &= 13 - 4 x_1 + x_4 \\ x_3 &= 6 - 3 x_1 + x_4 \\ x_5 &= 18 - 7 x_1 + 2 x_4 \\ \hline z &= -12 x_1 - 10 (13 - 4 x_1 + x_4) \\ &= -130 + 28 x_1 - 10 x_4 \end{aligned} $$

$x_1$ vstopi, $x_3$ izstopi: $$ \begin{aligned} x_1 &= 2 - {1 \over 3} x_3 + {1 \over 3} x_4 \\ x_2 &= 13 - 4 \left(2 - {1 \over 3} x_3 + {1 \over 3} x_4\right) + x_4 \\ &= 5 + {4 \over 3} x_3 - {1 \over 3} x_4 \\ x_5 &= 18 - 7 \left(2 - {1 \over 3} x_3 + {1 \over 3} x_4\right) + 2 x_4 \\ &= 4 + {7 \over 3} x_3 - {1 \over 3} x_4 \\ \hline z &= -130 + 28 \left(2 - {1 \over 3} x_3 + {1 \over 3} x_4\right) - 10 x_4 \\ &= -74 - {28 \over 3} x_3 - {2 \over 3} x_4 \end{aligned} $$ Imamo zadnji slovar druge faze, preberemo optimalno rešitev:

• $x_1^\ast = 2$ tableti Polivit
• $x_2^\ast = 5$ tablet Oligovit
• cena: $-z^\ast = 74$

Prva faza se vedno konča, ko ne moremo več izbrati vstopne spremenljivke (ker je problem omejen).

• $w^\ast < 0$: prvotni problem je nedopusten, končamo.
• $w^\ast = 0$, $x_0$ je nebazna spremenljivka v zadnjem slovarju prve faze: nadaljujemo z drugo fazo
• $w^\ast = 0$, $x_0$ je nebazna spremenljivka v zadnjem slovarju prve faze: temu se izognemo s pravilom, da če $x_0$ lahko izstopi iz baze, jo izberemo za izstopno spremenljivko (ali pa naredimo izrojen korak, da $x_0$ izstopi)

graph TD

LP[LP Π] -- "b ≱ 0" --- dvofazna[dvofazna simpleksna metoda]
LP -- "b ≥ 0" --- enofazna[simpleksna metoda]
dvofazna -- "w* < 0" --- nedopusten[Π nedopusten]
dvofazna -- "w* ≥ 0" --- dopusten[Π dopusten] --- enofazna
enofazna --- neomejen[Π neomejen]
enofazna --- optimalen[Π optimalen]

Osnovni izrek linearnega programiranja.

1. Če ima linearni program dopustno rešitev, ima bazno dopustno rešitev.
2. Če ima linearni program optimalno rešitev, ima bazno optimalno rešitev.
3. Za linearni program velja natanko ena od možnosti:
   • linearni program je nedopusten,
   • linearni program je neomejen, ali
   • linearni program je optimalen.

Dualnost pri linearnem programiranju

Naj bo $\Pi$ linearni program $$ \max \ 10 x_1 + 15 x_2 + 12 x_3 \\[1ex] \begin{aligned} \text{p.p.} && x_1 + x_2 + x_3 &\le 50 &/ \cdot y_4 \ge 0 \\ && 3 x_1 + 4 x_2 + 5 x_3 &\le 250 &/ \cdot y_5 \ge 0 \\ && 3 x_1 + 5 x_2 + 4 x_3 &\le 300 &/ \cdot y_6 \ge 0 \\ && x_1, x_2, x_3 &\ge 0 \end{aligned} $$

Iščemo zgornje meje za ciljno funkcijo: $$ (y_4 + 3 y_5 + 3 y_6) x_1 + (y_4 + 4 y_5 + 5 y_6) x_2 + (y_4 + 5 y_5 + 4 y_6) x_3 \le 50 y_4 + 250 y_5 + 300 y_6 $$

Če velja $$ \begin{aligned} y_4 + 3 y_5 + 3 y_6 &\ge 10, \\ y_4 + 4 y_5 + 5 y_6 &\ge 15, \\ y_4 + 5 y_5 + 4 y_6 &\ge 12, \end{aligned} $$ potem $$ 10 x_1 + 15 x_2 + 12 x_3 \le 50 y_4 + 250 y_5 + 300 y_6. $$ Hočemo čim manjšo zgornjo mejo.

Prvotnemu linearnemu programu $\Pi$ dodelimo dualni linearni program $\Pi'$: $$ \min \ 50 y_4 + 250 y_5 + 300 y_6 \\[1ex] \begin{aligned} \text{p.p.} && y_4 + 3 y_5 + 3 y_6 &\ge 10 \\ && y_4 + 4 y_5 + 5 y_6 &\ge 15 \\ && y_4 + 5 y_5 + 4 y_6 &\ge 12 \\ && y_4, y_5, y_6 &\ge 0 \end{aligned} $$

Definicija. Za prvotni linearni program $\Pi$ je njegov dualni linearni program $\Pi'$, kjer je

Trditev. $\Pi'' = \Pi$.

Dokaz. Zapišimo $\Pi'$ v standardni obliki. $$ \begin{aligned} \max \ -b^\top y \\[1ex] \text{p.p.} \quad -A^\top y &\le -c \\ y &\ge 0 \end{aligned} $$ Potem je $\Pi''$ sledeči linearni program: $$ \begin{aligned} \min \ -c^\top x \\[1ex] \text{p.p.} \quad -A x &\ge -b \\ x &\ge 0 \end{aligned} $$ Pretvorba v standardno obliko nam pokaže, da je $\Pi'' = \Pi$.

Šibki izrek o dualnosti (ŠID). Naj bo $\Pi$ prvotni linearni program kot zgoraj in $\Pi'$ njegov dual. Če je $x$ dopustna rešitev za $\Pi$ in $y$ dopustna rešitev za $\Pi'$, potem velja $c^\top x \le b^\top y$.

Dokaz.

1. varianta: $$ \begin{aligned} c^\top x &\le (A^\top y)^\top x & (A^\top y &\ge c, x \ge 0) \\ &= y^\top A x \\ &\le y^\top b & (Ax &\le b, y \ge 0) \\ &= b^\top y \end{aligned} $$

2. varianta: $$ \begin{aligned} \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 & \Big(\forall j: \sum_{i=1}^m a_{ij} y_{n+i} &\ge c_j, x_j \ge 0\Big) \\ &= \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} & \Big(\forall i: \sum_{j=1}^n a_{ij} x_j &\le b_i, y_{n+i} \ge 0\Big) \\ \end{aligned} $$

Posledica 1. Če sta $x$ in $y$ dopustni rešitvi za $\Pi$ oziroma $\Pi'$, za kateri velja $c^\top x = b^\top y$, potem sta $x$ in $y$ optimalni rešitvi za $\Pi$ oziroma $\Pi'$.

Dokaz. $b^\top y$ je zgornja meja za $c^\top x$, to zgornjo mejo dosežemo. $c^\top x$ je spodnja meja za $b^\top y$, to spodnjo mejo dosežemo.

Opomba. S to posledico lahko preverimo optimalnost ponujenih dopustnih rešitev $x$, $y$, za kateri velja $c^\top x = b^\top y$.

Posledica 2. Če je $\Pi$ neomejen problem, je $\Pi'$ nedopusten problem.

Dokaz. Če je $\Pi'$ dopusten, imamo zgornjo mejo za ciljno funkcijo $\Pi$, protislovje.

Krepki izrek o dualnosti (KID). Naj bo $\Pi$ prvotni linearni program kot zgoraj in $\Pi'$ njegov dual. Če je $x^\ast$ optimalna rešitev za $\Pi$, potem obstaja optimalna rešitev $y^\ast$ za $\Pi'$ in velja $c^\top x^\ast = b^\top y^\ast$.

Zadnji slovar za problem kmetije: $$ \begin{aligned} x_2 &= 50 - x_1 - x_3 - x_4 \\ x_5 &= 50 + x_1 - x_3 + 4 x_4 \\ x_6 &= 50 + 2 x_1 + x_3 + 5 x_4 \\ \hline z &= 750 - 5 x_1 - 0 x_2 - 3 x_3 - 15 x_4 - 0 x_5 - 0 x_6 \end{aligned} $$

Zadnji slovar za dual problema kmetije: $$ \begin{aligned} y_1 &= 5 + y_2 - y_5 - 2 y_6 \\ y_3 &= 3 + y_2 + y_5 - y_6 \\ y_4 &= 15 + y_2 - 4 y_5 - 5 y_6 \\ \hline z &= -750 - 0 y_1 - 50 y_2 - 0 y_3 - 0 y_4 - 50 y_5 - 50 y_6 \end{aligned} $$

Videti je, da so koeficienti dopolnilnih spremenljivk v zadnjem slovarju ravno negacija optimalne rešitve dualnega problema.