BADANIA OPERACYJNE KOL II

1. Czym zajmuje się teoria masowej obsługi (TMO)?

TMO zajmuje się problemami związanymi z masową obsługą klientów. Centralnym problemem jest wyznaczenie optymalnych decyzji dotyczących liczby aparatów obsługi, intensywności obsługi, czasu obsługi itp.

2. Podaj cele masowej obsługi z punktu widzenia klienta i zarządzającego systemem.

- dla klienta: minimalizacja czasu oczekiwania na obsługę (np. stojącego w kolejce)
- dla przedsiębiorcy: minimalizacja kosztów obsługi klienta, określenie optymalnej liczby stanowisk obsługi (ich zbyt duża liczba może doprowadzić do niedociążenia punktu obsługi i strat finansowych).

3. Co to jest stopa zgłoszeń i stopa obsługi w systemach masowej obsługi?

- stopa zgłoszeń: $\lambda = \ \frac{\text{liczba}\ \text{zg}l\text{osze}n}{\text{jednostka}\ \text{czasu}}$

- stopa obsługi: $u = \ \frac{\text{liczba}\ \text{obs}l\text{ug}}{\text{jednostka}\ \text{czasu}}$

4. Co to jest intensywność zgłoszeń i obsługi w TMO?

- intensywność zgłoszeń – odstęp czasu między kolejnymi zgłoszeniami (średnio: $\frac{1}{\lambda}$ )
- intensywność obsługi – czas obsługi zgłaszania przez jeden z s równoległych ? obsługi (średnio: $\frac{1}{u}$ )

5. Co to jest intensywność ruchu w systemach masowej obsługi?

Stosunek średniej liczby zgłoszeń napływających do systemu w jednostce czasu do średniej liczby obsług jaka może być wykonana w jednostce czasu.
Intensywność ruchu w systemach masowej obsługi określa stabilność systemu.

$\rho = \ \frac{\lambda}{s u}$

gdzie:
λ – stopa zgłoszeń
µ - stopa obsług
s – liczba stanowisk

6. Kiedy system masowej obsługi jest stabilny?

gdy ρ < 1

7. Kiedy system masowej obsługi nie jest stabilny?

gdy ρ ≥ 1

8. Co to jest stabilność systemu masowej obsługi (SMO)?

Zjawisko niepowstawania nieskończenie długiej kolejki – w systemie niestabilnym kolejka rośnie szybciej niż następuje obsługa (aż do ∞)

9. W jaki sposób można poprawić stabilność systemu?

• zwiększając liczbę stanowisk obsługi

• zwiększając szybkość obsługi

• zmniejszając liczbę klientów

10. Wymień co najmniej dwa znane Ci regulaminy kolejki:

• algorytm FIFO (‘first in first out’)

• algorytm LIFO (‘last in first out’)

11. Podaj przykład systemu M/M/1/∞

stoisko na bazarze z jednym sprzedawcą

12. Podaj przykład systemu M/M/1/4

sklep z jedną ekspedientką, mieszczący cztery osoby

13. Podaj przykład systemu M/M/2/∞

stoisko na bazarze z dwójką sprzedawców

14. Podaj przykład systemu M/M/3/5

warsztat samochodowy z trzema stanowiskami i parkingami na pięć samochodów

15. Wymień co najmniej 3 parametry charakteryzujące SMO:

• średnia liczba oczekujących w kolejce

• prawdopodobieństwo braku kolejki

• średnia liczba obiektów w systemie

• zgłoszenia w jednostce czasu

• obsługa w jednostce czasu

• prawdopodobieństwo oczekiwania w kolejce dłużej niż T

• prawdopodobieństwo wystąpienia kolejki

16. Na czym polega regulamin kolejki FIFO?

Polega na obsłudze zadań w kolejności pojawienia się zgłoszeń.

17. Na czym polega regulamin kolejki FIFO?

Polega na obsłudze zadań w kolejności odwrotnej do kolejności pojawienia się zgłoszeń.

18. Co to jest klasyfikacja Kendalla?

X/Y/s/n

Klasyfikacja systemów masowej obsługi zawierająca informacje:
- X – proces przebyć lub rozkład odstępów czasu pomiędzy zgłoszeniami
- Y – rozkład czasów obsługi lub proces obsługi
- s – liczba równoległych kosztów obsługi
- n – ograniczenie gługości kolejki w poczekalni

19. Podaj znaczenie terminu ‘oczekiwanie’ w SMO.

Czas od momentu zgłoszenia, do chwili rozpoczęcia obsługi.

20. Podaj znaczenie terminu ‘przebywanie’ w SMO.

Czas od momentu zgłoszenia, do momentu opuszczenia systemu.

21. Scharakteryzuj parametr oceniający strumień zgłoszeń w SMO

λ – liczba zgłoszeń w jednostce czasu

22. Scharakteryzuj parametr oceniający proces obsługi w SMO.

µ - liczba klientów obsługiwanych w jednostce czasu

23. Co to jest wielokrotny SMO?

To SMO posiadający więcej niż jedno stanowisko obsługi.

24. Podaj wzór na intensywność ruchu w SMO.

$\rho = \ \frac{\lambda}{s u}$

25. Podać klasyfikację systemów masowej obsługi pod względem organizacji obsługi.

• Szeregowe

• Równoległe

• Mieszane

26. Podać klasyfikację systemów masowej obsługi pod względem organizacji kolejki

• FIFO

• LIFO

• SIRO

27. Co to jest graf?

Grafem nazywamy trójkę uporządkowaną G =<W,U,Q>,

gdzie:
W – zbiór wierzchołków grafu
U – zbiór gałęzi
Q – relacja trójczłonowa Q c WxUxW

28. Co to jest sieć?

Siecią nazywamy trójkę uporządkowaną S = <G, {ξ_i}, {Ψ_i} >

gdzie:

G <W,U,Q> - dowolny graf,
{ξ_i} – zbiór funkcji ξ_i : W->R określanych na zbiorze wierzchołków grafu
{Ψ_i} – zbiór funkcji Ψ_i : U->R określanych na zbiorze gałęzi grafu

29. Czym różni się sieć od grafu?

Sieć jest pojęciem szerszym.
Stanowi ją graf i funkcje określane na zbiorze wierzchołków i na zbiorze krawędzi grafu.

30. Kiedy sieć staje się grafem?

Gdy oba zbiory funkcji (określane na zbiorze wierzchołków i na zbiorze krawędzi grafu) będą puste.

31. Wymień rodzaje gałęzi w grafie.

• krawędzie – linie łączące odpowiednie wierzchołki

• łuki – strzałki łączące odpowiednie wierzchołki

• pętle – linie zamknięte wychodzące i wchodzące do tego samego wierzchołka

32. Co to jest łuk w grafie?

Strzałka łącząca odpowiednie wierzchołki.

33. Co to jest pętla w grafie?

Linia zamknięta wychodząca i wchodząca do tego samego wierzchołka.

34. Co to jest krawędź w grafie?

Linie łączące odpowiednie wierzchołki.

35. Kiedy dwa wierzchołki są przyległe?

Gdy istnieje przynajmniej jedna gałąź incydentna jednocześnie z obu tymi wierzchołkami.

36. Kiedy dwie gałęzie są przyległe?

Gdy istnieje przynajmniej jeden wierzchołek incydentny jednocześnie z obu tymi gałęziami.

37. Co to znaczy, że wierzchołek i gałąź są incydentne?

To znaczy, że istnieje wierzchołek yєW taki, że <x,u,y> є Q lub <y,u,x> є Q,

gdzie:
W – wierzchołek
uєU – gałąź

38. Co to jest macierz przyległości wierzchołków grafu?

Macierz symetryczna, której elementy określają liczbę gałęzi łączących odpowiednie pary wierzchołków grafu.
R = [r_ij] (i,j = 1,2,…,n)

39. Co to jest macierz przejść grafu?

Macierz, której elementy określają liczbę łuków łączących wierzchołek i z j
P[p_ij] (i,j = 1,2,…,n)

40. O czym informuje binarna macierz przejść grafu?

O możliwości lub braku możliwości przejścia między wierzchołkami.

41. O czym informuje binarna macierz przyległości grafu?

O przyległości lub braku przyległości dwóch wierzchołków grafu (jest symetryczna).

42. Co to jest stopień wierzchołka grafu?

Jest to suma liczb: krawędzi, łuków wchodzących i wychodzących oraz pętli (wszystkich gałęzi indywidualnych)

s(x) = s ~ (x) + s ⁺ (x) + s ^- (x) + s ^o (x)

43. Co to jest rozwidlenie wierzchołka grafu?

Jest to suma liczb: krawędzi, łuków wchodzących i wychodzących oraz liczonych razy dwa pętli.

r(x) = s ~ (x) + s ⁺ (x) + s ^- (x) + 2s ^o (x)

44. Czym różni się rozwidlenie wierzchołka od jego stopnia?

Rozwidlenie wierzchołka to jego stopień powiększony o liczbę pętli.

r(x) = s(x) + s ^o (x)

45. Dla których wierzchołków stopień i rozwidlenie wierzchołków są równe?

Dla tych, na których nie ma pętli.

46. Dla których wierzchołków stopień i rozwidlenie wierzchołków są różne?

Dla tych, do których wchodzą/wychodzą pętle.

47. Co to jest graf skierowany?

Graf, który posiada tylko łuki i pętle.

48. Jakich gałęzi nie posiada graf skierowany?

Krawędzi.

49. Co to jest graf niezorientowany?

Graf, który posiada tylko krawędzie i pętle.

50. Jakich gałęzi nie posiada grał niezorientowany?

Łuków.

51. Co to jest graf pusty?

Graf, który nie posiada żadnych gałęzi.

52. Jakich gałęzi nie posiada graf pusty?

Krawędzi, łuków i pętli (żadnych gałęzi).

53. Jaka jest krotność unigrafu?

Krotność unigrafu wynosi 1.

54. Jaka jest krotność multigrafu?

Krotność multigrafu wynosi więcej niż 1.

55. Co to jest graf zwykły?

Jest to unigraf niezorientowany bez pętli (tylko po jednej krawędzi dla każdej pary przy różnych wierzchołkach) <1,0,0>

56. Co to jest graf Berge’a?

Jest to digraf(graf skierowany) i unigraf <0,1,1>

57. Co to jest podgraf?

Wybrana część wierzchołków grafu i wszystkie gałęzie incydentne z nimi.

58. Co to jest graf częściowy?

Wszystkie wierzchołki grafu i wybrana część gałęzi incydentnych z nimi.

59. Co to jest graf pusty?

Każdy taki podgraf, który jest grafem pustym.

60. Co to jest maksymalny podgraf pusty?

Taki podgraf pusty grafu, że zbiór jego wierzchołków nie jest podzbiorem właściwym żadnego innego zbioru wierzchołków tworzących podgraf pusty.

61. Wymień etapy metody wyznaczania optymalnego kolorowania wierzchołków grafu.

1. Obliczenie wszystkich maksymalnych zbiorów niezależnych.

2. Obliczenie minimalnych pokryć zbioru (reprezentuje minimalną liczbę kolorów do wykorzystania).

3. Wyeliminowanie elementów powtarzających się.

62. Zdefiniuj problem pokrycia minimalnych zbioru.

Mając pewien skończony zbiór W i ustalony zbiór podzbiorów W_k tego zbioru (k=1,2,…,K) spełniających warunek U_k = 1^kW_k = W, należy wybrać największą liczbę tych podzbiorów w ten sposób, aby w sumie tworzyły one cały zbiór W.

63. Wymień metody suboptymalnego kolorowania wierzchołków grafu.

• metoda redukcji grafu

• metoda macierzy podobieństw

64. Zdefiniuj problem kolorowania wierzchołków grafu.

W jaki sposób należy przyporządkować kolory poszczególnym wierzchołkom grafu, aby zużyć jak najmniejszą liczbę barw i aby żadne dwa przyległe wierzchołki nie miały tego samego koloru.

65. Podaj przykład zastosowania metody kolorowania wierzchołków grafu.

• przykład mapy politycznej – kolorowanie tak, by użyć jak najmniej kolorów i aby żadne sąsiadujące państwa nie miały tego samego koloru.

• przykład składowania materiałów chemicznych – nie przechowywanie w jednym pomieszczeniu materiałów reagujących silnie ze sobą – zaprojektowanie magazynu o minimalnej ale wystarczającej liczbie pomieszczeń.

66. Co to jest marszruta w grafie?

Dowolny ciąg przemienny wierzchołków i gałęzi.

67. Co to jest łańcuch w grafie?

Ł (x^P, x^K) – marszruta łącząca wierzchołek początkowy x^P z wierzchołkiem końcowym x^K, w której wszystkie gałęzie są różne.

68. Podaj definicję drogi w grafie.

Droga µ - łańcuch skierowany, tzn. marszruta skierowana o różnych gałęziach.

69. Podaj definicję drogi prostej w grafie.

Łańcuch skierowany o różnych wierzchołkach.

70. Podaj definicję drogi cyklicznej prostej w grafie.

Łańcuch skierowany dla którego tylko wierzchołek początkowy x^P jest jednocześnie wierzchołkiem końcowym x^K, a poza tym wszystkie wierzchołki i gałęzie są różne.

71. Podaj definicję łańcucha prostego w grafie.

Łańcuch o różnych wierzchołkach.

72. Podaj definicję łańcucha cyklicznego prostego w grafie.

Każdy taki łańcuch, w którym jedynie x^P = x^K a poza tym wszystkie wierzchołki i gałęzie są różne.

73. Jaką marszrutą jest droga cykliczna?

Jest marszrutą skierowaną i cykliczną.

74. Jakim łańcuchem jest droga prosta?

Jest łańcuchem prostym.

75. Co to jest łańcuch najkrótszy?

t_min (x^P, x^K) – łańcuch zamieniający największą liczbę gałęzi spośród wszystkich łańcuchów łączących x^P z x^k.

76. Podaj zastosowanie algorytmu znajdowania łańcucha najkrótszego.

Znalezienie drogi najkrótszej dla kierowcy od punktu A do B by zużyć jak najmniej paliwa.

77. Kiedy graf jest spójny?

Kiedy jego dwa dowolne wierzchołki można połączyć marszrutą.

78. Co to jest składowa spójności grafu?

Każdy maksymalny podgraf będący grafem spójnym.

79. Co to jest składowa silnej spójności grafu?

Każdy maksymalny podgraf będący grafem silnie spójnym, czyli takim, gdzie dla dwóch każdych wierzchołków istnieje droga.

80. Co oznacza, że graf posiada trzy składowe spójności?

Oznacza to, że graf posiada 3 podgrafy będące grafami spójnymi.

81. Co to jest łańcuch Eulera?

Łańcuch posiadający wszystkie gałęzie grafu.

82. Co to jest droga Hamiltona?

Droga zawierająca wszystkie wierzchołki grafu.

83. Jaka jest różnica między drogą Eulera a drogą Hamiltona?

W drodze Eulera trzeba przejść przez wszystkie gałęzie, w drodze Hamiltona przez wszystkie wierzchołki.

84. Podaj warunki istnienia łańcucha Eulera.

• digraf zawierający łańcuch Eulera jest spójny (z wyjątkiem wierzchołków gołych).

• liczba wierzchołków o nieparzystych rozwidleniach w tym grafie jest równa 0 lub 2.

85. Podaj warunki istnienia drogi Eulera.

- digraf zawierający drogę Eulera posiada dwa takie wierzchołki x_o i y_o, że

s ⁺ (x_o) – s ^- (x_o) = 1 i s ⁺ (y_o) – s ^- (y_o) = -1

Do jednego wierzchołka wchodzi o jeden więcej łuków niż wychodzi, do drugiego o 1 więcej wychodzi niż wchodzi.

Jeśli dla każdego wierzchołka x grafu spełniona jest również s⁺ (x) = s ^- (x) to w digrafie istnieje droga cykliczna Eulera.

86. Kiedy w grafie istnieje cykliczny łańcuch Eulera?

• digraf jest spójny (z wyjątkiem wierzchołków gołych

• liczba wierzchołków o nieparzystych rozwiązaniach = 0

87. Kiedy w grafie istnieje cykliczna droga Eulera?

Jeżeli dla każdego wierzchołka x grafu spełniona jest równość s⁺ (x) = s ^- (x) <- tyle samo łuków wchodzi co wychodzi.

88. Zdefiniuj problem komiwojażera.

Zagadnienie polegające na znalezieniu minimalnego cyklu Hamiltona w grafie. Ilustracją jest wędrowny sprzedawca, który ma odwiedzić n miast, który musi znaleźć najkrótszą/najtańszą/najszybszą drogę łączącą wszystkie miasta.

89. Kiedy graf skierowany jest cykliczny w sensie dróg?

Kiedy zawiera drogi cykliczne.

90. Kiedy graf skierowany jest acykliczny w sensie dróg?

Kiedy nie zawiera dróg cyklicznych.

91. Jakie warunki spełniają wierzchołki warstwy grafu?

• do W_o (warstwy zewnętrznej) należą takie wierzchołki x digrafu, dla których zbiór poprzedników jest pusty.

• każdy wierzchołek należący do warstwy W_k(k>0) ma poprzedniki tylko w warstwach od 0 do k-1.

• każdy wierzchołek, który ma poprzedniki i jest w k-tej warstwie, musi mieć przynajmniej jeden ze swoich poprzedników w warstwie bezpośrednio poprzedzającej.

92. Dla jakich grafów można wyznaczyć jego warstwy?

Dla grafów skierowanych (digrafów).

93. Jaki podgraf tworzą wierzchołki warstwy grafu?

Maksymalny podgraf pusty.

94. Do czego służy algorytm Leifmana?

Służy do wyznaczania wszystkich składowych silnej spójności.

95. Co to jest karkas grafu?

Dowolny graf częściowy spełniający dowolne dwa z podanych warunków:

m(T) = m(G) – λ(G)
ӕ(T) = ӕ(G)
λ(T) = 0

m-liczba gałęzi grafu
ӕ- liczba składowych spójności
λ – liczba cyklomatyczna

96. Co to jest najtańszy karkas grafu?

Taki karkas T= <W,U’,Q’> grafu G, aby suma Σ k(u) dla u є U’ miała wartość minimalną.

97. Podaj przykład zastosowania algorytmu wyznaczania drzewa ekonomicznego?

Połączenie odbiorców z jednym magazynem za pośrednictwem najtańszych/najkrótszych/najszybszych dróg.

98. Wymień znane Ci algorytmy wyznaczania najtańszego karkasu grafu.

• algorytm Prim’a – tworzenie kolejnych podgrafów częściowych poprzez dodawanie wierzchołków mających najtańsze połączenie już z wybranymi.

• algorytm Kruskal’a – tworzenie kolejnych grafów częściowych poprzez dodawanie najtańszych gałęzi.

99. Co to jest długość drogi łączącej wybrane wierzchołki w grafie?

Suma funkcji na poszczególnych gałęziach tworzących drogę między wierzchołkami.

100. Co to jest maksymalny dendryt dróg najkrótszych w grafie?

Spójny digraf, unigraf zawierający wszystkie wierzchołki grafu początkowego bez pętli mający dokładnie jeden wierzchołek początkowy (bez poprzedników) i pozostałe wierzchołki mające dokładnie po jednym poprzedniku z minimalnym funkcjami na gałęziach.

101. Co to jest maksymalny dendryt dróg najdłuższych w grafie?

Spójny digraf, unigraf zawierający wszystkie wierzchołki grafu początkowego bez pętli mający dokładnie jeden wierzchołek początkowy (bez poprzedników) i pozostałe wierzchołki mające dokładnie po jednym poprzedniku z maksymalnymi funkcjami na gałęziach.

102. Co decyduje o wyborze algorytmu wyznaczania dróg ekstremalnych w sieciach?

Czy sieć jest cykliczna czy acykliczna.

103. Wymień etapy algorytmu wyznaczania dróg ekstremalnych w sieciach acyklicznych?

1. stwierdzenie acykliczności sieci.

2. przedstawienie digrafu w postaci warstwowej

3. metodą programowania dynamicznego wyznaczenie wartości zmiennych decyzyjnych optymalizujących długość dróg.

4. zgodnie z zasadą Bellmana wyznaczenie dróg ekstremalnych

104. W jakich sieciach możemy stosować metodę dekompozycji przy wyznaczaniu dróg ekstremalnych?

W sieciach cyklicznych.

105. Jakim grafem powinna być opisana sieć czynnościowa w metodzie CPM/PERT?

• Ma mieć x^P x^k,

• grafem skierowanym acyklicznym w sensie dróg,

• unigrafem

106. Co reprezentuje łuk w metodzie CPM/PERT?

Kierunek przebiegu czynności.

107. Czy w metodzie CPM/PERT sieć czynnościowa może być cykliczna?

NIE

108. Czym jest ścieżka krytyczna w metodzie CPM/PERT?

µ_max (x^P, x^k) – jest najdłuższą sekwencją czynności niezbędnych do wykonania procesu technologicznego – czynności leżące na ścieżce (czynności krytyczne) ograniczają od dołu czas realizacji całego przedsięwzięcia, a luzy czasowe dla zdarzeń leżących na ścieżce krytycznej są równe 0.

109. Jak wyznaczamy najwcześniejszy możliwy czas realizacji przedsięwzięcia w metodzie CPM/PERT?

Wg wzoru T = F [µ_max (x^P, x^K)]

110. Co to jest luz czasowy w sieci czynnościowej?

Jest to zapas czasu dla poszczególnych zdarzeń.

111. Ile wynosi luz czasowy w ścieżce krytycznej w metodzie CPM?

Zero

112. Jakie zapasy czasu wyznacza się w metodzie analizy czynnościowej?

• zapas całkowity ZC(x,y) = T(y) – t(x) – τ(x,y)

• zapas swobodny ZS(x,y) = t(y) – t(x) – τ(x,y)

• zapas niezależny ZN(x,y) = max{ 0, t(y) – T(x) – τ(x,y)}

113. Co to jest przepływ w sieci?

Przepływem w sieci S nazywamy dowolną funkcję f: U->R spełniającą następujące warunki:

• dla każdej gałęzi przepływ ≥ 0, ale nie większy od przepustowości

• dla pośrednich wierzchołków różnica sumy przepływu towaru wypływającego z wierzchołka i sumy przepływu towaru wpływającego do wierzchołka musi być równa zero.

114. Co to jest przepływ zaspokajający w sieci?

Przepływ zaspakajający zapotrzebowanie odbiorców.

115. Co to jest przepływ zaspokajający o minimalnym koszcie w sieci?

To przepływ zaspokajający w sieci z minimalną funkcją ν(F).

116. Co to jest wartość przepływu w sieci?

$$v\left( f \right) = \ \sum_{y \in \Gamma s}^{}{f\left( s,y \right) - \ \sum_{z \in \Gamma s^{- 1}}^{}{f(z,s)}}$$

117. Czemu jest równa wartość przepływu maksymalnego w sieci?

Wartość maksymalnego przepływu v(f*) jest równa przepustowości minimalnego przekroju rozdzielającego H(P*).

118. Podaj warunki definiujące przepływ w sieci.

1. $\bigwedge_{< x,y > \ \in \ U}^{}{\lbrack\ 0\ \leq f\left( x,y \right) \leq h\left( x,y \right)\rbrack}$

2. $\bigwedge_{x \in W}^{}{\lbrack\sum_{y \in \Gamma x}^{}{f\left( x,y \right) - \ \sum_{z \in \Gamma x^{- 1}}^{}{f\left( z,x \right) = a\left( x \right)v(f)\rbrack}}}$

gdzie
Γx – zbiór następników wierzchołka
Γx^-1 – zbiór poprzedników wierzchołka

119. Co to jest ścieżka powiększalna w algorytmie wyznaczania przepływu maksymalnego w sieci?

Jest to ścieżka łącząca źródło odpływem, po której będziemy mogli zwiększyć przepływ towaru.

120. Kiedy przepływ maksymalny w sieci jest przepływem zaspokajającym?

Przepływ maksymalny w poszerzonej sieci jest przepływem zaspokajającym, gdy każdy odbiorca dostanie tyle, ile chce, czyli gdy łuki łączące odbiorców ze sztucznym odpływem będą nasycone.