Metoda Simplex - 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 bazowych.
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) ∆j =0- rozwiązanie wyjściowe jest optymalne
b) ∆j0- rozwiązanie można ulepszyć
Kryterium optymalności : Delta i = Zi - Ci ; Zi = ∑ Ci * Zji
Metoda sztucznej bazy Stosujemy ją gdy nie da się utworzyć macierzy jednostkowej. Należy do zadania wyjściowego wprowadzić zmienne sztuczne U1 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) min:
a) ∆j0, zij0, zij0- program można ulepszyć;
... zobacz całą notatkę
Komentarze użytkowników (0)