Sympleks dla zadania ograniczonego

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 ${\bf\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 6884 \begin{array}{lrcrcrcrcrcrcrcr... ..._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 (por. ćwiczenie ). 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ą bazę i nowe rozwiązania bazowe tak, by powiększać wartość funkcji celu. Zacznijmy od przykładu.

Przykład 6.2  

$$% latex2html id marker 6886 \begin{array}{rrrrrrrrr} \mbo... ... & 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 zwiększanie funkcji celu.
Zauważmy, że jeżeli podstawimy

$$\begin{array}{rcccrr} x_1 & = & 30 & - & \frac{1}{2}t\\ ... ...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$ oraz $x_4$ jako zmienne bazowe oraz $x_2$ i $x_3$ jako zmienne niebazowe. Nowe rozwiązanie ma wartość $\bar{z} = 170$. 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żany PPL postaci macierzowej, tak jak to zrobiliśmy w prezentacji zrewidowanej metodzie sympleks. Przyjmijmy więc następujące oznaczenia:

${\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 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}$$

Niech teraz $\bar{{\bf x}}$ będzie rozwiązaniem dopuszczalnym i bazowym problemu i niech

$x_j$ będzie pewną współrzędną niebazową wektora ${\bf x}$, zaś

${\bf a}=({\bf A_N})_j$ - kolumną macierzy ${\bf A}_N$ odpowiadającą współrzędnej $x_j$ wektora ${\bf x}$ (a więc $j-$tą kolumną macierzy $A$).

Wektor $\bar{\bf x}$ spełnia równanie

$$\bar{\bf x}_B = {\bf B}^{-1}{\bf b}-{\bf B}^{-1}{\bf A}_N\bar{\bf x}_N$$ (6.2)

Utwórzmy teraz nowy wektor $\bar{\bar{\bf x}}$ spełniający ograniczenia, czyli taki, że

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

gdzie $\bar{\bar{x}}_j+t$, zaś pozostałe współrzędne niebazowe wektora $\bar{\bar{\bf x}}$ nie ulegają zmianie (to znaczy $\bar{\bar{x}}_k=\bar{x}_j$ dla niebazowych indeksów $k \neq j$). Będziemy wtedy mieli

$$\bar{\bar{\bf x}}_B = {\bf B}^{-1}{\bf b} - {\bf B}^{-1}{\bf A}_N\bar{\bf x}_N - t{\bf B}^{-1}{\bf a}$$ (6.3)

Ze wzorów () i ()

$$\bar{\bar{\bf x}}_B= \bar{\bf x}_B - t{\bf B}^{-1}{\bf a}$$

a oznaczając ${\bf d}={\bf B}^{-1}{\bf a}$

$$\bar{\bar{\bf x}}_B = \bar{\bf x}_B - t{\bf d}$$

(${\bf d}$ to wektor który w przykładzie był równy ${\bf d} = [-\frac{1}{2},-\frac{1}{2}]^T$).
Wartość funkcji celu ${\bf cx}$ dla ${\bf x}=\bar{\bar{\bf x}}$ jest równa

$${\bf c}\bar{\bar{\bf x}} = {\bf yb} + ({\bf c}_N-{\bf yA}_N)\bar{\bf x}_N + (c_j - {\bf ya})t$$

(niebazową część wektora $\bar{\bar{\bf x}}$ otrzymaliśmy z $\bar{\bf x}_N$ przez zastąpienie $x_j$ przez zastąpienie $j-$tej współrzędnej $\bar{x}_j$ przez $\bar{x}_j+t$, pozostawiając inne współrzędne niebazowe bez zmiany).
Stąd wynika ważna obserwacja.

Obserwacja 6.1   Jeżeli w rozwiązaniu bazowym $\bar{\bf x}$ zastąpimy $\bar{x}_j$ przez $\bar{\bar{x}}_j=\bar{x}_j+t$, a pozostałe współrzędne niebazowe wektora $\bar{\bf x}$ nie ulegną zmianie, to

$$\bar{\bar{\bf x}}_B=\bar{\bf x}-t{\bf d}$$

gdzie ${\bf d}={\bf B}^{-1}{\bf a}$, ${\bf a}$ jest $j-$tą kolumną ${\bf A}_N$ oraz

$${\bf c}\bar{\bar{\bf x}}={\bf c}\bar{\bf x} + (c_j - {\bf ya})t$$

Naszym celem jest zwiększenie wartości funkcji celu. Jest to możliwe w każdej z następujących sytuacji:

1. $c_j-{\bf ya} > 0,\ \bar{x}_j < g_j$
   Wartości funkcji celu można zwiększyć przyjmując pewne $t>0$.
2. $\bar{x}_j > d_j, \ c_j - {\bf ya}<0$
   W tym przypadku wartość $z$ można zwiększyć przyjmując $\bar{\bar{x}}_j=\bar{x}_j+t$ dla pewnego $t$ ujemnego.

Po tych objaśnieniach możemy przedstawić nasz algorytm następująco:
Algorytm sympleks dla PPL () (ze zmiennymi ograniczonymi) Niech $\bar{\bf x}$ będzie rozwiązaniem bazowym dopuszczalnym.

Krok 1.

Rozwiąż układ ${\bf yB}={\bf c}_B$.

Krok 2.

Wybór zmiennej wchodzącej:
Zmienną wchodzącą może byc zmienna niebazowa $x_j$ taka, że

Przypadek (a):

$\bar{x}_j < g_j$ i $c_j > {\bf ya}$ lub

Przypadek (b):

$\bar{x}_j > d_j$ i $c_j < {\bf ya}$

gdzie ${\bf a}$ jest kolumną macierzy ${\bf A}$ odpowiadającą zmiennej $x_j$.
Jeśli ani przypadek (a) ani przypadek (b) nie zachodzi dla żadnej zmiennej niebazowej STOP: ${\bf x}$ jest rozwiązaniem optymalnym.

Krok 3.

Rozwiąż układ ${\bf Bd}={\bf a}$.
Zdefiniujmy: $x_j(t)=\bar{x}_j + t,\ {\bf x}_B(t)=\bar{\bf x}_B-{\bf td}$.

Krok 4.

Przypadek (a).

Jeśli dla dowolnego $t$ dodatniego:

$$d_j \leq x_j(t) \leq g_j \ \ \mbox{ i } \ \ {\bf d}_B \leq {\bf x}_B(t) \leq {\bf g}_B$$

(gdzie ${\bf d}_B$ i ${\bf g}_B$ są wektorami powstałymi z wektorów ${\bf d}$ i ${\bf g}$ przez opuszczenie współrzędnych niebazowych) STOP: problem jest nieograniczony.

Przypadek (b).

Jeśli dla dowolnego $t<0$

$$d_j \leq x_j(t) \leq g_j \ \ \mbox{ i } \ \ {\bf d}_B \leq {\bf x}_B(t) \leq {\bf g}_B$$

STOP: problem jest nieograniczony.

Krok 5.

Przypadek (a).

Weźmy $t_0$ maksymalne spełniające

$$d_j \leq x_j(t_0) \leq g_j \ \ \mbox{ i } \ \ {\bf d}_B \leq {\bf x}_B(t_0) \leq {\bf g}_B$$ (6.4)

Przypadek (b).

Niech $t_0$ będzie minimalne spełniające

$$d_j \leq x_j(t_0) \leq g_j \ \ \mbox{ i } \ \ {\bf d}_B \leq {\bf x}_B(t_0) \leq {\bf g}_B$$ (6.5)

Jeśli $t_0$ jest takie, że

$$d_j=x_j(t_0) \ \ \mbox{ lub } \ \ g_j=x_j(t_0)$$

to idź do Kroku 2 ($x_j$ pozostaje zmienną niebazową). W przeciwnym przypadku wybierz indeks bazowy $i_0$ dla którego zachodzi

$$x_{i_{0}}(t_0)=d_{i_{0}} \ \ \mbox{ lub }\ \ x_{i_{0}}(t_0)=g_{i_{0}}$$

$x_{i_{0}}$ jest zmienną wychodzącą.

Czytelnikowi pozostawiam wykazanie poniższych twierdzeń: pierwszy dowód jest bardzo łatwy, drugi wymaga zaadaptowania dowodu twierdzenia .

Twierdzenie 6.2   Jeśli metoda sympleks dla problemu ograniczonego () nie doprowadza do rozwiązania w skończonej liczbie kroków, to algorytm wpada w pętlę.

Twierdzenie 6.3   Jeśli do wyboru zmiennych wchodzących i wychodzących w algorytmie sympleks dla problemu ograniczonego () stosujemy regułę Blanda, to algorytm kończy się po skończonej liczbie iteracji.