45500

Istota metody Simpley

Metoda uniwersalna do rozwiązań liniowych Założenia:

l,n>m 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 Simpłex 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 cela 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).

Aj= Z, -Cj Zj=Eci*Z, 1=1,2... n j=m+l, ....n

c, - współczynnik funkcji celu dla funkcji bazowych

Cj- współczynnik funkcji celu

Z, - współczynnik kombinacji liniowej

KRYTERIUM OPTYMALNOŚCI

Aj= ZA,* Zy

1, A,Ś0; j= m+1, ... n (rozwiązanie wyjściowe jest optymalne)

2, Aj śO; Z,j ś 0 (program jest sprzeczny)

3, A, <. 0; Zi, > 0 (program można ulepszyć)