040 041 2

40 Programowanie liniowe

Iteracja 3

Sprawdzamy, czy otrzymane rozwiązanie bazowe: jc, =4, x₂ = 2, = 2, Xą — 0, x₅ = 0

jest optymalne. Ponieważ wszystkie wskaźniki optymalności zapisane w ostatnim wierszu tablicy 1.7 są niedodatnie, zgodnie z kryterium optymalności jest to rozwiązanie optymalne i możemy zakończyć procedurę obliczeniową.

1.3.7. Interpretacja geometryczna

Rozwiązaniu początkowemu: xi =0, *2 = 0, *₃ = 14, j:₄ = 8, *₅ = 16

odpowiada na płaszczyźnie Ox_tx₂ wierzchołek (7(0, 0). Rozwiązanie to nie jest optymalne, więc badamy możliwości przejścia do wierzchołków sąsiednich, w których funkcja celu ma większą wartość. Badając istniejące możliwości, stwierdziliśmy, że wprowadzając do rozwiązania zmienną x_t na poziomie 1, otrzymamy punkt Ri(l, 0), natomiast wprowadzając zmienną *₂ — punkt P₂(0, 1). Kryterium wejścia metody simpleks wskazuje na to, że należy wybrać przesunięcie wzdłuż osi Ox₂, wyznaczone przez punkt Kryterium wyjścia związane jest z od po w i edziąna pytanie, jak daleko należy przesunąć się w ustalonym kierunku. Rozpatrujemy dwa wierzchołki: 4(0, 4) oraz D(0, 7). Drugi z nich znajduje się już poza zbiorem rozwiązań dopuszczalnych, dlatego też wybieramy wierzchołek 4, któremu w przestrzeni pięciowymiarowej odpowiada rozwiązanie bazowe:

*i=0, *2 = 4, *₃ = 6, *₄ = 0, *, = 16.

Na początku drugiej iteracji stwierdzamy, że dla wierzchołka 4 jedyną możliwością poprawy wartości funkcji celu jest wprowadzenie do bazy zmiennej *,. Odpowiada to przesunięciu rozwiązania wzdłuż półprostej wychodzącej z punktu 4. Kryterium wyjścia odpowiada ponownie na pytanie, jak daleko należy posunąć się w ustalonym kierunku. Rozpatrywane są wierzchołki B, F i H. Przesunięcie do F lub H wyprowadza poza zbiór dopuszczalny, stąd wybieramy wierzchołek 5(4, 2), któremu w przestrzeni pięciowymiarowej odpowiada rozwiązanie:

*, =4, *₂ = 2, *j = 2, *₄ = 0, *5 = 0.

Rozwiązanie to jest optymalne. Geometryczną interpretację wykonanych iteracji przedstawiono na rys. 1.11.

Rysunek I. I I

ł 'i' C

-V ± y j.» 0

1.3.8. Macierz odwrotna

do macierzy bazowej

Rozwiązanie rozpatrywanego zadania metodą simpleks rozpoczęliśmy od rozwiązania bazowego początkowego, w którym zmiennymi bazowymi były zmienne x,, x₄ i x₅. Oznaczymy przez A_B podmacierz macierzy A, składającą się z kolumn macierzy A, odpowiadających zmiennym bazowym, tworzącym aktualną bazę. Kolumny odpowiadające zmiennym bazowym początkowego rozwiązania bazowego (w naszym przypadku są to kolumny odpowiadające zmiennym x₃, x₄ i x₅) tworzą macierz odwrotną A i,¹ do macierzy A_B.

Oznaczymy przez x_B wektor, którego składowymi są zmienne bazowe, ułożone w takiej kolejności, w jakiej pojawiają się w tablicy simpleksowej. W każdej iteracji wektor x_B możemy otrzymać z zależności:

(1.6)

x_B — A _Bb.

Własność ta nie jest niezbędna do rozwiązania rozpatrywanego zadania metodą simpleks, jednakże, ze względu na to, że będzie ona potrzebna w dalszych rozważaniach, zilustrujemy ją liczbowo. Wykorzystując wzór (1.6), wyznaczymy rozwiązanie bazowe, uzyskane w drugiej iteracji w podrozdziale 1.3.5.

Przypomnijmy fragment tablicy simpleksowej dla rozwiązania początkowego (tablica 1.8).