38145

Metoda Simple\ - metoda uniwersalna rozwiązywania parametrów liniowych Założenie metody;

•    n > m (liczba niewiadomych > liczba równań)

•    rząd macierzy A = m

Spośród n wektorów tylko m jest liniowo niezależna. Kiedy wektor spoza bazy można wyróżnić jedną kombinację wektorów bazowycli.

Istota metody - znajduje się dowolne bazowe rozwiązanie dopuszczalne i sprawdza się czy jest ono optymalne.

Sprawdzenie to polega na tym ze bada się czy wprowadzenie dodatkowych zmiennych nie ulepsza danego badania - jeśli nie to pierwsze rozwiązanie jest optymalne. Jeśli tak to wyznaczamy nowe rozwiązanie i badamy czy wprowadzone zmienne nie ulepszają nowego rozwiązania. Potem znajdujemy dowolny wierzchołek i sprawdzamy czy w jego sąsiedztwie nie ma takiego, który da nam wyższe rozwiązanie funkcji celu.

Zaleta tej metody - do rozwiązania optymalnego dochodzimy po n interpretacjach.

Mamy 3 przypadki:

a)    Aj >=0- rozwiązanie wyjściowe jest optymalne

b)    Aj<0, zij<=0- program jest sprzeczny

c)    Aj<=0, zij>0- rozwiązanie można ulepszyć

Kryterium optymalności: Delta i = Zi - G ; Zi = £ G * Zji Metoda sztucznej bazy

Stosujemy ją gdy nie da się utworzyć macierzy jednostkowej. Należy do zadania wyjściowego wprowadzić zmienne sztuczne Ul i U2. Parametry funkcji celu dla zmiennych sztucznych są równe +M dla min. f. celu lub -M dla max. f. celu.

M - bardzo duża liczba dodatnia, większa od liczb występujących w zadaniach

Jeżeli istnieje rozwiązanie optymalne programu rozszerzonego, to jest to jednocześnie rozwiązanie optymalne programu wyjściowego.

Jeżeli w rozwiązaniu bazowym przynajmniej jedna zmienna sztuczna jest mniejsza od 0, a programu nie można ulepszyć, to jest on sprzeczny.

Kryterium optymalności dla L(x)Q min:

a)    Aj<=0- program optymalny, nie można go ulepszyć;

b)    Aj>0, zij<=0- program sprzeczny;

c)    Aj>0, zij>0- program można ulepszyć;