img293 (7)

zmienne swobodne (ang. slack variables), które stanowią początkowe rozwiązanie bazowe (w pierwszej tablicy simpleksowej). W przypadku nierówności typu „ > ” - od lewych stron odejmujemy zmienne swobodne (ang. surplus variables) i dodajemy tzw. zmienne sztuczne (ang. artifical variables). W tym przypadku zmienne sztuczne wchodzą do pierwszej bazy¹. Do funkcji celu zmienne swobodne wchodzą ze współczynnikami równymi zeru, a zmienne sztuczne z tzw. współczynnikami M, gdzie M jest liczbą bardzo dużą (M-*co). O ile zmienne swobodne mogą znaleźć się w końcowym rozwiązaniu PL, o tyle zmienne sztuczne nie, dlatego w funkcji celu, która jest maksymalizowana, zmienne sztuczne występują ze współczynnikami — M (w ten sposób sztucznie zmniejszają wartość funkcji celu), natomiast w funkcji celu, która jest minimalizowana, zmienne sztuczne występują ze współczynnikami +M (zwiększają wartość funkcji celu).

Wykorzystując zapis macierzowy, zapisujemy pierwszą tablicę simpleks² (tabl. 36).

Tablica 36. Macierzowa postać pierwszej tablicy simpleksowej

		c
Cb	*b	A I	b
	^zi	0
	^cJ~^zi	c

W tablicy 36 A jest macierzą współczynników warunków ograniczających, b - wektorem wyrazów wolnych warunków ograniczających, c - wektorem wierszowym współczynników funkcji celu (zdefiniowanymi wyżej), jc_b - wektorem zmiennych bazowych, c_b - wektorem kolumnowym współczynników funkcji celu przy zmiennych bazowych, / jest macierzą jednostkową o wymiarach mxm (macierzą współczynników przy zmiennych występujących w pierwszej bazie), a 0 jest wektorem zer.

Zasadnicza część tablicy (obwiedziona pogrubioną ramką) składa się z kolumn odpowiadających łącznej liczbie zmiennych (decyzyjnych, swobodnych i sztucznych), natomiast liczba jej wierszy odpowiada liczbie warunków ograniczających (bo z tylu właśnie zmiennych składa się każde rozwiązanie bazowe). A zatem elementami tej części pierwszej tablicy simpleksowej są współczynniki stojące przy poszczególnych zmiennych w warunkach ograniczających (w postaci kanonicznej PL).

Również każdą pośrednią oraz końcową tablicę simpleks można przedstawić za pomocą macierzy. W każdej iteracji algorytmu tablica simpleks ma postać podaną w tabl. 37.

	Zmienne bazowe	c		Rozwiązanie
<‘b	*b	B^3A	B'	B'b
	^zi	clB^3A	clB-^3	cJ,B~ ^3b
	^cj~^zj	C—clB ^3A	1 E-i js U I

wartości zmiennych bazowych wartość funkcji celu

Wyjaśnienia wymaga obecnie jedynie macierz B~³. Otóż macierz W ³ jest odwrotnością macierzy współczynników warunków ograniczających, stojących przy aktualnych (w danej iteracji) zmiennych bazowych. Odwrotność macierzy B zajmuje pozycję macierzy jednostkowej w tablicy początkowej. Ponieważ zmienne bazowe zmieniają się w każdej iteracji, również macierz B (a tym samym i macierz B~³ są inne w każdej iteracji).

Warto jeszcze zwrócić uwagę na ostatni wierz tablicy simpleksowej zwany wierszem zerowym lub kryterium simpleks. Jego elementy odpowiadające poszczególnym zmiennym (kolumnom) informują, o ile zmieni się aktualna w danej iteracji wartość funkcji celu, jeżeli jedną jednostkę tej zmiennej wprowadzimy do nowej (kolejnej) bazy. Innymi słowy, służy on do sprawdzenia, czy aktualne rozwiązanie bazowe jest rozwiązaniem optymalnym. W przypadkach gdy funkcja celu jest maksymalizowana, rozwiązanie dotąd nie będzie optymalne, dopóki w wierszu zerowym będą występować liczby nieujemne (dodatnie liczby świadczą, iż wprowadzenie do bazy zmiennej, której odpowiada dodatni współczynnik, zwiększy wartość funkcji celu). W problemach minimalizacji funkcji celu kolejne rozwiązania bazowe dotąd nie będą optymalne, dopóki w wierszu zerowym będą występować wielkości niedodatnie (co znaczy, że wartość funkcji celu można zmniejszyć)³.

Przykład 8. Przedsiębiorstwo produkuje dwa wyroby: W_t i W₂. Ograniczeniem w procesie produkcji są zapasy trzech surowców:    S₂ i S₃.

W tablicy 38 podano jednostkowe nakłady surowców na produkcję wyrobów, zapasy surowców oraz ceny wyrobów.

Ustalić rozmiary produkcji wyrobów Wj i W₂, które gwarantują maksymalny przychód ze sprzedaży przy istniejących zapasach surowców.

43

1

   Również do warunków równościowych wprowadzamy zmienne sztuczne, które wchodzą do pierwszej bazy.

2

   Por. R.L. Childress [13].

3

Liczby równe zeru dla zmiennych niebazowych (bowiem dla zmiennych bazowych elementy wiersza zerowego są równe zeru) świadczą, iż wprowadzenie do bazy odpowiadających im zmiennych nie zmieni aktualnej wartości funkcji celu, a zatem istnieje także inne rozwiązanie optymalne.