Badania Operacyjne - WWSI

Jeśli istnieją dwa różne rozwiązania optymalne to rozwiązań optymalnych jest nieskończenie wiele

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.

Może nie istnieć, jeśli zbiór rozwiązań dopuszczalnych jest nieograniczony

Musi być wierzchołkiem zbioru poprawnych danych

Jeśli istnieje dokładnie jedno rozwiązanie optymalne to jest ono rozwiązaniem wierzchołkowym

Wyznacza się minimalny element zbioru rozwiązań dopuszczalnych

Wartości wszystkich zmiennych zerowych zmienia się na wartości dodatnie

Poszukuje się kolejnego wierzchołka zbioru rozwiązań dopuszczalnych

Oblicza się nowe wartości wszystkich zmiennych decyzyjnych

Bada się czy dotychczasowe rozwiązanie można poprawić

Zawsze istnieje optymalne rozwiązanie wierzchołkowe lub nie istnieje żadne rozwiązanie optymalne

Nie istnieje, jeśli zbiór rozwiązań dopuszczalnych zawiera nieskończenie wiele elementów

Jeśli jest rozwiązaniem wierzchołkowym, to zawiera tyle zmiennych niezerowych ile jest równań definiujących zbiór rozwiązań dopuszczalnych

Zawsze istnie, jeśli zbiór rozwiązań dopuszczalnych jest niepusty

Zawiera maksymalne wartości zmiennych decyzyjnych

Otrzymuję się minimalną wartość funkcji celu

Zmniejsza się wartość funkcji celu, o ile jest to możliwe

Oblicza się nową wartość jednej ze zmiennych decyzyjnych, która jest równa zeru

Każde rozwiązanie optymalne jest całkowitoliczbowe, o ile przepływ początkowy jest zerowy

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

Zbiór rozwiązań dopuszczalnych może być pusty

Może nie istnieć skończone rozwiązanie optymalne

Macierz ograniczeń zadania optymalnego może nie być całkowicie unimodularna

Wartość maksymalnego przepływu jest większa od przepustowości minimalnego przekroju rozdzielającego

Niemożliwość wyznaczenia łańcucha powiększalnego oznacza, że nie istnieje rozwiązanie optymalne

Każdy przepływ może rozłożyć na łańcuchy powiększalne.

Jeśli przepustowości są liczbami całkowitymi, to zawsze istnieje optymalne rozwiązanie całkowitoliczbowe

W przypadku, gdy popyt przekracza podaż, zastosowanie metody potencjałów wymaga wprowadzenia dodatkowego dostawcy

W otwartym zadaniu transportowym ograniczenia wynikające z zapotrzebowań mają postać równań

Może nie istnieć rozwiązanie optymalne zadania optymalizacyjnego

Liczba zmiennych decyzyjnych jest równa sumie liczb dostawców i odbiorców pomniejszona o jeden

Metoda kąta północno-zachodniego jest jedną z metod wyznaczania rozwiązania początkowego

Algorytm wyznaczania przydziału maksyminowego – algorytm rekurencyjny

Algorytm dla zadania plecakowego - algorytm programowania dynamicznego

Algorytm simpleks - metoda rozgałęzień i ograniczeń

Algorytm metody odcięć - algorytm zachłanny

Algorytm wyznaczania drogi najkrótszej w sieci acyklicznej - algorytm zachłanny