415 2

415

10.2. Metoda syrapleks

yspoicz

MńĆZCg^{0    s} *^arc 1

x₂ jest dodatni, wobec czego kryterium maksimum nic jest spełnione ' teraz zbadać x₂?). Zamieniamy zmienne x₂ i x_s, czemu na rys. 10.1.1 IggpPfcda przejście z A do B. Po obliczeniach, które zalecamy czytelnikowi wykonać krok po kroku, otrzymuje się, że

;t₂ = ±(60+4x₃-5x₅) (z powyższego równania dla x«), x₄*»^(60-7x₃+17x₃).

*“ yj (120 “ 3.Xj +^5),

/=±(43OO-J0x₃-7Ox_s).

Żaden ze współczynników przy zmiennych w/nie jest dodatni, czyli kryterium maksimum jest spełnione. Punkt o współrzędnych ± (120, 60, 0, 60, 0) - tzn. punkt B - jest zatem rozwiązaniem optymalnym, zgodnie z wynikiem otrzymanym wcześniej.

Metoda sympleks (w opisanym wariancie) daje w każdym kroku największy przyrost wartości f jaki można uzyskać, zmieniając tylko jedną zmienną prawostronną. Zdarza się jednak, że nawet w punkcie, który nic jest rozwiązaniem optymalnym, nie można zwiększyć f za pomocą zamiany pojedynczej współrzędnej, gdyż lo spowodowałoby konflikt z ograniczeniami. Ta wyjątkowa sytuacja występuje wtedy, gdy jedna zc zmiennych lewostronnych i jedna ze zmiennych prawostronnych są jednocześnie zerami, tzn. gdy znaleziono wektor dopuszczalny, w którym więcej niż n—m współrzędnych jest zerem. Jak wspomnieliśmy wcześniej, taki punkt nazywa się itdegenerowanym wektorem dopuszczalnym. Natrafiwszy na taki wektor próbuje się zamienić zmienną prawostronną z jedną z tych zmiennych lewostronnych, które zerują się w tym punkcie. \V trudniejszych przypadkach trzeba wykonać kilka takich zamian.

Przykład 10.2.1. Znaleźć maksimum wyrażenia

J— 2x₁+2x₂+3xj

przy warunkach

x,^0 (i = l,2.3).

dopuszczalne tworzą w przestrzeni (x_lt x₂, x₃) ostrosłup o podstawie czworo-10.2.1). Wprowadzamy zmienne wolne x_A, x₅ i wybieramy x,, x₂, x₃ jako Bzpffo¹*'⁶ prawostronne. Zauważmy, żc równania x*=0 i x₅-0 także określają ściany ostro-Wektor dopuszczalny otrzymuje się dla x₁=x_i=x₃=0 (punkt O na rys. 10.2.1),

' Ograniczenia są wtedy spełnione. Stąd

Jf«=l-x,-jt3,    J/« 2,

*5^fcl-X₂-X3, zfx₂-l, 4/=2,