Istota metody Simplex

Istota metody Simplex Metoda uniwersalna do rozwiązań liniowych
Założenia: 1,nm 2. rząd macierzy A-- r(A)=m Spośród n wektorów m jest liniowo niezależnych. Każdy wektor spoza bazy można przedstawić jako kombinację wektorów bazowych. Istota metody Simplex polega na tym, że znajduje się dowolne, bazowe rozwiązanie dopuszczalnie i sprawdza się czy jest to rozwiązanie optymalne. Sprawdzenie to polega na tym, że bada się czy wprowadzenie dodatkowych zmiennych nie ulepszy rozwiązania. Jeśli nie to rozwiązanie wyjścia jest optymalne. Jeśli natomiast ulepszy to wyznacza się nowe rozwiązanie i bada czy wprowadzone zmienne nie ulepszą tego nowego rozwiązania. Następnie znajdujemy badany wierzchołek i sprawdzamy czy w sąsiedztwie nie ma takiego, który da nam wyższe rozwiązanie funkcji celu. Jeśli nie, to jest to rozwiązanie optymalne. Zaletą metody Simplex jest to, że do rozwiązania optymalnego dochodzi się najlepiej po n - iteracjach (metodach). Δ j = Z j - c j Z j = Σc i * Z ij i=1,2… n j=m+1, ….n c i - współczynnik funkcji celu dla funkcji bazowych c j - współczynnik funkcji celu
Z ij - współczynnik kombinacji liniowej KRYTERIUM OPTYMALNOŚCI A j = Σ A i * Z ij 1,Δ j ≤0; j= m+1, … n (rozwiązanie wyjściowe jest optymalne)
2,Δ j ≤0; Z ij ≤ 0 (program jest sprzeczny)
3,Δ j ≤ 0; Z ij 0 (program można ulepszyć)
... zobacz całą notatkę