01LIP:Kapitola2: Porovnání verzí
Z WikiSkripta FJFI ČVUT v Praze
m |
|||
Řádka 44: | Řádka 44: | ||
podmínka nezápornosti, tudíž se nerovnosti nenaruší. | podmínka nezápornosti, tudíž se nerovnosti nenaruší. | ||
\end{proof} | \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} | \end{theorem} | ||
Verze z 3. 7. 2011, 20:27
[ znovu generovat, | výstup z překladu ] | Kompletní WikiSkriptum včetně všech podkapitol. | |
PDF Této kapitoly | [ znovu generovat, | výstup z překladu ] | Přeložení pouze této kaptioly. |
ZIP | Kompletní zdrojový kód včetně obrázků. |
Součásti dokumentu 01LIP
součást | akce | popis | poslední editace | soubor | |||
---|---|---|---|---|---|---|---|
Hlavní dokument | editovat | Hlavní stránka dokumentu 01LIP | Admin | 1. 8. 2010 | 01:38 | ||
Řídící stránka | editovat | Definiční stránka dokumentu a vložených obrázků | Admin | 7. 9. 2015 | 13:46 | ||
Header | editovat | Hlavičkový soubor | Admin | 1. 8. 2010 | 01:39 | header.tex | |
Kapitola1 | editovat | Úvod | Admin | 1. 8. 2010 | 01:40 | kapitola1.tex | |
Kapitola2 | editovat | Dualita v LP | Pohanjur | 3. 7. 2011 | 20:33 | kapitola2.tex | |
Kapitola3 | editovat | Simplexová metoda | Karel.brinda | 13. 9. 2010 | 17:32 | kapitola3.tex | |
Kapitola4 | editovat | Princip dekompozice | Admin | 1. 8. 2010 | 01:40 | kapitola4.tex | |
Kapitola5 | editovat | Celočíselné programování | Admin | 1. 8. 2010 | 01:40 | kapitola5.tex | |
Kapitola6 | editovat | Aplikace lineárního programování v teorii her | Admin | 1. 8. 2010 | 01:41 | kapitola6.tex |
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} \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~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} \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}