\[ \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: