Predavanje 2.3.
Dokaz KID. Simpleksna metoda za $\Pi$ se konča z zadnjim slovarjem z $$ z = z^\ast + \sum_{i=1}^{n+m} c^\ast_i x_i = \sum_{i=1}^n c_i x^\ast_i + \sum_{i=1}^n c^\ast_i x_i + \sum_{i=1}^m c^\ast_{n+i} x_{n+i}, $$ kjer velja $c^\ast_i \le 0$ ($1 \le i \le n+m$) in $c^\ast_i = 0$, če je $x_i$ bazna spremenljivka. Naj bo $y^\ast_{n+i} = -c^\ast_{n+i}$ ($1 \le i \le m$). Pokazali bomo, da je $y^\ast$ optimalna rešitev $\Pi'$. Velja $$ \begin{aligned} z &= \sum_{j=1}^n c_j x^\ast_j + \sum_{j=1}^n c^\ast_j x_j + \sum_{i=1}^m (-y^\ast_{n+i}) \left(b_i - \sum_{j=1}^n a_{ij} x_j\right) \\ &= \left(\sum_{j=1}^n c_j x^\ast_j - \sum_{i=1}^m b_i y^\ast_{n+i}\right) + \sum_{j=1}^n c^\ast_j x_j + \sum_{j=1}^n \left(\sum_{i=1}^m a_{ij} y^\ast_{n+i}\right) x_j \\ &= \left(\sum_{j=1}^n c_j x^\ast_j - \sum_{i=1}^m b_i y^\ast_{n+i}\right) + \sum_{j=1}^n \left(c^\ast_j + \sum_{i=1}^m a_{ij} y^\ast_{n+i}\right) x_j \\ \end{aligned} $$ Ker velja $z = \sum_{j=1}^n c_j x_j$, sledi $$ \begin{aligned} \sum_{j=1}^n c_j x^\ast_j - \sum_{i=1}^m b_i y^\ast_{n+i} &= 0, \\ c^\ast_j + \sum_{i=1}^m a_{ij} y^\ast_{n+i} &= c_j & (1 \le j \le n). \end{aligned} $$ Ker velja $y^\ast_{n+i} = -c^\ast_{n+i} \ge 0$ ($1 \le i \le m$) in $\sum_{i=1}^m a_{ij} y^\ast_{n+i} = c_j - c^\ast_j \ge c_j$ ($1 \le j \le n$), je $y^\ast$ dopustna rešitev za $\Pi'$. Ker velja $c^\top x^\ast = b^\top y^\ast$, je po Posledici 1 $y^\ast$ optimalna rešitev za $\Pi'$.
Če povzamemo:
- ŠID: $x, y$ dopustni za $\Pi, \Pi' \Rightarrow c^\top x \le b^\top y$
- KID: $\Pi$ optimalen $\Rightarrow \Pi'$ optimalen z isto optimalno vrednostjo
Imamo torej sledeče možnosti:
| $\Pi$ \ $\Pi'$ | nedopusten | neomejen | optimalen |
|---|---|---|---|
| nedopusten | ✔ | ✔ | ✗ (KID) |
| neomejen | ✔ | ✗ (ŠID) | ✗ (KID/ŠID) |
| optimalen | ✗ (KID) | ✗ (KID/ŠID) | ✔ |
Primer nedopustnih $\Pi$ in $\Pi'$:
| $$\Pi$$ | $$\Pi'$$ |
|---|---|
| $$\max \ 2x_1 - x_2 \\ \begin{aligned} \text{p.p.} && -x_1 + x_2 &\le -2 \\ && x_1 - x_2 &\le 1 \\ && x_1, x_2 &\ge 0 \end{aligned}$$ | $$\min \ -2y_3 + y_4 \\ \begin{aligned} \text{p.p.} && -y_3 + y_4 &\ge 2 \\ && y_3 - y_4 &\ge -1 \\ && y_3, y_4 &\ge 0 \end{aligned}$$ |
Izrek. Za linearna programa $\Pi$ in $\Pi'$ velja natanko ena od sledečih možnosti:
- oba sta optimalna,
- oba sta nedopustna, ali
- eden je neomejen, drugi pa nedopusten.
Izrek o dualnem dopolnjevanju (angl. complementary slackness). Naj bo $\Pi$ prvotni linearni program kot zgoraj in $\Pi'$ njegov dual, ter naj bosta $x$ in $y$ dopustni rešitvi za $\Pi$ oziroma $\Pi'$. Potem sta $x$ in $y$ optimalni rešitvi za $\Pi$ oziroma $\Pi'$ natanko tedaj, ko velja $$ \begin{aligned} \forall i &\in {1, \dots, m}: & \Big(\sum_{j=1}^n a_{ij} x_j &= b_i &&\lor& y_{n+i} &= 0\Big) \quad \text{in} \\ \forall j &\in {1, \dots, n}: & \Big(x_j &= 0 &&\lor& \sum_{i=1}^m a_{ij} y_{n+i} &= c_j\Big). \end{aligned} $$