Metoda Simpleks
|
P1 |
P2 |
ZASOBY |
S1 |
5 |
4 |
22 |
S2 |
5 |
6 |
45 |
S3 |
3 |
7 |
33 |
ZYSK |
3 |
4 |
|
NAJPIERW WYZNACZAMY FUNKCJĘ CELU
3x1 + 4x2 + 0x4 + 0x5 + 0x6 --> MAX
- kolejny krok to doprowadzenie do postaci kanonicznej układu:
5x1 + 4x2+x3= 22
5x1 +6x2+x4 = 45
5x1 + 7x2+x5 =33
x1 >= 0, x2 >= 0, x3 >= 0, x4 >= 0, x5 >= 0,
- układ doprowadzamy do bazowej postaci kanonicznej
5x1 + 4x2 + 1x3 + 0x4 + 0x5 = 22
5x1 + 6x2 + 0x3 + 1x4 + 0x5 = 45
5x1 + 7x2 + 0x3 + 0x4 + 1x5 = 33
- przystępujemy do tworzenia tabelki metody simpleks
Cx->max |
3 |
4 |
0 |
0 |
0 |
b |
|
Baza |
Cb |
x1 |
x2 |
x3 |
x4 |
x5 |
|
x3 |
0 |
5 |
4 |
1 |
0 |
0 |
22 |
x4 |
0 |
5 |
6 |
0 |
1 |
0 |
45 |
x5 |
0 |
5 |
7 |
0 |
0 |
1 |
33 |
Zj |
|
|
|
|
|
|
|
Cj -Zj |
|
|
|
|
|
|
|
- wyliczamy wskaźniki optymalności
*korzystamy ze wzorów; Zj=∑Cb*aij ; Fc=∑ Cb*b
Cx->max |
3 |
4 |
0 |
0 |
0 |
b |
|
Baza |
Cb |
x1 |
x2 |
x3 |
x4 |
x5 |
|
x3 |
0 |
5 |
4 |
1 |
0 |
0 |
22 |
x4 |
0 |
5 |
6 |
0 |
1 |
0 |
45 |
x5 |
0 |
5 |
7 |
0 |
0 |
1 |
33 |
Zj |
0*5+0*5+0*5=0 |
0*4+0*6+0*7=0 |
0*1+0*0+0*0=0 |
0*0+0*1+0*0=0 |
0*0+0*0+0*1=0 |
22*0+45*0+33*0=0 |
|
Cj -Zj |
3-0=3 |
4-0=4 |
0-0=0 |
0-0=0 |
0-0=0 |
|
|
Ponieważ współczynniki optymalności mają wartości dodatnie - rozwiązanie nie jest optymalne.
↓
* dlatego też następnym krokiem jest znalezienie kryterium wejściowego i wyjściowego;
- maksymalizujemy f-kcję celu więc szukamy maksymalnego wskaźnika optymalności (kryterium wejścia),poczym zaznaczamy całą kolumnę, w której znaleźliśmy max. wskaźnik.
↓
W naszym przypadku jest to wartość = 4
Cx->max |
3 |
4 |
0 |
0 |
0 |
b |
|
Baza |
Cb |
x1 |
x2 |
x3 |
x4 |
x5 |
|
x3 |
0 |
5 |
4 |
1 |
0 |
0 |
22 |
x4 |
0 |
5 |
6 |
0 |
1 |
0 |
45 |
x5 |
0 |
5 |
7 |
0 |
0 |
1 |
33 |
Zj |
0 |
0 |
0 |
0 |
0 |
0 |
|
Cj -Zj |
3 |
4 |
0 |
0 |
0 |
|
|
↓
MAX.
kryterium wejścia
-następnie wyliczamy kryteria wyjścia (ostatnia, szara kolumna) ,
Cx->max |
3 |
4 |
0 |
0 |
0 |
b |
||
Baza |
Cb |
x1 |
x2 |
x3 |
x4 |
x5 |
|
|
x3 |
0 |
5 |
4 |
1 |
0 |
0 |
22 |
22/4=5,5 |
x4 |
0 |
5 |
6 |
0 |
1 |
0 |
45 |
45/6=7,5 |
x5 |
0 |
5 |
7 |
0 |
0 |
1 |
33 |
33/7=4,7 |
Zj |
0 |
0 |
0 |
0 |
0 |
0 |
||
Cj -Zj |
3 |
4 |
0 |
0 |
0 |
|
||
↓
MAX.
kryterium wejścia
-teraz szukamy najmniejszej wartości w ostatniej kolumnie (szarej-kryterium wyjścia),poczym zaznaczamy całą kolumnę, w której znaleźliśmy najmniejszy wskaźnik. ;
Cx->max |
3 |
4 |
0 |
0 |
0 |
b |
||
Baza |
Cb |
x1 |
x2 |
x3 |
x4 |
x5 |
|
|
x3 |
0 |
5 |
4 |
1 |
0 |
0 |
22 |
22/4=5,5 |
x4 |
0 |
5 |
6 |
0 |
1 |
0 |
45 |
45/6=7,5 |
x5 |
0 |
5 |
7 |
0 |
0 |
1 |
33 |
33/7=4,7 |
↓
Kryterium wyjścia
MIN.
Zj |
0 |
0 |
0 |
0 |
0 |
0 |
Cj -Zj |
3 |
4 |
0 |
0 |
0 |
|
↓
MAX.
kryterium wejścia
-wymieniamy jedną zmienną bazową (kolumna żółta) znajdującą się w zaznaczonym wierszu (jest nią x5 ) na zmienną niebazową ,znajdującą się w zaznaczonej kolumnie (jest nią x2 ). Wraz ze zmienną przenosimy odpowiadający jej współczynnik z f-kcji celu (wartość z zielonego wiersza);
Cx->max |
3 |
4 |
0 |
0 |
0 |
b |
||
Baza |
Cb |
x1 |
x2 |
x3 |
x4 |
x5 |
|
|
x3 |
0 |
5 |
4 |
1 |
0 |
0 |
22 |
22/4=5,5 |
x4 |
0 |
5 |
6 |
0 |
1 |
0 |
45 |
45/6=7,5 |
X2 |
4 |
5 |
7 |
0 |
0 |
1 |
33 |
33/7=4,7 |
↓
Kryterium wyjścia
MIN.
Zj |
0 |
0 |
0 |
0 |
0 |
0 |
Cj -Zj |
3 |
4 |
0 |
0 |
0 |
|
↓
MAX.
kryterium wejścia
- zaktualizowanie tabeli wg nowej bazy;
Cx->max |
3 |
4 |
0 |
0 |
0 |
b |
|
Baza |
Cb |
x1 |
x2 |
x3 |
x4 |
x5 |
|
x3 |
0 |
5-0,58*4=2,68 |
4-1*4=0 |
1-0*4=4 |
0-0*4=0 |
0-0,14*4= -0,56 |
22-4,7*4=3,2 |
x4 |
0 |
5 - 0,58*6=1,52 |
6-1*6=0 |
0-0*6=0 |
1-0*6=1 |
0-0,14*6= -0,84 |
45-4,7*6=16,8 |
X2 |
4 |
5/7=0,58 |
7/7=1 |
0/7=0 |
0/7=0 |
1/7=0,14 |
33/7=4,7 |
-kolejny krok do wyliczenie wskaźników pomocniczych, wskaźników optymalności oraz wartość f-kcji celu dla bieżącego rozwiązania;
Cx->max |
3 |
4 |
0 |
0 |
0 |
b |
|
Baza |
Cb |
x1 |
x2 |
x3 |
x4 |
x5 |
|
x3 |
0 |
2,68 |
0 |
4 |
0 |
-0,56 |
3,2 |
x4 |
0 |
1,52 |
0 |
0 |
1 |
-0,84 |
16,8 |
X2 |
4 |
0,58 |
1 |
0 |
0 |
0,14 |
4,7 |
Zj |
0*2,68+0*1,52+4*0,58=2,32 |
0*0+0*0+4*1=4 |
0*4+0*0+4*0=0 |
0*0+0*1+4*0=0 |
0*(-0,56)+0* (-0,84)+4*0,14=0,56 |
0-3,2+0* 16,8+4*4,7 =15,6 |
|
Cj -Zj |
3-2,32=0,68 |
4-4=0 |
0-0=0 |
0-0=0 |
0-0,56= -0,56 |
|
|
Nowa tabela wygląda następująco;
Cx->max |
3 |
4 |
0 |
0 |
0 |
b |
||
Baza |
Cb |
x1 |
x2 |
x3 |
x4 |
x5 |
|
|
x3 |
0 |
2,68 |
0 |
4 |
0 |
-0,56 |
3,2 |
|
x4 |
0 |
1,52 |
0 |
0 |
1 |
-0,84 |
16,8 |
|
X2 |
4 |
0,58 |
1 |
0 |
0 |
0,14 |
4,7 |
|
Zj |
2,32 |
4 |
0 |
0 |
0,56 |
15,6 |
||
Cj -Zj |
0,68 |
0 |
0 |
0 |
-0,56 |
|
||
-szukamy kryteria wejściowe i wyjściowe dla nowej tabeli;