Badania operacyjne - teoria PDF

Preview

Summary

Materiały na zaliczenie części teoretycznej przedmiotu Badania Operacyjne
Wydział Transportu PW, semestr III...

Description

1) Przykłady zastosowań modeli decyzyjnych w działalności przedsiębiorstwa: - strategia wyboru produktu - strategia wyboru technologii - strategia wyboru miejsca lokalizacji - strategia rozmieszczenia obiektów - strategia organizacji zaopatrzenia - strategia wykorzystania czynnika ludzkiego. 2) Cechy metody badań operacyjnych: - Ukierunkowanie na podejmowanie decyzji - Interdyscyplinarny charakter badań operacyjnych - Konieczność budowy modelu decyzyjnego i eksperymentowanie na nim wg określonych reguł - Podejmowanie decyzji na podstawie modelu analizowanych systemów - Lepsze poznanie procesu decyzyjnego i jego specyfiki dzięki metodzie budowy modelu decyzyjnego - Konieczność wykorzystywania techniki komputerowej. 3) Etapy procedury rozwiązującej problemy decyzyjne za pomocą badań operacyjnych: 1. Rozpoznanie sytuacji i wynikającego z niej problemu decyzyjnego 2. Budowa modelu decyzyjnego 3. Rozwiązanie modelu decyzyjnego 4. Ocena poprawności i weryfikacja modelu 5. Przygotowanie decyzji i opracowanie systemu kontroli realizacji. 4) Podstawowe części modelu decyzyjnego: - funkcja celu - warunki ograniczające - warunek nieujemności zmiennych decyzyjnych. 5) Rodzaje modeli decyzyjnych: konceptualny, formalny, optymalizacyjny, komputerowy. 6) Podział problemów decyzyjnych zależny od warunków w jakich podejmowana jest decyzja: - dobrze ustrukturalizowane (dające się sformułować ilościowo oraz zmierzyć) - słabo ustrukturalizowane - nieustrukturalizowane. 7) Klasyfikacja modeli decyzyjnych: Wg liczby kryteriów: Jednokryteriowe i wielokryteriowe. Wg postaci funkcji celu i ograniczeń: Liniowe i nieliniowe. Wg postaci zmiennych decyzyjnych: Ciągłe i dyskretne. Wg charakteru parametrów modelu: Deterministyczne i stochastyczne. Wg liczby etapów opisu procesu decyzyjnego:

Statyczne – jednoetapowe i dynamiczne – wieloetapowe. 8) Działy badań operacyjnych: - programowanie liniowe - programowanie dynamiczne - programowanie wielokryterialne - zagadnienie transportowe - teoria grafów i sieci - teoria gier strategicznych - teoria masowej obsługi - modele decyzyjne gospodarki zapasami. 9) Układ wektorów liniowo niezależnych, zależnych:  Jeżeli jeden wektor jest kombinacją liniową pozostałych to jest to wektor liniowo zależny  Jeżeli nie, to jest to wektor liniowo niezależny. 10) Baza zbioru S to liniowo niezależny układ wektorów rozpinający zbiór S. Liczba wektorów stanowiących bazę zbioru S jest równa maksymalnej liczbie wektorów liniowo niezależnych należących do S.

11) Rozwiązanie dopuszczalne zadania programowania liniowego – dowolny wektor spełniający warunki ograniczające. 12) Rozwiązanie dopuszczalne bazowe zadania programowania liniowego – punkt wierzchołkowy, wszystkie zmienne bazowe są nieujemne. 13) Rozwiązanie optymalne zadania programowania liniowego – rozwiązanie optymalne zawsze jest lepsze od rozwiązania dopuszczalnego. Zadanie może nie mieć skończonego rozwiązania optymalnego lub mieć ich więcej niż jedno. 14) Zadanie programowania liniowego jest sprzeczne, gdy zbiór rozwiązań dopuszczalnych jest zbiorem pustym lub gdy nie ma ani jednego rozwiązania bazowego. 15) Zbiór wypukły to taki, w którym dwa dowolne 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 = lx1+(1-l)x2 16) Zmienne osłabiające w zadaniu programowania liniowego to zmienne dodawane do ograniczenia nierównościowego, aby zmienić je na ograniczenie równościowe. 17) Zmienne sztucznej bazy w zadaniu programowania liniowego służą do utworzenia brakującego wektora jednostkowego. Sztuczne zmienne nie powinny występować wśród zmiennych bazowych, więc 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 pozostawienie ich w kolejnych rozwiązaniach bazowych.

18) Ideą algorytmu simpleks jest rozwiązywanie tych zadań programowania liniowego, gdzie ze względu na liczbę zmiennych decyzyjnych nie sprawdza się metoda geometryczna. Jest to metoda iteracyjna, czyli po znalezieniu początkowego rozwiązania bazowego dopuszczalnego wyznaczamy następne, zależne od poprzedniego, polepszające wartości funkcji celu – aż do znalezienia rozwiązania optymalnego. 19) Zadanie pierwotne to takie, w którym nie ma żadnej zmiennej sztucznej bazy. Zadania rozszerzone mają zmienną sztucznej bazy z bardzo dużym współczynnikiem funkcji celu. 20) Etapy rozwiązywania zadania transportowego: - jeśli zadanie jest niezbilansowane to trzeba je zbilansować - wyznaczamy wstępne rozwiązanie bazowe (np. metodą kąta północno – zachodniego, metodą minimalnego elementu macierzy kosztów, metodą VAM) -wyznaczamy rozwiązanie optymalizacyjne (np. metodą potencjałów). 21) W przypadku degeneracji rozwiązania bazowego zadania transportowego, tj. gdy rozwiązanie ma mniej niż m+n-1 zmiennych bazowych dołączamy brakującą liczbę zmiennych bazowych z wartościami zerowymi. Graf rozwiązania musi być grafem spójnym i bez cykli. 22) Problemy decyzyjne formułowane w postaci zadania transportowego: 1. Zagadnienie transportowo – produkcyjne 2. Minimalizacja pustych przebiegów 3. Wybór optymalnej lokalizacji 4. Ograniczenie przepustowości na trasach przewozowych 5. Całkowita lub częściowa blokada przewozu na trasie. 23) Blokada przewozu na trasie:  Całkowita  0* (k, l) xkl = 0 Np. (2, 4) x24 = 0 

ckl = M c24 = M

Częściowa  M bardzo duże. Dopisujemy wiersz K” (np. 2”) z jedną z wartości zastąpioną M.

24) Zagadnienie przydziałów: n wyrobów można wykonywać w m miejscach produkcji. Znamy ograniczone moce produkcyjne poszczególnych miejsc pracy oraz macierz kosztów. Często też znamy zadania planowane w zakresie produkcji wyrobów. Należy zaproponować przydział zadań produkcyjnych do poszczególnych miejsc pracy, optymalny ze względu na: - minimalizację kosztów lub czasu wykonywania zadań planowanych - maksymalizację efektów (ilości wyprodukowanych wyrobów). 25) 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 oczka tablicy są przekreślone....