metoda simplex (1), notatki, notatki

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=6x₁+4x₂ → max

2x₁+2x₂ ≤ 100

x₁+4x₂ ≤ 160

x₁, x₂ ≥ 0

Postać kanoniczna:

F-6x₁-4x₂ = 0

2x₁+2x₂+s₁= 100

x₁+4x₂+s₂ = 160

x₁, x₂, s₁, s₂ ≥ 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:

W	F	x₁	x₂	s₁	s₂	st.
0	1	-6	-4	0	0	0
1	0	2	2	1	0	100
2	0	1	4	0	1	160

Każda tablica Simplex zawiera kolumny składające się z samych zer i jednej jedynki (kolumny F, s₁ i s₂) oraz kolumny zawierające „coś innego” (x₁ i x₂). 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 x₁ i x₂ 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 s₁ jedynka znajduje się w wierszu 1, w stałych w wierszu 1 jest liczba 100 tzn. s₁=100)

W tym kroku rozwiązaniem jest:

F = 0, x₁ = 0, x₂ = 0, s₁ = 100, s₂ = 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.

W	F	x₁	x₂	s₁	s₂	st.
0	1	-6 (0)	-4	0	0	0
1	0	2 (1)	2	1	0	100
2	0	1 (0)	4	0	1	160

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

Wszystkie działania muszą dotyczyć całych wierszy. Nie wolno wykonań jakiegoś działania dla jednego elementu macierzy.
Wiersz w którym ma być 1 (tutaj wiersz 1) należy pomnożyć lub podzielić przez liczbę (tutaj 2).
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).

W	F	x₁	x₂	s₁	s₂	st.	skąd on to wziął?
0	1	0	2	3	0	300	=w0+w1*3
1	0	1	1	½	0	50	=w1:2
2	0	0	3	- ½	1	110	=w2-w1:2

Odczytywanie rozwiązania:

Rozwiązanie dopuszczalne w tym kroku:

F = 300, x₁ = 50, x₂ = 0, s₁ = 0, s₂ = 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:

	W1	W2	Zapas
D1	0,4	0,4	120 m³
D2	0,6	0,2	120 m³
Zysk	120 zł	80 zł

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

Model matematyczny (postać normalna):

F=120x₁+80x₂ → max

0,4x₁+0,4x₂ ≤ 120

0,6x₁+0,2x₂ ≤ 120

x₁, x₂ ≥ 0

Postać kanoniczna:

F-120x₁-80x₂ = 0

0,4x₁+0,4x₂+s₁= 120

0,6x₁+0,2x₂+s₂ = 120

x₁, x₂, s₁, s₂ ≥ 0

W	F	x1	x2	s1	s2	st.	skąd on to wziął?
0	1	-120 (0)	-80	0	0	0
1	0	0,4 (0)	0,4	1	0	120
2	0	0,6 (1)	0,2	0	1	120
0	1	0	-40 (0)	0	200	24.000	=w0+w2*200
1	0	0	4/15 (1)	1	-2/3	40	=w1-w2*4/6
2	0	1	1/3 (0)	0	10/6	200	=w2*10/6
0	1	0	0	150	100	30.000	=w0+w1*150
1	0	0	1	15/4	-5/2	150	=w1*15/4
2	0	1	0	-5/4	5/2	150	=w2-w1*5/4

Rozwiązanie optymalne:

F = 30.000, x₁ = 150, x₂ = 150, s₁ = 0, s₂ = 0

Odpowiedz.

Aby osiągnąć maksymalny zysk w wysokości 30.000 zł należy produkować 150 sztuk wyrobu W1 i 150 sztuk wyrobu W2.

Zadania

Zadanie 1. Przedsiębiorstwo produkuje dwa wyroby: W1 i W2. Ograniczeniem w procesie produkcyjnym są zasoby trzech surowców: S1, S2 i S3. Jednostkowe nakłady surowców na produkcję wyrobów, zapasy surowców oraz zysk ze sprzedaży poszczególnych wyrobów podano w tabelce:

	Wyroby
Surowce	W1	W2	Zapas
S1	2	1	1000
S2	3	3	2400
S3	1,5	2	600
Zysk	30	20

Ustalić rozmiary produkcji, aby przychód ze sprzedaży był maksymalny, oraz aby spełnione były ograniczenia zasobów.

Zadanie 2. Zakład dziewiarski wyspecjalizował się w produkcji dwóch wyrobów wełnianych: W1 i W2. Wąskim gardłem procesu produkcji są maszyny typu R1 i R2. W tablicy podano normy pracy poszczególnych maszyn przy produkcji wyrobów W1 i W2 oraz ich zdolności produkcyjne.

	Wyroby
Maszyny	W1	W2	Maksymalny czas pracy
R1	2	1	12
R2	2	2	20

Cena zbytu wynosi: W1 - 50 zł, W2 - 75 zł. Ustalić plan produkcji, aby przychód był jak największy.

Zadanie 3. Przedsiębiorstwo produkuje dwa wyroby W1 i W2. Do ich produkcji zużywa się m.in. dwa limitowane surowce: S1 i S2. Zużycie tych surowców na jednostkę każdego z tych wyrobów, dopuszczalne limity zużycia surowców oraz zyski jednostkowe ze sprzedaży pokazuje tabelka: