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.