Dualność problemów programownia liniowego.

Rozważmy problem programowania liniowego

$$\inf_{x\in \mathbb{R}^{n}}<c,x> \rightarrow ?, \quad Ax \leq b,$$ (9.1)

Dualnym problemem PL do () nazywa się problem ekstremalny

$$\sup_{y\in \mathbb{R}^{m}}<b,y> \rightarrow ?, \quad A^{*}y=c, \quad y \leq 0.$$ (9.2)

Odpowiednio, dualnym problemem do problemu (gdzie $x \in \mathbb{R}^{n}, \, c \in \mathbb{R}^{n}, \, b \in \mathbb{R}^{m}$)

$$\sup_{x\in \mathbb{R}^{n}}<c,x> \rightarrow ?, \quad Ax=b, \quad x \geq 0.$$ (9.3)

będzie problem ekstremalny

$$\inf_{y\in \mathbb{R}^{m}}<b,y> \rightarrow ?, \quad A^{*}y \geq c,$$ (9.4)

gdzie $y,b \in \mathbb{R}^{m}, \, c \in \mathbb{R}^{n}$.

Najbardziej symetryczne są problemy w postaci normalnej:

$$\inf_{x\in \mathbb{R}^{n}}<c,x> \rightarrow ?, \quad Ax \leq b, \quad x \geq 0,$$ (9.5)

oraz dualny problem do ()

$$\inf_{y\in \mathbb{R}^{m}}<b,y> \rightarrow ?, \quad A^{*}y \geq c, \quad y \geq 0.$$ (9.6)

Damy dowód dla ().

$\lhd$ Włączymy problem () w rodzinę problemów PL z parametrem $\alpha \in \mathbb{R}^{m}:$

$$\inf_{x\in \mathbb{R}^{n}}<c,x> \rightarrow ?, \quad Ax \leq \alpha,$$ (9.7)

Wartość problemu PL () oznaczamy $S(\alpha)$:

$$S(\alpha):=\inf_{Ax \leq \alpha}<c,x>$$ (9.8)

i będziemy nazywać $S$-funkcją problemu (), a $S(b)$ jego poszukiwaną wartością.

Dość prosto zobaczyć, że $S$-funkcja () jest wypukła. Jej przekształcenie Fenchel'a oznaczmy $S^{*}({\alpha}^{*}), \, {\alpha}^{*} \in \mathbb{R}^{n}$. Wtedy otrzymujemy:

$$S^{*}({\alpha}^{*}):=\sup_{\alpha \in \mathbb{R}^{n}}\{<{\alpha}^{*},\alpha>-S(\alpha)\}=$$ (9.9)

$$= \sup_{\alpha\in \mathbb{R}^{m}}\big\{<{\alpha}^{*},\alpha> - \inf_{x}\{<c,x>\,: \, Ax \leq \alpha\}\big\}=$$

$$= \sup_{\alpha,x}\big\{ \{<{\alpha}^{*},\alpha> -<c,x>\,: \, Ax \leq \alpha \}\big\}=$$

$$= \left \{ \begin{array}{ll} \underset{x\in \mathbb{R}^{n}}{\... ...*} \leq 0\}.\\ + \infty, & {\alpha}^{*}>0. \end{array}\right.=$$

$$= \left \{ \begin{array}{ll} \underset{x\in \mathbb{R}^{n}}{\... ...*} \leq 0\}.\\ + \infty, & {\alpha}^{*}>0. \end{array}\right.=$$

$$= \left \{ \begin{array}{ll} 0,{A}^{*}{\alpha}^{*}=c,\,& {\alpha}^{*} \leq 0\\ + \infty, & {\alpha}^{*}>0. \end{array}\right.$$

Ponieważ $S^{**}(\alpha)=S(\alpha)$, jeśli $S(\alpha), \, \alpha \in \mathbb{R}^{n}$, jest funkcją domkniętą, znajdujemy z () że:

$$S^{**}(\alpha)=\sup_{{\alpha}^{*}\in \mathbb{R}^{m} }\{<\alpha,{\alpha}^{*}>-S^{*}({\alpha}^{*})\}=$$ (9.10)

$$=\,\sup_{{\alpha}^{*}\in \mathbb{R}^{m}}\{<\alpha,{\alpha}^{*}>: \, A^{*}{\alpha}^{*}=c, \quad {\alpha}^{*} \leq0\}.$$

W szczególności,

$$S^{**}(b)=\sup_{{\alpha}^{*}\in \mathbb{R}^{m}}\{<{\alpha}^{*},b>\,: \, A^{*}{\alpha}^{*} =c, \, {\alpha}^{*}\leq 0\}=S(b),$$ (9.11)

gdy funkcja $S(\alpha), \, \alpha \in \mathbb{R}^{n}$, jest domknięta. Problem () jest dualnym do (), jak było wypisane w (). Z drugiej strony $S$-funkcja () jest domnięta ponieważ nadwykres funkcji $S$ jest zbiorem domkniętym wg. lematu o domkniętości skończenie zgenerowanego stożka, jakim jest zbiór
$\{x \in \mathbb{R}^{n}: \, Ax \leq \alpha\}$ $\rhd$

9.1   Uwaga.Podobną metodę można stosować do następnych trzech podstawowych problemów PL:

i)

Zagadnienie ogólne PL:

$$\inf_{x \in \mathbb{R}^{n}}<c,x> \rightarrow ?, \quad Ax \leq b;$$ (9.12)

ii)

Zagadnienie PL w postaci kanonicznej:

$$\sup_{x\in \mathbb{R}^{n}}<c,x> \rightarrow ?, \quad Ax= b, \quad x \geq 0;$$ (9.13)

iii)

Zagadnienie PL w postaci normalnej:

$$\sup_{x\in \mathbb{R}^{n}}<c,x> \rightarrow ?, \quad Ax \leq b, \quad x \geq 0;$$ (9.14)

gdzie $x \in \mathbb{R}^{n}, \, c \in \mathbb{R}^{n}$ i $b \in \mathbb{R}^{m}$

9.2   Uwaga. Jest oczywistym że problem PL () jest równoważny przy odwzorowaniu $c: \, \rightarrow \,-c$

$$\sup_{x\in \mathbb{R}^{n}}<c,x> \rightarrow ?, \quad Ax \leq b,$$ (9.15)

co już był rozważany w rozdziale 6.

9.3   Uwaga. Warunek $Ax \leq b$ w () można rozpisać w takiej postaci na mocy definicji

$$\sum_{k=1}^{n}A_{jk}x_{k} \leq b_{j}, \quad j=\overline{1,m}.$$ (9.16)

Zdefiniujmy teraz na mocy () takie $m\in\mathbb{Z}_{+}$ funkcjonałów liniowych na $\mathbb{R}^{n}$:

$$\beta_{j}:=(A_{j1},A_{j2}, \ldots, A_{jn}) \in \mathbb{R}^{n}, \quad j=\overline{1,m}.$$ (9.17)

Wtedy oczywiście () przyjmie postać zbioru $m\in\mathbb{Z}_{+}$ funkcjonałów ():

$$\beta_{j}(x) \leq b_{j}, \quad j=\overline{1,m},$$ (9.18)

co dokładnie jest to samo co ().