Verze z 3. 7. 2011, 20:30

Zdrojový kód

%\wikiskriptum{01LIP}
\section{Dualita v~LP}
 
\begin{align*}
\text{Primární  úloha:} && \text{Duální úloha:}&\\
\min z&=\sum_{j=1}^n c_jx_j & \max w&=\sum_{i=1}^m y_ib_i\\
\sum_{j=1}^n a_{ij}x_j&\ge b_i,\ i\in\I\subset\hat m & y_i&\ge 0,\ i\in\I\subset\hat m\\
\sum_{j=1}^n a_{ij}x_j&= b_i,\ i\in\hat m\sm\I & y_i&\in\R,\ i\in\hat m\sm\I\\
x_j&\ge 0,\ j\in\J\subset\hat n & \sum_{i=1}^m y_ia_{ij}&\le c_j,\ j\in\J\subset\hat n\\
x_j&\in\R,\ j\in\hat n\sm\J & \sum_{i=1}^m y_ia_{ij}&= c_j,\ j\in\hat n\sm\J\\
\end{align*}
 
Úloha ve {\bf standardním tvaru}: samé nerovnice
\begin{align*}
\min z& =cx & \max w& =yb\\
\A x& \ge b & y\A& \le c\\
x& \ge 0 & y& \ge 0.
\end{align*}
 
Úloha v~{\bf kanonickém tvaru}: samé rovnice, nezápornost
\begin{align*}
\min z& =cx & \max w& =yb\\
\A x& = b & y\A& \le c\\
x& \ge 0 & y& \lesseqgtr 0.
\end{align*}
 
\begin{theorem}
\label{v_pd}
Nechť je dána dvojice (duálních) úloh LP, nechť $\x$
(resp. $\y$) je přípustné řešení primární, resp. duální
úlohy. Potom platí: $\y b\le c\x$.
\begin{proof}
Pro úlohu ve standardním tvaru:
\begin{align*}
\A\x&\ge b & \y\A\le c\\
\x&\ge 0 & \y\ge 0
\end{align*}
vynásobením $\x$ zprava a $\y$ zleva dostaneme
\begin{align*}
\y\A\x&\ge\y b & \y\A\x\le c\x,
\end{align*}
tedy $\y b\le\y\A\x\le c\x$. Pokud není úloha ve standardním tvaru, nic
se nemění, je nutné si uvědomit, že nerovnici odpovídá v~duální úloze
podmínka nezápornosti, tudíž se nerovnosti nenaruší.
\end{proof}
\end{theorem}
 
\begin{theorem}[o~dualitě]
Nechť je dána dvojice úloh LP ve standardním tvaru. Potom nastává
právě jedna z~následujících možností:
\begin{enumerate}[(i)]
\item Obě úlohy mají optimální řešení a hodnoty účelových funkcí na
nich jsou si rovny.
\item Jedna z~úloh nemá žádné přípustné řešení, druhá má přípustné
řešení, ale nemá optimální řešení.
\item Žádná z~úloh nemá přípustné řešení.
\end{enumerate}
\begin{proof}
Řešme soustavu nerovnic
\begin{align*}
\A x-tb&\ge 0 & x&\ge 0\\
-y\A+tc&\ge 0 & y&\ge 0\\
yb-cx&\ge 0   & t&\ge 0.
\end{align*}
Nechť $x_0,y_0,t_0$ je řešením této soustavy (existenci zaručuje věta
\ref{v_lin_ner}).
\begin{enumerate}
\item Nechť $t_0>0$. Pak
\begin{align*}
\A x_0&\ge t_0 b & \implies && \A\frac{x_0}{t_0}&\ge b\\
y_0\A&\le t_0 c & \implies && \frac{y_0}{t_0}\A&\le c
\end{align*}
$\frac{x_0}{t_0}$ a $\frac{y_0}{t_0}$ jsou přípustná řešení primární,
resp. duální úlohy. Dokážeme, že jsou optimální:
\[
y_0 b\ge c x_0\implies\frac{y_0}{t_0}b\ge c\frac{x_0}{t_0}.
\]
Protože ale podle věty \ref{v_pd} je
\[\frac{y_0}{t_0}b\le c\frac{x_0}{t_0},\]
je
\[\frac{y_0}{t_0}b= c\frac{x_0}{t_0},\]
takže tato řešení jsou optimální a hodnoty účelové funkce se na nich
rovnají.
\item Buď $t_0=0$. Dokážeme, že v~tomto případě nemohou mít obě úlohy
současně přípustné řešení. Platí, že
\begin{align*}
\A x_0&\ge 0 & x_0&\ge 0\\
y_0\A&\le 0 & y_0&\ge 0.
\end{align*}
Předpokládejme, že existují přípustná řešení obou úloh, označme je
$\x$, $\y$. Vynásobením nerovnic dostaneme
\begin{align*}
0&\ge y_0\A & \A\x&\ge b & \implies && 0&\ge y_0\A\x\ge y_0 b\\
0&\le \A x_0 & \y\A&\le c & \implies && 0&\le \y\A x_0\le c x_0,
\end{align*}
tedy $c x_0\ge y_0 b$. Z~věty \ref{v_lin_ner} ale okamžitě vyplývá, že $y_0 b-c
x_0+t_0>0$, tedy $y_0 b>c x_0$, což je spor.
 
Nechť $\x$ je přípustné řešení primární úlohy, nechť duální nemá
přípustné řešení. Dokážeme, že účelová funkce není omezená. Uvažujme
vektor $\x+\alpha x_0$, kde $\alpha\ge 0$. Platí, že
\[\x+\alpha x_0\ge0,\quad
\underbrace{\A\x}_{\ge b}+
\underbrace{\alpha\A x_0}_{\ge 0}\ge b,\]
takže $\x+\alpha x_0$ je přípustné řešení primární úlohy pro libovolné
$\alpha\ge 0$.
Protože $0\ge y_0\A\x\ge y_0 b>c x_0$, tedy $c x_0<0$, je
\[\lim_{\alpha\to +\infty}c(\x+\alpha x_0)=
\lim_{\alpha\to\infty}c\x+\alpha c x_0=-\infty.\]
\item Případ (iii) může nastat například v~úloze
\[
\A=
\begin{pmatrix}
-1 & 0 \\
0 & 1
\end{pmatrix},
\quad
b=\begin{pmatrix}
1\\ 1
\end{pmatrix},
\quad
c=(1,-1),
\]
kde podmínky $-x_1\ge 1\wedge x_1\ge 0$ a
$y_2\le -1\wedge y_2\ge 0$ evidentně nelze splnit.\qed
\end{enumerate}
\noqed
\end{proof}
\begin{remark}
 Hodnota účelové funkci na množine optimálních řešení je konstantní.
\begin{proof}
 Nechť množina optimálních řešení dané úlohy LP obsahuje alespoň dva prvky. Pro spor předpokládejme že existují dvě optimální řešení $\x_1 ,\x_2$  takové, že $z(\x_1) \neq z(\x_2)$. Bez ujmy na obecnosti nechť $z(\x_2) > z(\x_1)$.
 Nechť $\y_1 ,\y_2$ jsou příslušná optimální řešení úlohy duální. Pak platí $c\x_1 \textless \y_2 b$ což je spor s předchozí větou.
\end{proof}
\end{remark}
\end{theorem}
 
\begin{theorem}[o~slabé komplementaritě]
Nechť je dána dvojice (duálních) úloh LP, nechť $\x$
(resp. $\y$) jsou přípustná řešení primární (resp. duální)
úlohy. Potom $\x$ a $\y$ jsou optimální, právě když
$\y(\A\x-b)=0$ a
$(c-\y\A)\x=0$.
\begin{proof}
Označme $\alpha=\y(\A\x-b)$, $\beta=(c-\y\A)\x$. Platí, že
$\alpha+\beta=c\x-\y b$.
\begin{enumerate}[1)]
\item $\Rightarrow$: Platí, že $\alpha\ge 0$ a $\beta\ge 0$. Pro
standardní tvar je to jasné (nerovnice násobím kladnými čísly), jinak
ale zápornými čísly násobím vždy jen rovnice, takže i~v~tom případě je
to korektní.
 
Pro optimální řešení platí $\alpha+\beta=c\x-\y
b=0$, takže $\alpha=\beta=0$.
\item $\Leftarrow$: $c\x=\y b$, takže řešení je optimální.\qed
\end{enumerate}
\noqed
\end{proof}
\end{theorem}
 
\begin{dusl}
Platí
\begin{align*}
\y_i>0&\implies \A_{i\bullet}\x=b_i & 
  \y\A_{\bullet i}<c_i&\implies \x_i=0 \\
\A_{i\bullet}\x>b_i&\implies\y_i=0 &
  \x_i>0&\implies\y\A_{\bullet i}=c_i.
\end{align*}
To mi umožňuje při znalosti optimálního řešení primární úlohy nalézt
řešení duální. Nulové složky $y$ určím rovnou, ostatní řešením
soustavy rovnic $\y\A_{\bullet i}=c_i$.
 
Tímto způsobem lze testovat i~optimalitu řešení: Pokud se mi k~$\x$
podaří tímto způsobem najít $\y$, které je přípustné, je $\x$
optimální.
\end{dusl}
 
\begin{theorem}[o~silné komplementaritě]
Nechť je dána dvojice úloh LP ve standardním tvaru, nechť obě úlohy
mají přípustná řešení. Potom existují optimální řešení $\x$ resp. $\y$
taková, že
\begin{align*}
\A\x-b+\y^T&>0\\
c-\y\A+\x^T&>0.
\end{align*}
\begin{proof}
Důsledek věty \ref{v_lin_ner} a důkazu věty o~dualitě.
\end{proof}
\end{theorem}
 
\begin{define}
Krajním bodem (vrcholem) konvexní množiny nazýváme takový bod této
množiny, který není konvexní kombinací dvou jiných různých bodů této
množiny.
\end{define}
 
\begin{lemma}
Množina vzniklá průnikem poloprostorů je konvexním obalem svých
vrcholů.
\end{lemma}
 
\begin{theorem}
Nechť $f$ je konkávní funkce definovaná na konvexním mnohostěnu
$T$. Potom tato funkce nabývá svého minima v~krajním bodě $T$.
\begin{proof}
Označme $v_1,\dots,v_k$ vrcholy $T$. Pak podle předchozího lemmatu je
$T=\kob{v_1,\dots,v_k}$.
Buď $x\in T$. Pak
\[x=\sum_{j=1}^k\alpha_j v_j,\quad \alpha\ge 0,
\quad\sum_{j=1}^k\alpha_j=1.\]
\[f(x)=f\left(
\sum_{j=1}^k\alpha_j v_j
\right)\ge
\sum_{j=1}^k\alpha_j f(v_j)\ge
\sum_{j=1}^k\alpha_j\min_{j\in\hat k}f(v_j)=
\min_{j\in\hat k} f(v_j)\underbrace{\sum_{j=1}^k\alpha_j}_{=1}=
\min_{j\in\hat k} f(v_j)=f(v_{j_0}).\qed
\]
\noqed
\end{proof}
\end{theorem}
 
\begin{define}
Nechť je dána soustava lineárních rovnic $\A x=b$, nechť $\x$ je její
řešení. Řekneme, že $\x$ je bazické řešení, právě když sloupce matice
$\A$ odpovídající nenulovým složkám $\x$ jsou lineárně nezávislé.
\end{define}
 
\begin{remark}
V~lineárním programování je $\A\in\R^{m,n}$, $\A x=b$, $m<n$,
$\h(\A)=m$. Buď $\A=(\B|\mathbf N)$, kde $\B$ je regulární. Pak
\[x=\begin{pmatrix}
x_\B\\x_{\mathbf N}
\end{pmatrix},\]
kde $x_{\mathbf N}=0$, $x_\B=\B^{-1}b$. Pokud jsou všechny složky
$x_\B\not=0$ , nazýváme takové řešení {\bf nedegenerované}, jinak {\bf
degenerované}.
\end{remark}
 
\begin{theorem}
Každá řešitelná soustava lineárních rovnic má bazické řešení.
\begin{proof}
Soustavu převedu na horní stupňovitý tvar, složky řešení odpovídající
vedlejším sloupcům položím rovny nule, ostatní dopočítám. Získané
řešení je bazické.
\end{proof}
\end{theorem}
 
\begin{theorem}
Má-li soustava lineárních rovnic nezáporné řešení, má i~bazické
nezáporné řešení.
\begin{proof}
Indukcí podle počtu sloupců $n$.
\begin{enumerate}[1)]
\item Buď $n=1$, $x_1\A_{\bullet 1}=b$. Je-li $\A_{\bullet 1}\not=0$,
je $x_1$ bazické. Pokud $\A_{\bullet 1}=0$, musí být $b=0$ a $x_1=0$
je bazické řešení.
\item Buď
\[\x=
\begin{pmatrix}
\x_1\\\vdots\\\x_n
\end{pmatrix}
\ge 0\]
nezáporné řešení soustavy
\[\sum_{j=1}^n\A_{\bullet j} x_j=b.\]
\begin{enumerate}[A)]
\item Existuje $j_0\in\hat n$ takové, že $\x_{j_0}=0$. Pak soustava
\[\sum_{\substack{j=1\\j\not=j_0}}^n\A_{\bullet j} x_j=b\]
o~$n-1$ sloupcích má nezáporné řešení a podle indukčního předpokladu
má i~bazické nezáporné řešení.
\item $\x_j>0$ pro každé $j\in\hat n$:
\begin{enumerate}[a)]
\item $(\A_{\bullet j})_{j\in\hat n}$ je lineárně nezávislý, tedy
řešení je bazické.
\item $(\A_{\bullet j})_{j\in\hat n}$ je lineárně závislý. Uvažujme
netriviální lineární kombinaci
\[\sum_{j=1}^n\lambda_j\A_{\bullet j}=0.\]
Bez újmy na obecnosti můžeme předpokládat, že existuje alespoň jedno
$j\in\hat n$ tak, že $\lambda_j>0$ (pokud ne, můžeme sumu vynásobit
$-1$ a stále bude rovna nule). Položme
\[\max_{j\in\hat n}\frac{\lambda_j}{\x_j}=
\frac{\lambda_{j_0}}{\x_{j_0}}>0.\]
Nulovou netriviální kombinaci vynásobíme
$-\frac{\x_{j_0}}{\lambda_{j_0}}$ a přičteme k~ní soustavu rovnic:
\[\sum_{j=1}^n\left(
\x_j-\frac{\lambda_j\x_{j_0}}{\lambda_{j_0}}
\right)\A_{\bullet j}=b,\]
\[\sum_{j=1}^n
\underbrace{\frac{\x_j\x_{j_0}}{\lambda_{j_0}}}_{>0}
\underbrace{
\left(
\frac{\lambda_{j_0}}{\x_{j_0}}-\frac{\lambda_j}{\x_j}
\right)}_{\ge 0}
\A_{\bullet j}=b.\]
Alespoň $j_0$-tý sčítanec je nulový. Našli jsme tak nezáporné řešení
soustavy o~$n-1$ sloupcích, podle indukčního předpokladu existuje
i~bazické nezáporné řešení.
\qed
\end{enumerate}
\end{enumerate}
\end{enumerate}
\noqed
\end{proof}
\end{theorem}
 
\begin{theorem}
Nechť 
$T=\{x \in R^{n,1} | \A_{i\bullet}x \le b_i,\ i\in \J \subset \hat m \wedge \A_{i\bullet}x = b_i, i \in \hat m - \J\}$,
$m\ge n$, $\x\in T$. Potom $\x$ je krajní bod $T$, právě když existují
navzájem různé indexy $i_1,\dots,i_n\in\hat m$ takové, že $\x$ je
jediným řešením soustavy lineárních rovnic $\A_{i\bullet}x=b_i$,
$i\in\{i_1,\dots,i_n\}$ (tzn. submatice
\[\subm{\A}{i_1,\dots,i_n}{1,\dots,n}=\overline\A\]
je regulární).
\begin{proof}
\begin{enumerate}[1)]
\item $\Leftarrow$: Buďte $x_1,x_2\in T$, $x_1\not=x_2$ takové, že
$\x=\alpha x_1+(1-\alpha)x_2$,
\[\overline b=\begin{pmatrix}
b_{i_1}\\\vdots\\b_{i_n}
\end{pmatrix}.\]
Pak
\[\overline b=\overline\A\x=\alpha\overline\A x_1+
(1-\alpha)\overline\A x_2\le\alpha\overline b+
(1-\alpha)\overline b=\overline b,\]
tedy $\overline\A x_1=\overline b$ a $\overline\A x_2=\overline b$,
což je spor s~jednoznačností řešení.
\item $\Rightarrow$: Položme $\I=\{i\in\hat m|\A_{i\bullet}\x=b_i\}$
\begin{enumerate}[a)]
\item Dokážeme, že $\I$ je neprázdná. Předpokládejme, že $\I=\emptyset$,
tj. $\A_{i\bullet}\x<b_i$ pro každé $i\in\hat m$. Buď 
$\tilde x\in\R^{n,1}$, libovolné, $\tilde x\not=0$. Zvolme
$x_1=\x+\epsilon\tilde x$, $x_2=\x-\epsilon\tilde x$,
$\epsilon>0$. Pak pro dostatečně malé $\epsilon$ platí
$\A_{i\bullet}x_{1,2}=
\A_{i\bullet}\x\pm\epsilon\A_{i\bullet}\tilde x\le b_i$ pro každé
$i\in\hat m$.
Pak ale $x_1,x_2\in T$, $x_1\not=x_2$ a $\x=\frac12 x_1+\frac12 x_2$,
tedy $\x$ není krajní bod, což je spor.
\item Dokážeme, že $\abs{\I}\ge n$. Předpokládejme, že
$\abs{\I}<n$. Pak musí existovat $\tilde x\not=0$ takové, že
$\A_{i\bullet}\tilde x=0$ pro $i\in\I$, neboť matice soustavy má
hodnost menší než $n$. Zvolme opět $x_1=\x+\epsilon\tilde x$,
$x_2=\x-\epsilon\tilde x$. Dosazením dostaneme stejnou nerovnost jako
v~předchozím případě (rovnosti se nenaruší, protože
$\A_{i\bullet}\tilde x=0$) a opět dojdeme ke sporu.
\item $\h((\A_{i\bullet})_{i\in\I})=n$, právě když
$\lob{(\A_{i\bullet})_{i\in\I}}=\R^n$. Hodnost dokážeme stejně jako v~předchozím případě, pak můžeme vybrat $n$-člennou bázi.\qed
\end{enumerate}
\end{enumerate}
\noqed
\end{proof}
\end{theorem}
 
\begin{dusl}
Buď
\[
T\equiv\left|
\begin{split}
\A x&=b\\
x&\ge 0.
\end{split}
\right.
\]
Pak $\x$ je bazické nezáporné řešení soustavy $\A x=b$, právě když
$\x$ je krajní bod $T$.
\begin{proof}
\begin{enumerate}[1)]
\item $\Rightarrow$: Bez újmy na obecnosti můžeme předpokládat, že
prvních $k$ sloupců matice $\A$ je LN. Buď
\[\x=\begin{pmatrix}
\x_1\\\vdots\\\x_n
\end{pmatrix},\]
kde $\x_i>0$ pro $i\in\hat k$, $\x_i=0$ pro $i>k$ bazické řešení
soustavy $\A x=b$. Potom
\[
\h\left(\subm{\A}{i_1,\dots,i_k}{1,\dots,k}\right) = k.
\]
Soustava rovnic
\begin{align*}
\A_{{i_j}\bullet}x_j&=b_{i_j},\ j\in\hat k\\
x_j&=0,\ j>k~\end{align*}
má podle Frobeniovy věty jediné řešení $\x$, tedy $\x$ je krajní bod
$T$.
\item $\Leftarrow$: Buď $\x$ krajní bod $T$. 
 
Buď $\x_i>0$ pro $i\in\hat k$, $\x_i=0$ pro $i>k$.
\[
\left(
\begin{array}{c|ccc}
\\
\text{regulární} & & 0\\
\\
\hline
& 1 & \\
0 &   & \ddots \\
& &   & 1
\end{array}
\right).
\]
Levý horní blok má nezávislé sloupce, tudíž prvních $k$ sloupců matice
$\A$ je lineárně nezávislých.\qed
\end{enumerate}
\noqed
\end{proof}
\end{dusl}
 
\begin{theorem}
Nechť je dána úloha LP v~kanonickém tvaru
($\min z=cx$, $\A x=b$, $x\ge 0$), nechť množina přípustných řešení je
neprázdná a omezená. Potom existuje bazické optimální řešení této
úlohy.
\begin{proof}
Množina je neprázdná a omezená $\implies$ je to konvexní mnohostěn
$\implies$ lineární funkce nabývá minima v~krajním bodě $\implies$
existuje bazické optimální řešení.
\end{proof}
\end{theorem}
 
\begin{define}
Pojmem {\bf řešit úlohu LP} rozumíme buď
\begin{enumerate}[(i)]
\item najít minimum $z$ a bod, v~němž $z$ minima nabývá nebo
\item ukázat, že $z$ není omezená zdola nebo
\item množina přípustných řešení je prázdná.
\end{enumerate}
\end{define}