ImiÄ™ i nazwisko 13.06.2011
Wstęp do Badań Operacyjnych w logistyce
1. Dla pewnego klasycznego zbilansowanego zadania transportowego dane jest rozwiÄ…zanie dopusz-
czalne X0 i tabela wskaz
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 X0 wynosi 235.
(a) Znalez
ć nowe rozwiązanie dopuszczalne X1, dla którego spadek wartości funkcji celu będzie
największy z możliwych. (2p.)
(b) Podać interpretację wskaz
ników optymalności "ij i na podstawie powyższych danych obliczyć
wartość funkcji celu dla rozwiązania X1. (3p.)
2. Dana jest macierz kosztów jednostkowych pewnego zadania transportowego:
O1 O2 O3 O4 Podaż
D1 2 3 3 4 20
D2 5 2 1 6 30
D3 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 O2 ma zrealizować dostawca D4; (1p.)
(b) trasa (2, 3) jest zablokowana z powodu osunięcia terenu; (2p.)
(c) odbiorca O1 może przyjąc co najwyżej 10 jednostek towaru od dostawcy D1. (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łaszczyz
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 K11 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
K11. (1p.)
(b) Napisać listę L wierzchołków drzewa T uporządkowanych w porządku prefiksowym. (1p.)
(c) KorzystajÄ…c z listy L znalez
ć 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 znalez
ć 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ędz
przepustowość przepływ krawędz
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 znalez
ć w tej sieci ścieżkę powiększającą p zawierającą
krawędz
(s, a). (2p.)
(b) Korzystając ze ścieżki powiększającej p skonstruować nowy przepływ f w sieci (V, E, s, t)
spełniający nierówność |f | > |f|. (1p.)
(c) Dla przepływu f w sieci (V, E, s, t) znalez
ć ściez
kę powiększającą q zawierającą krawędz
(s, b)
i wykorzystać ją do skonstruowania nowego przepływu f = f + fq. Wykazać, że przepływ f jest
przepływem maksymalnym. (2p.)
Zgadzam siÄ™ na zamieszczenie uzyskanej przeze mnie oceny w portalu eduka-
cyjnym WIKAMP.
(Podpis)