\[
\def\_#1{\mathbf{#1}}
\def\bb#1{\mathbb{#1}}
\]

=====  LP: Simplexová metoda =====

==== Cíl ====

Chceme vyřešit úlohu lineárního programování
\begin{equation}
\min\{\, \_c^T\_x \mid \_x\in\bb R^n, \; \_A\_x=\_b, \; \_x\ge\_0 \,\} .
\label{eq:LP}
\end{equation}
Předpokládáme, že $\_A\in\bb R^{m\times n}$ má hodnost $m$. Nepředpokládáme ale, že $\_b\ge\_0$.

Implementujte dvoufázovou simplexovou metodu na řešení
úlohy \eqref{eq:LP} jako matlabskou funkci ''x = simplex(c,A,b)''
kde ''c'' je matice $n\times1$, ''A'' je matice $m\times n$, ''b'' je matice $m\times 1$. Hodnota ''x'' je následující:
  * Pokud má úloha optimální řešení, je ''x'' matice $n\times1$ s libovolným optimálním řešením.
  * Pokud je úloha nepřípustná nebo neomezená, ''x'' bude prázdná matice.

Doporučujeme nejdříve implementovat v samostatné matlabské funkci
základní simplexovou metodu, která řeší úlohu za
předpokladu, že $\_A$ obsahuje standardní bázi a $\_b\ge\_0$. Pomocí
této funkce pak implementujete požadovanou funkci ''simplex''.


==== Úkoly ====

Nejprve implementujte popsanou funkci ''simplex''. Výstupem tohoto
úkolu nebude žádný text ve zprávě, pouze odevzdaný kód. 

Poté pomocí této funkce vyřešte následující úlohy. Výstupem každé
úlohy bude argument a hodnota optimálního řešení:
  - Úloha
  \[
  \begin{array}{rrcr}
  \min & x_1 - x_2 + 2x_3 \\
  \mbox{za podmínek}
  & -3x_1 + x_2 + x_3 &=& 4\\
  & x_1 - x_2 + x_3 &=& 3\\
  & x_1, x_2, x_3 &\ge& 0
  \end{array}
  \]
  - Úloha
  \[
  \begin{array}{rrcr}
  \min & -x_1 - 3x_3 + x_4 \\
  \mbox{za podmínek} 
  & x_1 + 2x_2 + 3x_3 &=& 15\\
  & 2x_1 + x_2 + 5x_3 &=& 20\\
  & x_1 + 2x_2 + x_3 + x_4 &=& 10\\
  & x_1, x_2, x_3, x_4 &\ge& 0
  \end{array}
  \]
  - Úloha //Jistá výhra// z předchozího cvičení.
  - Úloha //Minimaxní prokládání lineární funkce// z předchozího cvičení.


==== Konečnost algoritmu: doplňkové úkoly pro dobrovolníky ====

Vyřešit tyto úkoly není povinné a nebude bodováno. Jsou určeny pro ty,
kteří si chtějí se simplexovou metodou více pohrát.

U základní simplexové metody není bez dodatečné péče zaručena její
konečnost. V případě degenerované úlohy může algoritmus cyklit mezi
několika degenerovanými bázemi příslušnými stejnému bázovému
řešení. Hodnota účelové funkce se v tom případě nezlepšuje a
algoritmus se nikdy nezastaví.

Zamyslete se nad následujícímu úkoly:
  - Proveďte modifikaci algoritmu, která zajistí, že se pro žádnou vstupní úlohu nezacyklí. Pomocí internetu prostudujte běžně používaná anticyklící pivotová pravidla a jedno z nich implementujte.
  - Nalezněte příklad úlohy LP a pivotové pravidlo, které povedou k cyklení.