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.

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í:

1. Ú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} \]

1. Ú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} \]

1. Úloha Jistá výhra z předchozího cvičení.
2. Úloha Minimaxní prokládání lineární funkce z předchozího cvičení.

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:

1. 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.
2. Nalezněte příklad úlohy LP a pivotové pravidlo, které povedou k cyklení.