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

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:

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).

Wyszukiwarka

Podobne podstrony:
040 041 40 Anna Borowska. Rafał Chaba Odpowiedź jednostkowa: h{t) = k{t - r0) (2.40) Odpowiedź
040 041 40 Anna Borowska. Rafał Chaba Odpowiedź jednostkowa: h(ł) = k(ł-T0)
086 087 2 86 Programowanie liniowe Rysunek 1.20 Alternatywnymi bazowymi rozwiązaniami optymalnymi są
Zagadnienie programowania liniowego - metoda graficzna Wyznaczenie zbioru rozwiązań dopuszczalnych:
Kolokwium (2) Zad 1. Sprawdzić czy istnieją rozwiązań w układu (korzystając z tw. Kroneckerar-CapeJ
Następnie należy sprawdzić, czy otrzymane przedziały objęcia zgadzają się co do ustalonej tolerancji
9.    Sprawdzić, czy zastosowane rozwiązania w zakresie instalacji i ich
10. Uzupełni), a następnie sprawdź, czy otrzymana liczba spełnia
TW. Jeżeli optymalne rozwiązanie programu PKL istnieje, to przynajmniej jedno rozwiązanie bazowe teg
Napisz program, który czyta liczbę naturalną z zakresu 1 do 2000000000 i sprawdza, czy jest ona podz
Napisz program, który czyta liczbę naturalną (nieprzekraczającą tryliona) i sprawdza, czy wszystkie
Napisz program, który czyta cztery różne liczby naturalne (do dwóch miliardów) i sprawdza, czy można
IMG (2) Algebra liniowa IS Egzamin 5.02.2010 1.    Podać definicję grupy i ciała. Spr
078 079 2 78 Programowanie liniowe Wykorzystując dualną metodę simpleks, wykonujemy kolejne iteracje
Badania operacyjr Zagadnienia programowania liniowego Sprawdzamy warunek na redundancję rank(A) <
Aby sprawdzić, czy istnieje liniowa zależność pomiędzy analizowanymi wielkościami, należy policzyć
116 117 I 16 Programowanie liniowe całkowitoliczbowe Iteracja 5 Porządkujemy lisię zadań. Na liście

więcej podobnych podstron