Strona 2
Badania Operacyjne - WWSI
Pytanie 9
Optymalne rozwiązanie zadania LPM w postaci standardowej dla metody simpleks ma następującą właściwość:
Jeśli istnieją dwa różne rozwiązania optymalne to rozwiązań optymalnych jest nieskończenie wiele
Jeśli istnieje dokładnie jedno rozwiązanie optymalne to jest ono rozwiązaniem wierzchołkowym
Jeśli jest rozwiązaniem wierzchołkowym, to liczba niezerowych zmiennych decyzyjnych jest równa różnicy pomiędzy liczbą zmiennych decyzyjnych a liczbą równań definiujących zbór rozwiązań dopuszczalnych.
Musi być wierzchołkiem zbioru poprawnych danych
Może nie istnieć, jeśli zbiór rozwiązań dopuszczalnych jest nieograniczony
Pytanie 10
W metodzie simpleks w każdym kroku iteracyjnym:
Wartości wszystkich zmiennych zerowych zmienia się na wartości dodatnie
Wyznacza się minimalny element zbioru rozwiązań dopuszczalnych
Bada się czy dotychczasowe rozwiązanie można poprawić
Poszukuje się kolejnego wierzchołka zbioru rozwiązań dopuszczalnych
Oblicza się nowe wartości wszystkich zmiennych decyzyjnych
Pytanie 11
Optymalne rozwiązanie zadania LPM w postaci standardowej dla metody simpleks ma następującą właściwość:
Jeśli jest rozwiązaniem wierzchołkowym, to zawiera tyle zmiennych niezerowych ile jest równań definiujących zbiór rozwiązań dopuszczalnych
Zawsze istnieje optymalne rozwiązanie wierzchołkowe lub nie istnieje żadne rozwiązanie optymalne
Zawiera maksymalne wartości zmiennych decyzyjnych
Zawsze istnie, jeśli zbiór rozwiązań dopuszczalnych jest niepusty
Nie istnieje, jeśli zbiór rozwiązań dopuszczalnych zawiera nieskończenie wiele elementów
Pytanie 12
W metodzie simpleks w każdym kroku iteracyjnym:
Otrzymuję się minimalną wartość funkcji celu
Oblicza się nową wartość jednej ze zmiennych decyzyjnych, która jest równa zeru
Zmniejsza się wartość funkcji celu, o ile jest to możliwe
Pytanie 13
Zadanie wyznaczania maksymalnego przepływu ma następującą właściwość:
Jeśli bieżące rozwiązanie nie jest optymalne to nie można wyznaczyć łańcucha powiększalnego
W łańcuchu powiększanym łuki, których przepływ jest równy przepustowości, muszą być skierowany od odpływu do źródła
Może nie istnieć skończone rozwiązanie optymalne
Zbiór rozwiązań dopuszczalnych może być pusty
Każde rozwiązanie optymalne jest całkowitoliczbowe, o ile przepływ początkowy jest zerowy
Pytanie 14
Zadanie wyznaczania maksymalnego przepływu ma następującą właściwość:
Niemożliwość wyznaczenia łańcucha powiększalnego oznacza, że nie istnieje rozwiązanie optymalne
Jeśli przepustowości są liczbami całkowitymi, to zawsze istnieje optymalne rozwiązanie całkowitoliczbowe
Każdy przepływ może rozłożyć na łańcuchy powiększalne.
Wartość maksymalnego przepływu jest większa od przepustowości minimalnego przekroju rozdzielającego
Macierz ograniczeń zadania optymalnego może nie być całkowicie unimodularna
Pytanie 15
Zagadnienie transportowe ma następującą właściwość:
W przypadku, gdy popyt przekracza podaż, zastosowanie metody potencjałów wymaga wprowadzenia dodatkowego dostawcy
Metoda kąta północno-zachodniego jest jedną z metod wyznaczania rozwiązania początkowego
Może nie istnieć rozwiązanie optymalne zadania optymalizacyjnego
W otwartym zadaniu transportowym ograniczenia wynikające z zapotrzebowań mają postać równań
Liczba zmiennych decyzyjnych jest równa sumie liczb dostawców i odbiorców pomniejszona o jeden
Pytanie 16
Zaznacz poprawne pary: nazwa algorytmu - typ algorytmu:
Algorytm wyznaczania przydziału maksyminowego – algorytm rekurencyjny
Algorytm metody odcięć - algorytm zachłanny
Algorytm simpleks - metoda rozgałęzień i ograniczeń
Algorytm wyznaczania drogi najkrótszej w sieci acyklicznej - algorytm zachłanny
Algorytm dla zadania plecakowego - algorytm programowania dynamicznego