\[ \def\_#1{\mathbf{#1}} \def\bb#1{\mathbb{#1}} \]
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í:
x matice $n\times1$ s libovolným optimálním řešením.
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í:
\[ \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} \]
\[ \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} \]
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: