2999072771

Dwa ostatnie wiersze tabeli simpleksowej przeznaczone zostały dla obliczeń pomocniczych. W jednym z nich wyznaczamy wskaźnik zj - obliczony jako iloczyn skalarny dwóch wektorów będących kolumnami tablicy simpleksowej: wektora Cb oraz odpowiedniej kolumny Xj macierzy współczynników A. Wiersz ten nazywa się wierszem zerowym, ponieważ w pierwszej postaci bazowej występują w nim same zera. W drugim wierszu wyznaczona została wartość różnicy ej - Zj, nazywana wskaźnikiem optymalności lub kryterium simpleks. Wiersz ten odgrywa bardzo istotną rolę w algorytmie simpleks. Na jego podstawie dokonujemy oceny, czy aktualnie analizowane rozwiązanie bazowe jest rozwiązaniem optymalnym i należy zakończyć postępowanie, czy też nie i należy, w poszukiwaniu rozwiązania lepszego, przejść do sąsiedniej bazy. Wskaźnik ten informuje, o ile jednostek wzrosłaby lub zmalała wartość funkcji celu, gdyby zmienna odpowiadająca temu wskaźnikowi wzrosła o jedną jednostkę. Jeśli dla pewnych zmiennych wartość tych wskaźników jest dodatnia, oznacza to, że wprowadzenie którejkolwiek z nich do bazy spowoduje proporcjonalny wzrost wartości funkcji celu. Oznacza to w końcu, że można znaleźć jeszcze inną bazę, dla której rozwiązanie funkcji kryterium będzie lepsze lub przynajmniej nie gorsze od obecnie analizowanej.

Z tablicy simpleksowej łatwo również odczytać wartość funkcji celu odpowiadającą aktualnie rozwiązaniu bazowemu (bazę stanowią zmienne x₃, x₄, jc₅). Wartość funkcji celu otrzymujemy, mnożąc skalarnie kolumnę zawierającą składowe wektora Cb oraz kolumnę ostatnią, zawierającą składowe wektora b. W pierwszej tablicy simpleksowej naszego przykładu wartość tę wyznaczamy, obliczając:

0-14 + 0-8 + 0-16 = 0

czyli wartość funkcji celu odpowiadającą pierwszemu rozwiązaniu bazowemu.

Aby wykonać następny krok algorytmu simpleks należy:

-    sprawdzić, czy rozpatrywane rozwiązanie bazowe jest optymalne, czy też nie;

-    w przypadku, gdy nie jest optymalne, należy wyznaczyć nową bazę sąsiednią, przekształcić za pomocą przekształceń elementarnych macierz warunków ograniczających do postaci bazowej (tak by zmienne bazowe w tej macierzy utworzyły macierz jednostkową I); jeśli będziemy korzystać ze schematu obliczeniowego zawartego w tab. 2.3, wykorzystując działania na macierzach, to macierz jednostkową, jaką utworzą zmienne bazowe, uzyskamy automatycznie i nie będzie konieczności wykonywania przekształceń elementarnych. Sprawdźmy zatem optymalność rozwiązania naszego pierwszego rozwiązania

bazowego. Ponieważ wartość współczynników optymalności jest większa od zera dla zmiennych X/ i x₂, oznacza to, że jeżeli wprowadzimy do nowej bazy którąkolwiek z tych zmiennych, to możemy liczyć na poprawę wartości funkcji kryterium. Można więc sformułować ogólne kryterium optymalności rozwiązania w następujący sposób:

Kryterium optymalności

Jeżeli wartości wszystkich wskaźników optymalności nie są dodatnie (dla zadania maksymalizacji), to rozwiązanie jest optymalne. Jeśli choć jeden ze wskaźników optymalności jest większy od zera (dodatni), to rozwiązanie nie jest optymalne i można je jeszcze poprawić.

20