AISDE Egzamin Komandosa

Wyznaczanie maksymalnego przepływu wymaga iteracyjnego znajdowania ścieżki wzbogacającej:
a) najkrótszej, algorytmem Dijkstry
b) najkrótszej, algorytmem poprawiania etykiet
c) dowolnej, algorytmem Dijkstry
d) dowolnej, algorytmem poprawiania etykiet

W grafie o m wierzchołkach i n krawędziach stosunek liczby ograniczeń dotyczących przepustowości w
sformułowaniach problemu przepływu d towarów i 1 towaru wynosi:
a) 1
b) d
c) m
d) n

Dane są 4 krawędzie grafu i ich przepustowości: AB=1, BC=2, CD=1, DA=2 oraz zapotrzebowania
AC=3, BD=2. Przepływ wielotowarowy jest:
a) realizowany, bo 6>5
b) nierealizowany, bo 6<10
c) realizowany, bo 6<=10
d) nierealizowany, bo 6>=5

W algorytmie minimalizacji metodą sympleksu zawsze generowany jest kolejny wierzchołek zbioru
rozwiązań dopuszczalnych:
a) różniący się jedną zmienną bazową i poprawiający wartość funkcji kosztu
b) zachowujący jedną zmienną bazową i poprawiający wartość funkcji kosztu
c) różniący się jedną zmienną bazową i najbardziej poprawiający wartość funkcji kosztu
d) zachowujący jedną zmienną bazową i najbardziej poprawiający wartość funkcji kosztu

W algorytmie minimalizacji metodą sympleksu faza analizy kolumny tablicy sympleksowej może
prowadzić do stwierdzenia:
a) że problem jest nieograniczony
b) że zostało znalezione optimum
c) która zmienna powinna wejść do bazy
d) że problem jest sprzeczny