Przykładowy zestaw na pierwsze kolokwium z Badań Operacyjnych
1. J. Carpenter jest właścicielem sklepu z materiałami budowlanymi. Pewnego dnia, bierze on udział w aukcji uŜywanych
materiałów budowlanych. Interesują go bloczki betonowe oraz deski podłogowe. Po obserwacji pierwszej sprzedaŜy
doszedł do wniosku, Ŝe oferując 0,25 $ za kaŜdy bloczek będzie mógł kupić tyle bloczków ile zechce. Później mógłby je
sprzedać w swoim sklepie po 0,5 $ za jeden. Natomiast oferta 4 $ za kaŜdą deskę (deski później moŜe sprzedać po 5 $
za jedną) zapewni mu zakup ich w takiej ilości jakiej zapragnie. Jednym ograniczeniem kupna wspomnianych
materiałów jest pojemność samochodu dostawczego. Nie moŜe on załadować więcej niŜ 2 tony towaru oraz 60 cubic
feet (cubic feet jest to miara objętości odpowiadająca wymiarom kostki o krawędziach 0,30 cm*0,30cm*0,30cm).
KaŜdy bloczek waŜy 36,32 kg i ma 0,5 cubic foot. KaŜda deska waŜy 18,16 kg i ma 1 cubic foot objętości. Jaką ilość
bloczków i desek powinien nabyć na aukcji Joe Carpenter, aby osiągnął maksymalny zysk ze sprzedaŜy? Zakładamy, Ŝe
Joe moŜe wykonać tylko jeden przejazd swoim samochodem.
a) RozwiąŜ problem stosując metodę graficzną.
b) Określ optymalny zakres dla jednostkowego zysku z bloczków betonowych.
c) Wyznacz cenę dualną związaną z limitem objętości załadunku i jej zakres stosowalności.
Rozwiązanie.
a)
.
60
,
60
,
0
max
2
1
=
=
=
z
x
x
b)
].
5
,
0
;
(
1
−∞
∈
c
c) Cena dualna wynosi 1, a jej zakres stosowalności
].
1322
,
110
;
0
(
2
∈
RHS
2. Racjonalna hodowla drobiu wymaga dostarczenia
kaŜdej sztuce dwóch składników odŜywczych S
1
i S
2
w ilościach nie mniejszych niŜ odpowiednio 1200 i
600 jednostek. Składniki te zawarte są w czterech
paszach: P
1
, P
2
, P
3
, P
4
. W tablicy podano zawartości
tych składników w poszczególnych paszach oraz ceny
zakupu
pasz.
W
jakich
ilościach
zakupić
poszczególne pasze, aby dostarczyć niezbędne składniki odŜywcze przy moŜliwie najniŜszych kosztach zakupu
pasz?
a) Napisz model matematyczny rozpatrywanego problemu.
b Napisz model matematyczny zagadnienia dualnego.
c) RozwiąŜ graficznie zagadnienie dualne.
d) Znając rozwiązanie zagadnienia dualnego znajdź rozwiązanie zagadnienia pierwotnego.
Rozwiązanie.
ZD
1080
,
1200
,
300
max
2
1
=
=
=
z
y
y
ZP
max
min
4
3
2
1
1080
,
0
,
0
,
250
,
750
z
z
x
x
x
x
=
=
=
=
=
=
3. Pewne przedsiębiorstwo produkuje 4 wyroby (W
1
, W
2
, W
3
, W
4
). Kierownictwo tej
firmy zastanawia się nad takim planem produkcji, który by maksymalizował zysk, a limity
trzech surowców nie zostały przekroczone. RozwiąŜ dany model matematyczny za
pomocą algorytmu simpleks (dokończ tabelkę drugiej iteracji i utwórz trzecią − ostatnią),
a następnie uzupełnij tabelkę – wydruk komputerowy.
baza
wartość
bazy
RHS
Ilorazy
s1
0
-3
3
1
-2/3
0
4
x1
1
2
1
0
1/3
0
8
s3
0
-14
-7
1
-2⅓
1
14
Z=120
0
-24
-6
2
-5
0
baza
wartość
bazy
RHS
Ilorazy
Z=
Rozwiązanie.
.
128
,
4
,
0
,
0
,
8
max
4
3
2
1
=
=
=
=
=
z
x
x
x
x
Zawartość składnika w 1 kg paszy
Cena 1 kg
PASZE
S
1
S
2
paszy
P
1
P
2
P
3
P
4
0,8
2,4
0,9
0,4
0,6
0,6
0,3
0,3
960
1440
1080
720
≥
≤
+
≤
+
+
≤
+
+
+
→
+
+
+
0
,
,
,
70
7
24
3
6
3
20
5
2
max
2
9
6
15
4
3
2
1
4
1
3
2
1
4
3
2
1
4
3
2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
