Zdrojový kód
%\wikiskriptum{01LIP}
\section{Simplexová metoda}
Simplexová metoda se používá k~řešení úlohy v~kanonickém tvaru
\begin{align*}
\min z& =cx\\
\A x& = b\\
x& \ge 0.
\end{align*}
Tabulka simplexové metody: Matici soustavy rovnic $\A x=b$
\[
\begin{array}{lclllllllllll}
&a_{00} &= -z & & & & & + & a_{0,m+1} x_{m+1} &+& \cdots &+& a_{0n} x_n\\
&a_{10} &= & x_1 & & & & + & a_{1,m+1} x_{m+1} &+& \cdots &+& a_{1n} x_n\\
&a_{20} &= & & x_2 & & & + & a_{2,m+1} x_{m+1} &+& \cdots &+& a_{2n} x_n\\
&\vdots& & & &\ddots& & & & & & \\
&a_{m0} &= & & & & x_m & + & a_{m,m+1} x_{m+1} &+& \cdots &+& a_{mn} x_n
\end{array}
\]
zapisujeme do tabulky
\[
\left(
\begin{array}{c|cccccc}
a_{00} & 0 & \hdots & 0 & a_{0,m+1} & \hdots & a_{0n}\\
\hline
a_{10} & 1 & \hdots & 0 & a_{1,m+1} & \hdots & a_{1n}\\
\vdots & \vdots & \ddots & \vdots & \vdots & & \vdots\\
a_{m0} & 0 & \hdots & 1 & a_{m,m+1} & \hdots & a_{mn}\\
\end{array}
\right)
\]
Pokud $a_{i0}\ge 0$ pro $i\in\hat m$, nazýváme tabulku {\bf primárně
přípustnou}, je-li $a_{0i}\ge 0$, nazýváme tabulku {\bf duálně
přípustnou}.
Je-li tabulka primárně přípustná, vyjadřuje přípustné řešení primární
úlohy.
\subsection{Algoritmus simplexové metody}
\begin{enumerate}
\item Vyjdu z~primárně přípustné tabulky.
\item Je-li tabulka i~duálně přípustná, je optimální a končím.
\item Pokud není duálně přípustná, mezi sloupci, kde $a_{0i}<0$ vyberu
nějaký {\bf vedoucí sloupec} ($s$-tý).
\item Vyberu {\bf vedoucí řádek}: najdu
\[\min\left\{\left.
\frac{a_{i0}}{a_{is}}\right|
a_{is}>0
\right\}=\frac{a_{r0}}{a_{rs}}\ge 0\]
(tzv. {\bf prověrka poměrů}) a jako vedoucí zvolím $r$-tý. $x_r$ bude
nová nebazická proměnná a položím
\[x_s=\frac{a_{r0}}{a_{rs}}.\]
Prvek $a_{rs}$ nazýváme {\bf vedoucí prvek} ({\bf pivot}).
Pokud jsou všechny $a_{is}\le 0$, není účelová funkce $z$ omezená,
takže končím.
\end{enumerate}
Pokud je v~prvním sloupci nějaká nula, prověrka poměrů dá nulu a jsem
v~blbé situaci, protože nemůžu bezprostředně přejít k~jinému vrcholu.
\subsection{Časová náročnost}
Teoreticky je exponenciální: maximálně $\binom{m}{n}$.
\[n!\approx\frac{n^n}{e^n}\sqrt{2\pi n}\]
\[\binom{n}{\frac n2}=\frac{n!}{\left(\left(\frac n2\right)!\right)^2}
\approx\frac{\frac{n^n}{e^n}\sqrt{2\pi n}}
{\frac{\left(\frac{n}{2}\right)^n}{e^n}\pi n}= 2^n\sqrt{\frac{2}{\pi
n}},\]
tj. řádově $2^n$. V~praxi se to ale chová polynomiálně, obvykle
stačí cca. $2m$ až $3m$ iterací.
\subsection{Nalezení počátečního přípustného bazického řešení}
\begin{enumerate}
\item
Do každé rovnice přidáme tzv. {\bf umělou proměnnou} $x_i'\ge 0$.
Dostanu tak soustavu
\begin{align*}
x_1'+\sum_{j=1}^n a_{1j}x_j&=b_1\\
&\xvdots\\
x_m'+\sum_{j=1}^n a_{mj}x_j&=b_m\\
\min\xi&=\min\sum_{j=1}^m x_j'
\end{align*}
položím $x_1',\dots,x_m'=b_1,\dots,b_m$, $x_j=0$ pro $j\in\hat n$.
\begin{enumerate}
\item Je-li $\xi_{min}>0$, neexistuje přípustné řešení výchozí úlohy.
\item Je-li $\xi_{min}=0$, je $x$ přípustné řešení.
\end{enumerate}
\item Nerovnice typu $\A x\le b$, $b\ge 0$, $x\ge 0$ převedu na rovnice
se slabou proměnnou a slabé proměnné položím rovny $b$. {\bf Slabé
proměnné nejsou v~účelové funkci !}
\item Nerovnice typu
\[\sum_{j=1}^n a_{ij}x_j\ge b_i,\quad i\in k,\ b_i\ge 0\]
převedu na rovnice se slabou proměnnou a do každé z~nich přidám {\bf
stejnou} umělou proměnnou $x'$:
\[x'+\sum_{j=1}^n a_{ij}x_j-s_i=b_i,\quad s_i\ge 0,\ x'\ge 0.\]
Buď $\max\{b_i|i\in\hat k\}=b_l$. Soustavu nerovnic převedeme na novou
soustavu
\begin{align*}
x'+\sum_{j=1}^n a_{lj}x_j-s_l&=b_l\\
\sum_{j=1}^n(a_{lj}-a_{ij})x_j-s_l+s_i&=
\underbrace{b_l-b_i}_{\ge 0},\quad i\in\hat k\sm\{l\}.
\end{align*}
Proměnnou $s_l$ položím rovnou nule a proměnné $x'$ a $s_i$
dopočítám. Minimalizuji funkci $\xi=x'$. Neuškodí zopakovat, že {\bf v
účelové funkci se v~každém případě vyskytují pouze umělé proměnné}.
\end{enumerate}
Pokud mám soustavu, kde jsou rovnice i~nerovnice, lze tyto postupy
samozřejmě kombinovat.
\subsection{Zacyklení --- jak z~toho ven}
Zacyklením nazýváme situaci, kdy se při prověrce poměrů vyjde
nula. V~následujícím kroku se pak nezmění hodnota účelové funkce,
protože se k~ní tato nula přičte.
\begin{define}
Buď $x\in\R^n$, $x\not=0$. Vektor $x$ nazýváme {\bf lexikograficky
kladný} ($x\lexgr 0$), právě když první nenulová složka vektoru $x$ je
kladná. Pro dva různé vektory $x,y$ definujeme $x\lexgr y$, právě když
$x-y\lexgr 0$.
\end{define}
\begin{description}
\item[Dantzig] Vycházíme z~toho, že prvky nultého řádku jsou
jednoznačně určeny volbou báze. Vedoucí sloupec volím stejně,
tj. sloupec, v~jehož prvním řádku je záporné číslo.
Volba vedoucího řádku: Na počátku musí být všechny řádky
lexikograficky kladné (s~výjimkou nultého). Pokud nejsou, přečísluji
neznámé tak, aby jednotková matice byla nalevo. Kandidáta na vedoucí
řádek pak hledám mezi řádky, kde $a_{is}>0$. Pro každé $a_{is}>0$
vezmu vektor $(a_{i0},a_{i1},\dots,a_{in})$ a vydělím $a_{is}$. Získám
tak vektory
\[\left(
\frac{a_{i0}}{a_{is}},\frac{a_{i1}}{a_{is}},\dots,\frac{a_{in}}{a_{is}}
\right).\]
Z~těchto vektorů vyberu lexikograficky nejmenší ($r$-tý) a za vedoucí
řádek zvolím $r$-tý řádek.
\begin{theorem}
Při použití Dantzigova pravidla nedojde k~zacyklení.
\begin{proof}
Dokážeme, že v~každé další tabulce bude nultý řádek lexikograficky
větší a že řádky $1$ až $m$ zůstanou lexikograficky kladné.
Platí, že $a_{rs}>0$. Chceme dokázat, že pro $i$-tý řádek platí
\[(a_{i0},\dots,a_{in})-\frac{a_{is}}{a_{rs}}
(a_{r0},\dots,a_{rs})\lexgr 0.\]
Pokud $a_{is}=0$, je to zřejmé. Je-li $a_{is}<0$, přičítám k~lexikograficky kladnému řádku lexikograficky kladný řádek, tedy $i$-tý
řádek zůstane lexikograficky kladný. Pokud $a_{is}>0$, vydělím
nerovnici $a_{is}$ a dostanu
\[
\left(\frac{a_{i0}}{a_{is}},\dots,\frac{a_{in}}{a_{is}}\right)
\lexgr
\left(\frac{a_{r0}}{a_{rs}},\dots,\frac{a_{rn}}{a_{rs}}\right).
\]
Protože jsem volil vedoucí řádek tak, aby vektor napravo byl
lexikograficky nejmenší, je nerovnost splněna.
Pro nultý řádek nastává případ $a_{0s}<0$, přičítám k~němu
lexikograficky kladný vektor, takže bude lexikograficky větší.
\end{proof}
\end{theorem}
\item[Bland] Za vedoucí sloupec se (z kandidátů) zvolí sloupec odpovídající proměnné
s~nejmenším indexem. Z kandidátů na vyřazení z~báze při rovnosti prověrky poměrů
vezmeme proměnnou s nejmenším indexem.
\begin{theorem}
Při použití Blandova pravidla \uv{nejmenších indexů} nedojde k~zacyklení.
\begin{proof}
Větu dokážeme sporem. Předpokládejme, že máme degenerovanou úlohu,
posloupnost tabulek je nekonečná a žádná z~tabulek není
optimální. Proměnné rozdělíme na tři typy:
\begin{enumerate}[1)]
\item nikdy nejsou v~bázi,
\item jsou stále v~bázi,
\item vyskytují se jak v~bázi tak mimo bázi --- \uv{běhny}.
\end{enumerate}
Označme
\begin{itemize}
\item $x_t$ běhnu s~největším indexem,
\item$D$ tabulku, v~níž je $x_t$ bazická, ale v~následující není
bazická,
\item $x_s$ proměnnou, která je v~D nebazická, ale v~následující je
bazická,
\item $D^*$ tabulku, v~níž je $x_t$ nebazická, ale v~následující je
bazická,
\item $v$ prvek $a_{00}$ všech tabulek (nemění se),
\item $B=\{i\in\hat n|x_i\text{ je v $D$ bazická}\}$.
\item Pokud řádek vektoru $b$ nebo matice $\A$ indexuji indexem $i\in
B$ nějaké bazické proměnné, myslí se tím ten řádek, ve kterém je v
$i$-tém sloupci jednotka.
\end{itemize}
Tabulka $D$ má tvar
\begin{align*}
z&=v+\sum_{j\not\in B}c_j x_j\\
x_i&=b_i-\sum_{j\not\in B}a_{ij}x_j,\quad i\in B,
\end{align*}
nultý řádek tabulky $D^*$ má tvar
\[z=v+\sum_{j=1}^n c_j^* x_j.\]
Položme $x_s=y\in\R$, $x_j=0$ pro $j\not\in B$, $j\not=s$. Pak
$x_i=b_i-a_{is}y$ pro $i\in B$ a
\[z=v+c_sy=v+c_s^* y+
\sum_{i\in B}c_i^*\underbrace{(b_i-a_{is}y)}_{x_i}.\]
Pro každé $y\in\R$ pak platí
\[\left(c_s-c_s^*+\sum_{i\in B}c_i^* a_{is}\right)y=
\sum_{i\in B}c_i^* b_i.\]
To je ale možné jen v~případě, že koeficienty u~$y$ jsou nulové, tedy
\[c_s-c_s^*+\sum_{i\in B}c_i^* a_{is}=0.\]
Platí, že $c_s<0$, protože $x_s$ jde v~$D$ do báze. Naopak $c_s^*\ge
0$, protože do báze jde v~$D^*$ $x_t$ a kdyby $c_s^*<0$, podle
Blandova pravidla by do báze šla $x_s$. Tedy $c_s-c_s^*<0$, z~čehož
plyne, že alespoň jeden sčítanec v~sumě je kladný. Tedy existuje $i\in B$
takové, že $c_i^*a_{is}>0$.
Dokážeme, že $x_i$ je běhna a $i<t$. Proměnná $x_i$ nemůže být v~$D^*$
bazická, protože $c_i^*\not=0$. Protože $a_{ts}>0$ (je to pivot)
a $c_t^*<0$ ($x_t$ jde do báze), je $c_t^* a_{ts}<0$. Je proto $i<t$,
neboť $c_i^*a_{is}>0$. Čili $x_i$ je běhna s~indexem menším než $t$.
Proměnná $x_i$ je ve všech tabulkách nulová. Pokud není v~bázi, je to
jasné a když jde do báze, zůstane nulová, protože prověrka poměrů dá
nulu a nulová zůstane i~dál, protože nultý sloupec se nemění. V~tabulce $D$ má hodnotu $b_i$, takže $b_i=0$.
Z~toho, že $x_i$ je běhna, plyne, že $c_i^*>0$, jinak bych musel do
báze podle Blandova pravidla zařadit $x_i$ a ne $x_t$. Protože
$c_i^*>0$, je i $a_{is}>0$. Z~toho plyne, že řádek odpovídající $i$-té
proměnné je rovněž kandidátem na vedoucí řádek. Prověrka poměrů dá
nulu ($b_i=0$ a podle předpokladu i $b_t=0$), podle Blandova pravidla
vybírám řádek odpovídající proměnné s~nejmenším indexem, takže
v~tabulce $D$ se měl volit řádek odpovídající $i$-té proměnné, což je
spor.
\end{proof}
\end{theorem}
\end{description}
\subsection{Maticový zápis simplexového algoritmu}
Soustavu rovnic simplexové metody
\begin{align*}
z&=cx-a_{00}\\
0&=-b+\A x
\end{align*}
lze zapsat maticově jako
\[
\begin{pmatrix}
a_{00} & c \\
b & \A
\end{pmatrix}
\begin{pmatrix}
-1\\x
\end{pmatrix}=
\begin{pmatrix}
z\\ 0
\end{pmatrix}.
\]
Buďte $\A=(\B|\mathbf N)$, kde $\B$ je regulární, $c=(c_\B,c_{\mathbf
N})$, $x=
\begin{pmatrix}
x_\B\\x_{\mathbf N}
\end{pmatrix}
$. Dosazením a vynásobením soustavy
\[
\left.
\begin{pmatrix}
a_{00} & c_\B & c_{\mathbf N} \\
b & \B & \mathbf N
\end{pmatrix}
\begin{pmatrix}
-1\\x_\B\\x_{\mathbf N}
\end{pmatrix}=
\begin{pmatrix}
z\\ 0
\end{pmatrix}
\qquad
\right|
\cdot
\begin{pmatrix}
1 & -c_\B\B^{-1}\\
0 & \B^{-1}
\end{pmatrix}
\text{ zleva}
\]
dostaneme
\[
\begin{pmatrix}
a_{00}-c_B\B^{-1}b & 0 & c_{\mathbf N}-c_B\B^{-1}\mathbf N \\
\B^{-1}b & \E & \B^{-1}\mathbf N
\end{pmatrix}
\begin{pmatrix}
-1\\x_\B\\x_{\mathbf N}
\end{pmatrix}=
\begin{pmatrix}
z\\ 0
\end{pmatrix},\]
tj. tabulku simplexové metody.
Označme $c_\B\B^{-1}=\pi$. Je-li $c_{\mathbf N}-\pi\mathbf N\ge 0$, je
tabulka duálně přípustná. Označme $\overline{c_j}=c_j-\pi\A_{\bullet
j}$ koeficienty v~nové matici (platí i~pro $c_\B$). Pak
$\overline{c_j}\ge 0$, právě když $\pi\A_{\bullet j}\le c_j$ pro každé
$j\in\hat n$ a to právě když $\pi\A\le c$. Pak ale $\pi$ splňuje
soustavu omezení duální úlohy $y\A\le c$. Protože
$w=yb-a_{00}=\pi b-a_{00}=c_\B\B^{-1}b-a_{00}$, jsou hodnoty účelové
funkce stejné a proto je řešení optimální.
\subsection{Duální simplexová metoda}
Vychází se z~{\bf duálně přípustné tabulky}.
\begin{enumerate}
\item Pokud je tabulka i~primárně přípustná, končím.
\item Určím vedoucí řádek $r$, který má v~nultém sloupci záporné
číslo. Prověrkou poměrů najdu vedoucí sloupec (kandidáti $a_{ri}<0$),
pokud je každé $a_{ri}\ge 0$, neexistuje přípustné řešení. Hledám
minimum
\[\min_{a_{rj}<0}\abs{\frac{a_{0j}}{a_{rj}}}=\abs{\frac{a_{0s}}{a_{rs}}},\]
za vedoucí sloupec zvolím $s$.
\end{enumerate}
\subsection{Modifikovaná (redukovaná) simplexová metoda}
V~modifikované metodě se počítají pouze prvky, které jsou právě
potřeba. Vychází se vždy z~počáteční tabulky. V~paměti mám
výchozí tabulku a matici $\B^{-1}$. Nové prvky se počítají
následujícími vztahy:
\begin{align*}
\overline b&=\B^{-1}b &
\overline{\A}_{\bullet j}&=\B^{-1}\A_{\bullet j} &
\overline{c}_j&=c_j-\pi\A_{\bullet j},\ \pi=c_\B\B^{-1}
\end{align*}
Pro $k+1.$ tabulku potřebujeme spočítat nebazická $\overline{c}_j$,
mezi nimi vybereme $s$-tý vedoucí sloupec $\B^{-1}\A_{\bullet s}$ a
provedeme prověrku poměrů s~$\overline{b}$. Matici $\B^{-1}$ poté
vynásobíme zleva elementárními maticemi, které provedou řádkové
úpravy stejné jako v~původní simplexové metodě. Postup opakujeme,
dokud není $c\ge 0$.
\subsection{Primárně duální simplexová metoda}
Tato metoda kombinuje primární i~duální simplexovou metodu. Její
výhodou je, že není nutné začínat bazickým přípustným řešením, ovšem
účelová funkce musí být omezená, aby měla přípustné řešení i~duální
úloha.
Nechť primární a duální úloha mají tvar
\begin{align}
\label{pd_prim}\min z&=cx & \A x&=b,\quad b\ge 0 & x&\ge 0,\\
\label{pd_dual}\max w&=yb & y\A&\le c.
\end{align}
Nejprve nalezneme přípustné řešení duální úlohy.
\begin{enumerate}
\item Buď je $c\ge 0$, v~tom případě vyhovuje řešení $\pi=0$.
\item Existuje $j\in\hat n$ takové, že $c_j<0$. V~tom případě budeme
řešit upravenou úlohu
\begin{equation}
\begin{split}
\min z&=cx\\
\A x&=b,\quad b\ge 0\\
\sum_{i=1}^n x_i+x_{n+1}&=\alpha\\
x&\ge 0,\\
\end{split}
\end{equation}
resp.
\begin{equation}
\begin{split}
\max w&=yb\\
a_{11}y_1+a_{21}y_2+\dots+a_{m1}y_m+y_{m+1}&\le c_1\\
a_{12}y_1+a_{22}y_2+\dots+a_{m2}y_m+y_{m+1}&\le c_2\\
&\xvdots\\
a_{1n}y_1+a_{2n}y_2+\dots+a_{mn}y_m+y_{m+1}&\le c_n\\
y_{m+1}&\le 0,
\end{split}
\end{equation}
kde $\alpha$ je \uv{hodně velké} číslo (např. maximální hodnota,
kterou počítač snese). Potom $\pi_j=0$ pro $j\in\hat m$,
$\pi_{m+1}=\min_{j\in\hat n}c_j<0$.
\end{enumerate}
Nechť $\pi$ je přípustné řešení úlohy \eqref{pd_dual}. Potom podle
věty o~slabé komplementaritě jsou $\pi$ a $x$ optimální řešení
\eqref{pd_dual} resp. \eqref{pd_prim}, právě když $\pi(\A x-b)=0$ a
$(c-\pi\A)x=0$. První rovnost platí vždy, protože v~primární úloze
jsou pouze rovnice, v~druhé rovnosti jsou $(c-\pi\A)$ i $x$
nezáporné. Aby mohla rovnost platit, musí být všechny složky
skalárního součinu nulové.
Je-li $c_j-\pi\A_{\bullet j}>0$, pak $x_j=0$. Definujme
$\J=\{j\in\hat n|c_j-\pi\A_{\bullet j}=0\}$. Pak pro každé
$j\not\in\J$ je $x_j=0$.
Chceme nakombinovat vektor $b$ ze sloupců matice $\A$ s~indexy z~$\J$.
Budeme řešit pomocnou úlohu
\begin{equation}
\label{pd_pom1}
\begin{split}
\min \xi&=\sum_{i=1}^n x_i'\\
\sum_{j\in\J} a_{ij}x_j+x_i'&=b_i\\
x_j&\ge 0,\\
x_i'&\ge 0.
\end{split}
\end{equation}
Funkce $\xi$ je omezená zdola (nezáporná), existuje přípustné řešení
$x_i'=b_i$ pro $i\in\hat m$ a $x_j=0$ pro $j\in\J$. Úlohu vyřeším
\uv{klasickou} simplexovou metodou. Mohou nastat dva případy:
\begin{enumerate}
\item Je $\xi_{min}=0$, potom řešení $x$ je optimální.
\item Je $\xi_{min}>0$, v~tom případě dál řeším úlohu duální
k~\eqref{pd_pom1}:
\end{enumerate}
\begin{equation}
\label{pd_pom2}
\begin{split}
\max w&=yb\\
y\A_{\bullet j}&\le 0,\quad j\in\J\\
y_i&\le 1,\quad i\in\hat m.
\end{split}
\end{equation}
Nechť $\opi$ je optimální řešení \eqref{pd_pom2}. Rozlišíme
opět dva případy:
\begin{enumerate}
\item $\opi\A_{\bullet j}\le 0$ pro všechna $j\not\in\J$. Potom
$\opi\A\le 0$. Dokážeme, že \eqref{pd_prim} nemá přípustné
řešení.
Z~toho, že $\opi\A\le 0$ vyplývá, že
$\pi+\beta\opi$, kde $\beta\ge 0$, je přípustné řešení
\eqref{pd_dual}.
\[(\pi+\beta\opi)\A_{\bullet j}=
\underbrace{\pi\A_{\bullet j}}_{\le c_j}+
\underbrace{\beta\opi\A_{\bullet j}}_{\le 0}\le c_j.\]
Protože podle věty o~dualitě je $\opi b=w_{max}=\xi_{min}>0$, je
\[w=(\pi+\beta\opi)b=
\underbrace{\pi b}_{\text{konst.}}+
\beta\underbrace{\opi b}_{> 0}\]
a pro $\beta\to +\infty$ se $w$ blíží $+\infty$.
\item Existuje $j_0\not\in\J$ takové, že
$\opi\A_{\bullet j_0}>0$. Označme
\[\theta=\min\left\{
\left.
\frac{c_j-\pi\A_{\bullet j}}{\opi\A_{\bullet j}}
\right|
\opi\A_{\bullet j}>0
\right\}>0.\]
Dokážeme, že $\pi'=\pi+\theta\opi$ je \uv{lepší} řešení
\eqref{pd_dual} než bylo $\pi$.
\[
(\pi+\theta\opi)\A_{\bullet j}=\pi\A_{\bullet j}+
\theta\opi\A_{\bullet j}\le
\begin{cases}
\pi\A_{\bullet j}\le c_j\text{ pro $\opi
\A_{\bullet j}\le 0$}\\
\pi\A_{\bullet j}+\frac{c_j-\pi\A_{\bullet j}}
{\opi\A_{\bullet j}}\opi\A_{\bullet j}=c_j
\text{ pro $\opi\A_{\bullet j}>0$},
\end{cases}
\]
takže $\pi'$ je přípustné. Dále platí $\pi'b=\pi
b+\theta\opi b>\pi b$, protože $\theta>0$ a $\opi b>0$.
Vrátím se na začátek, najdu nové $\J$ a opakuji proces.
\end{enumerate}
\subsection{Dopravní problém}
Mám $m$ skladů a $n$ odběratelů. Označme
\begin{itemize}
\item $a_i$, $i\in m$ počet jednotek v~$i$-tém skladu,
\item $b_j$, $j\in n$ požadavek $j$-tého odběratele,
\item $c_{ij}$ přepravní náklad na jednotku z~$i$ do $j$,
\item $x_{ij}$ neznámé --- kolik se přepravuje z~$i$ do $j$.
\end{itemize}
Budeme nejprve předpokládat, že nabídka a poptávka jsou
stejné, tedy
\[\sum_{i=m}^n a_i=\sum_{j=1}^n b_j=A\ge 0.\]
Dopravní problém lze zapsat jako úlohu LP takto:
\begin{align*}
\min z&=\sum_{i=1}^m\sum_{j=1}^n c_{ij}x_{ij},\quad
\text{kde $c_{ij}>0$}\\
\sum_{i=1}^m x_{ij}&=b_j,\quad\text{kde $j\in\hat n$}\\
\sum_{j=1}^n x_{ij}&=a_i,\quad\text{kde $i\in\hat m$}\\
x_{ij}&\ge 0
\end{align*}
Máme soustavu $m+n$ rovnic a $mn$ proměnných. Rovnice jsou lineárně
závislé, o~tom se lze přesvědčit sečtením prvních $n$ rovnic a
odečtením dalších $m$ rovnic. Vynecháním kterékoli z~nich dostaneme
systém $n-1$ nezávislých rovnic.
\begin{theorem}
Dopravní problém má přípustné řešení a účelová funkce je omezená
zdola, úloha má tedy i~optimální řešení.
\begin{proof}
Úlohu řeší například
\[x_{ij}=\frac{a_ib_j}{A}.\qed\]
\noqed
\end{proof}
\end{theorem}
Nalezení počátečního přípustného bazického řešení, metoda
severozápadního rohu: Mějme matici proměnných
\[
\begin{pmatrix}
x_{11} & x_{12} & \hdots & x_{1n}\\
x_{21} & x_{22} & \hdots & x_{2n}\\
\hdotsfor{4}\\
x_{m1} & x_{m2} & \hdots & x_{mn}
\end{pmatrix}.
\]
Na počátku položme $a'_i=a_i$, $b'_i=b_i$. Začneme u~proměnné
$x_{11}$.
\begin{enumerate}
\item Pokud je $a'_1>b'_1$, položíme $a'_1\leftarrow a'_1-b'_1$,
$b'_1\leftarrow 0$ a pokračujeme u~$x_{12}$.
\item Je-li $a'_1<b'_1$, položíme $b'_1\leftarrow b'_1-a'_1$,
$a'_1\leftarrow 0$ a pokračujeme u~$x_{21}$.
\item Je-li $a'_1=b'_1$, položíme $a'_1\leftarrow 0$,
$b'_1\leftarrow 0$ a pokračujeme u~$x_{22}$.
\end{enumerate}
Takto nalezené řešení je bazické.
Odstranění předpokladu rovnosti nabídky a poptávky: Je-li
\[\sum_{i=1}^n a_i<\sum_{j=1}^n b_j,\]
přidám $m+1.$ sklad a položím
\[a_{m+1}=\sum_{j=1}^n b_j-\sum_{i=1}^n a_i,\quad c_{m+1,j}=0\text
{ pro každé $j\in\hat n$}.\]
Analogicky pro převis nabídky.
