Metoda geometryczna i simpleks ([1] - str. 43)

Przedsiębiorstwo wytwarza dwa produkty: P1 i P2. Ograniczeniem w procesie produkcji są zapasy trzech surowców: S1, S2, S3. Jednostkowe nakłady surowców na produkcję wyrobów, zapasy surowców i ceny wyrobów są następujące:

Surowce	Zużycie surowca na 1 sztukę produktu		Zapas surowca [kg]
		P1		P2
S1 S2 S3	2 3 1,5	1 3 0	1000 2400 600
Cena wyrobu [zł]:	30	20

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

Rozwiązanie:

x₁ i x₂ to zmienne oznaczające wielkość produkcji wyrobów P1 i P2.

Funkcja celu:

f(x₁, x₂) = 30 ^. x₁ + 20 ^. x₂ → max

Metoda geometryczna:

Ograniczenia w postaci funkcji x₂(x₁):

x₂ ≤ -2 ^. x₁ + 1000

x₂ ≤ -x₁ + 800

x₁ ≤ 400

Metoda simpleks:

z = 30 ^. x₁ + 20 ^. x₂ → max

2 ^. x₁ + x₂ ≤ 1000

3 ^. x₁ + 3 ^. x₂ ≤ 2400

1,5 ^. x₁ ≤ 600

Wprowadzamy zmienne dodatkowe i zamieniamy nierówności na równania:

2 ^. x₁ + x₂ + x₃ = 1000

3 ^. x₁ + 3 ^. x₂ + x₄ = 2400

1,5 ^. x₁ + x₅ = 600

Funkcję celu zapisujemy w postaci:

-z + 30 ^. x₁ + 20 ^. x₂ = 0

Przyjmujemy początkowe rozwiązanie bazowe:

x₃ = 1000, x₄ = 2400, x₅ = 600

a więc:

x₁ = x₂ = 0

Pierwsza tabela simpleksowa:

x1	x2	x3	x4	x5		zmienne bazowe:
2 3 1,5	1 3 0	1 0 0	0 1 0	0 0 1	1000 2400 600	x3 x4 x5
30	20	0	0	0

Krok 1:

Ostatni wiersz tabeli: wszystkie współczynniki poza ostatnim są ≤ 0? NIE - przechodzimy do kroku 2.

x1	x2	x3	x4	x5		zmienne bazowe:
2 3 1,5	1 3 0	1 0 0	0 1 0	0 0 1	1000 2400 600	x3 x4 x5
30	20	0	0	0

Krok 2:

Wybieramy największy z tych współczynników, czyli 30 (odpowiada on zmiennej x₁) i nową zmienną bazową jest właśnie x₁. Mamy więc zmienną wchodzącą.

x1	x2	x3	x4	x5		zmienne bazowe:
2 3 1,5	1 3 0	1 0 0	0 1 0	0 0 1	1000 2400 600	x3 x4 x5
30	20	0	0	0

Krok 3:

Szukamy zmiennej wychodzącej, zastępowanej przez wchodzącą.

Wśród współczynników przy zmiennej wchodzącej wyszukujemy ten, który dzieląc odpowiadający mu wynik z ostatniej kolumny da najmniejszą wartość:

1000/2=500

2400/3=800

600/1,5=400

UWAGA: pod uwagę bierzemy jedynie współczynniki > 0 !!!

Wybieramy więc wiersz trzeci, a odpowiadająca mu dotychczasowa zmienna bazowa jest wychodząca i zastępuje ją zmienna wchodząca:

x1	x2	x3	x4	x5		zmienne bazowe:
2 3 1,5	1 3 0	1 0 0	0 1 0	0 0 1	1000 2400 600	x3 x4 x1
30	20	0	0	0

Krok 4:

Wybrany wiersz mnożymy przez odpowiednie współczynniki i odejmujemy od pozostałych wierszy tak by w kolumnie zmiennej wchodzącej jedynym niezerowym wyrazem był element z wybranego wiersza, czyli:

• mnożymy wiersz trzeci przez (2/1,5=4/3) i odejmujemy od wiersza pierwszego,

• mnożymy wiersz trzeci przez 2 i odejmujemy od wiersza drugiego,

• mnożymy wiersz trzeci przez 20 i odejmujemy od wiersza czwartego,

• na koniec dzielimy trzeci wiersz przez 1,5, tak by niezerowy element sprowadzić do jedności:

x1	x2	x3	x4	x5		zmienne bazowe:
2 3 1,5	1 3 0	1 0 0	0 1 0	0 0 1	1000 2400 600	x3 x4 x1	w1-(w3*2/1,5) w2-(w3*2) w3/1,5
30	20	0	0	0			w4-(w3*20)

Otrzymujemy:

x1	x2	x3	x4	x5		zmienne bazowe:
0 0 1	1 3 0	1 0 0	0 1 0	-4/3 -2 2/3	200 1200 400	x3 x4 x1
0	20	0	0	-20

POWTARZAMY PROCEDURĘ

Krok 1: ponieważ istnieje w ostatnim wierszu wyraz > 0 więc:

Krok 2:

Największy współczynnik jest przy x₂ i to jest nasza zmienna wchodząca:

x1	x2	x3	x4	x5		zmienne bazowe:
0 0 1	1 3 0	1 0 0	0 1 0	-4/3 -2 2/3	200 1200 400	x3 x4 x1
0	20	0	0	-20

Krok 3:

200/1=200

1200/3=400

Zmienna wychodząca to x₃.

x1	x2	x3	x4	x5		zmienne bazowe:
0 0 1	1 3 0	1 0 0	0 1 0	-4/3 -2 2/3	200 1200 400	x2 x4 x1
0	20	0	0	-20

Krok 4:

Mnożymy wiersz pierwszy i odejmujemy od innych tak by zerować współczynniki w kolumnie przy x₂:

x1	x2	x3	x4	x5		zmienne bazowe:
0 0 1	1 3 0	1 0 0	0 1 0	-4/3 -2 2/3	200 1200 400	x2 x4 x1	w2-(w1*3)
0	20	0	0	-20			w4-(w1*20)

Otrzymujemy:

x1	x2	x3	x4	x5		zmienne bazowe:
0 0 1	1 0 0	1 -3 0	0 1 0	-4/3 2 2/3	200 600 400	x2 x4 x1
0	0	-20	0	20/3

POWTARZAMY PROCEDURĘ

Krok 1: ponieważ istnieje w ostatnim wierszu wyraz > 0 więc:

Krok 2:

Największy współczynnik jest przy x₅ i to jest nasza zmienna wchodząca:

x1	x2	x3	x4	x5		zmienne bazowe:
0 0 1	1 0 0	1 -3 0	0 1 0	-4/3 2 2/3	200 600 400	x2 x4 x1
0	0	-20	0	20/3

Krok 3:

600/2=300

400/(2/3)=600

Zmienną wychodzącą jest x₄:

x1	x2	x3	x4	x5		zmienne bazowe:
0 0 1	1 0 0	1 -3 0	0 1 0	-4/3 2 2/3	200 600 400	x2 x5 x1
0	0	-20	0	20/3

Krok 4:

x1	x2	x3	x4	x5		zmienne bazowe:
0 0 1	1 0 0	1 -3 0	0 1 0	-4/3 2 2/3	200 600 400	x2 x5 x1	w1-(w2*(-2/3)) w2/2 w3-(w2*1/3)
0	0	-20	0	20/3			w4-(w2*10/3)

x1	x2	x3	x4	x5		zmienne bazowe:
0 0 1	1 0 0	-1 -1,5 1	2/3 0,5 -1/3	0 1 0	600 300 200	x2 x5 x1
0	0	-10	-10/3	0

WSZYSTKIE PARAMETRY W OSTATNIM WIERSZU SĄ ≤ 0!!!

Wartości uzyskane przy zmiennych bazowych są rozwiązaniem optymalnym:

x₁ = 200

x₂ = 600

x₅ = 300 - niewykorzystany zasób surowca S3

Literatura

1. Jędrzejczyk Z., Skrzypek J., Kukuła K., Walkosz A.: Badania operacyjne w przykładach i zadaniach, wyd. 2, PWN, Warszawa 1997

1

Ograniczenia:

2 . x1 + x2 ≤ 1000

3 . x1 + 3 . x2 ≤ 2400

1,5 . x1 ≤ 600

x1 ≥ 0, x2 ≥ 0

Izolinie przychodów:

30 ^. x₁ + 20 ^. x₂ = z

Rozwiązanie optymalne:

x = (x₁*, x₂*) = (200, 600)

Przychód ze sprzedaży
przy optymalnym asortymencie produkcji:

f(x₁*, x₂*) = 30 ^. x₁ + 20 ^. x₂ =

= 6000 + 12000 = 18000 zł

400 500

x₂

1000

800

800 x₁

100

200

300

400

500

600

700

100

200

300

900

600 700

maksymalny zysk ze sprzedaży

izolinia przychodów

obszar rozwiązań dopuszczalnych

---