Predavanje 22.2.
Trditev. Naj bo $\Pi = (\Omega, f, \max)$ linearni program. Potem velja:
- $\Omega$ je konveksna množica.
- Množica optimalnih rešitev $\Pi$ je konveksna množica.
Dokaz.
- $\Omega$ je presek polprostorov (in hiperravnin), torej je konveksna množica.
- Če optimalnih rešitev ni, potem je množica optimalnih rešitev prazna, torej konveksna. Sicer naj bo $c$ optimalna vrednost. Potem je množica optimalnih rešitev enaka $$ \{x \in \Omega \mid f(x) = c\} $$ in je zato konveksna množica.
Grafično reševanje LP z dvema spremenljivkama
Primer. $$ \begin{aligned} \max \ x + y \\[1ex] \text{p.p.} \quad x + 2y &\le 6 \\ 5x + 4y &\le 20 \\ x, y &\ge 0 \end{aligned} $$
$$ \begin{aligned} x + 2y &= 6 &&/ \cdot (-2) \\ 5x + 4y &= 20 \\ 3x &= 8 \\ x &= {8 \over 3} \\ 2y &= 6 - {8 \over 3} = {10 \over 3} \\ y &= {5 \over 3} \end{aligned} $$
$(x^\ast, y^\ast) = ({8 \over 3}, {5 \over 3})$ je optimalna rešitev, $z^\ast = {13 \over 3}$ je optimalna vrednost.
Množica dopustnih rešitev $\Omega$ je politop (lahko neomejen). Množica optimalnih rešitev je lice tega politopa (oglišče, stranica, stranska ploskev, itd.). Optimalna vrednost (če obstaja) je vedno dosežena (tudi) v oglišču.
Simpleksna metoda
Denimo, da imamo linearni program v standardni obliki $$ \begin{aligned} \max \ c^\top x \\[1ex] \text{p.p.} \quad A x &\le b \\ x &\ge 0 \end{aligned} $$ kjer velja
- $A \in \mathbb{R}^{m \times n}$, $b \in \mathbb{R}^m$, $c \in \mathbb{R}^n$
- $b \ge 0$ (če velja $b \not\ge 0$, uporabimo dvofazno simpleksno metodo, ki jo bomo spoznali kasneje)
Primer. Kmetija: $$ \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} $$
Ciljno funkcijo in omejitve lahko skaliramo brez vpliva na pomen spremenljivk: $$ \max \ 10 x_1 + 15 x_2 + 12 x_3 \\[1ex] \begin{aligned} \text{p.p.} && x_1 + x_2 + x_3 &\le 50 \\ && 3 x_1 + 4 x_2 + 5 x_3 &\le 250 \\ && 3 x_1 + 5 x_2 + 4 x_3 &\le 300 \\ && x_1, x_2, x_3 &\ge 0 \end{aligned} $$
Neenakosti spremenimo v enakosti z uvedbo novih nenegativnih spremenljivk.
Prvi slovar: $$ \begin{aligned} x_4 &= 50 - x_1 - x_2 - x_3 \\ x_5 &= 250 - 3 x_1 - 4 x_2 - 5 x_3 \\ x_6 &= 300 - 3 x_1 - 5 x_2 - 4 x_3 \\ \hline z &= 10 x_1 + 15 x_2 + 12 x_3 \end{aligned} $$
V zgornjem sistemu enačb nastopajo sledeče spremenljivke:
- prvotne spremenljivke: $x_1, x_2, \dots, x_n$
- dopolnilne spremenljivke: $x_{n+1}, x_{n+2}, \dots, x_{n+m}$
- funkcional $z$
Slovar je izražava $m$ izmed spremenljivk $x_1, x_2, \dots, x_{n+m}$ (bazne spremenljivke) in funkcionala $z$ z ostalimi izmed spremenljivk (nebazne spremenljivke).
V prvem slovarju velja:
- nebazne spremenljivke so prvotne spremenljivke, in
- bazne spremenljivke so dopolnile spremenljivke.
Slovar je dopusten, če so konstantni koeficienti baznih spremenljivk nenegativni. Prvi slovar je dopusten zaradi predpostavke $b \ge 0$.
Dopusten slovar nam da bazno dopustno rešitev, ki jo dobimo tako, da nebaznim spremenljivkam dodelimo vrednost $0$.
$$ \begin{aligned} x_4 &= 50 - x_1 - x_2 - x_3 & \leftarrow x_2 &\le 50 \\ x_5 &= 250 - 3 x_1 - 4 x_2 - 5 x_3 & x_2 &\le {250 \over 4} = {125 \over 2} \\ x_6 &= 300 - 3 x_1 - 5 x_2 - 4 x_3 & x_2 &\le {300 \over 5} = 60 \\ \hline z &= 10 x_1 + 15 \underline{x_2} + 12 x_3 \end{aligned} $$
Izberemo nebazno spremenljivko s pozitivnim koeficientom pri funkcionalu $z$. Če je kandidatov več, izberemo poljubnega. Pogosto uporabljamo:
- pravilo največjega koeficienta
- pravilo najmanjšega indeksa
- pravilo največjega povečanja
Izbrani spremenljivki pravimo vstopna spremenljivka. V našem primeru smo izbrali $x_2$ (sta pa tudi $x_1$ in $x_3$ kandidata).
Vrstici, ki izbrano vstopno spremenljivko najbolj omejuje, pravimo pivotna vrstica, pripadajoči bazni spremenljivki pa izstopna spremenljivka. Če imamo več pivotnih vrstic (tj., več baznih spremenljivk najbolj omejuje vstopno spremenljivko), potem za izstopno spremenljivko izberemo poljubno izmed njih.
Vstopna spremenljivka vstopi v bazo, izstopna iz nje izstopi. Rešimo enačbo za vstopno spremenljivko in vstavimo v enačbe za ostale bazne spremenljivke in funkcional $z$:
$$ \begin{aligned} x_2 &= 50 - x_1 - x_3 - x_4 \\ x_5 &= 250 - 3 x_1 - 4 (50 - x_1 - x_3 - x_4) - 5 x_3 \\ &= 50 + x_1 - x_3 + 4 x_4 \\ x_6 &= 300 - 3 x_1 - 5 (50 - x_1 - x_3 - x_4) - 4 x_3 \\ &= 50 + 2 x_1 + x_3 + 5 x_4 \\ \hline z &= 10 x_1 + 15 (50 - x_1 - x_3 - x_4) + 12 x_3 = \\ &= 750 - 5 x_1 - 3 x_3 - 15 x_4 \end{aligned} $$
Če so vsi koeficienti pri funkcionalu $z$ nepozitivni, smo našli optimalno rešitev in se simpleksna metoda ustavi. V nasprotnem primeru ponavljamo postopek.
Vsi slovarji, ki smo jih dobili tekom reševanja, so dopustni. Če smo dobili kak nedopusten slovar, smo se zmotili (npr. izbrali napačno izstopno spremenljivko ali naredili računsko napako).
Kaj se lahko še zgodi?
Konstantni koeficient bazne spremenljivke je enak $0$: $$ \begin{aligned} &\vdots \\ x_j &= 0 + \ldots - 3 x_i + \ldots & \leftarrow x_i \le 0 \\ &\vdots \\ \hline z &= 10 + \ldots + 4 \underline{x_i} + \ldots \end{aligned} $$ Vrednost v bazni dopustni rešitvi se ne poveča - izrojen korak.
Nobena vrstica na omejuje vstopne spremenljivke: $$ \begin{aligned} &\vdots \\ x_j &= \ldots + 3 x_i + \ldots & x_i \le \infty \\ &\vdots \\ \hline z &= \ldots + 4 \underline{x_i} + \ldots \end{aligned} $$ Tedaj je linearni program neomejen - končamo simpleksno metodo. Neomejeno družino dopustnih rešitev dobimo tako, da vstopno spremenljivko pustimo kot nenegativen parameter brez zgornje meje, ostalim nebaznim spremenljivkam pa dodelimo vrednost $0$.
Kako iz zadnjega slovarja za optimalni problem dobimo vse optimalne rešitve?
- Nebaznim spremenljivkam z negativnim koeficientom dodelimo vrednost $0$.
- Nebazne spremenljivke z ničelnim koeficientom pustimo kot parametre (tj., jim ne dodelimo nujno vrednosti $0$).
- Upoštevamo, da so vse bazne spremenljivke nenegativne.
Primer. Denimo, da imamo sledeči zadnji slovar. $$ \begin{aligned} x_2 &= 40 - {2 \over 3} x_1 - {4 \over 5} x_3 - {1 \over 15} x_6 \\ x_4 &= 10 - {1 \over 3} x_1 - {1 \over 5} x_3 + {1 \over 15} x_6 \\ x_5 &= 90 - {1 \over 3} x_1 - {9 \over 5} x_3 + {4 \over 15} x_6 \\ \hline z &= 200 - {1 \over 3} x_1 - {1 \over 3} x_6 \end{aligned} $$
Potem velja:
- $x_1^\ast = x_6^\ast = 0$
- $x_2^\ast = 40 - {4 \over 5} x_3^\ast \ge 0$, torej $x_3^\ast \le 50$
- $x_4^\ast = 10 - {1 \over 5} x_3^\ast \ge 0$, torej $x_3^\ast \le 50$
- $x_6^\ast = 90 - {9 \over 5} x_3^\ast \ge 0$, torej $x_3^\ast \le 50$
Optimalne rešitve so torej oblike $x_1^\ast = 0$, $x_2^\ast = 40 - {4 \over 5} x_3^\ast$, $0 \le x_3^\ast \le 50$, $z^\ast = 200$.