Przykłady zastosowań modeli decyzyjnych w działalności przedsiębiorstwa
Modele decyzyjne w przygotowaniu działalności przedsiębiorstwa
strategia wyboru produktu (co wytwarzać)
strategia wyboru technologii (ile produkować)
strategia wyboru miejsca lokalizacji (gdzie wytwarzać)
strategia rozmieszczenia obiektów
strategia organizacji zaopatrzenia (niezbędne czynniki produkcji i ich ilość)
strategia wykorzystania czynnika ludzkiego
Modele decyzyjne w planowaniu działalności produkcyjnej przedsiębiorstwa:
problem przydziału zadań w czasie
problem harmonogramowania zadań na urządzeniach
problem planowania i kontroli przedsięwzięć złożonych z wielu zadań elementarnych
Modele decyzyjne w planowaniu działalności marketingowej
Modele decyzyjne w planowaniu działalności finansowej przedsiębiorstwa
Cechy metody badań operacyjnych
ukierunkowanie na podejmowanie decyzji
interdyscyplinarny charakter badań operacyjnych - konieczność tworzenia zespołów specjalistów z wielu dziedzin w celu formułowania i rozwiązywania modeli badań operacyjnych
podejmowanie decyzji na podstawie modelu analizowanych systemów, a nie bezpośrednio na podstawie analizy systemów
konieczność budowy modelu decyzyjnego i eksperymentowanie na nim według określonych reguł
lepsze poznanie procesu decyzyjnego i jego specyfiki dzięki metodzie budowy modelu decyzyjnego
konieczność wykorzystywania techniki komputerowej
Etapy procedury rozwiązującej problemy decyzyjne za pomocą badań operacyjnych
rozpoznanie sytuacji decyzyjnej i wynikającego z niej problemu decyzyjnego
budowa modelu decyzyjnego
rozwiązanie modelu decyzyjnego
ocena poprawności i weryfikacja modelu
przygotowaniu decyzji i opracowanie systemu kontroli realizacji
Rodzaje modeli decyzyjnych
model konceptualny
model formalny (matematyczny)
model optymalizacyjny
model komputerowy
Klasyfikacja modeli decyzyjnych
według liczby kryteriów (jednokryteriowe, wielokryteriowe)
według postaci funkcji celu i ograniczeń (liniowe, nieliniowe)
według postaci zmiennych decyzyjnych (ciągłe, dyskretne)
według charakteru parametrów modelu (deterministyczne, stochastyczne)
według liczby etapów opisu procesu decyzyjnego
Działy badań operacyjnych
programowanie liniowe, optymalizacja dyskretna
zagadnienie transportowe
programowanie wielokryterialne
programowanie dynamiczne
teoria grafów i sieci
teoria gier strategicznych
teoria masowej obsługi
modele decyzyjne gospodarki zapasami
Układ wektorów liniowo niezależnych, liniowo zależnych
układ wektorów jest liniowo zależny, jeżeli chociaż jeden z nich jest kombinacją pozostałych
w układzie wektorów niezależnych żadnego z tych wektorów nie można przedstawić jako kombinacji liniowej pozostałych
Czy wektory jednostkowe tworzą układ wektorów liniowo zależny, czy liniowo niezależny?
Wektory jednostkowe w przestrzeni Rn stanowią układ liniowo niezależny
Liczba wektorów liniowo niezależnych w przestrzeni n-wymiarowej
Maksymalna liczba liniowo niezależnych wektorów w przestrzeni Rn wynosi n.
Baza zbioru, liczność wektorów liniowo niezależnych, tworzących bazę.
bazą zbioru S nazywamy liniowo niezależny układ wektorów b1..bk należących do S, 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.
Czy dowolny element zbioru można przedstawić w sposób jednoznaczny jako kombinację liniową wektorów bazowych tego zbioru?
Dla ustalonej bazy B zbioru S dowolny element a należący do S można przedstawić w sposób jednoznaczny jako kombinację liniową wektorów bazy.
Rozwiązanie bazowe układu równań
rozwiązaniem bazowym układu równań nazywamy takie rozwiązanie x(B) należące do Rn w którym wszystkie zmienne niebazowe są równe zeru (xR=0)
Wartości zmiennych niebazowych w rozwiązaniu bazowym
jw. = 0
Rozwiązanie bazowe zdegenerowane
rozwiązanie bazowe nazywamy zdegenerowanym, jeżeli chociaż jedna ze składowych części bazowej (tzn. xB) jest równa 0
Maksymalna liczba rozwiązań bazowych układu równań o macierzy m x n.
maksymalna liczba rozwiązań bazowych układu Ax = b, w którym A jest typu mx n, r (A) =m, m<=n, wynosi
m równań, n niewiadomych
Postać klasyczna zadania programowania liniowego
postać f-ji celu:
warunki ograniczające:
gdzie:
(x1, x2...xn) należące do Rn - wektor zmiennych decyzyjnych
z należące do R - wartość f-ji celu
(c1...cn) należące do Rn - wektor kosztów (cen jednostkowych) ?????????????
A = |aij| macierz współczynników nakładów
B = |bi| wektor ograniczeń nakładów
Postać standardowa zdania programowania liniowego
postać f-ji celu:
warunki ograniczające:
gdzie:
(x1, x2...xn) należące do Rn - wektor zmiennych decyzyjnych
z należące do R - wartość f-ji celu
(c1...cn) należące do Rn - wektor kosztów (cen jednostkowych) ??????
A = |aij| macierz współczynników nakładów
B = |bi| wektor ograniczeń nakładów
Rozwiązanie dopuszczalne zadania programowania liniowego
dowolny wektor spełniający warunki ograniczające
Rozwiązanie bazowe zadania programowania liniowego
jw. - wszystkie zmienne niebazowe = 0
jeśli dla każdego
, to takie rozwiązanie nazywamy optymalnym
20. Rozwiązanie optymalne zadania programowania liniowego
dla dowolnego rozwiązania dopuszczalnego xo jeśli x<>x0 f(x)<=f(x0) ???????????
ich ilość może być >1, może ich nie być w ogóle (nieograniczona wartość f-cji celu)
Kiedy zadanie programowania liniowego nazywamy sprzecznym
kiedy zadanie nie ma rozwiązań dopuszczalnych (metoda simpleks: w rozwiązaniu optymalnym występują niezerowe zmienne sztuczne)
Liczba zmiennych bazowych rozwiązania bazowego dopuszczalnego zadania programowania liniowego
il. warunków ograniczających?
Zbiory wypukłe, wierzchołki zbioru wypukłego
zbiór C należący do Rn nazywamy wypukłym, jeżeli dla dowolnych x1,x2 należących do C oraz dla dowolnego 0<=λ<=1 zachodzi: (λ *x1 + (1 - λ)*x2) należy do C.
Wierzchołkiem zbioru wypukłego nazywamy p-t, dla którego nie istnieją dwa różne p-ty x1<> x2<>x, że x=ax1+(1-a)x2
Jaki zbiór w przestrzeni (interpretacja geometryczna) tworzy zbiór rozwiązań dopuszczalnych zadania programowego liniowego?
figura geometryczne zawarta między wykresami funkcji ograniczających - może być zbiorem pustym lub być nieograniczona ZBIÓR WYPUKŁY
Gdzie w zbiorze rozwiązań dopuszczalnych zadania programowania liniowego znajdują się rozwiązania bazowe dopuszczalne?
Jest punktem wierzchołkowym zbioru rozwiązań dopuszczalnych.
Gdzie w przestrzeni należy poszukiwać rozwiązania optymalnego zadania programowania liniowego?
Rozwiązań optymalnych zadania programowania liniowego należy szukać wśród dopuszczalnych rozwiązań bazowych układu ograniczeń. (w wierzchołkach zbioru rozwiązań dopuszczalnych)
Liczba rozwiązań optymalnych zadania programowania liniowego.
zero - zadanie sprzeczne
1
wiele
brak skończonego rozwiązania optymalnego
Zmienne osłabiające w zadaniach programowania liniowego
Zmienne osłabiające (bilansujące) służą do usunięcia nierówności < (dodanie zmiennej) lub > (odjęcie zmiennej) w ograniczeniach ZPL (podczas doprowadzania do postaci standardowej)
postać standardową uzyskuje się poprzez wprowadzenie zmiennych osłabiających (wektora zmiennych dodatkowych)
Ax+xd=b, b>=0
X>=0, xd>=0
Wtedy początkowym rozwiązaniem bazowym jest: x=0, xd=b ???????????????????????????????
Zmienne sztucznej bazy w zadaniach programowania liniowego
są to sztuczne wektory jednostkowe, dodawane, gdy nie mamy wystarczającej ilości wektorów, mogących być bazowymi (rozwiązaniem dopuszczalnym jest rozwiązanie, którym nie wstępują niezerowe zmienne sztuczne)
Przyczyny i konsekwencje wprowadzania zmiennych osłabiających i zmiennych sztucznej bazy do warunków ograniczających zadania programowania liniowego
osłabiające: wprowadzane, gdy warunki ogr. są wyrażone w postaci nierówności
sztuczna baza: wprowadzane. Gdy po uzyskaniu postaci standardowej nie mamy podmacierzy jednostkowej m-tego stopnia
konsekwencje: modyfikacja f-ji celu tylko w przypadku zmiennych sztucznej bazy
Idea algorytmu simplex
metoda simpleks po znalezieniu początkowego rozwiązania bazowego dopuszczalnego wyznacza następne (sąsiednie) dopuszczalne rozwiązania bazowe zależne od poprzedniego, polepszające wartość funkcji celu. Przez sąsiednie rozwiązanie bazowe przyjmuje się rozwiązanie różniące się od niego tylko jedną zmienną bazową. (przeskakiwanie do sąsiedniego wierzchołka zbioru)
Wyznaczanie początkowego rozwiązania bazowego dopuszczalnego zadania programowania liniowego
sprowadzenie zadania do postaci standardowej
wyodrębnienie lub stworzenie podmacierzy jednostkowej (wprowadzenie wektorów sztucznej bazy)
Interpretacja elementów wektora wskaźników optymalności w tablicy simpleksowej
wskaźniki optymalności informują nas:
czy dane rozwiązanie jest rozwiązaniem optymalnym
czy wprowadzenie danej zmiennej do bazy zwiększy czy zmniejszy wartość f-cji celu
Wyznaczanie elementu centralnego w tablicy simpleksowej
obliczenie wskaźników optymalności
sprawdzenie, czy dane rozwiązanie nie jest rozwiązaniem optymalnym
wybranie wskaźnika optymalności o najwyższej wartości. Element centralny znajduje się w kolumnie nad tym wskaźnikiem. Sprawdzenie, czy nie mamy do czynienia z funkcją celu o nieograniczonej wartości
kontrola, czy wszystkie elementy w wybranej kolumnie nie są <=0
obliczenie ilorazu elementów xb / x, wybór najmniejszego dodatniego ilorazu. EC znajduje się w tym wierszu
Kiedy aktualne dopuszczalne rozwiązanie bazowe zadania programowania linowego jest rozwiązaniem optymalnym (opisz etap algorytmu simpleks)
wtedy, kiedy wskaźniki optymalności są <=0
Kiedy zadanie programowania liniowego nie ma skończonego rozwiązania optymalnego (opisz etap algorytmu simpleks)
jeżeli istnieje j takie, że zj-cj>0 przy którym aij<=0 dla wszystkich i należące do B to zadanie nie ma skończonego rozwiązania optymalnego
Zadanie pierwotne, a zadanie poszerzone w metodzie simpleks
funkcję celu modyfikujemy o współczynniki M przy dodatkowych wektorach sztucznej bazy
modyfikujemy ograniczenia o wektory sztucznej bazy i osłabiające
dodajemy kolejny wiersz w tabeli simpleksowej, obrazujący ilość współczynników M w danej kolumnie K
Wyznaczanie rozwiązania optymalnego zadania pierwotnego na podstawie rozwiązania optymalnego zadania poszerzonego
gdy wśród zmiennych bazowych do rozwiązania optymalnego występują niezerowe zmienne sztuczne - zadanie wyjściowe jest sprzeczne
gdy wśród zmiennych bazowych do rozwiązania optymalnego występując zerowe zmienne sztuczne - odrzucamy je i otrzymujemy rozwiązanie pierwotne
gdy wśród zmiennych losowych nie ma zmiennych sztucznych - mamy rozwiązanie optymalne zadania wyjściowego
Postępowanie w przypadku degeneracji rozwiązania zadania programowania liniowego - metoda perturbacji
występuje niezwykle rzadko w rzeczywistości
degeneracja może prowadzić do cykliczności
Jeśli zachodzi alternatywa wyboru nr-u wiersza zmiennej do usunięcia, to obliczamy ilorazy dla pozostałych wierszy, poczynając od 1 szukamy ilorazów xi/xk o najmniejszej nieujemnej wartości. Jeśli znaleźliśmy, to tę zmienną usuwamy z bazy, jeśli nie, to liczymy tak aż do końca tablicy sympleksowej i załamujemy się, bo wtedy nie wiemy, którą zmienną wprowadzić do bazy.
Istnieje jeszcze kilka innych metod postępowania w przypadku degeneracji
Symetryczne / niesymetryczne pierwotne / dualne zadania programowania liniowego
niesymetryczne zadanie dualne
zadanie pierwotne: min f(x)=cT X, AX=b, X>=0
zadanie dualne: max g(w)=bT X, AT W <=c, brak wymagań, aby wi>=0
symetryczne zadanie dualne
zadanie pierwotne: min f(x)=cT X, AX>=b. X>=0
zadanie dualne: max g(w)=bT X, AT W<=c, W>=0
Postać ogólna zagadnienia transportowego
Niech xij (i=1..m, j=1..n) oznacza wielkość przewozu od i-tego dostawcy do j-tego odbiorcy
Sformułowane zadanie można zapisać w następującej postaci:
Postać funkcji celu
Warunki ograniczające:
(warunki bilansowe dostawców): „suma od j=1..n” xij<=ai, i=1..m
(warunki bilansowe odbiorców) „suma od i=1 do m” xij=bj j=1..n
xij>=0, i=1..m, j=1.n
gdzie:
X - macierz zmiennych decyzyjnych
z - wartość f-ji celu
C - macierz kosztów
a - wektor dostawy
b - wektor odbioru
Interpretacja warunków ograniczających zagadnienia transportowego
suma towarów wysyłanych do odbiorców musi być <= zasobom, które posiadają
suma towarów przyjmowanych przez odbiorców musi być równa zapotrzebowaniu odbiorców
Zadanie transportowe zbilansowane, niezbilansowane.
Zadanie zbilansowane:
tj. suma zasobów towarów jest równa sumie zapotrzebowań
Zadanie niezbilansowane - sumy te nie są sobie równe
Metody sprowadzania zadania transportowego do postaci zbilansowanej
wprowadzenie fikcyjnego odbiorcy lub fikcyjnego dostawcy:
fikcyjny odbiorca ma zapotrzebowanie
fikcyjny dostawca ma zapas
Czy zadanie transportowe zawsze posiada rozwiązanie optymalne?
Tak, jeśli jest to zadanie zbilansowane, a do takiej postaci możemy zawsze doprowadzić.
Czy zadanie transportowe zawsze posiada skończone rozwiązanie optymalne?
Jw - tak, jeśli jest to zadanie zbilansowane, a do takiej postaci możemy zawsze doprowadzić.
Warunki otrzymania rozwiązania zadania transportowego o wartościach całkowitych
Jeśli wszystkie ai i bj w zadaniu transportowym zbilansowanym są liczbami całkowitymi, to każde rozwiązanie bazowe (także optymalne) jest utworzone z liczb całkowitych
Liczba wszystkich zmiennych decyzyjnych w zadaniu transportowym o m dostawcach i n odbiorcach
m*n
Liczba zmiennych bazowych w rozwiązaniu bazowym zadania transportowego
Z ogólnych własności zadania programowania liniowego wynika, że rozwiązanie bazowe zadania transportowego składa się dokładnie z m+n-1 zmiennych bazowych.
Etapy procedury rozwiązywania zadania transportowego
wyznaczanie wstępnego rozwiązania bazowego (np. metodą kąta północno-zachodniego, metodą minimalnego elementu macierzy kosztów, metodą VAM)
wyznaczanie rozwiązania optymalnego (np. metodą potencjałów)
51. Metody wyznaczania wstępnego rozwiązania bazowego zadania transportowego.
- metoda kąta północno-zachodniego
Wybieramy za każdym razem zmienną bazową, stojącą w rogu północno-zachodnim redukowanej macierzy przewozów X. Pierwszą zmienną bazową będzie zmienna x11, ostatnią zmienna xmn
- metoda minimalnego elementu macierzy kosztów
Jako pierwszą zmienną bazową wybieramy zmienną, której odpowiada najmniejszy współczynnik kosztu jednostkowego. Redukujemy zbiór dostawców lub zbiór odbiorców oraz korygujemy zasoby dostawców i zapotrzebowania odbiorców. Po redukcji ponownie wybieramy zmienną, której odpowiada najmniejszy współczynnik kosztu jednostkowego.
- metoda VAM
52. Postępowanie w przypadku degeneracji rozwiązania bazowego zadania transportowego.
Jeżeli rozwiązanie zadania transportowego ma mniej niż M+n-1 zmiennych bazowych (tzw. zdegenerowane rozwiązanie bazowe, w którym co najmniej jedna zmienna bazowa jest równa zeru), należy dołączyć brakującą liczbę zmiennych bazowych z wartościami zerowymi. Wyboru dokonujemy tak, aby graf rozwiązania był grafem spójnym i bez cykli.
53. Interpretacja elementów tablicy wskaźników optymalności w metodzie potencjałów.
Sprawdzamy, czy macierz wskaźników optymalności C0 >=0. Jeśli tak, rozwiązanie jest optymalne.
54. Kryterium stopu w algorytmie rozwiązywania zadania transportowego metodą potencjałów.
Metoda z wykładu: wszystkie wskaźniki optymalności są liczbami dodatnimi
Metoda z ćwiczeń: wszystkie wskaźniki optymalności są elementami ujemnymi (jak w metodzie simpleks)
55. Przykłady problemów decyzyjnych formułowanych w postaci zadania transportowego.
zagadnienie transportowo-produkcyjne
zagadnienie wyboru lokalizacji produkcji
zagadnienie minimalizacji pustych przebiegów
56. Definicja gry.
Sytuacja decyzyjna między stronami grającymi o przeciwstawnych interesach, sformalizowaną matematycznie.
57. Elementy składowe gry.
Zbiór strategii
zbiór informacyjny
reguły
58. Gra o sumie zerowej, gra z naturą.
- gra o sumie zerowej występuje, gdy suma wypłat wygranych przez wygrywających równa się sumie strat ponoszonych przez przegrywających
- gra z naturą: natura jako druga strona nie jest zainteresowana końcowym wynikiem gry, a wykonywane przez nią ruchy mają charakter losowy
59. Gra otwarta, gra zamknięta
Gra zamknięta jest to gra w której górna wartość gry jest równa dolnej wartości gry (i równa wartości gry). Gra otwarta jest to gra w której wartości górna i dolna są różne od siebie.
60. Co to jest strategia?
- dokładnie sprecyzowana przed rozpoczęciem gry reguła decyzyjna, na podstawie której gracz podejmuje decyzję (gracze nie znają nawzajem swoich strategii) ???????????????????????????????
61. Wartość gry, czy oczekiwana wypłata w grze może być ujemna.
- średnia kwota na partię, którą wygrałby w długim okresie czasu jeden z graczy, gdyby obaj stosowali swoje najlepsze strategie
- tak
62. Jakie elementy są konieczne dla istnienia gry ?
- niepewność
- ryzyko
- konflikt interesów
63. Co to jest gra w postaci ekstensywnej, w postaci normalnej.
- gra w postaci normalnej: proces statyczny, każdy gracz dysponuje zbiorem przyporządkowanych mu strategii. Obaj gracze dokonują jednocześnie wyboru po jednej ze swoich strategii, żaden nie zna wyboru strategii swojego przeciwnika. Wybór ten jednoznacznie określa wynik gry (macierz wypłat)
- gra w postaci ekstensywnej: wieloetapowy proces prowadzenia gry; ciąg ruchów wykonywanych na przemian i nie jednocześnie (np. gra w szachy) (drzewo decyzyjne)
64. Gra skończona, gra nieskończona.
- jeśli gra ma skończoną liczbę strategii, to jest to gra skończona, w przeciwnym wypadku - nieskończona
65. Kiedy grę nazywamy strategiczną ?
Gdy poza ruchami losowymi występują świadome wybory graczy (zgodne z przyjętą strategią) - za [5]
66. Strategia mieszana gracza, strategia czysta.
- strategia mieszana - strategia polegająca na tym, że gracz postanawia w pewnej ustalonej proporcji zastosować wiele z dostępnych sposobów działania
- strategia czysta - gracz decyduje się na tylko jeden określony sposób działania podczas gry
67. Kiedy gra jest grą ściśle konkurencyjną ?
Kiedy wszyscy uczestnicy są zainteresowani wygraną.
68. Podaj przykłady gier towarzyskich z kompletną i niekompletną informacją.
- kompletna: szachy, warcaby
- niekompletna: brydż, poker
69. Kiedy układ n strategii jest w równowadze ?
Gdy w wyniku rozwiązania gry uzyskaliśmy informację, że optymalnym rozwiązaniem jest stosowanie przez gracza n strategii z określonym prawdopodobieństwem
70. Co to jest punkt siodłowy gry, kiedy gra posiada punkt siodłowy.
- położenie równowagi, istnienie p-tu siodłowego informuje nas o istnieniu układu strategii czystych w równowadze (graczom najbardziej opłaca się stosować strategie określone nr wiersza i nr kolumny punktu siodłowego)
71. Kiedy grę możemy rozwiązać metodą graficzną ?
- kiedy jeden z graczy ma tylko 2 strategie. (układ 2xn lub mx2)
72. Co zapewnia uczestnikowi strategia maxyminowa ?
- gwarantowaną maksymalną wartość minimalnej (najmniejszej możliwej) wygranej - gracz wygra co najmniej .....jest to najbezpieczniejsza strategia gracza I
73. Co zapewnia uczestnikowi strategia minimaxowa ?
- gwarantowaną minimalną wartość maksymalnej (największej możliwej) przegranej - gracz przegra co najwyżej .....jest to najbezpieczniejsza strategia gracza II
74. Wymień znane ci metody znajdowania wartości gry.
Wyznaczenie punktu siodłowego, rozwiązanie układów równań w grach 2x2, metoda graficzna, wykorzystanie metod rozwiązywania ZPL
75. Twierdzenie von Neumanna dla gier zamkniętych.
Każda gra dwuosobowa o sumie zero posiada określoną wartość, a dla każdego gracza istnieje co najmniej jedna strategia optymalna (może być to strategia mieszana)
76. Dla jakich gier istnieje zawsze układ n strategii w równowadze ?
77. Metody wyznaczania strategii optymalnych dla gier dwuosobowych o sumie zerowej.
Metoda szukania punktu siodłowego, metoda dominant, metoda graficzna, metoda programowania liniowego
78. Jak nazywamy układ strategii czystych w równowadze ?
- jest to punkt siodłowy
79. Na czym polega metoda dominant ?
- usuwanie z macierzy wypłat kolumn i wierszy reprezentujących strategie zdominowane, gdyż dążący do osiągnięcia największego zysku gracze nigdy nie zastosują tych strategii.
80. Co to znaczy dla gracza pierwszego, że strategia i dominuje strategię j ?
Strategia i da lepszy wynik, niż strategia j (graczowi I nie opłaca się stosować strategii j, gdyż strategia i da mu mniejszą wygraną niezależnie od zagrania gracza II)
81. Co to znaczy dla gracza drugiego, że strategia i dominuje strategię j ?
Strategia i da lepszy wynik, niż strategia j (graczowi II nie opłaca się stosować strategii j, gdyż strategia i da mu większą przegraną niezależnie od zagrania gracza I)
82. Metoda fikcyjnych założeń dla określenia strategii optymalnej.
Algorytmy
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).
4. Przekształcanie gry danej w postaci dendrytu do postaci normalnej i poszukiwanie punktu siodłowego.
5. Rozwiązanie gry w postaci macierzy z wykorzystaniem metody dominant oraz metody graficznej.