13.06.2011
Wstęp do Badań Operacyjnych w logistyce
1. Dla pewnego klasycznego zbilansowanego zadania transportowego dane jest rozwiązanie dopuszczalne X 0 i tabela wskaźników optymalności dla tego rozwiązania: O1
O2
O3
v1
v2
v3
D1
20
u1
− 1
0
D2
30
15
u2
− 2
D3
10
5
u3
0
D4
20
u4
2
− 3
Wiadomo, że wartość funkcji celu dla rozwiązania X 0 wynosi 235.
(a) Znaleźć nowe rozwiązanie dopuszczalne X 1, dla którego spadek wartości funkcji celu będzie największy z możliwych.
(2p.)
(b) Podać interpretację wskaźników optymalności ∆ ij i na podstawie powyższych danych obliczyć wartość funkcji celu dla rozwiązania X 1.
(3p.)
2. Dana jest macierz kosztów jednostkowych pewnego zadania transportowego: O 1
O 2
O 3
O 4
Podaż
D 1
2
3
3
4
20
D 2
5
2
1
6
30
D 3
3
4
6
2
50
Popyt
30
10
20
40
W każdym z poniższych przypadków zbudować macierz kosztów umożliwiającą rozwiązanie tego zadania (z podanym warunkiem) za pomocą algorytmu transportowego:
(a) całość popytu odbiorcy O 2 ma zrealizować dostawca D 4; (1p.)
(b) trasa (2 , 3) jest zablokowana z powodu osunięcia terenu;
(2p.)
(c) odbiorca O 1 może przyjąc co najwyżej 10 jednostek towaru od dostawcy D 1.
(2p.)
3. Poniższa tabela zawiera czasy trwania (w tygodniach) czynności koniecznych do wykonania pewnego przedsięwzięcia:
Czynność
Czas
Czynność
Czas
A(1 , 2)
9
F (2 , 8)
6
B(1 , 3)
7
G(3 , 4)
3
C(2 , 5)
8
H(4 , 7)
4
D(2 , 6)
5
I(7 , 8)
3
E(2 , 7)
3
J (8 , 9)
3
(a) Zbudować diagram tego przedsięwzięcia w postaci sieci czynności.
(1p.)
(b) Po ilu tygodniach zakończy się to przedsięwzięcie?
(1p.)
(c) Które z czynności C, F , H leżą na ścieżce krytycznej?
(1p.)
(d) Jak należy zmienić czas trwania czynności D, aby znalazła się ona na ścieżce krytycznej? (1p.) (e) Która z czynności niekrytycznych ma największą, a która najmniejszą rezerwę czasową? (1p.)
4. Na płaszczyźnie dane są punkty:
A(2 , 5) ,
B(5 , 5) ,
C(0 , 3) ,
D(2 , 3) ,
E(4 , 3) ,
F (6 , 2)
G(2 , 1) ,
H(6 , 1) ,
I(4 , 0) ,
J (5 , 0) ,
K(7 , 0) .
W grafie pełnym K 11 o wierzchołkach A, B, . . . , K wagami krawędzi są odległości pomiędzy koń-
cami tych krawędzi.
(a) Zbudować (i narysować) minimalne drzewo rozpinające T , z korzeniem A, powyższego grafu K 11.
(1p.)
(b) Napisać listę L wierzchołków drzewa T uporządkowanych w porządku prefiksowym.
(1p.)
(c) Korzystając z listy L znaleźć przybliżone rozwiązanie problemu komiwojażera dla powyższego grafu i oszacować jego wagę. W rachunkach wystarczy posługiwać się przybliżeniami dziesiętnymi długości krawędzi z dokładnością do jednego miejsca po przecinku.
(2p.)
(d) Korzystając z algorytmu lokalnego znaleźć inne przybliżone rozwiązanie tego problemu i po-równać z rozwiązaniem otrzymanym poprzednio.
(1p.)
5. Niech V = {s, a, b, c, d, t} i E ⊂ V × V będzie pewnym zbiorem. Każdej krawędzi należącej do zbioru E przyporządkowano przepustowość i pewien przepływ netto tak, jak to pokazuje tabela: krawędź
przepustowość
przepływ
krawędź
przepustowość
przepływ
( s, a)
9
6
( b, d)
6
6
( s, b)
15
9
( c, b)
4
0
( a, c)
7
7
( c, d)
3
0
( a, d)
5
2
( c, t)
12
7
( b, a)
6
3
( d, t)
8
8
( b, c)
10
0
Pozostałym krawędziom przyporządkowanoe zerowe przepustowości i przepływy netto otrzymując przepływ f w sieci ( V, E, s, t).
(a) Wyznaczyć sieć residualną, a następnie znaleźć w tej sieci ścieżkę powiększającą p zawierającą krawędź ( s, a).
(2p.)
(b) Korzystając ze ścieżki powiększającej p skonstruować nowy przepływ f 0 w sieci ( V, E, s, t) spełniający nierówność |f 0| > |f |.
(1p.)
(c) Dla przepływu f w sieci ( V, E, s, t) znaleźć ścieźkę powiększającą q zawierającą krawędź ( s, b) i wykorzystać ją do skonstruowania nowego przepływu f 00 = f + fq. Wykazać, że przepływ f 00 jest przepływem maksymalnym.
(2p.)
Zgadzam się na zamieszczenie uzyskanej przeze mnie oceny w portalu eduka-cyjnym WIKAMP.
(Podpis)