BADANIA OPERACYJNE cz. I

Omawiane zagadnienia (pytania testowe)

1. Przykłady zastosowań modeli decyzyjnych w działalności przedsiębiorstwa.

Strategia: wyboru produktu, wyboru technologii, wyboru miejsca lokalizacji, rozmieszczenia obiektów, organizacji zaopatrzenia, wykorzystania czynnika ludzkiego.

1. Cechy metody badań operacyjnych.

Dokładne sformułowanie zadania, interdyscyplinarny charakter badań operacyjnych, podejmowanie decyzji na podstawie modelu analizowanych systemów, konieczność budowy modelu decyzyjnego i eksperymentowanie na nim wg określonych reguł, lepsze poznanie procesu decyzyjnego i jego specyfiki dzięki budowie modelu decyzyjnego, konieczność wykorzystywania technik komputerowych.

1. Etapy procedury rozwiązującej problemy decyzyjne za pomocą badań operacyjnych.

Określenie problemu => budowa modelu decyzyjnego => rozwiązanie modelu decyzyjnego => badanie poprawności => przygotowanie decyzji i opracowanie systemu kontroli realizacji

1. Rodzaje modeli decyzyjnych.

Model: konceptualny, formalny, optymalizacyjny, komputerowy.

1. Klasyfikacja modeli decyzyjnych.

Według liczby kryteriów, według postaci funkcji celu i ograniczeń, według postaci zmiennych decyzyjnych, według charakteru parametrów modelu, według liczby etapów opisu procesu decyzyjnego.

1. Działy badań operacyjnych.

Programowanie liniowe, zagadnienia transportowe, programowanie wielokryterialne, programowanie dynamiczne, teoria grafów i sieci, teoria gier strategicznych, teoria masowej obsługi, modele decyzyjne gospodarki zapasami

1. Układ wektorów liniowo niezależnych, liniowo zależnych.

Jeśli jeden wektor będzie kombinacją liniową dwóch pozostałych to jest to wektor liniowo zależny. Jeśli nie to jest to wektor liniowo niezależny.

1. Czy wektory jednostkowe tworzą układ wektorów liniowo zależny czy liniowo niezależny.

Liniowo niezależny

1. Liczba wektorów liniowo niezależnych w przestrzeni n - wymiarowej.

Wynosi n

1. Baza zbioru, liczność wektorów liniowo niezależnych tworzących bazę.

Baza zbioru S jest to liniowo niezależny zbiór wektorów rozpinający zbiór S. Liczba wektorów stanowiących bazę zbioru jest równa max liczbie wektorów liniowo niezależnych należących do tego zbioru.

1. Czy dowolny element zbioru można przedstawić w sposób jednoznaczny jako kombinację liniową wektorów bazowych tego zbioru.

Tak

1. Rozwiązanie bazowe układu równań.

Jest to takie x_B w którym wszystkie zmienne niebazowe są równe zeru. x_R = 0

1. Wartości zmiennych niebazowych w rozwiązaniu bazowym.

Przyjmują wartość zero

1. Rozwiązanie bazowe zdegenerowane.

Nazywamy je tak gdy chociaż jedna ze składowych części bazowej (x_B) jest równa zeru.

1. Maksymalna liczba rozwiązań bazowych układu równań o macierzy m x n.

$$\left( \frac{n}{m} \right)$$

1. Postać klasyczna zadania programowania liniowego.

Postać funkcji celu

$$\left( \max \right)z = \sum_{j = 1}^{n}{c_{j}x_{j}}$$

Warunki ograniczające

i = 1, 2 , …, m

x_j ≥ 0 j = 1, 2, …, n

1. Postać standardowa zadania programowania liniowego.

$$\left( \max \right)z = \sum_{j = 1}^{n}{c_{j}x_{j}}$$

b_i ≥ 0, i = 1, 2, …, m

x_j ≥ 0 j = 1, 2, …, n

1. Rozwiązanie dopuszczalne zadania programowania liniowego.

Dowolny wektor spełniający warunki ograniczające (jak zb.rozw.dopuszczalnych jest zb.pustym to zadanie nazywamy sprzecznym).

1. Rozwiązanie bazowe dopuszczalne zadania programowania liniowego.

Jest to punkt wierzchołkowy, oraz wszystkie zmienne bazowe są nieujemne

1. Rozwiązanie optymalne zadania programowania liniowego.

Dla dowolnego rozwiązania dopuszczalnego x rozwiązanie optymalne zawsze będzie lepsze od rozwiązania dopuszczalnego f(x^*) ≥ f(x). Zadanie może nie mieć skończonego rozw.optymalnego lub mieć ich więcej niż jedno.

1. Kiedy zadanie programowania liniowego nazywamy sprzecznym.

Wtedy kiedy zbiór rozwiązań dopuszczalnych jest zbiorem pustym lub kiedy nie ma ani jednego rozwiązania bazowego.

1. Liczba zmiennych bazowych rozwiązania bazowego dopuszczalnego zadania programowania liniowego.

Dwie.

1. Zbiory wypukłe, wierzchołki zbioru wypukłego.

Zbiorem wypukłym nazywamy taki zbiór w którym dowolne dwa punkty połączone prostą zawsze będą wewnątrz tego zbioru. Wierzchołek zbioru wypukłego jest to taki punkt dla którego nie Można znaleźć punktów spełniających warunek: x=lx₁+(1-l)x₂

1. Jaki zbiór w przestrzeni (interpretacja geometryczna) tworzy zbiór rozwiązań dopuszczalnych zadania programowania liniowego.

Zbiór wypukły

1. Gdzie w zbiorze rozwiązań dopuszczalnych zadania programowania liniowego znajdują się rozwiązania bazowe dopuszczalne.

W punkcie wierzchołkowym zbioru rozwiązań dopuszczalnych

1. Gdzie w przestrzeni (interpretacja geometryczna) należy poszukiwać rozwiązania optymalnego zadania programowania liniowego.

Należy szukać wśród dopuszczalnych rozwiązań bazowych układu ograniczeń, zawsze w wierzchołku.

1. Liczba rozwiązań optymalnych zadania programowania liniowego.

Może być tyle ile jest rozwiązań dopuszczalnych o ile wartości wskaźników optymalności są niedodatnie.

1. Zmienne osłabiające w zadaniu programowania liniowego.

Jest to zmienna dodawana do ograniczenia nierównościowego w celu zamiany go na ograniczenie równościowe

1. Zmienne sztucznej bazy w zadaniu programowania liniowego.

Służą do utworzenia brakującego wektora jednostkowego, jednakże z racji tej że sztuczne zmienne nie powinny występować wśród zmiennych bazowych to przypisuje się im bardzo duży współczynnik w funkcji celu aby pogarszały one jej wartości i przez to nie będzie opłacalne pozostawianie ich w kolejnych rozwiązaniach bazowych.( max z plusem, min z minusem)

1. Przyczyny i konsekwencje wprowadzania zmiennych osłabiających i zmiennych sztucznej bazy do warunków ograniczających zadania programowania liniowego.

Zmienne osłabiające wprowadza się w celu zamienienia ograniczenia nierównościowego na równościowe, a zmienne sztuczne w celu utworzenia brakującego wektora jednostkowego.

1. Idea algorytmu simpleks.

Metoda Simpleks jest metodą iteracyjną. Po znalezieniu rozwiązania początkowego bazowego dopuszczalnego wyznacza następne zależne od poprzedniego, polepszające wartość funkcji celu. Aż do znalezienia rozwiązania optymalnego.

1. Wyznaczanie początkowego rozwiązania bazowego dopuszczalnego zadania programowania liniowego.

Przekształcenie warunków ograniczających poprzez: wprowadzenie zmiennych osłabiających, wyodrębniając podmacierz jednostkową lub wprowadzając wektory sztucznej bazy, do uzyskania postaci standardowej i wyliczenia z niej początkowego rozwiązania dopuszczalnego.

1. Interpretacja elementów wektora wskaźników optymalności w tablicy simpleksowej.

Jeśli wszystkie wskaźniki optymalności są większe od zera to aktualne rozwiązanie bazowe jest optymalne.

1. Wyznaczanie elementu centralnego w tablicy simpleksowej.

1. Wyliczenie wskaźników optymalności (różnica pomiędzy iloczynem skalarnym kolumny z współ. Z f.celu i kolumny z odpowiednim wektorem a współczynnikiem z f.celu)

2. Sprawdzenie który wskaźnik jest najmniejszy

3. Dla każdego dodatniego elementu wektora x_k z najmniejszym współczynnikiem optymalności należy obliczyć iloraz: elementu wektora x_b przez element kolumny x_k. Element stojący na przecięciu kolumny i wiersza z najmniejszymi elementami nosi nazwę elementu centralnego

1. Kiedy aktualne dopuszczalne rozwiązanie bazowe zadania programowania liniowego jest rozwiązaniem optymalnym (opisz etap algorytmu simpleks).

Gdy po wyliczeniu wskaźników optymalności wszystkie są większe od zera.

1. Kiedy zadanie programowania liniowego ma nieskończenie wiele rozwiązań optymalnych (opisz etap algorytmu simpleks).

Jeśli istnieje taki wskaźnik optymalności z_j - c_j < 0, przy którym wektor a_ij ≤ 0 dla wszystkich iϵB. Funkcja celu jest nieograniczona => koniec postępowania.

1. Zadanie pierwotne a zadanie poszerzone w metodzie simpleks.

Zadanie pierwotne jest to takie, w którym nie ma żadnej zmiennej sztucznej bazy, a zadania rozszerzone mają zmienną sztucznej bazy z bardzo dużym współczynnikiem w funkcji celu.

1. Wyznaczanie rozwiązania optymalnego zadania pierwotnego na podstawie rozwiązania optymalnego zadania poszerzonego.

Jeżeli w rozwiązaniu optymalnym x = [x₀, x_S] zadania rozszerzonego mamy x_S = 0, to x₀ jest rozwiązaniem optymalnym zadania pierwotnego, jeśli w tym rozwiązaniu x_S > 0, to zadanie pierwotne jest sprzeczne.

1. Postępowanie w przypadku degeneracji rozwiązania zadania programowania liniowego, metoda perturbacji.

Jeżeli w macierzy A współczynników nie można wyodrębnić podmacierzy jednostkowej, wtedy wprowadzamy wektory sztucznej bazy (zmienne sztuczne).

1. Symetryczne/niesymetryczne pierwotne/dualne zadania programowania liniowego.

Niesymetryczne zadanie dualne:

Zadanie pierwotne zadanie dualne

min f(x) = c^T X max g(w) = b^T X

AX = b A^T W ≤ c

X ≥ 0 brak wymagań, aby w_i ≥ 0

Symetryczne zad dualne

Pierwotne dualne

min f(x) = c^T X max g(w) = b^T X

AX ≥ b A^T W ≤ c

X ≥ 0

1. Postać ogólna zagadnienia transportowego.

Postać funkcji celu: $\left( \min \right)z = \sum_{i = 1}^{m}{\sum_{j = 1}^{n}{c_{\text{ij}}x_{\text{ij}}}}$

x_ij - wielkość przewozu od i-tego dostawcy do j-tego odbiorcy

War ograniczające: $\sum_{j = 1}^{n}{x_{\text{ij}} \leq a_{i}}$ i = 1, 2, …, m

$\sum_{i = 1}^{m}x_{\text{ij}} = b_{j}$ j = 1, 2, …, n

x_ij ≥ 0

1. Interpretacja warunków ograniczających zagadnienia transportowego.

X = [x_ij] – macierz zmiennych decyzyjnych (ilość towaru na drodze {i,j})

a = [a_i] – wektor dostawy (zasoby dostawców)

b = [b_j] – wektor odbioru (zapotrzebowanie odbiorców)

1. Zadanie transportowe zbilansowane, niezbilansowane.

Zbilansowane jest gdy suma towarów w magazynach jest równa zapotrzebowaniu odbiorców. Gdy ten warunek nie jest spełniony zadanie jest niezbilansowane.

1. Metody sprowadzania zadania transportowego do postaci zbilansowanej.

Gdy suma towarów w magazynach > zapotrzebowania odbiorców, wprowadzamy fikcyjnego odbiorcę. Gdy suma towarów jest < zapotrzebowania odb, wprowadzamy fikcyjnego dostawcę. Do macierzy kosztów dopisujemy zera.

1. Czy zadanie transportowe zawsze posiada rozwiązanie optymalne.

Tak.

1. Czy zadanie transportowe zawsze posiada skończone rozwiązanie optymalne.

Tak.

1. Warunki otrzymania rozwiązania zadania transportowego o wartościach całkowitych.

a_i (towary w magazynach) oraz b_j (zapotrzebowanie odbiorców) muszą być liczbami całkowitymi.

1. Liczba wszystkich zmiennych decyzyjnych w zadaniu transportowym o m dostawcach i n odbiorcach.

m * n

1. Liczba zmiennych bazowych w rozwiązaniu bazowym zadania transportowego.

m + n - 1

1. Etapy procedury rozwiązywania zadania transportowego.

1. Sprawdzenie czy zadanie jest zbilansowane i jeśli nie to przekształcenie go w zad zbilansowane

2. Wyznaczenie wstępnego rozwiązania bazowego (np. metodą kąta płn.-zach., met minimalnego elementu macierzy kosztów, metodą VAN)

3. Wyznaczenie rozwiązania optymalnego (np. met potencjałów).

1. Metody wyznaczania wstępnego rozwiązania bazowego zadania transportowego.

Metoda kąta płn.-zach., minimalnego elementu macierzy kosztów, met potencjałów

1. Postępowanie w przypadku degeneracji rozwiązania bazowego zadania transportowego.

Jeśli rozwiązanie zad tr ma mniej niż m+n-1 zmiennych bazowych należy dołączyć brakującą liczbę zmiennych bazowych z wartościami zerowymi. Graf rozwiązania musi być spójny i bez cykli.

1. Interpretacja elementów tablicy wskaźników optymalności w metodzie potencjałów.

C⁰ = [c⁰_ij] i = 1, 2, …, m; j = 1, 2, …, n

gdzie c⁰_ij = u_i + v_j + c_ij

1. Kryterium stopu w algorytmie rozwiązywania zadania transportowego metodą potencjałów.

rozwiązanie jest optymalne, gdy C⁰ ≥ 0

1. Przykłady problemów decyzyjnych formułowanych w postaci zadania transportowego.

Określenie planu przewozu między dostawcami a odbiorcami tak, by po uwzględnieniu dostępnych zasobów dostawców i wymaganego zapotrzebowania odbiorców łączne koszty transportu były minimalne.

Zagadnienia transportowo-produkcyjne, minimalizacja pustych przebiegów, wybór optymalnej lokalizacji produkcji, ograniczenie przepustowości na trasach przewozowych, całkowita blokada przewozu na wybranej trasie, częściowa blokada trasy.

1. Co to są przydziały wzajemnie jednoznaczne?

Dane są zbiory elementów A i B. Należy elementom zbioru A przyporządkować jeden i tylko jeden element zbioru B i na odwrót – każdemu elementowi B jeden element A.

1. Sformułuj zagadnienie przydziałów?

n czynności można wykonać w m miejscach produkcji. Znane są ograniczone moce produkcyjne poszczególnych miejsc pracy, często też zadania planowe w zakresie produkcji wyrobów. Jest też dana macierz kosztów. Należy zaproponować przydział zadań produkcyjnych do poszczególnych miejsc pracy, optymalny z punktu widzenia jednego z kryteriów:

- minimalizacji kosztów lub czasu wykonywania zadań planowych

- maksymalizacji efektów (ilości wyprodukowanych wyrobów)

1. Co to jest tablica oczek dopuszczalnych?

Zapis zadania w postaci tablicy możliwości przydziału. Oczka dopuszczalne odpowiadają możliwości przydziału elementom zbioru A danych elementów zbioru B. Pozostałe (przekreślone) oczka tablicy są oczkami niedopuszczalnymi.

1. Co to są niezależne oczka dopuszczalne w algorytmie wyznaczania przydziału najliczniejszego?

Gdy w każdym wierszu i w każdej kolumnie omawianej tablicy będzie wybrane maksymalnie jedno oczko. Wybrane oczka oznaczane są jedynkami.

1. Kiedy przerywamy etap cechowania i przechodzimy do zmiany układu jedynek w algorytmie wyznaczania przydziału najliczniejszego?

Jeśli jest ocechowana kolumna nie zawierająca jedynki.

1. Kiedy stwierdzamy optymalność rozwiązania w algorytmie wyznaczania przydziału najliczniejszego?

Jeśli nie ma ocechowanej kolumny bez jedynki, bo wtedy aktualny zbiór jedynek w tablicy jest najliczniejszy i wyznacza rozwiązanie optymalne. Nie da się wstawić więcej jedynek.

1. Kiedy stwierdzamy optymalność rozwiązania w algorytmie wyznaczania przydziału optymalnego z kryterium maxmin?

W zbiorze oczek dopuszczalnych wyznaczamy najliczniejszy zbiór niezależnych oczek. Jeśli liczność wyznaczonego zbioru jest mniejsza niż min{m,n} to wtedy wyznaczony poprzedni zbiór niezależnych oczek dopuszczalnych określa przydział optymalny z kryterium max(min).

1. Kiedy stwierdzamy optymalność rozwiązania w algorytmie wyznaczania przydziału optymalnego z kryterium minmax?

W zbiorze oczek dopuszczalnych wyznaczamy najliczniejszy zbiór niezależnych oczek. Jeśli liczność wyznaczonego zbioru jest mniejsza niż min{m,n} to wtedy wyznaczony poprzedni zbiór niezależnych oczek dopuszczalnych określa przydział optymalny z kryterium min(max).

1. Podaj przykład zastosowania algorytmu wyznaczania przydziału optymalnego o minimalnym koszcie?

Takie przyporządkowanie kierowców do poszczególnych samochodów, aby koszt transportu towaru był minimalny.

1. Podaj przykład zastosowania algorytmu wyznaczania przydziału optymalnego o maksy.malnym zysku?

Takie przydzielenie pracowników na poszczególne kontrakty, aby zmaksymalizować zysk przedsiębiorstwa.

1. Podaj przykład zastosowania algorytmu wyznaczania przydziału optymalnego(wąskie gardło) z kryterium minmax?

Takie przydzielenie prac pracownikom, aby zminimalizować czas pracy, której realizacja jest najdłuższa.

1. Podaj przykład zastosowania algorytmu wyznaczania przydziału optymalnego(wąskie gardło) z kryterium maxmin?

Takie przydzielenie prac pracownikom, aby zmaksymalizować najmniejszą wydajność pracownika.

1. Jak zmodyfikować algorytm wyznaczania przydziału optymalnego o minimalnym koszcie aby uzyskać przydział optymalny o maksymalnym zysku?

Każdy element macierzy kosztów przemnożyć przez -1.

1. Co to jest skojarzenie najliczniejsze w grafie?

Takie które ma największy rozmiar.

Zestaw obowiązujących algorytmów

1. Interpretacja geometryczna zadań programowania liniowego.

2. Algorytm simpleks (zadanie pierwotne, zadanie poszerzone).

3. Zadanie transportowe (metoda kąta północno-zachodniego + metoda potencjałów, metoda minimalnego elementu macierzy kosztów + metoda potencjałów).

4. Przydział optymalny o minimalnym koszcie/maksymalnym zysku.

5. Przydziały typu wąskie gardło z kryterium maxmin i minmax.