Slajd49 4

Metoda simpleks

Jak już wspomniano, program liniowy może mieć więcej niż jedno rozwiązanie optymalne. Aby to stwierdzić, wystarczy przeanalizować wskaźniki optymalności Cj - Zj dotyczące optymalnego rozwiązania programu, zawarte w ostatnim wierszu tablicy simpleksowej. Dla zmiennych wchodzących do bazy otrzymujemy przynajmniej m wskaźników optymalności zerowych, co wynika bezpośrednio ze sposobu konstrukcji kryterium metody simpleks. W ostatecznej bazie mamy więc co najmniej m wskaźników Cj - z-_l zerowych, pozostałe przyjmują wartości ujemne. Jeśli wskaźniki optymalności są równe zeru tylko dla zmiennych bazowych rozwiązania optymalnego (jest więc dokładnie m zer), to otrzymane rozwiązanie optymalne jest jedynym. Jeśli natomiast wskaźniki optymalności w ostatecznym rozwiązaniu bazowym przyjmują wartości zerowe także dla zmiennych niebazowych (jest więcej niż m zer), to program ma wiele rozwiązań optymalnych. Wówczas można zmienną niebazową z zerowym wskaźnikiem optymalności wprowadzić do bazy i uzyskać nowe rozwiązanie optymalne, przy czym wartość funkcji celu nie ulegnie zmianie.