Ćwiczenia

Ćwiczenie 7.1   Niech będzie dany PPL

$$\left\{ \begin{array}{rcr} -x_1+x_2 & \leq & 3 \\ -x_1+... ...ine z=4x_1+5x_2 & \rightarrow & \max \end{array}\right\}$$

(a)

Napisz postać standardową i kanoniczną tego problemu.

(b)

Podaj jego interpretację geometryczną (wykonaj rysunek).

Nie stosując algorytmu sympleks:

(c)

Znajdź rozwiązanie optymalne. Czy istnieje tylko jedno optymalne rozwiązanie tego problemu?

(d)

Zakładając, że wybór zmiennej wchodzący dokonowany jest tak jak zazwyczaj (tj. zmienną wchodzącą jest ta której dodatni współczynnik w funkcji celu jest największy). podaj rozwiązania bazowe każdej iteracji.

(e)

To samo pytanie przy wyborze zmiennej wchodzącej regułą Blanda.

W (d) i (e) zakładamy, że pierwszym rozwiązaniem bazowym jest $x_1=x_2=z=0$ (w rozwiązaniach bazowych należy podać wartości $x_1, x_2$ i $z$).

Ćwiczenie 7.2   Znajdź powłokę wypukłą zbiorów:

(a)

$X=\{(x,y)\in {\bf R}^2: x^2+y^2 \leq 1, 0 \leq y, \mid x \mid \}$

(b)

$X=\{(1,1), (1,0), (0,1)\}$

(c)

Podaj przykład zbioru $X \subset {\bf R}^n$ takiego, że jego powłoka wypukła jest wypukłą kombinacją mniej niż $n+1$ elementów zbioru $X$, oraz taki przykład by we wzorze

$$conv(X)=\{ \alpha {\bf u}_1+...+\alpha_{n+1}: \alpha_i \geq 0 \mbox{ dla } i=1,...,n;\ \sum_{i=1}^n\alpha_i=1\}$$

$n+1$ nie dała się zastąpić przez nic mniejszego.

Ćwiczenie 7.3   Zbadaj niesprzeczność poniższych układów.

1. 
   
   $$\left\{ \begin{array}{rcrcrcrcrcrc} x_1&-&3x_2&+&x_3&-&x_4... ...x_1& + & 3x_2 & + & x_3 & - & x_4 & = & 1 \end{array} \right.$$
   
   

2. 
   
   $$\left\{ \begin{array}{rcrcrcrcrcrc} x_1&+&x_2&-&x_3&= & 3\... ... & -1\\ 3x_1& + & x_2 & & & \leq & 2\\ \end{array} \right.$$
   
   

3. 
   
   $$\left\{ \begin{array}{l} 3x_1 - 2x_2 + 4 x_3 \leq 1\\ 2... ...\geq 3 \\ x_1 + 7 x_2 - 3x_3 \geq 2 \end{array} \right.$$
   
   

Ćwiczenie 7.4   Metodą Fouriera-Motzkina zredukuj układy nierówności z ćwiczeń i niniejszego rozdziału.

Ćwiczenie 7.5   Korzystając z metody Fouriera-Motzkina znajdź optymalne rozwiązania problemów:

$$\left\{ \begin{array}{ccc} 2x_1 + 3x_2 + x_3 & \leq & 3\\ ... ...\\ 2x_1 + x_2 + 4x_3 & \rightarrow & \max \end{array}\right.$$

$$\left\{\begin{array}{ccc} x_1-x_2 & \leq & 3\\ x_1 + x+2 &... ... \hline\\ 2x_1 + x_2 & \rightarrow & \max \end{array}\right.$$

Ćwiczenie 7.6   Wykaż, że dla każdego zbioru skończonego $X \subset {\bf R}^n$ powłoką wypukłą jest przedział domknięty.

Ćwiczenie 7.7   Udowodnij, że każdy wielościan jest zbiorem wypukłym.

Ćwiczenie 7.8   Wskaż przykłady dowodzące, że w twierdzeniu wielościanów nie da się zastąpić zbiorami wypukłymi.

Ćwiczenie 7.9   Niech będą dane dwa wielościany w ${\bf R}^4$:

$$W_1: \left\{ \begin{array}{rrrrrr} x_1 & + 2x_2 & -x_3 & +... ...\ 3x_1 & + x_2 & - 2x_3 & +x_4 & \geq & 4 \end{array}\right.$$

$$W_2: \left\{ \begin{array}{rrrrrr} 2x_1 & - x_2 & + 3x_3 & ... ...5x_1 & - 8x_2 & + 15x_3 & + 2x_4 & \geq & 4 \end{array}\right.$$

(a)

Wykaż, że $W_1 \neq \emptyset, W_2 \neq \emptyset$ i $W_1 \cap W_2 = \emptyset$.

(b)

Posługując się metodą dowodu twierdzenia wskaż rozłączne półprzestrzenie $P_1$ i $P_2$ w ${\bf R}^4$ takie, że $W_1 \subset P_1$ i $W_2 \subset P_2$.