METODA SIMPLEX
lkm
METODA SIMPLEX
lkm
Do przewozu środkiem transportowym o
maksymalnej ładowności
16800
i kubaturze
przestrzeni ładunkowej
800
wyznaczone są
trzy produkty:
A, B
i
C.
Masa produktów
wynosi:
280, 120,
i
100
; zaś objętość
odpowiednio
10,
8
oraz
20.
Cena
poszczególnych produktów kształtuje się
następująco:
12, 5
i
10.
Dodatkowo produkty
charakteryzują się zróżnicowanym poziomem
trwałości, który wynosi
2, 5
oraz
10.
Środek
transportowy zapewnia maksymalny poziom
trwałości towarów w granicach
100.
Treść zadania.
.
A(x
1
)
B(x
2
)
C(x
3
)
ograniczen
ia
masa
280
120
100
16800
objętość
10
8
20
800
trwałość
2
5
10
100
cena
12
5
10
MAX
Postać standardowa
układu.
Funkcja celu
12x
1
+ 5x
2
+10x
3
→ MAX
280x
1
+ 120x
2
+100x
3
≤ 16800
10x
1
+ 8x
2
+20x
3
≤ 800
2x
1
+ 5x
2
+10x
3
≤ 100
Warunki nieujemności
x
1
≥ 0, x
2
≥ 0, x
3
≥ 0,
Postać kanoniczna
układu
.
Funkcja celu
12x
1
+ 5x
2
+10x
3
+ 0x
4
+ 0x
5
+ 0x
6
→ MAX
280x
1
+ 120x
2
+100x
3
+ x
4
= 16800
10x
1
+ 8x
2
+20x
3
+ x
5
= 800
2x
1
+ 5x
2
+10x
3
+ x
6
= 100
Warunki nieujemności
x
1
≥ 0, x
2
≥ 0, x
3
≥ 0, x
4
≥ 0, x
5
≥ 0, x
6
≥ 0
Bazowa postać kanoniczna
układu.
Funkcja celu
12x
1
+ 5x
2
+10x
3
+ 0x
4
+ 0x
5
+ 0x
6
→ MAX
280x
1
+ 120x
2
+100x
3
+ 1x
4
+ 0x
5
+ 0x
6
= 16800
10x
1
+ 8x
2
+20x
3
+ 0x
4
+ 1x
5
+ 0x
6
= 800
2x
1
+ 5x
2
+10x
3
+ 0x
4
+ 0x
5
+ 1x
6
= 100
Warunki nieujemności
x
1
≥ 0, x
2
≥ 0, x
3
≥ 0, x
4
≥ 0, x
5
≥ 0, x
6
≥ 0
Metoda Simpleks –
tabela.
12
5
10
0
0
0
x1
x2
x3
x4
x5
x6
0
x4
280
120
100
1
0
0
1680
0
0
x5
10
8
20
0
1
0
800
0
x6
2
5
10
0
0
1
100
Współczynniki funkcji
celu (ceny)
Współczynniki
przy zmiennych
szukanych
Współczynniki
przy zmiennych
swobodnych
Ograniczenia
Współczynnik
funkcji celu
bieżącego
równania
wartość funkcji celu
bieżącego równania
Wskaźniki
pomocnicze
Wskaźniki
optymalności
Kryteria wyjścia
Wskaźniki pomocnicze
wyliczamy jako iloczyn skalarny pierwszej kolumny
współczynnika funkcji celu bieżącego równania oraz kolejnej kolumny
współczynników.
Wskaźnik optymalności
liczymy odejmują od cen współczynniki
pomocnicze. Wskaźniki te pozwalają nam określić czy dane równanie jest
optymalne. Jeżeli wszystkie wskaźniki będą niedodatnie w przypadku
maksymalizacji funkcji celu to nasze rozwiązanie będzie optymalne.
Wartość funkcji
celu dla bieżącego równania (kolor żółty) obliczamy jako
wektor skalarny pierwszej kolumny współczynnika funkcji celu bieżącego
równania
i
kolumny
ograniczeń.
12
5
10
0
0
0
x1
x2
x3
x4
x5
x6
0
x4
280
120
100
1
0
0
1680
0
0
x5
10
8
20
0
1
0
800
0
x6
2
5
10
0
0
1
100
0
0
0
0
0
0
12
5
10
0
0
0
280·0+10·0+3·
0=0
MAX
Kryterium
wejścia
12 – 0 = 8
Maksymalizujemy funkcję celu, więc szukamy maksymalnego
wskaźnika
optymalności
i
zaznaczamy
całą
kolumnę.
Wyliczamy kryteria wyjścia, jako iloraz ograniczeń i zaznaczonej
kolumny.
12
5
10
0
0
0
x1
x2
x3
x4
x5
x6
0
x
4 280
120
100
1
0
0
16800
16800/280
=60
0
x
5 10
8
20
0
1
0
800
800/10
=80
0
x
6
2
5
10
0
0
1
100
100/2
=50
0
0
0
0
0
0
12
5
10
0
0
0
MAX
Kryterium
wejścia
MIN
Kryterium
wyjścia
Wymieniamy zmienną bazową – x6 na zmienną
niebazową – x1 oraz zaktualizujemy współczynniki
oraz ograniczenia.
12
5
10
0
0
0
x1
x2
x3
x4
x5
x6
0
x4
280-
1·280
=0
120-
2,5·2
80
= -580
100-5·280
= -1300
1-
0·2
80
=1
0-
0·2
80
=0
0-
0,5·
280
=-140
16800-
50·280
= 2800
0
x5
10-1·10
=0
8-2,5·10
=-17
20-5·10
=-30
0-0·10
=0
1-0·10
=1
0-
0,5·
10
=-5
800-50·10
=300
12 x1
2/2 = 1
5/2= 2,5
10/2= 5
0/2= 0
0/2= 0 1/2=0,5
100/2 = 50
Wyliczamy wskaźniki pomocnicze, wskaźniki
optymalności i wartość funkcji celu.
12
5
10
0
0
0
x1
x2
x3
x4
x5
x6
0
x4
280-
1·280
=0
120-
2,5·28
0
= -580
100-5·280
= -1300
1-
0·2
80
=1
0-
0·2
80
=0
0-0,5·280
=-140
16800-
50·280
= 2800
0
x5
10-1·10
=0
8-2,5·10
=-17
20-5·10
=-30
0-0·10
=0
1-0·10
=1
0-0,5·10
=-5
800-50·10
=300
12 x1
2/2 = 1
5/2= 2,5
10/2= 5
0/2= 0
0/2= 0
1/2=0,5
100/2 = 50
0·0+0·0
+1·12=1
2
0·-
580+0·-
17+2,5·1
2=30
0·-
1300+0·-
30+5·12=
60
0·1+0·
0+0·12
=0
0·0+0·
1+0·1
2=0
0·-
140+0·-
5+0,5·12
=6
12-12
=0
5-30
= -25
10-60
=-50
0-0
=0
0-0
=0
0-6
=-6
600
Otrzymaliśmy rozwiązanie optymalne, gdyż żaden współczynnik nie
jest dodatni.
Rozwiązanie zadania.
x
1
= 50
x
4
= 2 800
x
5
= 300
x2 = 0
x3 = 0
x6 = 0
Maksymalny zysk uzyskany wynosi
600.
Przy założonych ograniczeniach należy wybrać
50
sztuk produktu
A
.