Predavanje 16.2.
Primer. Zapišimo prejšnji primer v standardni obliki. $$ \begin{aligned} \max \ -2x_1 + 3x^+_2 - 3x^-_2 + 2x'_3 \\[1ex] \text{p.p.} \quad x_1 + 2x^+_2 - 2x^-_2 + x'_3 &\le 4 \\ -x_1 - 5x^+_2 + 5x^-_2 + 2x'_3 &\le -2 \\ 2x_1 - 3x^+_2 + 3x^-_2 + 4x'_3 &\le 1 \\ -2x_1 + 3x^+_2 - 3x^-_2 - 4x'_3 &\le -1 \\ x_1, x^+_2, x^-_2, x'_3 &\ge 0 \end{aligned} $$
V splošnem lahko zapišemo linearni program v standardni obliki kot $$ \begin{aligned} \max \ c_1 x_1 + c_2 x_2 + \dots + c_n x_n \\[1ex] \text{p.p.} \quad a_{11} x_1 + a_{12} x_2 + \dots a_{1n} x_n &\le b_1 \\ a_{21} x_1 + a_{22} x_2 + \dots a_{2n} x_n &\le b_2 \\ &\ \ \vdots \\ a_{m1} x_1 + a_{m2} x_2 + \dots a_{mn} x_n &\le b_m \\ x_1, x_2, \dots, x_n &\ge 0 \end{aligned} $$
Matrična oblika: $$ x = \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{bmatrix}, \quad c = \begin{bmatrix} c_1 \\ c_2 \\ \vdots \\ c_n \end{bmatrix} \in \mathbb{R}^n, \quad b = \begin{bmatrix} b_1 \\ b_2 \\ \vdots \\ b_m \end{bmatrix} \in \mathbb{R}^m, \quad A = [a_{ij}]_{i,j=1}^{m,n} \in \mathbb{R}^{m \times n} $$
$$ \begin{aligned} \max \ c^\top x \\[1ex] \text{p.p.} \quad A x &\le b \\ x &\ge 0 \end{aligned} $$
Definicija. Množica $A \subseteq \mathbb{R}^n$ je konveksna, če za vsaka $x, y \in A$ in vsak $\lambda \in [0, 1]$ velja $(1 - \lambda) x + \lambda y \in A$.
- $\sum_{i=1}^k \alpha_i x_i$ z $\sum_{i=1}^k \alpha_i = 1$ je afina kombinacija točk $x_i$ ($1 \le i \le k$).
- Afin prostor: "premaknjen" linearen prostor = afina kombinacija točk neke množice
- $\sum_{i=1}^k \alpha_i x_i$ z $\sum_{i=1}^k \alpha_i = 1$ in $\alpha_i \ge 0$ ($1 \le i \le k$) je konveksna kombinacija točk $x_i$ ($1 \le i \le k$).
Torej: množica $A$ je konveksna, če je vsaka daljica s krajišči v množici $A$ v celoti vsebovana v $A$.
Primer.
- Konveksne množice v $\mathbb{R}$: intervali
- Krogla v $\mathbb{R}^n$ je konveksna, sfera pa ne
- Polprostor v $\mathbb{R}^n$ je konveksen: $$ \begin{aligned} a_1 x_1 + a_2 x_2 + \dots + a_n x_n &\le b &&/ \cdot (1 - \lambda) \\ a_1 y_1 + a_2 y_2 + \dots + a_n y_n &\le b &&/ \cdot \lambda \\ a_1 ((1-\lambda) x_1 + \lambda y_1) + \dots + a_n ((1-\lambda) x_n + \lambda y_n) &\le (1-\lambda) b + \lambda b = b \end{aligned} $$ $\Rightarrow$ $(1-\lambda) x + \lambda y$ je tudi v polprostoru.
Trditev. Presek konveksnih množic je konveksen: $A_i$ ($i \in I$) konveksne $\Rightarrow \bigcap_{i \in I} A_i$ konveksna.
Dokaz. Preveriti moramo: za vsaka $x, y \in \bigcap_{i \in I} A_i$ in vsak $\lambda \in [0, 1]$ velja $\forall i \in I: (1-\lambda) x + \lambda y \in A_i$. To je res, ker so množice $A_i$ ($i \in I$) konveksne.
Unija konveksnih množic ni nujno konveksna!