---
tags: vaje, om, kkt, fisher
hackmd: https://hackmd.io/4w8b7Db_SaeR04VoWXixEw
plugins: mathjax
---
# Optimizacijske metode - vaje 28.5.2021

---

## Fisherjev model trga

$$
\begin{aligned}
a_i &> 0 \quad \text{kapital kupca $i = 1, \dots, m$} \\
u_{ij} &\ge 0 \quad \text{zadovoljstvo kupca $i = 1, \dots, m$ z dobrino $j = 1, \dots, n$} \\
p_j &> 0 \quad \text{cena dobrine $j = 1, \dots, n$} \\
x_{ij} &\ge 0 \quad \text{količina dobrine $j = 1, \dots, n$, ki jo kupi kupec $i = 1, \dots, m$}
\end{aligned}
$$

Eisenberg-Galeov konveksni program:

$$
\begin{aligned}
\Omega &= \left\{x \in \mathbb{R}^{mn} \mid \forall i = 1, \dots, m : \sum_{j=1}^n u_{ij} x_{ij} > 0\right\} \\[2ex]
-\min &\ -\sum_{i=1}^m a_i \log \left(\sum_{j=1}^n u_{ij} x_{ij}\right) \\[1ex]
\sum_{i=1}^m x_{ij} &\le 1 \quad \text{za } j = 1, \dots, n \\
x_{ij} &\ge 0 \quad \text{za } i = 1, \dots, m, \ j = 1, \dots, n
\end{aligned}
$$

Zapišimo Lagrangeevo funkcijo:

$$
\begin{aligned}
f(x) &= -\sum_{i=1}^m a_i \log \left(\sum_{j=1}^n u_{ij} x_{ij}\right) \\
g_j(x) &= \sum_{i=1}^m x_{ij} - 1 \\
h_{ij}(x) &= -x_{ij} \\[1ex]
L(x) &= f(x) + \sum_{j=1}^n p_j g_j(x) + \sum_{i=1}^m \sum_{j=1}^n \mu_{ij} h_{ij}(x)
\end{aligned}
$$

---

### Naloga 1

Trgovec z začimbami na bazarju ima zalogo
$50$kg cimeta in $2$kg žafrana. Njegovi glavni kupci so Arabci, ki mu tedensko prinesejo $550.000$ dinarjev prometa, in Berberi, ki mu tedensko prinesejo $250.000$ dinarjev prometa. Zadovoljstvo Arabca ob nakupu kilograma cimeta je $5$, ob nakupu kilograma žafrana pa $360$. Zadovoljstvo Berbera ob nakupu kilograma cimeta je $4$, ob nakupu kilograma žafrana pa $440$. Kako naj trgovec postavi izklicne cene, da bodo ravnovesne in da bo zadovoljstvo kupcev čim večje?

----

$$
\begin{aligned}
a_A &= 550 \\
a_B &= 250 \\
u_{Ac} &= 250 \\
u_{Až} &= 720 \\
u_{Bc} &= 200 \\
u_{Bž} &= 880 \\[1ex]
L &= -550 \log(250 x_{Ac} + 720 x_{Až}) - 250 \log(200 x_{Bc} + 880 x_{Bž}) + \\
&\ + p_c (x_{Ac} + x_{Bc} - 1) + p_ž (x_{Až} + x_{Bž} - 1) \\
&\ - \mu_{Ac} x_{Ac} - \mu_{Až} x_{Až} - \mu_{Bc} x_{Bc} - \mu_{Bž} x_{Bž} \\[1ex]
L_{Ac} &= {-550 \cdot 250 \over 250 x_{Ac} + 720 x_{Až}} + p_c - \mu_{Ac} = 0 \\
L_{Až} &= {-550 \cdot 720 \over 250 x_{Ac} + 720 x_{Až}} + p_ž - \mu_{Až} = 0 \\
L_{Bc} &= {-250 \cdot 200 \over 200 x_{Bc} + 880 x_{Bž}} + p_c - \mu_{Bc} = 0 \\
L_{Bž} &= {-250 \cdot 880 \over 200 x_{Bc} + 880 x_{Bž}} + p_ž - \mu_{Bž} = 0 \\[1ex]
g_c = g_ž &= 0 \\
x_{Bc} &= 1 - x_{Ac} \\
x_{Bž} &= 1 - x_{Až} \\[1ex]
L_{Ac} &= {-550 \cdot 250 \over 250 x_{Ac} + 720 x_{Až}} + p_c - \mu_{Ac} = 0 \\
L_{Až} &= {-550 \cdot 720 \over 250 x_{Ac} + 720 x_{Až}} + p_ž - \mu_{Až} = 0 \\
L_{Bc} &= {-250 \cdot 200 \over 200 (1 - x_{Ac}) + 880 (1 - x_{Až})} + p_c - \mu_{Bc} = 0 \\
L_{Bž} &= {-250 \cdot 880 \over 200 (1 - x_{Ac}) + 880 (1 - x_{Až})} + p_ž - \mu_{Bž} = 0 \\[1ex]
\end{aligned}
$$

1. $$
\begin{aligned}
h_{Bc} &= 0 = x_{Bc} \\
x_{Ac} &= 1 \\
h_{Ac} &< 0 \\
\mu_{Ac} &= 0 \\[1ex]
L_{Ac} &= {-550 \cdot 250 \over 250 + 720 x_{Až}} + p_c = 0 \\
L_{Až} &= {-550 \cdot 720 \over 250 + 720 x_{Až}} + p_ž - \mu_{Až} = 0 \\
L_{Bc} &= {-250 \cdot 200 \over 880 (1 - x_{Až})} + p_c - \mu_{Bc} = 0 \\
L_{Bž} &= {-250 \over 1 - x_{Až}} + p_ž - \mu_{Bž} = 0 \\[1ex]
\end{aligned}
$$

1. $$
\begin{aligned}
h_{Až} &= 0 = x_{Až} \\
x_{Bž} &= 1 \\
h_{Bž} &< 0 \\
\mu_{Bž} &= 0 \\[1ex]
L_{Ac} &= -550 + p_c = 0 \\
L_{Až} &= {-550 \cdot 720 \over 250} + p_ž - \mu_{Až} = 0 \\
L_{Bc} &= {-250 \cdot 200 \over 880} + p_c - \mu_{Bc} = 0 \\
L_{Bž} &= -250 + p_ž = 0 \\[1ex]
p_c &= 550 \\
p_ž &= 250 \\
\mu_{Až} &= 250 - {550 \cdot 720 \over 250} < 0
\end{aligned}
$$

2. $$
\begin{aligned}
h_{Až} &< 0 \\
x_{Až} &> 0 \\
\mu_{Až} &= 0 \\[1ex]
L_{Ac} &= {-550 \cdot 250 \over 250 + 720 x_{Až}} + p_c = 0 \\
L_{Až} &= {-550 \cdot 720 \over 250 + 720 x_{Až}} + p_ž = 0 \\
L_{Bc} &= {-250 \cdot 200 \over 880 (1 - x_{Až})} + p_c - \mu_{Bc} = 0 \\
L_{Bž} &= {-250 \over 1 - x_{Až}} + p_ž = 0 \\[1ex]
x_{Až} &< 1 \\
x_{Bž} &> 0 \\
h_{Bž} &< 0 \\
\mu_{Bž} &= 0 \\
{550 \cdot 720 \over 250 + 720 x_{Až}} &= {250 \over (1 - x_{Až})} \\
250 (250 + 720 x_{Až}) &= 550 \cdot 720 (1 - x_{Až}) \\
800 \cdot 720 x_{Až} &= 550 \cdot 720 - 250 \cdot 250 \\
x_{Až} &= 0.58 \\
x_{Bž} &= 0.42 \\
p_ž & = 593.81 \\
p_c &= 206.19 \\
\mu_{Bc} &= 71.23
\end{aligned}
$$

---

### Naloga 2

Definirajmo množico

$$
\Omega = \{(x, y) \in \mathbb{R}^2 \mid x^2 + y^2 < 4\}
$$

in preslikavo

$$
\begin{aligned}
f &: \Omega \to \mathbb{R} \\
f &: (x, y) \mapsto - x^4 - 2x^2 y^2 - y^4 + 54x^2 + 54y^2 - 184y + 666
\end{aligned}
$$

S Karush-Kuhn-Tuckerjevimi pogoji dokaži, da je $(x, y) = (0, 1)$ optimalna rešitev problema vezanih ekstremov z neenačbami

$$
\begin{aligned}
\min \quad f(x, y) \\[1ex]
x \le 1 \\
y \le 1 & .
\end{aligned}
$$

----

$$
\begin{aligned}
g_1 &= x - 1 \\
g_2 &= y - 1 \\
H_f &= \begin{pmatrix}
-12x^2 - 4y^2 + 108 & -8xy \\
-8xy & -4x^2 - 12y^2 + 108
\end{pmatrix} \\
3x^2 + y^2 &\le 3(x^2 + y^2) < 12 \le 27 \\
\det H_f &= (-12x^2 - 4y^2 + 108) (-4x^2 - 12y^2 + 108) - 64 x^2 y^2 \\
&= 48x^4 + 96 x^2 y^2 + 48y^4 - 1296 x^2 - 1296 y^2 + 108^2 \\
{1 \over 48} \det H_f &= x^4 + 2 x^2 y^2 + y^4 - 27 x^2 - 27 y^2 + 243 \\
&= (x^2 + y^2)^2 - 27 (x^2 + y^2) + 243 \\
&> (x^2 + y^2)^2 - 108 + 243 > 0
\end{aligned}
$$

$$
\begin{aligned}
L(x, y) &= - x^4 - 2x^2 y^2 - y^4 + 54x^2 + 54y^2 - 184y + 666 + \lambda_1 (x - 1) + \lambda_2 (y - 1) \\
L_x(x, y) &= -4x^3 - 4x y^2 + 108x + \lambda_1 = 0 \\
L_y(x, y) &= -4x^2 y - 4y^3 + 108y - 184 + \lambda_2 = 0 \\[1ex]
g_1(0, 1) &= -1 \\
g_2(0, 1) &= 0 \\
L_x(0, 1) &= \lambda_1 = 0 \\
L_y(0, 1) &= -4 + 108 - 184 + \lambda_2 = 0 \\
\lambda_2 &= 80
\end{aligned}
$$