« nazaj
Optimizacijske metode - vaje 5.3.2021
Simpleksna metoda
Naloga 1
Fotografski zanesenjak Niko N. ima zdaj že d.o.o., v katerem proizvaja tri vrste fotoaparatov: Minimum 1, Optimum 5 in Maksimum 9. Za vsak aparat Minimum 1 potrebuje 1 uro dela in material, vreden 30 evrov, za vsak Optimum 5 za 80 evrov materiala in 3 ure dela, za vsak Maksimum 9 pa 4 ure dela in material, vreden 300 evrov. Optimum 5 lahko proda za 150 evrov, Maksimum 9 za 500 evrov, Minimum 1 pa za 50 evrov. Katere fotoaparate naj naredi Niko, če ima 1700 evrov kapitala in 42 ur časa?
- ${x_1}$ … število Minimum 1
- ${x_2}$ … število Optimum 5
- ${x_3}$ … število Maksimum 9
\[\begin{aligned}
\max \quad 20 x_1 + 70 x_2 + 200 x_3 \\[1ex]
3 x_1 + 8 x_2 + 30 x_3 &\le 170 \quad \text{(delili smo z $10$)} \\
x_1 + 3 x_2 + 4 x_3 &\le 42 \\
x_1, x_2, x_3 &\ge 0
\end{aligned}\]
Začetni slovar:
\[\begin{aligned}
x_4 &= 170 - 3 x_1 - 8 x_2 - 30 x_3 \\
x_5 &= 42 - x_1 - 3 x_2 - 4 x_3 \\
z &= 20 x_1 + 70 x_2 + 200 x_3
\end{aligned}\]
- Vstopi: ${x_3}$
- Izstopi: ${x_4}$
Drugi (zadnji) slovar:
\[\begin{aligned}
x_3 &= 17/3 - 1/10 x_1 - 4/15 x_2 - 1/30 x_4 \\
x_5 &= 58/3 - 3/5 x_1 - 29/15 x_2 + 2/15 x_4 \\
z &= 3400/3 + 50/3 x_2 - 20/3 x_4
\end{aligned}\]
- Vstopi: ${x_2}$
- Izstopi: ${x_5}$
\[\begin{aligned}
x_2 &= 10 - 9/29 x_1 + 2/29 x_4 - 15/29 x_5 \\
x_3 &= 3 - 1/58 x_1 - 3/58 x_4 + 4/29 x_5 \\
z &= 1300 - 150/29 x_1 - 160/29 x_4 - 250/29 x_5
\end{aligned}\]
Rešitev:
- ${x_1} = 0$ Minimum 1
- ${x_2} = 10$ Optimum 5
- ${x_3} = 3$ Maksimum 9
- ${x_4} = 0$
- ${x_5} = 0$
Naloga 2
S simpleksno metodo reši linearni problem:
\[\begin{aligned}
\max \quad 3 x_1 + 2 x_2 \\[1ex]
-x_1 + x_2 &\le 3 \\
x_1 - x_2 &\le 1 \\
x_1 - 2 x_2 &\le 4 \\[1ex]
x_1, x_2 &\ge 0
\end{aligned}\]
Začetni slovar:
\[\begin{aligned}
x_3 &= 3 + x_1 - x_2 \\
x_4 &= 1 - x_1 + x_2 \\
x_5 &= 4 - x_1 + 2 x_2 \\
z &= 3 x_1 + 2 x_2
\end{aligned}\]
- Vstopi: ${x_1}$
- Izstopi: ${x_4}$
\[\begin{aligned}
x_1 &= 1 + x_2 - x_4 \\
x_3 &= 4 - x_4 \\
x_5 &= 3 + x_2 + x_4 \\
z &= 3 + 5x_2 - 3 x_4
\end{aligned}\]
- Vstopi: ${x_2}$
- Nimamo kandidata za izstop, problem je neomejen!
Družina dopustnih rešitev z neomejeno vrednostjo ciljne funkcije:
- ${x_1} = 1 + {x_2}$
- ${x_2} \ge 0$
- $z = 3 + 5 {x_2}$
Naloga 3
Poišči vse rešitve naslednjega linearnega problema:
\[\begin{aligned}
\max \quad x_1 + x_2 \\[1ex]
x_1 &\le 2 \\
x_2 &\le 2 \\
x_1 + x_2 &\le 3 \\[1ex]
x_1, x_2 &\ge 0
\end{aligned}\]
Začetni slovar:
\[\begin{aligned}
x_3 &= 2 - x_1 \\
x_4 &= 2 - x_2 \\
x_5 &= 3 - x_1 - x_2 \\
z &= x_1 + x_2
\end{aligned}\]
- Vstopi: ${x_1}$
- Izstopi: ${x_3}$
\[\begin{aligned}
x_1 &= 2 - x_3 \\
x_4 &= 2 - x_2 \\
x_5 &= 1 - x_2 + x_3 \\
z &= 2 + x_2 - x_3
\end{aligned}\]
- Vstopi: ${x_2}$
- Izstopi: ${x_5}$
\[\begin{aligned}
x_2 &= 1 + x_3 - x_5 \\
x_1 &= 2 - x_3 \\
x_4 &= 1 - x_3 + x_5 \\
z &= 3 + 0 x_3 - x_5
\end{aligned}\]
- Ni kandidata za vstop, imamo optimalno rešitev.
- ${x_1} = 2$
- ${x_2} = 1$
- $z = 3$
- Naj vseeno vstopi ${x_3}$.
- Izstopi ${x_4}$.
\[\begin{aligned}
x_3 &= 1 - x_4 + x_5 \\
x_2 &= 2 - x_4 \\
x_1 &= 1 + x_4 - x_5 \\
z &= 3 + 0 x_4 - x_5
\end{aligned}\]
- Druga optimalna rešitev:
- ${x_1} = 1$
- ${x_2} = 2$
- $z = 3$
- Splošna optimalna rešitev:
- ${x_1} = 1 + {x_4}$
- ${x_2} = 2 - {x_4}$
- $0 \le {x_4} \le 1$
- $z = 3$
Naloga 4
Z dvofazno metodo rešite linearni problem:
\[\begin{aligned}
\max \quad 3 x_1 + x_2 \\[1ex]
x_1 - x_2 &\le -1 \\
-x_1 - x_2 &\le -3 \\
2 x_1 + x_2 &\le 4 \\[1ex]
x_1, x_2 &\ge 0
\end{aligned}\]
Začetni slovar prve faze:
\[\begin{aligned}
x_3 &= -1 + x_0 - x_1 + x_2 \\
x_4 &= -3 + x_0 + x_1 + x_2 \\
x_5 &= 4 + x_0 - 2 x_1 - x_2 \\
w &= -x_0 \\
z &= 3 x_1 + x_2
\end{aligned}\]
Prvi korak:
- vstopi ${x_0}$
- izstopi spremenljivka z najbolj negativnim prostim členom
\[\begin{aligned}
x_0 &= 3 - x_1 - x_2 + x_4 \\
x_3 &= 2 - 2 x_1 + x_4 \\
x_5 &= 7 - 3 x_1 - 2 x_2 + x_4 \\
w &= -3 + x_1 + x_2 - x_4 \\
z &= 3 x_1 + x_2
\end{aligned}\]
- vstopi: ${x_2}$
- izstopi: ${x_0}$
\[\begin{aligned}
x_2 &= 3 - x_0 - x_1 + x_4 \\
x_3 &= 2 - 2 x_1 + x_4 \\
x_5 &= 1 + 2 x_0 - x_1 - x_4 \\
w &= -x_0 \\
z &= 3 - x_0 + 2 x_1 + x_4
\end{aligned}\]
Končali smo s prvo fazo, nastavimo ${x_0} = 0$ in zapišemo prvi slovar druge faze.
\[\begin{aligned}
x_2 &= 3 - x_1 + x_4 \\
x_3 &= 2 - 2 x_1 + x_4 \\
x_5 &= 1 - x_1 - x_4 \\
z &= 3 + 2 x_1 + x_4
\end{aligned}\]
- vstopi: ${x_1}$
- izstopi: ${x_5}$
\[\begin{aligned}
x_1 &= 1 - x_4 - x_5 \\
x_2 &= 2 + 2 x_4 + x_5 \\
x_3 &= 0 + 3 x_4 + 2 x_5 \\
z &= 5 - x_4 - 2 x_5
\end{aligned}\]
Optimalna rešitev:
- ${x_1} = 1$
- ${x_2} = 2$
- ${x_3} = {x_4} = {x_5} = 0$
- $z = 5$
Naloga 5
Laboratorijski tehnik Stanko mora dnevno hraniti zajca, ki potrebuje 24 gramov maščobe, 36 gramov ogljikovih hidratov in 4 grame beljakovin, vendar ne sme pojesti več kot 400 gramov hrane na dan.
Stanko ima na voljo žito, ki vsebuje 8 % maščob, 8 % ogljikovih hidratov in 2 % beljakovin in stane 0,002 centa na gram,
ter oreščke, ki vsebujejo 15 % maščob, 12 % ogljikovih hidratov in 1 % beljakovin in stanejo 0,003 centa na gram.
Zapiši Stankov problem kot linearni program ter poišči čim cenejšo mešanico, pri kateri bo zajec imel primerno prehrano.
- ${x_1}$ … število gramov žita
- ${x_2}$ … število gramov oreščkov
\[\begin{aligned}
\min \quad 2 x_1 + 3 x_2 & \quad \text{enota: tisočinka centa} \\[1ex]
8 x_1 + 15 x_2 &\ge 2400 \\
8 x_1 + 12 x_2 &\ge 3600 \\
2 x_1 + x_2 &\ge 400 \\
x_1 + x_2 &\le 400 \\[1ex]
x_1, x_2 &\ge 0
\end{aligned}\]
Linearni program v standardni obliki:
\[\begin{aligned}
\max \quad -2 x_1 - 3 x_2 \\[1ex]
-8 x_1 - 15 x_2 &\le -2400 \\
-8 x_1 - 12 x_2 &\le -3600 \\
-2 x_1 - x_2 &\le -400 \\
x_1 + x_2 &\le 400 \\[1ex]
x_1, x_2 &\ge 0
\end{aligned}\]
Začetni slovar prve faze:
\[\begin{aligned}
x_3 &= -2400 + x_0 + 8 x_1 + 15 x_2 \\
x_4 &= -3600 + x_0 + 8 x_1 + 12 x_2 \\
x_5 &= -400 + x_0 + 2 x_1 + x_2 \\
x_6 &= 400 + x_0 - x_1 - x_2 \\
w &= -x_0 \\
-z &= -2 x_1 - 3 x_2
\end{aligned}\]
- Vstopi: ${x_0}$
- Izstopi: ${x_4}$
\[\begin{aligned}
x_0 &= 3600 - 8 x_1 - 12 x_2 + x_4 \\
x_3 &= 1200 + 3 x_2 + x_4 \\
x_5 &= 3200 - 6 x_1 - 11 x_2 + x_4 \\
x_6 &= 4000 - 9 x_1 - 13 x_2 + x_4 \\
w &= -3600 + 8 x_1 + 12 x_2 - x_4 \\
-z &= -2 x_1 - 3 x_2
\end{aligned}\]
- Vstopi: ${x_1}$
- Izstopi: ${x_6}$
\[\begin{aligned}
x_1 &= 4000/9 - 13/9 x_2 + 1/9 x_4 - 1/9 x_6 \\
x_0 &= 400/9 - 4/9 x_2 + 1/9 x_4 + 8/9 x_6 \\
x_3 &= 1200 + 3 x_2 + x_4 \\
x_5 &= 1600/3 - 7/3 x_2 + 1/3 x_4 + 2/3 x_6 \\
w &= -400/9 + 4/9 x_2 - 1/9 x_4 - 8/9 x_6 \\
-z &= -8000/9 - 1/9 x_2 - 2/9 x_4 + 2/9 x_6
\end{aligned}\]
- Vstopi: ${x_2}$
- Izstopi: ${x_0}$
\[\begin{aligned}
x_2 &= 100 - 9/4 x_0 + 1/4 x_4 + 2 x_6 \\
x_1 &= 300 + 13/4 x_0 - 1/4 x_4 - 3 x_6 \\
x_3 &= 1500 -27/4 x_0 + 7/4 x_4 + 6 x_6 \\
x_5 &= 300 + 21/4 x_0 - 1/4 x_4 - 4 x_6 \\
w &= -x_0 \\
-z &= -900 + 1/4 x_0 - 1/4 x_4
\end{aligned}\]
Konec prve faze, zapišimo začetni slovar druge faze.
\[\begin{aligned}
x_2 &= 100 + 1/4 x_4 + 2 x_6 \\
x_1 &= 300 - 1/4 x_4 - 3 x_6 \\
x_3 &= 1500 + 7/4 x_4 + 6 x_6 \\
x_5 &= 300 - 1/4 x_4 - 4 x_6 \\
-z &= -900 - 1/4 x_4
\end{aligned}\]
Optimalna rešitev:
- ${x_1} = 300$ g žita
- ${x_2} = 100$ g oreščkov
- $z = 900$ tisočink centa
Splošna optimalna rešitev:
- ${x_1} = 300 - 3 {x_6}$
- ${x_2} = 100 + 2 {x_6}$
- $0 \le {x_6} \le 75$
- $z = 900$