Metoda SIMPLEX

Przykład 1

Rozwiązać metodą SIMPLEX:

Wytwórnia Zabawek Pluszowych „KUBUŚ PUCHATEK” produkuje dwa rodzaje zabawek Kłapouchego i Prosiaczka. Do produkcji używa się m.in. dwóch rodzajów guzików: czerwonych i niebieskich. Przy produkcji Kłapouchego zużywa się 2 guziki czerwone i 1 niebieski, przy produkcji Prosiaczka : 2 czerwone i 4 niebieskie. W magazynie znajduje się 100 guzików czerwonych i 160 niebieskich. Zysk ze sprzedaży Kłapouchego wynosi 6 zł, natomiast Prosiaczka – 4 zł. Proszę podać optymalną produkcję wytwórni ze względu na zysk.

Model matematyczny (postać normalna):

F=6x1+4x2 ® max

2x1+2x2 £ 100

x1+4x2 £ 160

x1, x2 ³ 0

Postać kanoniczna:

F-6x1-4x2 = 0

2x1+2x2+s1= 100

x1+4x2+s2 = 160

x1, x2, s1, s2 ³ 0

Uwaga!

Opisywana metoda SIMPLEX rozwiązuje wyłącznie zadania na maksimum.

Budowa tablicy Simplex:

Do tablicy przepisujemy w wierszach współczynniki stojące przy wszystkich zmiennych z postaci kanonicznej modelu matematycznego:

Każda tablica Simplex zawiera kolumny składające się z samych zer i jednej jedynki (kolumny F, s1 i s2) oraz kolumny zawierające „coś innego” (x1 i x2). Pierwsze należą do rozwiązania bazowego, pozostałe są poza tym rozwiązaniem.

Z kolumn z zerami i jedynką zawsze można zbudować macierz jednostkową (jedynki na przekątnej pozostałe to zera).

W każdym kroku można odczytać rozwiązanie dopuszczalne i sprawdzić czy jest ono rozwiązaniem optymalnym.

Odczytywanie rozwiązania:

·         Zmienne spoza rozwiązania bazowego mają wartość 0 (z definicji). Czyli x1 i x2 równają się 0.

·         Zmienne z rozwiązania bazowego: w kolumnie odszukujemy jedynkę i w wierszu w którym ona się znajduje, w stałych odczytujemy wynik. (np. w kolumnie s1 jedynka znajduje się w wierszu 1, w stałych w wierszu 1 jest liczba 100 tzn. s1=100)

W tym kroku rozwiązaniem jest:

F = 0, x1 = 0, x2 = 0, s1 = 100, s2 = 160

Rozwiązanie optymalne?

Odczytane rozwiązanie jest optymalne, jeżeli w wierszu 0 niema liczb ujemnych. Jeżeli w wierszu 0 znajdują się liczby ujemne to rozwiązanie nie jest optymalne i należy je poprawić.

Otrzymane rozwiązanie nie jest optymalne.

Poprawianie rozwiązania dopuszczalnego:

Wyszukujemy kolumnę mającą w wierszu 0 liczbę ujemną i najmniejszą.

Dzielimy stałą (kolumna st.) przez liczbę z kolumny i wybieramy najmniejszy iloraz. Nie dzielimy przez liczby ujemne.

W miejscu, gdzie jest najmniejszy iloraz będzie 1, w pozostałych komórkach kolumny będą 0.

Aby uzyskać taki układ kolumny można wykonywać następujące działania:

1. Wszystkie działania muszą dotyczyć całych wierszy. Nie wolno wykonań jakiegoś działania dla jednego elementu macierzy.
2. Wiersz w którym ma być 1 (tutaj wiersz 1) należy pomnożyć lub podzielić przez liczbę (tutaj 2).
3. Do wiersza w którym ma być 0 można dodać (odjąć) wiersz z pkt. 2 pomnożony lub podzielony przez liczbę. Ważne aby zachować kolejność działań. (tu jest sporo błędów).

Odczytywanie rozwiązania:

Rozwiązanie dopuszczalne w tym kroku:

F = 300, x1 = 50, x2 = 0, s1 = 0, s2 = 110

Rozwiązanie optymalne?

Ponieważ w wierszu 0 są same liczby nieujemne, rozwiązanie jest również rozwiązaniem optymalnym.

(Gdyby były liczby ujemne należałoby znowu poprawiać to rozwiązanie).

Odpowiedz. (dla zadania z treścią jest obowiązkowa)

Aby zmaksymalizować zysk należy produkować 50 Kłapouchów i 0 Prosiaczków (niestety). Zysk wyniesie wtedy 300 zł. W magazynie pozostanie 0 guzików czerwonych i 110 guzików niebieskich.

Przykład 2.

Przy produkcji 2 wyrobów: W1 i W2 zużywa się 2 rodzaje drewna: D1 i D2. Zużycie i zapas drewna oraz zysk ze sprzedaży wyrobów podano w tabeli:

Proszę podać wielkość produkcji optymalnej ze względu na zysk.

Model matematyczny (postać normalna):

F=120x1+80x2 ® max

0,4x1+0,4x2 £ 120

0,6x1+0,2x2 £ 120

x1, x2 ³ 0

Postać kanoniczna:

F-120x1-80x2 = 0

0,4x1+0,4x2+s1= 120

...