45502

Metoda s/tucynej l>aiv

Metoda ta jest stosowana, gdy macierz utworzona z parametrów występujących przy zmiennych swobodnych w postaci kanonicznej nie jest macierzą jednostkową.

Np. L(y)= 15yi+24y2+0yi+y4+MUi+MU2“> min

15yi+24y2-y3⁺U i =50

3yi+6yry4⁺U2=50

yaytyny* u_i; u^o

parametry funkcji celu zmiennych sztucznych zależą czy jest ona maksymalizowana czy minimalizowana. Jeśli min to parametr wynosi +M, jeśli -> MAX to parametr wynosi -M. Zadanie ze zmiennymi sztucznymi to tzw. zadanie rozszerzone.

Bazowe rozwiązanie dopuszczalne v=(0.0.0.0. Ui_: U2) czyli y=(0,0,0,0, 50, 80). Rozwiązanie tworzą tu zmienne sztuczne, czyli sztuczna baza.

Twierdzenia:

1, Jeśli istnieje rozwiązanie optymalne programu rozszerzonego(ze zmiennymi sztucznymi) to jest ono jednocześnie optymalnym rozwiązaniem programu wyjściowego(bez zmiennych sztucznych). Wynika z tego, ze w rozwiązaniu optymalnym wartości zmiennych sztucznych powinny być równe 0.

2, Jeżeli w rozwiązaniu bazowym dopuszczalnym przynajmniej jedna zmienna sztuczna będzie większa od 0, a programu nie będzie można ulepszyć, oznacza to, że zadanie jest sprzeczne- źle zbudowane.

3,    Jeśli istnieje rozwiązanie optymalne programu pierwotnego, to istnieje także rozwiązanie optymalne programu dualnego. Wartość funkcji celu rozwiązań optymalnych obu programów są takie same. MaxL^cp'(x)=minL^t,,,(y)