Ćwiczenia

Ćwiczenie 5.1   Niech będzie dany PPL:

$$\left\{ \begin{array}{rcrrrrl} x_4 & = & 5 & -x_1 & - 2x_... ...&& x_1 & + x_2 & + x_3 & \rightarrow \max \end{array} \right.$$

(a)

Wykaż, że $x_2, x_4, x_5$ są zmiennymi bazowymi pewnego słownika.

(b)

Znajdź wartość funkcji celu dla tego słownika.

(c)

Jakie są wtedy możliwe zmienna wchodzące?

Ćwiczenie 5.2   Wykaż, że jeśli zbiór wierszy macierzy $A \in {\bf R}^{n \times n}$ można podzielić na dwa rozłączne podzbiory $W_1$ i $W_2$ takie, że dla każdego $j=1,...,n$ spełniona jest równość (), to $\det A=0$ (prawdziwe także gdy jeden ze zbiorów $W_1, W_2$ jest pusty^5.3).

Ćwiczenie 5.3   Niech będą dane macierz totalnie unimodularna ${\bf A}$, układ nierówności

$${\bf Ax} \leq {\bf b}$$ (5.21)

oraz mu układ

$${\bf\bar{A}x} = {\bf b}$$ (5.22)

powstały z () przez wprowadzenie zmiennych dodatkowych. Wykaż, żemacierz ${\bf\bar{A}}$ jest totalnie unimodularna.

Ćwiczenie 5.4   Z twierdzenia nie wynika, że jeśli są spełnionezałożenia tego twierdzenia, to wszystkie rozwiązania problemu() są całkowite. Skonstruuj przykład PPL w którym macierzograniczeń ${\bf A}$ jest totalnie unimodularnai wektor ${\bf b}$ całkowity, dla którego istnieją optymalne rozwiązania niecałkowite.