Ćwiczenia

Ćwiczenie 3.1   Rozwiąż następujące problemy:


$\begin{array}{rrrrl} x_1 & + x_2 & \leq 3\\ 2x_1 & - x_2 & \leq 4\\ &x_1,x_2 & \geq 0\\ \hline 2x_1& + x_2 & \rightarrow &\max \end{array}$ $\begin{array}{rrrrl} 2x_1 & + 4x_2 & + x_3 & \leq 6\\ x_1 & - 4x_2 & + x_3 &... ...& (j=1,2,3)\\ \hline x_1 & + 2x_2 & + 3x_3 & \rightarrow & \max \end{array}$

Ćwiczenie 3.2   Posługując sie tabelami simpleksowymi rozwiąż przykład .

Ćwiczenie 3.3   Posługując sie tabelami simpleksowymi rozwiąż PPL:


$\begin{array}{rrrrrrl} x_1 & - & 2x_2 & + & 3x_3 & \leq & 10\\ 2x_1& + & x_2... ...4x_3 & \rightarrow & \mbox{max}\\ &&& x_i & \geq & 0 & i=1,2,3 \end{array}$

Ćwiczenie 3.4   Rozwiąż następujące PPL:


$\begin{array}{rrl} -3 x_1 & + x_2 & \leq -3 \\ x_1 & + x_2 & \ge 1 \\ &x_1,x_2 & \geq 0 \\ \hline x_1 & + 3x_2 & \rightarrow \mbox{ max} \end{array}$


$\begin{array}{rrrl} -x_1 & -x_2 & +x_3 & \leq -1 \\ 2x_1 & + x_2 & + x_3 &... ...\leq 10 \\ \hline x_1 & + 2x_2 & + x_3 & \rightarrow \mbox{max} \end{array}$
$x_i \geq 0, \ i=1,2,3$.

Ćwiczenie 3.5   Sprawdź, że PPL
$\begin{array}{rrrl} 2x_1 & -x_2 & +x_3 & \leq 12 \\ x_1 & + 2x_2 & + x_3 &... ...\geq 4 \\ \hline 2x_1 & + x_2 & - 3x_3 & \rightarrow \mbox{max} \end{array}$
$x_i \geq 0, \ i=1,2,3$.
jest niesprzeczny. Wskaż dla tego problemu bazowe rozwiązanie dopuszczalne.

Ćwiczenie 3.6 (przykład Chvatála)   Zastosuj algorytm simpleks do PPL

$$\begin{array}{rrrrrrr} x_5 & = && -0,5 x_1 & + 5,5 x_2 & ... ...& = & & 10 x_1 & - 57 x_2 & - 9 x_3 & - 24 x_4 \end{array}$$ (3.43)

wybierając za każdym razem

-

zmienną wchodzącą o największym współczynniku we wzorze na $z$,

-

zmienną wychodzącą o najmniejszym indeksie spośród tych które dają najostrzejsze ograniczenie od góry na zmienną wchodzącą (np pierwszą zmienną wychodzącą będzie $x_5$).

Ćwiczenie 3.7   Wykaż, że każda wypukła kombinacja rozwiązań optymalnych PPL jest rozwiązaniem tego problemu (kombinacja wypukła zdefiniowana jest w podrozdziale ).

Ćwiczenie 3.8   Algorytmem sympleks rozwiąż zadanie Klee-Minty'ego dla $n=3$ (a jeśli masz cierpliwość i potrzebę lepszego zrozumienia dowodu twierdzenia to dla $n=4$). Ile otrzymasz iteracji a ile słowników w każdym z tych przypadków (por. przykład )?