B.Gładysz Badania operacyjne
2007
ALGORYTM SIMPLEX
B.Gładysz Badania operacyjne
2007
ALGORYTM SIMPLEX
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:
-
4
S3
3
2
Zysk
jednostkowy
2
1
S2
2
2
S1
P2
P1
Firma dysponuje nast
ę
puj
ą
cym zapasem surowców: S1 – 14kg, S2 – 8kg,
S3 – 16kg. Zoptymalizuj struktur
ę
produkcji.
B.Gładysz Badania operacyjne
2007
Model matematyczny
Zmienne decyzyjne
- planowana wielko
ść
produkcji wyrobu P1,
- planowana wielko
ść
produkcji wyrobu P2,
• Funkcja celu
• Ograniczenia
max
3
2
2
1
→
+
x
x
0
,
16
4
8
2
14
2
2
2
1
1
2
1
2
1
≥
≤
≤
+
≤
+
x
x
x
x
x
x
x
1
x
2
x
B.Gładysz Badania operacyjne
2007
0 1 2 3 4 5 6 7 8
1
2
3
4
5
6
7
8
X1 –produkt1
X2 - produkt2
S3
S2
(4,2)
Z=14
(0,4)
Z=12
(0,0)
Z=0
(4,0)
Z=8
B.Gładysz, Badania operacyjne 2007
B.Gładysz Badania operacyjne
2007
Posta
ć
bazowa
0
,
,
,
,
16
4
8
2
14
2
2
3
2
1
2
1
3
1
2
2
1
1
2
1
≥
=
+
=
+
+
=
+
+
s
s
s
x
x
s
x
s
x
x
s
x
x
max
0
0
0
3
2
3
2
1
2
1
→
+
+
+
+
s
s
s
x
x
B.Gładysz Badania operacyjne
2007
Algorytm simpleks
0
0
0
3
2
cj-zj
Wska
ź
niki
optymalno
ś
ci
0
0
0
0
0
0
zj
16
1
0
0
0
4
s3
0
8
0
1
0
2
1
s2
0
14
0
0
1
2
2
s1
0
s3
s2
s1
x2
x1
Baza
b
0
0
0
3
2
cj
B.Gładysz Badania operacyjne
2007
Rozwi
ą
zanie
• Zmienne niebazowe = 0
X1=0, x2=0.
• Funkcja celu = 0
• Zmienne bazowe = bj.
S1=14, s2=8, s3=16.
B.Gładysz Badania operacyjne
2007
0 1 2 3 4 5 6 7 8
1
2
3
4
5
6
7
8
X1 –produkt1
X2 - produkt2
S3
S2
(4,2)
Z=14
(0,4)
Z=12
(0,0)
Z=0
(4,0)
Z=8
B.Gładysz, Badania operacyjne 2007
B.Gładysz Badania operacyjne
2007
Wska
ź
niki optymalno
ś
ci
∑
−
=
−
=
∆
=
m
i
iB
ij
j
j
j
j
c
a
c
z
c
1
B.Gładysz Badania operacyjne
2007
Kryterium optymalno
ś
ci
• Rozwi
ą
zanie jest optymalne (max),
gdy wszystkie wska
ź
niki s
ą
niedodatnie.
• Rozwi
ą
zanie jest optymalne (min),
gdy wszystkie wska
ź
niki s
ą
nieujemne.
B.Gładysz Badania operacyjne
2007
Zamiana zmiennych bazowych
j
0
=2
wchodzi
do bazy
max
0
0
0
3
2
cj-zj
0
0
0
0
0
0
zj
i
o
=2
-
16
1
0
0
0
4
s3
0
wychodzi
z bazy
min
8/2 = 4
8
0
1
0
2
1
s2
0
14/2 = 7
14
0
0
1
2
2
s1
0
s3
s2
s1
x2
x1
Baza
bi/aij
0
bi
0
0
0
3
2
cj
B.Gładysz Badania operacyjne
2007
Rozwi
ą
zanie w nowej bazie
0
0
0
0
j
i
j
i
j
i
a
a
a
=
′
Elementy wiersza zmiennej wychodz
ą
cej z bazy
Wiersz zmiennej wychodz
ą
cej z bazy dzielimy przez
główny element przekształcenia:
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.
0
0
ij
j
i
ij
ij
a
a
a
a
′
−
=
′
B.Gładysz Badania operacyjne
2007
Rozwi
ą
zanie w nowej bazie
nowy wiersz2 = stary wiersz2 : 2
s3
0
4
0
0,5
0
1
0,5
x2
3
s1
0
s3
s2
s1
x2
x1
Baza
b
0
0
0
3
2
cj
B.Gładysz Badania operacyjne
2007
Rozwi
ą
zanie w nowej bazie
nowy wiersz1 = stary wiersz1 – 2 * nowy wiersz2
s3
0
4
0
0,5
0
1
0,5
x2
3
6
0
-1
1
0
1
s1
0
s3
s2
s1
x2
x1
Baza
b
0
0
0
3
2
cj
B.Gładysz Badania operacyjne
2007
Rozwi
ą
zanie w nowej bazie
nowy wiersz3 = wiersz3 – 0 * nowy wiersz2
16
1
0
0
0
4
s3
0
4
0
0,5
0
1
0,5
x2
3
6
0
-1
1
0
1
s1
0
s3
s2
s1
x2
x1
Baza
b
0
0
0
3
2
cj
B.Gładysz Badania operacyjne
2007
Wska
ź
niki optymalno
ś
ci
0
-1,5
0
0
0,5
Cj-zj
12
0
1,5
0
3
1,5
Zj
16
1
0
0
0
4
s3
0
4
0
0,5
0
1
0,5
x2
3
6
0
-1
1
0
1
s1
0
s3
s2
s1
x2
x1
Baza
b
0
0
0
3
2
cj
B.Gładysz Badania operacyjne
2007
Rozwi
ą
zanie
• Zmienne niebazowe = 0
X1=0, s2=0.
• Funkcja celu = 12
• Zmienne bazowe = bj.
X1 =4, S1=6, s3=16.
B.Gładysz Badania operacyjne
2007
0 1 2 3 4 5 6 7 8
1
2
3
4
5
6
7
8
X1 –produkt1
X2 - produkt2
S3
S2
(4,2)
Z=14
(0,4)
Z=12
(0,0)
Z=0
(4,0)
Z=8
B.Gładysz, Badania operacyjne 2007
B.Gładysz Badania operacyjne
2007
Zamiana zmiennych bazowych
j
0
=1
wchodzi
do bazy
max
0
-1,5
0
0
0,5
cj-zj
i
0
=3
12
0
1,5
0
3
1,5
zj
wychodzi
z bazy
min
16 : 4 = 4
16
1
0
0
0
4
s3
0
4 : 0,5 = 8
4
0
0,5
0
1
0,5
x2
3
6 : 1 = 6
6
0
-1
1
0
1
s1
0
s3
s2
s1
x2
x1
Baz
a
bi/aij
0
bi
0
0
0
3
2
cj
B.Gładysz Badania operacyjne
2007
nowy wiersz3= stary wiersz3 :4
4
0,25
0
0
0
1
x1
2
x2
3
s1
0
s3
s2
s1
x2
x1
Baza
b
0
0
0
3
2
cj
B.Gładysz Badania operacyjne
2007
Rozwi
ą
zanie w nowej bazie
nowy wiersz1 = stary wiersz1 – 1* nowy wiersz3
4
0,25
0
0
0
1
x1
2
x2
3
2
-0,25
-1
1
0
0
s1
0
s3
s2
s1
x2
x1
Baza
b
0
0
0
3
2
cj
B.Gładysz Badania operacyjne
2007
Rozwi
ą
zanie w nowej bazie
nowy wiersz2 = stary wiersz2 – 0,5 * nowy wiersz3
4
0,25
0
0
0
1
x1
2
2
-0,125
0,5
0
1
0
x2
3
2
-0,25
-1
1
0
0
s1
0
s3
s2
s1
x2
x1
Baza
b
0
0
0
3
2
cj
B.Gładysz Badania operacyjne
2007
Wska
ź
niki optymalno
ś
ci
-0,125
-1,5
0
0
0
cj - zj
14
0,125
1,5
0
3
2
zj
4
0,25
0
0
0
1
x1
2
2
-0,125
0,5
0
1
0
x2
3
2
-0,25
-1
1
0
0
s1
0
s3
s2
s1
x2
x1
Baza
b
0
0
0
3
2
cj
B.Gładysz Badania operacyjne
2007
Rozwi
ą
zanie optymalne
• Zmienne niebazowe = 0
s2=0, s3=0.
• Funkcja celu = 14
• Zmienne bazowe = bj.
X1 =4, x2=2, s1=2.
B.Gładysz Badania operacyjne
2007
0 1 2 3 4 5 6 7 8
1
2
3
4
5
6
7
8
X1 –produkt1
X2 - produkt2
S3
S2
(4,2)
Z=14
(0,4)
Z=12
(0,0)
Z=0
(4,0)
Z=8
B.Gładysz, Badania operacyjne 2007
MAX
B.Gładysz Badania operacyjne
2007
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
0
-M
0
0
1
a1
-M
0
0
M
-20+100M
-2+50M
cj-zj
Wska
ź
niki
optymalno
ś
ci
-100M
0
0
M
-100M
-50M
zj
1
1
0
0
0
1
s3
0
200
0
1
0
200
20
s2
0
100
0
0
-1
100
50
a1
-M
s3
s2
s1
x2
x1
Baza
b
0
0
0
-20
-2
cj
Algorytm Simplex
Pierwsze rozwi
ą
zanie bazowe (max)