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) x = ,
0 x = 6 ,
0 z
= 60.
b) c ∈ (
;
−∞
]
5
,
0
.
1
2
max
1
c) Cena dualna wynosi 1, a jej zakres stosowalności RHS ∈ ( ; 0 110 1
, 32 ]
2 .
2
2. Racjonalna hodowla drobiu wymaga dostarczenia Zawartość składnika w 1 kg paszy
Cena 1 kg
każdej sztuce dwóch składników odżywczych S1 i S2
w ilo
PASZE
S
ściach nie mniejszych niż odpowiednio 1200 i 1
S2
paszy
600 jednostek. Składniki te zawarte są w czterech P1
0,8
0,6
960
paszach: P
P2
2,4
0,6
1440
1, P2, P3, P4. W tablicy podano zawartości tych składników w poszczególnych paszach oraz ceny P3
0,9
0,3
1080
zakupu
pasz.
W
jakich
ilościach
zakupić
P4
0,4
0,3
720
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
y = 30 ,
0 y = 120 ,
0 z
= 1080
1
2
max
ZP
x = 75 ,
0 x = 25 ,
0 x = ,
0 x = ,
0 z
= 1080 = z
1
2
3
4
min
max
3. Pewne przedsiębiorstwo produkuje 4 wyroby (W1, W2, W3, W4). Kierownictwo tej 15 x x
x
x
1 + 6 2 + 9 3 + 2 4 → max
firmy zastanawia się nad takim planem produkcji, który by maksymalizował zysk, a limity 2 x x x
x
1 +
2 + 5 3 +
4 ≤ 20
trzech surowców nie zostały przekroczone. Rozwiąż dany model matematyczny za 3 x
x
x
1 + 6 2 + 3 3 ≤
24
pomoc
ą algorytmu simpleks (dokończ tabelkę drugiej iteracji i utwórz trzecią − ostatnią),
a nast
7 x
x
1
+
4 ≤
ępnie uzupełnij tabelkę – wydruk komputerowy.
70
x , x , x , x 1
2
3
4 ≥ 0
wartość
baza
RHS
Ilorazy
bazy
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
wartość
baza
RHS
Ilorazy
bazy
Z=
Rozwiązanie. x = ,
8 x = ,
0 x = ,
0 x = ,
4 z
= 128.
1
2
3
4
max
Przykładowy zestaw na pierwsze kolokwium z Badań Operacyjnych 4. Znając rozwiązanie problemu z zadania nr 3 uzupełnij poniższą tabelkę i odpowiedz na pytania.
Decision
Solution
Unit Cost or
Total
Reduced
Basis
Allowable Allowable
Variable
Value
Profit c(j)
Contribution
Cost
Status
Min. c(j)
Max. c(j)
1
X1
0
6
M
2
X2
-18
-M
24
3
X3
-12
-M
21
4
X4
0
0
7,5
Objective
Function
(Max.)
Left Hand
Right Hand
Slack or
Shadow
Allowable Allowable
Constraint
Side
Direction
Side
Surplus
Price
Min. RHS Min. RHS
1
C1
≤
2
16
30
2
C2
≤
3,6667
0
30
3
C3
≤
0
60
+M
Pytanie
Odpowiedź
a) Które z wyrobów nie są produkowane? Jeśli tak, to co należałoby zrobić aby znalazły się w optymalnym planie produkcji?
b) W jakich ilościach wykorzystane są surowce, przy optymalnym planie produkcji?
c) O ile należy zwiększyć zasób surowca nr 1 aby zysk wyniósł 140 ?
d) Ile wynosi minimalna ilość surowca nr 3 potrzebna do wyznaczonego planu produkcji?
e) Podaj optymalne zakresy w jakich mogą zmieniać się wielkości surowców aby zysk firmy zmieniał się zgodnie z wyznaczonymi cenami dualnymi.
Rozwiązanie.
a) Wskazówka: patrz kolumna „Reduced Cost”.
b) Odpowiednio 20, 24 i 60.
c) o 6.
d) 60
e) Wskazówka: patrz kolumny „Allowable Min i Max RHS”.
5.* Papiernia ma dostarczyć co najmniej 1000 rolek papieru 1,5 calowego, 2000 rolek 2,5 calowego i 4000 3,5
calowego. Ma do dyspozycji bele 10 calowe. Zbuduj model matematyczny problemu realizacji zamówienia przy a) kryterium minimalizacji zużytych belek,
b) kryterium minimalizacji odpadu.
Wskazówka do rozwiązania.
Jest 10 sposobów wykroju rolek papieru 1,5, 2,5 i 3,5 calowych z bel 10 calowych.
10
a) z = ∑ x
i → min
i 1
=
b) z = x +
5
,
0 x +
5
,
0 x + x + x +
5
,
0 x
→ min
1
3
4
5
7
10
* Jeśli na laboratoriach zdążymy przerobić zagadnienie całkowitoliczbowe, to kolokwium obejmie również to zagadnienie i wtedy należy spodziewać się zadań tego typu.