418 2

418

10. Optymalizacja

Zmienna sztuczna stała się teraz zmienną prawostronną. Zdarza się to wcześniej lub p6iui • w każdym zadaniu spełniającym założenia z §■ 10.1. Odrzucając x₆ i podstawiając zero pozostałe zmienne prawostronne, otrzymuje się wektor dopuszczalny dla pierwotre (pięć i owym i arowego) zadania. Zmienna sztuczna nic jest już potrzebna w obli czeniach. Po dwóch iteracajch (zamianie x₃ i x₄. a potem x₂ i x₅) kryterium maksimum jest spełnione i otrzymuje si ę/** = 3 dla (x, , x₂. x₃, x*, x_s) = (4, 1, 5, 0, 0). W trudniejszych sytuacjach może być potrzebne wprowadzenie wiciu zmiennych sztucznych.

Dane zadanie może mieć wiele rozwiązań optymalnych, ale oczywiście j_e5l określone jednoznacznie. Taka sytuacja ujawnia się w obliczeniach w ten sposób, żc co najmniej jedna ze zmiennych prawostronnych nic występuje w wyrażeniu dla / obowiązującym wtedy, gdy jest spełnione kryterium maksimum.

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

/=2-*₄

przy warunkach

x₃=6—2x₄ + x₂,

x_t=2— x₄+ x₂, x₃ = 3+ x₄-2x₂, x_i&0.

Kryterium maksimum jest spełnione. Wobec tego punkt (2,0, 6,0, 3) jest rozwiązaniem optymalnym. Jest jednak f=f_mjtx=2 dla dowolnego x₂. W istocie x₂ można zwiększyć do 3, nic obniżając wartości żadnej ze zmiennych lewostronnych (w^r cym przypadku x>) poniżej zera. Jeśli zamienimy x₂ i x₅ i przyjmiemy x₄=x₅ = 0, to otrzymamy inne rozwiązanie optymalne (f, f, 0, 0). Ogólnym rozwiązaniem powyższego zadania jest odcinek prostej łączący te dwa rozwiązania, tzn. zbiór punktów c (2, O, 6, 0, 3)+ (l —c) ($, |» T • ^ ® dla    l.

Metoda sympleks ma wiele wariantów. Zmienne można zamieniać na różne sposoby, np. gdy rozwiązuje się na komputerze duże zadanie, można z pożytkiem poprzestać hi pierwszym punkcie sąsiednim, który zwiększa wartość/ i nic szukać punktu dającego fl^aJ większy przyrost tej wartości.

że (\*

_; pozostać

Wyniki obliczeń można umieszczać w tablicach podobnie jak w^f eliminacji Gaussa (zob. przykład 5.3.1). Niezbędne wzory' łatwo wyprowadzić; zob. zadanie 3 do tego grafu. Takie wzory mogą być też potrzebne, gdy nie korzysta się ze standardowych °P***gp4 kowanych programów, ani z fabrycznego pakietu podprogramów, lecz pisze się ^w program optymalizacji liniowej.

Metodę sympleks opisuje się niekiedy inaczej; zob. np. Gass {I45J. Mówi się, dej iteracji) jako wektory bazowe wybiera się/n kolumn macierzy {a_i}) z (10.1.2),s