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.