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

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

Variable

Solution

Value

Unit Cost or

Profit c(j)

Total

Contribution

Reduced

Cost

Basis

Status

Allowable

Min. c(j)

Allowable

Max. c(j)

1
2
3
4

X1
X2
X3
X4

0

-18
-12

0

6

-M
-M

0

M

24
21

7,5

Objective

Function

(Max.)

Constraint

Left Hand

Side

Direction

Right Hand

Side

Slack or

Surplus

Shadow

Price

Allowable
Min. RHS

Allowable
Min. RHS

1
2
3

C1
C2
C3

≤

≤

≤

2

3,6667

0

16

0

60

30
30

+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.

a)

min

10

1

→

=

∑

=

i

i

x

z

b)

min

5

,

0

5

,

0

5

,

0

10

7

5

4

3

1

→

+

+

+

+

+

=

x

x

x

x

x

x

z

*

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.