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

Przygotowanie 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

Planowanie 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

2 . 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

3 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

• przygotowanie decyzji i opracowanie systemu kontroli realizacji

4. Podstawowe części modelu decyzyjnego

• Funkcja celu

• Warunki ograniczające

• Warunki nieujemności zmiennych decyzyjnych

5 .Rodzaje modeli decyzyjnych

• Model konceptualny - wynik wiedzy i doświadczenia konstruktora modelu
  służący poznaniu najistotniejszych cech badanego zjawiska i jego związku z
  otoczeniem. Służy celom poznawczym, polegającym na opisie i ułatwieniu
  zrozumienia zasad zachowania się zastępowalnych przez nie systemów.

• Model formalny (matematyczny) - wzorzec pozwalający zidentyfikować
  zdarzenia i procesy, całokształt ich powiązań i współzależności o charakterze
  strukturalnym i funkcjonalnym. Strukturę badanego procesu tworzą związki
  pomiędzy wyróżnionymi właściwościami, opisywanymi za pomocą zmiennych
  decyzyjnych i parametrów modelu.

Celem modelu matematycznego jest odwzorowanie istoty badanego procesu za

pomocą funkcji matematycznych. Za pomocą reguł matematycznych model

matematyczny sprowadza opis działania procesu (systemu) do opisu jego cech,

przede wszystkim mierzalnych.

Modele matematyczne mogą być formułowane w postaci modeli algebry

liniowej, modeli statystycznych, modeli optymalizacyjnych i modeli

sieciowych.

• Model optymalizacyjny - model matematyczny z wyróżnionym pewnym
  miernikiem realizacji celu (funkcją kryterium) pozwalającym na ocenę jakości
  otrzymanych rozwiązań.

• Model komputerowy - model formalny, w którym za pomocą procedur
  numerycznych przy wykorzystaniu techniki komputerowej opisano zachowanie
  się modelu i jego elementów składowych. Eksperymentowanie na modelu
  komputerowym (symulacja komputerowa) umożliwia przebadanie różnych
  alternatyw decyzyjnych.

6. Podział problemów decyzyjnych zależny od warunków w jakich podejmowana jest decyzja

W warunkach zdeterminowanych, ryzyka, niepewności (niemożliwość przewidywania).

7. Klasyfikacja modeli decyzyjnych

Według liczby funkcji celu	jednokryterialne wielokryterialne
Według postaci analitycznej funkcji celu i warunków ubocznych	liniowe nieliniowe
According to the type of variables	ciągłe
		dyskretne	całkowitoliczbowe boolowskie (binarne)
	Według rodzaju parametrów	deterministyczne
		stochastyczne	probabilistyczne statystyczne strategiczne
	Według liczby stopni procesów decyzyjnych	statyczne
		dynamiczne	ciągłe dyskretne

8. Działy Badań Operacyjnych:

• programowanie liniowe, optymalizacja dyskretna

• zagadnienie transportowe, programowanie dynamiczne

• teoria grafów i sieci

• gry i strategie

• teoria masowej obsługi

• modele decyzyjne gospodarki zapasami

9. 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 liniowo niezależnych żadnego z tych wektorów nie można przedstawić jako kombinacji liniowej pozostałych.

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

Linowo niezależny

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

n

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

Bazą zbioru S nazywamy liniowo niezależny układ wektorów b₁, b₂, …, b_k należących do S zawierają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.

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

Tak

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

Rozwiązanie bazowe układu równań to takie rozwiązanie x_(B) należące do R_n, w którym wszystkie zmienne niebazowe są równe 0.

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

Równe 0.

16. Rozwiązanie bazowe zdegenerowane

Rozwiązanie bazowe jest wtedy zdegenerowane, gdy chociaż jedna ze składowych części bazowej jest równa zero.

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

(ⁿ_m) = n!/(m-n)!m!

18. Postać klasyczna zadania programowania liniowego

postać funkcji celu: (max)z = ∑ c_j*x_j

warunki ograniczające: ∑ a_ij*x_j <= b_j i = 1,2,3,..., m

x_j >= 0 j = 1,2,3,..., n

gdzie: (x1,x2,…..xn ) € Rn wektor zmiennych decyzyjnych

z € R wartość funkcji celu

(c1,c2,….cn) € Rn wektor kosztów (cen) jednostkowych

A = [a_ij ] macierz współczynników nakładów

b =[ b_j ] wektor ograniczeń nakładów

19. Postać standardowa zadania programowania liniowego

Zamiast układu nierówności z postaci klasycznej rozpatrujemy układ równań.

20 . Rozwiązanie dopuszczalne zadania programowania liniowego

Dowolny wektor x spełniający ograniczenia

21 . Rozwiązanie bazowe dopuszczalne zadania programowania liniowego

Rozwiązanie bazowe dopuszczalne stanowią wierzchołki wypukłego zbioru rozwiązań dopuszczalnych.

22. Rozwiązanie optymalne zadania programowania liniowego

Dla dowolnego rozwiązania dopuszczalnego x f(x*) => f(x)

23 . Kiedy zadanie programowania liniowego nazywamy sprzecznym

Kiedy zbiór rozwiązań dopuszczalnych jest zbiorem pustym

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

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

Zbiór C należący do R_n nazywamy wypukłym jeżeli dla dowolnego x₁, x₂ należących do C oraz dla dowolnego 0 <= l <= 1 zachodzi lx₁ + ( 1- l)x₂ należy do C. Punkt x nazywamy punktem wierzchołkowym zbioru wypukłego C wtedy i tylko wtedy, gdy nie można znaleźć punktów x₁, x₂ należących do C spełniających powyższy warunek.

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

Wielościan wypukły

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

Na wierzchołkach zbioru rozwiązań dopuszczalnych

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

Na wierzchołkach zbioru wypukłego rozwiązań dopuszczalnych.

29. Liczba rozwiązań optymalnych zadania programowania liniowego

Może być ich nieskończenie wiele lub w ogóle.

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

To są zmienne, które trzeba dodać w celu uzyskania postaci standardowej.

31. Zmienne sztucznej bazy w zadaniu programowania liniowego

Jeżeli nie mamy podmacierzy jednostkowej to dodajemy zmienną sztucznej bazy.

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

Wprowadzamy zmienną osłabiającą w sytuacji, gdy ograniczenia są w postaci nierówności bez macierzy jednostkowej. Konsekwencja to uzyskanie postaci standardowej.

33. Idea algorytmu simpleks

Znalezienie rozwiązania dopuszczalnego optymalnego .

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

Początkowym rozwiązaniem bazowym są wektory jednostkowe.

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

Aktualne rozwiązanie bazowe.

36. Wyznaczanie elementu centralnego w tablicy simpleksowej

Szukamy największego wskaźnika optymalności (MAX). Ta kolumna w której jest maksymalny wskaźnik optymalności będzie zawierała element centralny, który będzie na przecięciu tej kolumny i wiersza z najmniejszym ilorazem wartości x_b przez element tej kolumny w każdym wierszu.

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

Wtedy gdy wszystkie wskaźniki optymalności są niedodatnie

38. Kiedy zadanie programowania liniowego nie ma skończonego rozwiązania optymalnego (opisz etap algorytmu simpleks).

Kiedy stwierdzamy nieograniczoność rozwiązania optymalnego.

39. Zadanie pierwotne a zadanie poszerzone w metodzie simpleks.

Poszerzone zadanie w metodzie simpleks jest po dodaniu wektora sztucznej bazy.Pierwotne zadanie w metodzie simpleks jest przed dodaniem wektora sztucznej bazy.

40. 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.

41. Możliwe oceny rozwiązania optymalnego zadania PL.

42. Formułowanie parametrycznego zadania programowania liniowego.

43. Postać ogólna zagadnienia transportowego.

Postać funkcji celu:

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

Warunki ograniczające:
i = 1, 2, …, m

j = 1, 2, …, n

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

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

a = [
- wektor dostawy (zasoby dostawców)

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

45. 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.

46. 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.

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

Tak.

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

Tak.

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

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

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

m * n

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

m + n - 1

52. 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).

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

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

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

Jeśli rozwiązanie zad transportowego 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.

55. 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

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

Rozwiązanie jest optymalne, gdy C⁰ ≥ 0

57. 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.

58. Postępowanie w przypadku całkowitej blokady przewozu na wybranej trasie w algorytmie rozwiązywania zadania transportowego.

59. Postępowanie w przypadku częściowej blokady trasy w algorytmie rozwiązywania zadania transportowego.

60. Postać zadania transportowego z kryterium czasu I i II rodzaju.

61. 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)

62. 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.

63. 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.

64. 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.

65. 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.

66. 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.

67. 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).

68. 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).

69. 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.

70. Podaj przykład zastosowania algorytmu wyznaczania przydziału optymalnego o maksymalnym zysku?

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

71. 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.

72. 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.

73. 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.

74. Na czym polega istota metody programowania dynamicznego.

Na zamianie zadania optymalizacyjnego z N zmiennymi decyzyjnymi w N zadań optymalizacyjnych tylko z jedną zmienną decyzyjną, przy czym zadania te są powiązane zależnością rekurencyjną.

75. Do jakiej grupy procesów decyzyjnych należą zagadnienia rozwiązywane metodami programowania dynamicznego.

Wieloetapowe procesy decyzyjne.

76. Jakie własności posiadają tzw. wieloetapowe procesy decyzyjne.

Stan wejściowy procesu do danego etapu, decyzję podejmowaną na każdym etapie, stan wyjściowy procesu z danego etapu.

77. Zinterpretuj (jak rozumiesz) zasadę optymalności Bellmana.

Każde kolejne rozwiązanie jest optymalne niezależnie od początkowego stanu i pierwszych decyzji a tylko od tych bezpośrednio poprzedzających.

78. Zdefiniuj własnymi słowami zadanie wyboru najkrótszej drogi.

Wybieramy najkrótszą drogę cechując wszystkie „przystanki” od końca i wybierając najkrótsze odcinki za każdym razem.

79. Zdefiniuj własnymi słowami zadanie alokacji.

Dokonujemy takiego przydziału rozpatrywanego środka, aby łączny dochód był maksymalny.

80. Zdefiniuj własnymi słowami zadanie załadunku.

Ładujemy ciężarówkę tak, aby wartość załadowanych różnych towarów była maksymalna.

81. Podaj wzór rekurencyjny zadania załadunku.

Max z_o = Σ v_jx_j , gdzie v to zysk a x to ilość.

82. Podaj wzór rekurencyjny zadania alokacji.

Max F = Σ g_kx_k , gdzie iloczyn to dochód z k-tego rodzaju działalności.

83. Podaj przykład problemu decyzyjnego rozwiązywanego z wykorzystaniem algorytmu alokacji.

Wybór miejsc otwarcia x sklepów w y miejscowościach, które przyniosą najwyższy zysk.

84. Podaj przykład problemu decyzyjnego rozwiązywanego z wykorzystaniem algorytmu załadunku.

Załadunek x tonowej ciężarówki y różnymi towarami o maksymalnej wartości.

85. Podaj przykład problemu decyzyjnego rozwiązywanego z wykorzystaniem algorytmu sterowania zapasami.

Ile jakich towarów przechowywać w magazynie i w jakiej kolejności je wydawać.

86. Wymień omawiane na zajęciach problemy rozwiązywane metodami programowania dynamicznego.

Wybór najkrótszej drogi, alokacja zapasów, sterowanie zapasami, problem załadunku.

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.

6. Zagadnienie załadunku i alokacja.

---