Optimizacijske metode

Ali se simpleksna metoda vedno ustavi? NE.

Možnih slovarjev je ${n+m \choose m}$. Če se simpleksna metoda ne ustavi, pomeni, da je prišlo do "ciklanja". V tem primeru so vsi koraki v ciklu degenerirani.

Ciklanje je izjemno redko. Dokazati se da, da do ciklanja ne bo prišlo, če za vstopne in izstopne spremenljivke uporabimo pravilo najmanjšega indeksa (Blandovo pravilo).

Časovne zahtevnosti algoritmov:

• "Hitri" algoritmi: uporabijo polinomsko mnogo operacij.
• "Počasni" algoritmi: uporabijo eksponentno mnogo operacij.

Ali je simpleksna metoda hitra?

• Tipično: $\approx m \log n$ korakov
• Najslabši primer: simpleksna metoda ni polinomska

Primer. (Klee-Minty) Za $n = 3$: $$ \max \ 100 x_1 + 10 x_2 + x_3 \\[1ex] \begin{aligned} \text{p.p.} && x_1 &\le 1 \\ && 20 x_1 + x_2 &\le 100 \\ && 200 x_1 + 20 x_2 + x_3 &\le 10000 \\ && x_1, x_2, x_3 &\ge 0 \end{aligned} $$

• Če uporabimo metodo največjega koeficienta, potrebujemo $2^n - 1$ korakov.
• Če uporabimo pravilo največjega povečanja, potrebujemo $1$ korak.

Obstajajo algoritmi za reševanje linearnih programov, ki so dokazljivo polinomski.

Dvofazna simpleksna metoda

Uporabljamo jo za linearne programe v standardni obliki, za katere ne velja $b \ge 0$.

1. faza: ugotovi, ali je linearni program dopusten - če je, nam prva faza da dopusten začetni slovar za drugo fazo.
2. faza: identična simpleksni metodi.

Primer. Imamo dve vitaminski tableti, Polivit in Oligovit, ki vsebujejo različne količine vitaminov A, B in C.

Kako najceneje zadostiti dnevnim potrebam?

$$ \min \ 12 x_1 + 10 x_2 \\[1ex] \begin{aligned} \text{p.p.} && x_1 + x_2 &\ge 7 \\ && 4 x_1 + x_2 &\ge 13 \\ && x_1 + 2 x_2 &\ge 8 \\ && x_1, x_2 &\ge 0 \end{aligned} $$

Zapišimo ekvivalentni linearni program v standardni obliki. $$ \max \ -12 x_1 - 10 x_2 \\[1ex] \begin{aligned} \text{p.p.} && -x_1 - x_2 &\le -7 \\ && -4 x_1 - x_2 &\le -13 \\ && -x_1 - 2 x_2 &\le -8 \\ && x_1, x_2 &\ge 0 \end{aligned} $$

Ker v zgornjem linearnem programu velja $b \not\ge 0$, zapišimo še pomožni problem prve faze: $$ \min \ x_0 \\[1ex] \begin{aligned} \text{p.p.} && -x_1 - x_2 &\le -7 + x_0 \\ && -4 x_1 - x_2 &\le -13 + x_0 \\ && -x_1 - 2 x_2 &\le -8 + x_0 \\ && x_0, x_1, x_2 &\ge 0 \end{aligned} $$ Pomožni problem je vedno dopusten ($x_0$ mora biti dovolj velik). Pomožni problem ima optimalno vrednost $0$ natanko tedaj, ko je prvotni problem dopusten.

Zapišimo začetni slovar za prvo fazo - ta slovar ni dopusten: $$ \begin{aligned} x_3 &= -7 + x_0 + x_1 + x_2 \\ x_4 &= -13 + x_0 + 4 x_1 + x_2 \\ x_5 &= -8 + x_0 + x_1 + 2 x_2 \\ \hline w &= -x_0 \end{aligned} $$

V prvem koraku prve faze v bazo vstopi $x_0$, izstopi pa spremenljivka z najmanjšim (najbolj negativnim) konstantnim členom - v našem primeru $x_4$: $$ \begin{aligned} x_0 &= 13 - 4 x_1 - x_2 + x_4 & \leftarrow x_2 &\le 13 \\ x_3 &= 6 - 3 x_1 + x_4 & x_2 &\le \infty \\ x_5 &= 5 - 3 x_1 + x_2 + x_4 & x_2 &\le \infty \\ \hline w &= -13 + 4 x_1 + \underline{x_2} - x_4 \end{aligned} $$

Nadaljujemo enako kot pri osnovni simpleksni metodi. V našem primeru po metodi največjega povečanja izberemo $x_2$ za vstopno spremenljivko in $x_0$ za izstopno spremenljivko. $$ \begin{aligned} x_2 &= 13 - x_0 - 4 x_1 + x_4 \\ x_3 &= 6 - 3 x_1 + x_4 \\ x_5 &= 18 - x_0 - 7 x_1 + 2 x_4 \\ \hline w &= -x_0 \end{aligned} $$

Optimalna vrednost pomožnega problema je $0$ - prvotni problem je torej dopusten.