---
tags: vaje, om, lp, simpleks
hackmd: https://hackmd.io/jWmpLOEXQIms4oPT0YdSIA
plugins: mathjax
---
# 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
- v našem primeru ${x_4}$

$$
\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$