01LIP:Kapitola1

Z WikiSkripta FJFI ČVUT v Praze
Přejít na: navigace, hledání
PDF [ 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.
ZIPKompletní zdrojový kód včetně obrázků.

Součásti dokumentu 01LIP

součástakcepopisposlední editacesoubor
Hlavní dokument editovatHlavní stránka dokumentu 01LIPAdmin 1. 8. 201001:38
Řídící stránka editovatDefiniční stránka dokumentu a vložených obrázkůAdmin 7. 9. 201513:46
Header editovatHlavičkový souborAdmin 1. 8. 201001:39 header.tex
Kapitola1 editovatÚvodAdmin 1. 8. 201001:40 kapitola1.tex
Kapitola2 editovatDualita v LPPohanjur 3. 7. 201120:33 kapitola2.tex
Kapitola3 editovatSimplexová metodaKarel.brinda 13. 9. 201017:32 kapitola3.tex
Kapitola4 editovatPrincip dekompoziceAdmin 1. 8. 201001:40 kapitola4.tex
Kapitola5 editovatCeločíselné programováníAdmin 1. 8. 201001:40 kapitola5.tex
Kapitola6 editovatAplikace lineárního programování v teorii her Admin 1. 8. 201001: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}