ALGORYTM SIMPLEX
B.Gładysz Badania operacyjne
2007
Zagadnienie asortymentu produkcji
Firma produkuje dwa wyroby P1, P2. Ograniczeniem dla produkcji są trzy
surowce S1, S2 i S3.Nakłady jednostkowe surowców są następujące:
P1 P2
S1 2 2
S2 1 2
S3 4 -
Zysk 2 3
jednostkowy
Firma dysponuje następującym zapasem surowców: S1  14kg, S2  8kg,
S3  16kg. Zoptymalizuj strukturę produkcji.
Model matematyczny
Zmienne decyzyjne
- planowana wielkość produkcji wyrobu P1,
x1
x2 - planowana wielkość produkcji wyrobu P2,
" Funkcja celu
2x1 + 3x2 max
" Ograniczenia
2x1 + 2x2 d" 14
x1 + 2x2 d" 8
4x1 d" 16
x1, x2 e" 0
B.Gładysz Badania operacyjne
2007
B.Gładysz, Badania operacyjne 2007
X2 - produkt2
S2
(0,4)
Z=12
S3
(4,2)
Z=14
X1  produkt1
0 1 2 3 4 5 6 7 8
(4,0)
(0,0)
Z=8
Z=0
B.Gładysz Badania operacyjne
2007
1 2 3 4 5 6 7 8
Postać bazowa
2x1 + 3x2 +0s1 +0s2 +0s3 max
2x1 + 2x2 +s1 = 14
x1 + 2x2 + s2 = 8
4x1 +s3 = 16
x1, x2, s1, s2, s3 e" 0
B.Gładysz Badania operacyjne
2007
Algorytm simpleks
cj 2 3 0 0 0
Baza x1 x2 s1 s2 s3 b
0 s1 2 2 1 0 0 14
0 s2 1 2 0 1 0 8
0 s3 4 0 0 0 1 16
zj 0 0 0 0 0 0
Wskaz
niki
cj-zj 2 3 0 0 0
optymalności
B.Gładysz Badania operacyjne
2007
Rozwiązanie
" Zmienne niebazowe = 0
X1=0, x2=0.
" Zmienne bazowe = bj.
S1=14, s2=8, s3=16.
" Funkcja celu = 0
B.Gładysz Badania operacyjne
2007
B.Gładysz, Badania operacyjne 2007
X2 - produkt2
S2
(0,4)
Z=12
S3
(4,2)
Z=14
X1  produkt1
0 1 2 3 4 5 6 7 8
(4,0)
(0,0)
Z=8
Z=0
B.Gładysz Badania operacyjne
2007
1 2 3 4 5 6 7 8
Wskaz
niki optymalności
m
" = c - z = c - aijciB
"
j j j j
i=1
B.Gładysz Badania operacyjne
2007
Kryterium optymalności
" Rozwiązanie jest optymalne (max),
gdy wszystkie wskaz
niki są niedodatnie.
" Rozwiązanie jest optymalne (min),
gdy wszystkie wskaz
niki są nieujemne.
B.Gładysz Badania operacyjne
2007
Zamiana zmiennych bazowych
cj 2 3 0 0 0
bi bi/aij0
Baza x1 x2 s1 s2 s3
0 s1 2 2 1 0 0 14 14/2 = 7
wychodzi
0 s2 1 2 0 1 0 8 8/2 = 4 min
z bazy
0 s3 4 0 0 0 1 16 - io=2
zj 0 0 0 0 0 0
cj-zj 2 3 0 0 0
max
wchodzi
do bazy
B.Gładysz Badania operacyjne
2007
j0=2
Rozwiązanie w nowej bazie
Elementy wiersza zmiennej wychodzącej z bazy
Wiersz zmiennej wychodzącej z bazy dzielimy przez
główny element przekształcenia:
ai j
0
2
ai j =
0
ai j0
0
Elementy pozostałych wierszy
Od danego wiersza odejmujemy nowy wiersz zmiennej
wychodzącej z bazy pomno\
ony przez element tego wiersza
stojący w kolumnie zmiennej wychodzącej z bazy.
2 2
aij = aij - ai jaij
0 0
B.Gładysz Badania operacyjne
2007
Rozwiązanie w nowej bazie
nowy wiersz2 = stary wiersz2 : 2
cj 2 3 0 0 0
Baza x1 x2 s1 s2 s3 b
0 s1
3 x2 0,5 1 0 0,5 0 4
0 s3
B.Gładysz Badania operacyjne
2007
Rozwiązanie w nowej bazie
nowy wiersz1 = stary wiersz1  2 * nowy wiersz2
cj 2 3 0 0 0
Baza x1 x2 s1 s2 s3 b
0 s1 1 0 1 -1 0 6
3 x2 0,5 1 0 0,5 0 4
0 s3
B.Gładysz Badania operacyjne
2007
Rozwiązanie w nowej bazie
nowy wiersz3 = wiersz3  0 * nowy wiersz2
cj 2 3 0 0 0
Baza x1 x2 s1 s2 s3 b
0 s1 1 0 1 -1 0 6
3 x2 0,5 1 0 0,5 0 4
0 s3 4 0 0 0 1 16
B.Gładysz Badania operacyjne
2007
Wskaz
niki optymalności
cj 2 3 0 0 0
Baza x1 x2 s1 s2 s3 b
0 s1 1 0 1 -1 0 6
3 x2 0,5 1 0 0,5 0 4
0 s3 4 0 0 0 1 16
Zj 1,5 3 0 1,5 0 12
Cj-zj 0,5 0 0 -1,5 0
B.Gładysz Badania operacyjne
2007
Rozwiązanie
" Zmienne niebazowe = 0
X1=0, s2=0.
" Zmienne bazowe = bj.
X1 =4, S1=6, s3=16.
" Funkcja celu = 12
B.Gładysz Badania operacyjne
2007
B.Gładysz, Badania operacyjne 2007
X2 - produkt2
S2
(0,4)
Z=12
S3
(4,2)
Z=14
X1  produkt1
0 1 2 3 4 5 6 7 8
(4,0)
(0,0)
Z=8
Z=0
B.Gładysz Badania operacyjne
2007
1 2 3 4 5 6 7 8
Zamiana zmiennych bazowych
cj 2 3 0 0 0
Baz
bi bi/aij0
a x1 x2 s1 s2 s3
0 s1 1 0 1 -1 0 6 6 : 1 = 6
3 x2 0,5 1 0 0,5 0 4 4 : 0,5 = 8
wychodzi
0 s3 4 0 0 0 1 16 16 : 4 = 4 min z bazy
i0 =3
zj 1,5 3 0 1,5 0 12
cj-zj 0,5 0 0 -1,5 0
max
wchodzi
do bazy
B.Gładysz Badania operacyjne
j0=1
2007
nowy wiersz3= stary wiersz3 :4
cj 2 3 0 0 0
Baza x1 x2 s1 s2 s3 b
0 s1
3 x2
2 x1 1 0 0 0 0,25 4
B.Gładysz Badania operacyjne
2007
Rozwiązanie w nowej bazie
nowy wiersz1 = stary wiersz1  1* nowy wiersz3
cj 2 3 0 0 0
Baza x1 x2 s1 s2 s3 b
0 s1 0 0 1 -1 -0,25 2
3 x2
2 x1 1 0 0 0 0,25 4
B.Gładysz Badania operacyjne
2007
Rozwiązanie w nowej bazie
nowy wiersz2 = stary wiersz2  0,5 * nowy wiersz3
cj 2 3 0 0 0
Baza x1 x2 s1 s2 s3 b
0 s1 0 0 1 -1 -0,25 2
3 x2 0 1 0 0,5 -0,125 2
2 x1 1 0 0 0 0,25 4
B.Gładysz Badania operacyjne
2007
Wskaz
niki optymalności
cj 2 3 0 0 0
Baza x1 x2 s1 s2 s3 b
0 s1 0 0 1 -1 -0,25 2
3 x2 0 1 0 0,5 -0,125 2
2 x1 1 0 0 0 0,25 4
zj 2 3 0 1,5 0,125 14
cj - zj 0 0 0 -1,5 -0,125
B.Gładysz Badania operacyjne
2007
Rozwiązanie optymalne
" Zmienne niebazowe = 0
s2=0, s3=0.
" Zmienne bazowe = bj.
X1 =4, x2=2, s1=2.
" Funkcja celu = 14
B.Gładysz Badania operacyjne
2007
B.Gładysz, Badania operacyjne 2007
X2 - produkt2
S2
(0,4)
Z=12
S3
(4,2)
MAX
Z=14
X1  produkt1
0 1 2 3 4 5 6 7 8
(4,0)
(0,0)
Z=8
Z=0
B.Gładysz Badania operacyjne
2007
1 2 3 4 5 6 7 8
Zagadnienie mieszaniny
Dziennie nale\
y spo\
yć co najmniej 100g białka. Spo\
ycie chleba nie
powinno przekraczać 1 kg dziennie, zaś spo\
ycie ponad 200g tłuszczy jest
szkodliwe dla zdrowia. Wiedząc, \
e w jednym kg chleba zawiera się 50g
białka i 20g tłuszczy oraz \
e w 1 kg mięsa zawiera się 100g białka i 200g
tłuszczy nale\
y obni\
yć do minimum koszty wy\
ywienia. Cena chleba za 1
kg wynosi 2 zł, zaś mięsa 20 zł.
Zmienne decyzyjne:
X1-dzienna racja chleba
X2  dzienna racja tłuszczu
Funkcja celu:
z = 2 x1 + 20 x2
Ograniczenia:
50 x1 + 100 x2 >= 100
20 x1 + 200 x2 <= 200
x1 <= 1
x1 >= 0
x2 >= 0
B.Gładysz Badania operacyjne
2007
Zagadnienie mieszaniny
Funkcja celu:
z = 2 x1 + 20 x2+0 s1+0 s2+0 s3+M a1 ->min
Ograniczenia:
50 x1 + 100 x2  s1 + a1 = 100
20 x1 + 200 x2 + s2 = 200
x1 +s3 = 1
x1, x2, s1, s2, s3, a1>=0,
M  du\
a liczba
B.Gładysz Badania operacyjne
2007
Algorytm Simplex
Pierwsze rozwiązanie bazowe (max)
cj -2 -20 0 -M 0 0
Baza x1 x2 s1 a1 s2 s3 b
-M a1 50 100 -1 1 0 0 100
0 s2 20 200 0 0 1 0 200
0 s3 1 0 0 0 0 1 1
zj
-50M -100M M -M 0 0 -100M
Wskaz
niki
optymalności
cj-zj -2+50M -20+100M M 0 0 0
B.Gładysz Badania operacyjne
2007