Zadanie ograniczone

W wielu praktycznych zagadnieniach obok ograniczeń

$$\sum_{j=1}^n a_{ij}x_j \leq b_i \ \ \ (i=1,...,m)$$

występują indywidualne ograniczenia od góry na zmienne (wszystkie lub niektóre postaci

$$x_j \leq g_j \ \ \ \ (j=1,...,n)$$

Zadanie PL z tak określonymi ograniczeniami jest wtedy oczywiście zadaniem w postaci standardowej

$$\sum_{j=1}^n a_{ij}x_j \leq b_i \ \ \ (i=1,...,m)$$

$$x_j \leq g_j \ \ \ \ (j=1,...,n)$$

$$x_j \geq 0 (j=1,...,n)$$

Jednak po dołączeniu zmiennych sztucznych otrzymujemy wtedy macierz ograniczeń o rozmiarze $(m+2n)\times (m+2n)$. Jeśli liczba zmiennych (a więc liczba $n$) jest duża, wielkość problemu który należało będzie rozwiązać może być kłopotliwa. Stąd istotna może się okazać metoda zasugerowana po raz pierwszy przez Dantziga w [4].
Problem postawimy jeszcze ogólniej niż wspomniano wyżej, mianowicie będziemy zakładać ograniczenia nie tylko górne ale i dolne i to na wszystkie zmienne, czyli

$$d_j \leq x_j \leq g_j \ \ \ \ (j=1,...,n)$$

przy czym dopuszczać będziemy $-\infty$ dla dolnego i $+\infty$ dla górnego ograniczenia (co oczywiście oznacza, że odpowiednich ograniczeń nie ma) ^6.1 Będziemy też zakładali równości $\sum_{j=1}^n a_{ij}x_j = b_i, \ (i=1,...,m)$, czyli sytuację którą mamy po wprowadzeniu zmiennych sztucznych. Problem nasz będzie więc postaci

$$% latex2html id marker 5195 \begin{array}{lrclcrrr} \mbox... ...\ &d_j & \leq & x_j & \leq & g_j & (j=1,...,n) \end{array}$$

lub w formie macierzowej

$$% latex2html id marker 5196 \begin{array}{lrcrcrr} \mbox{... ...bf b}\\ & {\bf d} &\leq {\bf x} \leq & {\bf g} \end{array}$$

gdzie ${\bf A} \in {\bf R}^{n \times n}, \ {\bf b},{\bf d},{\bf g},{\bf x} \in {\bf R}^{n\times 1}, {\bf c} \in {\bf R}^{1 \times n}$.
Różnica pomiędzy algorytmem dla zadań ograniczonych a poznanym wcześniej polega, jak zobaczymy, na żądaniu, by w rozwiązaniach bazowych wartości zmiennych niebazowych były równe dolnym lub górnym ograniczeniom ^6.2.

Definicja 6.1   Rozwiązanie $\bar{x}$ układu równań ${\bf Ax}={\bf b}$ nazywamy rozwiązaniem bazowym jeżeli $n$ współczynników wektora ${\bf x}$ można podzielić na

(a)

$m$ zmiennych bazowych oraz

(b)

$n-m$ zmiennych niebazowych

w ten sposób, że

1. kolumny macierzy ${\bf A}$ których elementy są współczynnikami przy zmiennych bazowych tworzą macierz (kwadratową o $m$ wierszach i $m$ kolumnach) nieosobliwą,
2. wartości zmiennych niebazowych w wektorze $\bar{\bf x}$ równe są ich ograniczeniom górnym lub dolnym.

Rozwiązanie bazowe $\bar{\bf x}$ jest dopuszczalne jeżeli spełnia warunek

$${\bf d} \leq \bar{\bf x} \leq {\bf g}$$

Przykład 6.1   Dla problemu

$$% latex2html id marker 5198 \begin{array}{rrcrcrcrcrcrcrcr... ...x_5 & \leq & 2 \\ 1 \leq & x_6 & \leq & 4 \\ \end{array}$$

zmienne $x_2,x_6$ są^6.3 bazowymi, zaś $x_1, x_3, x_4, x_5$ niebazowymi, a bazowym rozwiązaniem dopuszczalnym jest $\bar{\bf x} = [2,2,5,0,0,4]^T$.

Oczywiście dla danego wyboru zmiennych bazowych może być więcej niż jedno rozwiązanie bazowe.

Ćwiczenie 6.1   Znajdź wszystkie rozwiązania bazowe odpowiadające w przykładzie zmiennym bazowym $x_2,x_6$. Znajdź inne zbiory zmiennych bazowych dla tego przykładu.

Dalszy ciąg postępowania będzie w dużej mierze przypominał metodę sympleks: będziemy utrzymywać ograniczenie

$${\bf Ax}={\bf b}$$

starając sie wybierać nową bażę i nowe rozwiązania bazowe tak, by powiększać wartość funkcji celu. Zacznijmy od przykładu.

Przykład 6.2  

$$% latex2html id marker 5200 \begin{array}{rrrrrrrrr} \mbo... ...q & x_3 \leq & 30\\ 0 \leq & x_4 \leq & 20\\ \end{array}$$

Przyjmijmy jako zmienne bazowe $x_1, x_2$ i weźmy rozwiązanie bazowe

$$x_1=30, \ x_2=20,\ x_3=30, \ x_4=0$$

Wartość funkcji celu dla naszego rozwiązania bazowego wynosi $z=160$.
Będziemy, tak jak w metodzie sympleks, zmieniać wartości jednej ze zmiennych niebazowych tak, aby powiększała się wartość rozwiązania, przy zachowaniu warunków ograniczających, a w szczególności pierwszych dwóch równań warunków ograniczających.
Wybierzmy zmienną $x_4$ jako tę zmienną niebazową niebazową której powiększenie powoduje najszybsze zwiększanie funkcji celu.
Zauważmy, że jeżeli podstawimy

$$\begin{array}{rcccrr} x_1 & = & 30 & - & \frac{1}{2}t\\ ... ...\ x_3 & = & 30\\ x_4 & = & & &t & (t \geq 0) \end{array}$$

to także takie zmienne spełniają oba równania w ograniczeniach naszego zdania PL.
$t$ możemy zwiększyć do 20. Wtedy otrzymamy

$$\begin{array}{rcrl} \bar{x}_1 & = & 20 \\ \bar{x}_2 & = ... ...\ \bar{x}_3 & = & 30 \\ \bar{x}_4 & = & 20 \end{array}$$

Przyjąć więc można: $x_1$ oraż $x_4$ jako zmienne bazowe oraz $x_2$ i $x_3$ jako zmienne niebazowe. Nowe rozwiązanie ma wartość $\bar{z} = 180$. Teraz zmienną wchodzącą będzie $x_2$. Podobnie jak poprzednio zauważmy, że podstawiając

$$\begin{array}{rcrcr} x_1 & = & 20 & + & t\\ x_2 & = & 10 & + & t \\ x_3 & = & 30\\ x_4 & = & 20 & - 2 & t \end{array}$$

$t$ możemy zwiększyć do $10$ (rozpoczynając od $t=0$), wtedy jednak funkcja celu maleje - a więc naszego rozwiązania nie da się już poprawić.

W ogólnym przypadku możemy napisać rozwaązny PPL postaci macierzowej, tak jak to zrobiliśmy w prezentacji zrewidowanej metodzie sympleks,. Przyjmijmy więc

${\bf A}_N$ - macierz otrzymana przez wybór z ${\bf A}$ kolumn o indeksach niebazowych,

${\ bf B}$ - macierz powstała z ${\bf A}$ przez wybór kolumn o indeksach bazowych,

${\bf x}_N,{\bf x}_B, {\bf c}_N, {\bf c}_B$ - odpowiednie wektory otrzymane z ${\bf x}$ i ${\bf c}$.

Wtedy oczywiście ograniczenie ${\bf Ax}={\bf b}$ można zapisać w postaci

$${\bf A}_N{\bf x}_N + {\bf Bx}_B={\bf b}$$

i

$${\bf x}_B = {\bf B}^{-1}{\ bf b} - {\bf B}^{-1}{\bf A}_N{\bf x}_N$$

Funkcja celu będzie postaci

$${\bf cx}= {\bf c}_B({\bf B}^{-1}{\bf b} - {\bf B}^{-1}{\bf A}_N{\bf x}_N) + {\ c}_N{\bf x}_N$$

$${\bf cx}= {\bf c}_B{\bf B}^{-1}{\bf b} + ({\bf c}_N-{\bf c}_B{\bf B}^{-1}{\bf A}_N){\bf x}_N$$

lub krócej

$${\bf cx} = {\bf yb} + ({\bf c}_N - {\bf yA}_N){\bf x}_N$$

gdzie

$${\bf y} = {\bf c}_B{\bf B}^{-1}$$