01LIP:Kapitola1
Z WikiSkripta FJFI ČVUT v Praze
Verze z 1. 8. 2010, 02:40, kterou vytvořil Admin (diskuse | příspěvky) (Založena nová stránka: %\wikiskriptum{01LIP} \section{Úvod} \begin{define} Úlohou lineárního programování rozumíme nalezení minima (resp. maxima) {\bf účelové funkce} \[z=\sum_{j=1}^...)
[ 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 | 02:38 | ||
Řídící stránka | editovat | Definiční stránka dokumentu a vložených obrázků | Admin | 7. 9. 2015 | 14:46 | ||
Header | editovat | Hlavičkový soubor | Admin | 1. 8. 2010 | 02:39 | header.tex | |
Kapitola1 | editovat | Úvod | Admin | 1. 8. 2010 | 02:40 | kapitola1.tex | |
Kapitola2 | editovat | Dualita v LP | Pohanjur | 3. 7. 2011 | 21:33 | kapitola2.tex | |
Kapitola3 | editovat | Simplexová metoda | Karel.brinda | 13. 9. 2010 | 18:32 | kapitola3.tex | |
Kapitola4 | editovat | Princip dekompozice | Admin | 1. 8. 2010 | 02:40 | kapitola4.tex | |
Kapitola5 | editovat | Celočíselné programování | Admin | 1. 8. 2010 | 02:40 | kapitola5.tex | |
Kapitola6 | editovat | Aplikace lineárního programování v teorii her | Admin | 1. 8. 2010 | 02:41 | kapitola6.tex |
Zdrojový kód
%\wikiskriptum{01LIP} \section{Úvod} \begin{define} Úlohou lineárního programování rozumíme nalezení minima (resp. maxima) {\bf účelové funkce} \[z=\sum_{j=1}^n c_j x_j\] za podmínek \[\sum_{j=1}^n a_{ij} x_j\ge b_i,\quad i\in\I\subset\hat m,\] \[\sum_{j=1}^n a_{ij} x_j=b_i,\quad i\in\hat m\sm\I,\] \[x_j\ge 0,\quad j\in\J\subset\hat n,\] \[x_j\lesseqgtr 0,\quad j\in\hat n\sm\J,\] kde \[c=(c_1,\dots,c_n),\quad\A=(a_{ij})\in\R^{m,n},\quad b= \begin{pmatrix} b_1\\\vdots\\b_m \end{pmatrix} ,\quad x= \begin{pmatrix} x_1\\\vdots\\x_n \end{pmatrix} ,\quad y=(y_1,\dots,y_n). \] Každý vektor $x$ vyhovující soustavě omezení nazýváme {\bf přípustným řešením}. Přípustné řešení, na kterém nabývá $z$ extremální hodnoty, nazýváme {\bf optimálním řešením}. \end{define} \begin{remark} Ekvivalentní formulace úlohy LP: \begin{enumerate} \item Hledání maxima funkce $z$ je ekvivalentní hledání minima funkce $-z$. \item Převod nerovnic na rovnice zavedením {\bf slabých proměnných}: \[\sum_{j=1}^n a_{ij} x_j-s_i=b_i,\quad s_i\ge 0,\ i\in\I.\] \item Převod rovnic na nerovnice: \[\sum_{j=1}^n a_{ij} x_j\ge b_i,\quad\sum_{i=1}^m\sum_{j=1}^n a_{ij} x_j-b_i\le 0.\] \item Odstranění proměnných bez podmínky nezápornosti: Buď $x_j\in\R$, $j\in\hat n\sm\J$. Zavedeme proměnné $x_0$ a $x_j'$, dosadíme $x_j=x_j'-x_0$ a přidáme podmínky $x_0\ge 0$, $x_j'\ge 0$ pro $j\in\hat n\sm\J$. \end{enumerate} \end{remark} \begin{theorem} Z~následujících dvou soustav lineárních rovnic \begin{enumerate}[(i)] \item $\A x=b$ $(b\not=0)$, \item $y\A=0$, $yb\not=0$ \end{enumerate} má řešení právě jedna z~nich. \begin{proof} \begin{enumerate}[1)] \item Buď (i) řešitelná. Pak $b\in\lob{\A_{\bullet 1},\dots,\A_{\bullet n}}$. Buď $y\A=0$, takže $y\in\lob{\A_{\bullet 1},\dots,\A_{\bullet n}}^\perp$, tedy $y\perp b$ a $yb=0$, což je spor. \item Buď (i) neřešitelná, tedy $b\not\in\lob{\A_{\bullet 1},\dots,\A_{\bullet n}}=P$. Platí, že $P\oplus P^\perp=\R^{m,1}$, $b=u+v$, kde $u\in P$, $v\in P^\perp$. Platí, že $v\not=0$, protože $b\not\in P$. Protože $v\in P^\perp$, je $v^T\A=0$ a $v^Tb=v^Tu+v^Tv=0+\norm{v}^2\not=0$. Tedy $v$ řeší (ii).\qed \end{enumerate} \noqed \end{proof} \end{theorem} \begin{theorem} Z~následujících dvou výroků \begin{enumerate}[(i)] \item $\A x=b$ $(b\not=0)$ má nezáporné řešení, \item $y\A\ge0$, $yb<0$ má řešení \end{enumerate} je pravdivý právě jeden. \begin{proof} \begin{enumerate}[1)] \item (i) a (ii) nemohou platit najednou: Buď $\A x=b$, $x\ge 0$, vynásobením $y$ zleva a použitím (ii) dostáváme $y\A x=yb<0$. Buď $y\A\ge 0$, $yb<0$, pak $y\A x\ge 0$, což je spor. \item (i) neplatí $\implies$ (ii) platí: Nechť $\A x=b$ nemá nezáporné řešení: \begin{enumerate}[A)] \item $\A x=b$ nemá žádné řešení. Pak podle předchozí věty existuje $\y$ takové, že $y\A=0$, $yb\not=0$. (ii) vyhovuje buď $y$ nebo $-y$. \item $\A x=b$ je řešitelná, ale nemá nezáporné řešení: Důkaz provedeme indukcí podle počtu sloupců $n$. Buď $n=1$, $A_{\bullet 1}x_1=b$, $x_1<0$. Definujme $y=-b^T$, pak \[y\A=-b^T\A_{\bullet 1}= \frac{-b^Tb}{x_1}=\frac{-\norm{b}^2}{x_1}>0\] a $yb=-b^Tb=-\norm{b}^2<0$, tedy (ii) má řešení. Přechod $n-1\to n$: Nechť soustava $\A x=b$ má řešení, ale ne nezáporné. Pak ani soustava \[\sum_{j=1}^{n-1}\A_{\bullet j}x_j=b\] nemá nezáporné řešení, tedy existuje $\y$ takové, že $\y A_{\bullet j}\ge 0$ pro $j\in\hat{n-1}$ a $\y b<0$. \begin{enumerate}[a)] \item Je-li $\y\A_{\bullet n}\ge 0$, je $\y\A\ge 0$, takže (ii) má řešení. \item Buď $\y\A_{\bullet n}<0$. Uvažujme soustavu \[\sum_{j=1}^{n-1}\A'_{\bullet j}x_j'=b',\] kde \[\A'_{\bullet j}=\A_{\bullet j}- \frac{\y\A_{\bullet j}}{\y\A_{\bullet n}}\A_{\bullet n},\] \[b'=b-\frac{\y b}{\y\A_{\bullet n}}\A_{\bullet n}.\] Dále platí \[\sum_{j=1}^{n-1}\left( \A_{\bullet j}-\frac{\y\A_{\bullet j}}{\y\A_{\bullet n}}\A_{\bullet n} \right)x_j'=b-\frac{\y b}{\y\A_{\bullet n}}\A_{\bullet n},\] \[\sum_{j=1}^{n-1} \A_{\bullet j}x_j'+ \underbrace{ \left( \frac{\y b}{\y\A_{\bullet n}}- \sum_{j=1}^{n-1}\frac{\y\A_{\bullet j}} {\y\A_{\bullet n}}x_j' \right)}_{>0}\A_{\bullet n}=b.\] Tato soustava nemá nezáporné řešení, protože jinak by měla nezáporné řešení soustava $\A x=b$ a to je spor s~předpokladem. Existuje tedy $\y'$ takové, že $\y'\A'_{\bullet j}\ge 0$ a $\y'b'<0$ pro $j\in\hat{n-1}$. Definujme \[y=\y'-\frac{\y'\A_{\bullet n}}{\y\A_{\bullet n}}\y.\] Pro $j\in\hat{n-1}$ pak platí \[y\A_{\bullet j}=\y'\A_{\bullet j}- \frac{\y'\A_{\bullet n}}{\y\A_{\bullet n}} (\y\A_{\bullet j})= \y'\left( \A_{\bullet j}- \frac{\y\A_{\bullet j}}{\y\A_{\bullet n}}\A_{\bullet n} \right)=\y'\A'_{\bullet j}\ge 0.\] \[y\A_{\bullet n}=\y'\A_{\bullet n}- \frac{\y'\A_{\bullet n}}{\y\A_{\bullet n}}\y\A_{\bullet n}=0.\] \[yb=\y'b-\frac{\y'\A_{\bullet n}}{\y\A_{\bullet n}}\y b= \y'\left( b-\frac{\y b}{\y\A_{\bullet n}}\A_{\bullet n} \right)=\y'b'<0.\qed\] \end{enumerate} \end{enumerate} \end{enumerate} \noqed \end{proof} \end{theorem} \begin{theorem}[Farkaš] Z~následujících dvou soustav lineárních nerovnic \begin{enumerate}[(i)] \item $\A x\le b$ $(b\not=0)$, \item $y\A\ge 0$, $yb<0$ \end{enumerate} má nezáporné řešení právě jedna z~nich. \begin{proof} Buď $s$ vektor slabých proměnných \[s= \begin{pmatrix} s_1\\\vdots\\s_m \end{pmatrix} .\] Potom $\A x+s=b$, právě když $\tilde\A\tilde x=b$, kde $\tilde \A=(\A|\E)$, \[\tilde x= \begin{pmatrix} x_1\\\vdots\\x_n\\ s_1\\\vdots\\s_m \end{pmatrix} .\] Podmínka nezápornosti řešení $\A x\le b$ je ekvivalentní s~nezáporností řešení $\tilde\A\tilde x=b$. Dále platí, že $y\tilde\A\ge 0$, právě když $y\A\ge 0$ a $y\ge 0$. Soustava $y\A\ge 0$, $yb<0$ má nezáporné řešení, právě když $y\tilde\A\ge 0$, $yb<0$ má řešení. Tím jsme větu převedli na předchozí. \end{proof} \end{theorem} \begin{dusl} Z~následujících dvou soustav lineárních nerovnic \begin{enumerate} \item $\A x\ge b$, \item $y\A \le 0$, $yb>0$ \end{enumerate} má nezáporné řešení právě jedna. \begin{proof} Vynásobíme nerovnice $-1$. \end{proof} \end{dusl} \begin{theorem} Nechť $\K\in\R^{n,n}$ je čtvercová matice $n$-tého řádu, antisymetrická (tj. $\K^T=-\K$). Soustava lineárních nerovnic $\K x\ge 0$, $x\ge 0$ má alespoň jedno řešení $\x$ takové, že $\K\x+\x>0$. \begin{proof} Buď \[ \x_i= \begin{pmatrix} \x_{i_1}\\ \vdots\\ \x_{i_n} \end{pmatrix}\quad \text{pro $i\in\hat n$} \] \[ \x=\sum_{i=1}^n\x_i \] Položme $\A=\K$, $b=e_i^T$. Pak podle předchozí věty může nastat právě jeden ze dvou případů: \begin{enumerate}[1)] \item $\K\x_i\ge e_i^T\ge 0$, tedy $\K_{i\bullet}\x_i\ge 1$. \item $\x_i^Te_i^T>0\iff\x_{ii}>0$, $\x_i^T\K\le 0\iff\K^T\x_i\le 0\iff -\K\x_i\le 0\iff\K\x_i\ge 0$. \end{enumerate} V~obou případech je $\K_{i\bullet}\x_i+\x_{ii}>0$, takže $\K\x+\x>0$. \end{proof} \end{theorem} \begin{theorem} \label{v_lin_ner} Soustava lineárních nerovnic \[ \begin{split} \A x-tb&\ge 0\\ -y\A+tc&\ge 0\\ yb-cx&\ge 0 \end{split} \] má alespoň jedno řešení $x_0,y_0,t$ takové, že \[ \begin{split} \A x_0-t_0b+y_0^T&> 0\\ -y_0\A +t_0c+x_0^T&> 0\\ y_0b-cx_0+t_0&> 0. \end{split} \] \begin{proof} \[ \K= \begin{pmatrix} 0 & \A & -b \\ -\A^T & 0 & c^T \\ b^T & -c & 0 \end{pmatrix} \left( \begin{array}{l} y^T\\ x\\ t \end{array} \right)\ge 0.\qed \] \noqed \end{proof} \end{theorem}