419 2

419

10.2. Metoda sympleks

wyraża się jako kombinacje liniowe tamtych. W każdej iteracji zamienia się wektor jazowy z wektorem nic należącym do bazy. Związek z naszym ujęciem jest bardzo prosty: bazowe są tymi kolumnami macierzy układu (10.1.2), którym odpowiadają aktualne zmienne lewostronne. Obliczenia są w obu ujęciach takie same.

Pytanie przeglądowe

Opisać metodę sympleks. Jak postępuje się w przypadku zdegenerowanego wektora dopuszczalnego?

Zadania

1.    (a) Znaleźć maksimum wyrażenia/=x_x + 3x₂ przy warunkach

2x₁ + x₂<2,

<10.2.2)    x₁+2x₂<2,

x_Ł^0,    x₂>.0.

Rozwiązać najpierw' to zadanie graficznie, a potem zastosować metodę sympleks, przyjmując jako punkt początkowy x, = x₂=0.

W wariantach (b) - (d) zacząć od tych zmiennych prawostronnych, które otrzymano w rozwiązaniu optymalnym z (a).

(b)    Znaleźć maksimum wyrażenia f=2x_x + 5x₂ przy warunkach z (a).

(c)    Znaleźć maksimum wyrażenia f=x₁^-x₂ przy warunkach z (a).

(d)    Znaleźć maksimum wyrażenia f=x_l^Jr3x₂ zmieniwszy warunek (10.2.2) na 2x_t + ~2x₂<3.

(c) Jakie wnioski można wysnuć z zadań (b) - (d)?

2.    Załóżmy, że dla pewnego komputera opracowano układ programów — nazwijmy go LP — rozwiązujących zadania programowania liniowego w postaci normalnej. LP obli-^".ięc _max/= ceprzy ograniczeniach Ax=b, x^O, gdzie c, x\b są wektorami kolumnowymi, a ,4 jest macierzą. (Relacja x^O oznacza, że wszystkie składowe wektora x są nie-°jemne.) Do maszyny należy wprowadzić tylko A, b i c. Zamierza się rozwiązać następujące zadanie:

znaleźć min (Xi+2x₂+3*j+4**+5*5+**+*.,), gdzie |x,-f*₂ + x_a-4|<]2,

3xi-fx₂+5x*<ó,

x,+x₂ + 3x₃>3,

|x₁-x₂ + 5x₇|>I , x,>0    (i*=3,2,

Pod •

^ac B i c dla tego przykładu.