Przykładowy zestaw na drugie kolokwium z Badań Operacyjnych 1. Zaplanuj projekt uruchomienia baru w starych wagonach kolejowych. Lista czynności i ich czas trwania podaje tabela.
Czynności
Czynności
a
poprzedzaj
ij
mij
bij
ące
A
−
5
7
27
B
−
0
3
6
C
−
1
1
1
D
−
0
1
8
E
D
3
6
15
F
E
1
3
5
G
A, F
0
6
6
H
G
1
2
15
I
B, H
2
4
6
J
B, H
2
3
4
K
I, J
3
5
13
L
G
3
3
3
M
C, I
2
3
10
N
K, L
1
8
9
a) Sporządzić siatkę zaleŜności. b) Jaki jest najwcześniejszy moment zakończenia przedsięwzięcia?
c) Jaki jest zapas czasu dla czynności poszczególnych czynności? d) Ile jest ścieŜek krytycznych?
e) Które czynności są niekrytyczne? Wymień je.
Rozwiązanie.
a) Wskazówka. Do poprawnego narysowania sieci naleŜy wprowadzić 2 czynności pozorne.
b) 38. c) Wskazówka. Zapas czasu dla czynności liczymy ze wzoru: z
= T − t − t .
ij
j
i
ij
d) 1. e) A, B, C, J, L, M.
2. 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
3.. Firma A zatrudnia 5 pracowników roznoszących reklamy, firma B zatrudnia 3 takich pracowników. Obydwie firmy zainteresowane są rozprowadzaniem reklam w dzielnicach D1 i D2. Zdefiniuj strategie dla firm i macierz gry, uwzględniając przydział pracowników do pracy w tych dzielnicach. Zasady konkurencji:
– konkurencję w dzielnicy wygrywa firma wysyłająca do pracy więcej pracowników, za to otrzymuje jeden punkt oraz dodatkowo tyle punktów ile pracowników wysłała do pracy w dzielnicy firma przegrywającą konkurencję,
– wartość wygranej jest sumą punktów uzyskanych przez firmę w obydwu dzielnicach łącznie,
– przy takiej samej liczbie pracowników wysłanych do pracy przez firmy w tej samej dzielnicy, wygrana jest równa zero. a) Zapisz macierz wypłat. b) Czy istnieją strategie zdominowane? ……………… b) Czy istnieje rozwiązanie w strategiach czystych? ………. d) Napisz model liniowy prowadzący do rozwiązania.
Rozwiązanie.
a) Wskazówka: Firma A ma 4 strategie, a firma B tylko dwie strategie. Wynika to z faktu, Ŝe firmy muszą wysłać pracowników do dwóch dzielnic.
b) TAK (gracz A ma dwie strategie zdominowane. Wymień które!) c) NIE.
Przykładowy zestaw na drugie kolokwium z Badań Operacyjnych 4. Transport kamienia odbywa się samochodami cięŜarowymi (sześciotonowymi) z kamieniołomów (1 i 2) do zakładów kamieniarskich (7 i 8). Koszt transportu zaleŜy od ilości przejechanych kilometrów. Na poniŜszym rysunku zaznaczone są odległości pomiędzy poszczególnymi punktami. Zasoby kamieniołomów i zapotrzebowanie zakładów kamieniarskich, wyraŜone w liczbie samochodów 6-tonowych, podaje tabela.
6
7
Punkty
PodaŜ/popyt w
7
9
[samochodach]
1
25
2
6
2
15
6
2
4
3, 4, 5, 6 0
5
8
7
−20
6
7
8
1
8
−20
3
7
9
3
4
a) Napisz model matematyczny do tego problemu.
b) Problem powyŜszy rozwiązano. Zinterpretuj − językiem przystępnym dla osób z działu transportu nie znających badań operacyjnych − wyróŜnione liczby z fragmentu wydruku rozwiązania (pogrubiona czcionka).
Zmienne
Jednostkowy
Całkowity
Koszt
Zakres
Zakres
Rozwiązanie
decyzyjne
koszt/zysk
wkład
alternatywny
Baza
Min.c(j)
Max. c(j)
…
…
…
…
…
…
…
…
…
2
X13
25
6
150
0
Bazowa
4
9
3
X14
0
9
0
3
niebazowa
6
+ ∞
…
…
…
…
…
…
…
…
…
Reszta lub
Ceny
Ograniczenia
LSO
Kierunek
PSO
Min. PSO
Min. PSO
nadmiar
dualne
1
C1
25
≤
25
0
0
25
+ ∞
…
…
…
…
…
…
…
…
…
8
C8
20
≥
20
0
15
0
20
Interpretacja
3
(6, + ∞ )
25
15
(0, 20)
5. Gazeciarz zaopatruje się w gazety płacąc 80 groszy za kaŜdą sztukę. Gazety są sprzedawane po 1 zł, co daje gazeciarzowi 20 groszy zysku na kaŜdej sprzedanej sztuce. Z doświadczenia gazeciarz wie, Ŝe dzienny popyt na gazety moŜe wynosić 50 szt., 70 szt., 90 szt. lub 120 szt. Odpowiednio z prawdopodobieństwem 0,3, 0,2, 0,4 oraz 0,1.
Gazeciarz kupuje gazety w paczkach po 60, 80 lub 100 sztuk. Problem gazeciarza polega na podjęciu takiej decyzji odnośnie do ilości kupowanych gazet, która przyniesie mu największy zysk. Narysuj drzewo decyzyjne i oblicz efekty finansowe. Jaką decyzje powinien podjąć gazeciarz? (ZałoŜenie: gazeciarz nie moŜe zwrócić niesprzedanych gazet).
Rozwiązanie.
Gazeciarz powinien kupować paczki po 60 sztuk, przyniesie mu to zysk 9 zł.