Jest to metoda polegająca na badaniu zachowania się systemu przy użyciu modeli realizowanych na maszynach cyfrowych. Pod pojęciem systemu rozumieć będziemy pewien zbiór powiązanych ze sobą obiektów scharakteryzowanych przy pomocy atrybutów (cech), które również mogą być ze sobą powiązane. Zakładamy, że ich struktura nie podlega zmianom, a jedynie cechy poszczególnych obiektów mogą przyjmować różne wartości w kolejnych chwilach czasu tzn. system osiąga kolejne stany pod wpływem zachodzących zdarzeń.

Ile kas ma być czynnych w banku?

Identyfikacja głównych części systemu: stanowiska obsługi i klienci.

Zdefiniowanie każdej operacji:

do systemu przybywa klient - w jaki sposób, np. wg rozkładu Poissona o określonej średniej lub zgodnie z danymi empirycznymi.

klient wybiera kolejkę - w jaki sposób: z reguły najkrótszą a jeśli są jednakowo długie - wg innych kryteriów.

przesuwanie się kolejki - reguła FIFO, czas obsługi losowany z rozkładu empirycznego lub np. normalnego z daną średnią i odchyleniem.

Symulację tego systemu zaczynamy od wylosowania momentu przybycia pierwszego klienta. Posyłamy go do wybranej wg jakiejś reguły kasy, gdzie jest natychmiast obsłużony. Wyznaczamy czas jego obsługi losując z odpowiedniego rozkładu i notujemy moment zakończenia. Następnie losujemy czas przybycia następnego klienta itd. Na każdym etapie musimy uważać, by we właściwej chwili wprowadzić każdego klienta, usunąć go z systemu, uaktualnić kolejkę po zakończeniu każdej obsługi.

W miarę trwania symulacji obliczamy też statystyki np. średni czas oczekiwania, średnia długość kolejki, łączny czas bezczynności kasjerek.

Ta prosta sytuacja ilustruje najważniejsze cechy symulacji:

Jest dobrze dostosowana do problemów, które są trudne lub wręcz niemożliwe do analitycznego rozwiązania.

Możliwość analizy “what if”. Modele optymalizacyjne odpowiadają na pytanie, jakie wartości zmiennych decyzyjnych są najlepsze dla przyjętej funkcji celu. Przyczyną powstania trudności jest zwykle złożoność rozpatrywanego modelu. Zastosowanie zwykłych metod analitycznych wymaga przyjęcia nierealistycznych założeń i uproszczeń. W tej sytuacji decydent może woleć określić zbiór decyzji, symulować rezultaty i obserwować, co się dzieje z kryterium.

Łatwa w użyciu. Symulacja nie wymaga skomplikowanego aparatu matematycznego. Decydent, który zna strukturę systemu może bez trudu opracować jego model przy użyciu aplikacji menadżerskich (np. arkusz kalkulacyjny). Model opisuje problem z punktu widzenia decydenta, który w łatwy sposób może go zrozumieć i kontrolować.

Laboratorium zarządzania. Model ilustruje i pozwala lepiej poznać rzeczywisty proces. Gry kierownicze pozwalają uczestnikom zrozumieć relacje między zmiennymi decyzyjnymi a rezultatami oraz rozwinąć umiejętności decyzyjne.

Nie gwarantuje optymalnego rozwiązania. Podczas eksperymentu badane są tylko warianty podane przez użytkownika. Zawsze mogą istnieć lepsze układy zmiennych decyzyjnych, o których decydent nie ma pojęcia.

Pozorna łatwość stosowania. Często istnieje pokusa by stosować ją tam, gdzie można wyznaczyć rozwiązanie optymalne przy użyciu metod analitycznych. Ponadto nadmiar szczegółów wbudowanych w model może utrudnić przeprowadzenie eksperymentów.

Technika ta jest szeroko używana w biznesie i w instytucjach rządowych. Wg źródeł amerykańskich około 85% organizacji używa różnego rodzaju modeli symulacyjnych. Symulacja przybiera najróżniejsze formy od modelowania prostych systemów dla celów zarządzania operacyjnego (zapasy, produkcja, finanse, obsługa), poprzez gry menadżerskie, do modelowania wielkich systemów (korporacje, ekonomia światowa, pogoda). Symulacją jest również tzw. rzeczywistość wirtualna.

Ogólnie rzecz biorąc model identyfikuje kluczowe elementy problemu oraz ich relacje i ma przetransformować niekontrolowane i kontrolowane (decyzyjne) wejścia w zamierzone dane wyjściowe. Jeśli możemy dokładnie opisać zmienne niekontrolowane to mówimy o symulacji deterministycznej, jeśli zmienne te są opisane rozkładami statystycznymi - o symulacji probabilistycznej. Zmienne mogą mieć charakter dyskretny lub ciągły.

Estymacji parametrów modelu dokonuje się na podstawie bezpośrednich obserwacji lub danych historycznych. Parametry te i założenia modelu powinny być zweryfikowane przez doświadczonych użytkowników lub ekspertów. Po oprogramowaniu modelu, należy go zweryfikować statystycznie wprowadzając doń dane historyczne. W razie potrzeby należy model przebudować.

W przypadku symulacji deterministycznej prowadzimy tylko jeden przebieg dla każdej wartości zmiennej kontrolowanej.

W przypadku symulacji probabilistycznej wartości zmiennych niekontrolowanych są losowane z odpowiednich rozkładów, stąd każdy przebieg daje inne wyniki. By wyniki były statystycznie wiary-godne należy przeprowadzić kilkadziesiąt przebiegów dla każdej wartości zmiennej decyzyjnej.

2. Metoda symulacji - przykład

Firma A konkuruje z firmą B na lokalnym rynku w sprzedaży odkurzaczy Rainbow. Badania wykazały, że chłonność rynku wynosi 1040 szt. rocznie. Sugerowana cena detaliczna wynosi 5000 zł, a cena zakupu od producenta - 4000 zł (dla obu firm).

Dyrektor firmy A chce znać cenę, która pozwoli na maksymalizację rocznego zysku. Nie jest to proste, gdyż udział A w rynku zależy od stosunku cen A i B. Firma B zmienia ceny bez uprzedzenia z tygodnia na tydzień.

Jeśli obie firmy mają jednakowe ceny, A ma 40% udział w rynku. Jeżeli B ma niższą cenę, A traci z tego poziomu 4% udziału za każde 100 zł różnicy, gdy sytuacja jest odwrotna, A zyskuje 1% udziału za każde 100 zł różnicy.

Przeprowadzenie eksperymentu w sytuacji rzeczywistej byłoby zbyt długotrwałe, a ponadto ryzykowne. Lepiej zastosować metodę prób i błędów nie w stosunku do rzeczywistej sytuacji, lecz jej modelu.

Zmienna kontrolowana (decyzyjna): cena sprzedaży A.

Zmienna niekontrolowana: cena sprzedaży B.

Prowadzimy symulację przez np. 20 tygodni dla cen firmy A zmieniających się co 100 zł (4100, 4200, ..., 4900). Razem daje to 9 przebiegów symulacyjnych.

W każdym przebiegu:

W praktyce decydent powinien przeprowadzić dłuższe eksperymenty (52 tygodnie), a ceny konkurenta powinny być bardziej uściślone.

3. Metoda Monte Carlo

Metoda Monte Carlo wywodzi się z poszukiwań prowadzonych podczas II wojny światowej. Naukowcy z laboratorium w Los Alamos chcieli opisać, jak daleko neutrony przenikają przez różne materiały. Zagadnienie było niezmiernie ważne przy projektowaniu urządzeń nuklearnych, a nie istniały odpowiednie metody analityczne. Metoda prób i błędów byłaby zbyt czasochłonna i ryzykowna.

Naukowcy sięgnęli po technikę znaną już od wieku, która została zaniechana ze względu na swą dziwność. Technika ta zakładała użycie znanych fizycznych właściwości i zaobserwowanych prawdopodobieństw do określenia wyniku eksperymentu, który nie mógł być wykonany; oszacowanie wyniku było oparte na przeprowadzonej symulacji eksperymentu. Technice tej nadano nazwę Monte Carlo, gdyż opierała się na tych samych zasadach, co gra hazardowa.

Metoda Monte Carlo to każda metoda wymagająca użycia zachowania losowego do rozwiązania problemu. Metody te są stosowane do szerokich klas problemów deterministycznych i probabilistycznych. Problemy deterministyczne to np. rozwiązywanie równań różniczkowych, znajdowanie pól i objętości, odwracanie macierzy czy obliczanie wartości p. Zastosowania probabilistyczne dotyczą symulacji procesów, które istotnie zawierają zmienne losowe, np. symulacja połączeń telefonicznych przez centralę czy obsługa samochodów na stacji benzynowej.

Zastosowanie metody Monte Carlo do problemów deterministycznych opiera się na prawie wielkich liczb Bernoulliego:

Wychodząc z tego twierdzenia, metoda Monte Carlo może być zastosowana np. do całkowania dowolnych funkcji.

Całkowanie numeryczne oparte na definicji Riemanna jest bardzo dobrą techniką aproksymacji całki z żądaną dokładnością. Zawodzi jednak w przypadku całek nad skomplikowanymi obszarami przestrzeni wielowymiarowych. W tej sytuacji zasadne może być użycie metody Monte Carlo.

Na podstawie danych historycznych zarząd A oszacował rozkład cen firmy B:

W modelu musimy tak generować ceny B, by były one zgodne z zaobserwowanym rozkładem. Dobrym rozwiązaniem jest wykorzystanie generatora liczb pseudolosowych z przedziału [0...1] w taki sposób, by prawdopodobieństwo wylosowanych liczb było dokładnie takie samo jak prawdopodobieństwo powiązanych cen firmy B.

Liczby losowe związane z cenami firmy B:

Prowadzimy symulację przez np. 20 tygodni dla cen firmy A zmieniających się co 100 zł (4100, 4200, ..., 4900). Razem daje to 9 przebiegów symulacyjnych.

W każdym przebiegu:

Zgodnie z wynikami zaprezentowanymi w tabeli, spośród zbadanych cen, 4800 zł/sztukę prowadzi do największego skumulowanego zysku.

W praktyce decydent powinien przeprowadzić kilkadziesiąt dłuższych eksperymentów (52 tygod-nie) i zanalizować wariancję zysku.

Analiza wyników obejmuje przede wszystkim analizę wariancji dla wielu średnich. Testy te pozwalają na sprawdzenie, czy pewne czynniki regulowane w trakcie eksperymentu (tu: cena A) wywierają wpływ, a jeśli tak, to jaki, na kształtowanie się średnich wartości badanych cech (tu: zysk). W naszym przypadku powinniśmy przeprowadzić tzw. klasyfikację pojedynczą mierzącą wpływ pojedynczego czynnika.

We wszystkich testach analizy wariancji warunkiem koniecznym jest założenie jednorodności wariancji (np. test Bartletta).

4. Statystyczne aspekty symulacji

W symulacjach występuje wiele problemów statystycznych, specyficznych i nie - dla tej metody:

• wygenerowanie ciągu liczb losowych o zadanym rozkładzie opisującym zmienną losową,
• statystyczna analiza modelu,
• statystyczna analiza wyników.

W przypadku symulacji stochastycznej podstawowe znaczenie ma generowanie liczb z rozkładu jednostajnego, gdyż przez jego przekształcenie można uzyskać liczby losowe o dowolnym rozkładzie.

Losowy oznacza, że nie da się przewidzieć, jakie liczby otrzymamy.

Spośród różnych metod otrzymywania liczb losowych (specjalne urządzenia, rzuty kostkami, tablice) najwygodniejsze i najszybsze jest generowanie liczb za pomocą zależności rekurencyjnej. Generowane w ten sposób liczby nie są, ściśle rzecz ujmując, losowe i dlatego nazywamy je liczbami pseudolosowymi. Liczby te spełniają warunki 1, 5 i 6, natomiast stopień spełnienia pozostałych warunków zależy od własności stosowanych zależności rekurencyjnych.

Metody generowania liczb pseudolosowych opierają się na koncepcji kongruencji. Dwie liczby całkowite a i b są w konkruencji z modułem m, jeśli ich różnica jest liczbą całkowitą, stanowiącą wielokrotność m. Relację kongruencji zapisujemy jako: a º b (mod m), a jest kongruentne z b modulo m.

Przykład: 1897 º 7 (mod 5)

n_i+1 º [a_*n_i + b] (mod m)

gdzie

n_i, a, b, m są liczbami całkowitymi nieujemnymi, a - stały mnożnik, b - stała dodatkowa, n₀ - wartość początkowa.

Następującymi kolejno po sobie liczbami {n_i} są całkowicie zdeterminowane liczby całkowite tworzące ciąg reszt dla mod m. Oznacza to, że wszystkie n_i < m.

Z liczb występujących w ciągu {n_i} można otrzymać właściwe liczby z przedziału [0...1] tworząc ciąg {r_i} = {n_i/m}.

Czy istnieje najmniejsza wartość i = h, że n_h= n₀, gdzie h jest okresem ciągu? Jeśli bowiem i = h, to n_h+1 = n₁, n_h+2 = n₂, itd. Można wykazać, że taka liczba h zawsze istnieje i że jej wartość maksymalna zależy od m.

Najpopularniejszą metodą tworzenia liczb pseudolosowych opartą na kongruencji jest generator multiplikatywny, w którym stała dodatkowa b=0:

n_i+1 º a_*n_i (mod m)

Generator ten ma b.dobre własności statystyczne tzn. liczby nie są ze sobą skorelowane i mają rozkład równomierny, a przy założeniu pewnych warunków na a, n₀ i m. możemy zapewnić maksymalny okres ciągów h. Ponadto ciągi te można powtarzać, a same obliczenia są b.szybkie.

Podano wiele reguł doboru a, n₀ i m. Dla komputerów dwójkowych o słowie 32-bitowym przyjmuje-my, że m=2³¹-1 (=2147483647). Algorytm wygląda następująco:

• za wartość początkową n₀ podstaw całkowitą liczbę nieparzystą.
• jako a wybierz dużą liczbę całkowitą pierwszą,
• oblicz n₁=a_*n₀ (mod m)
• oblicz pierwszą zmienną losową o rozkładzie równomiernym r₁=n₁/m
• powtarzaj dwa ostatnie kroki w celu otrzymania kolejnych liczb losowych.

Niech p oznacza frakcję takich elementów w zbiorowości statystycznej, które mają pewną wyróżnioną cechę (0<=p<=1); parametr może być interpretowany jako prawdopodobieństwo wylosowania z tej zbiorowości elementu z wyróżnioną cechą.

H₀: p = p₀ wobec H₁: p <> p₀

Niech X oznacza liczbę elementów z cechą wyróżnioną w próbie losowej, a n - liczność próby. Zmienna losowa Z

ma rozkład normalny N(0,1).

Ciąg liczb R’=1-R (R={r_i}) ma też rozkład jednostajny w przedziale [0, 1] i nazywany jest ciągiem przeciwnym. Ciągi takie są ważnym środkiem zmniejszania wariancji w symulacjach stochastycznych.

P = a+(b-a)_*R ma rozkład prostokątny w [a, b].

Ogólna metoda polega na odwróceniu dystrybuanty F(x).

Weź liczbę losową R o rozkładzie jednostajnym w przedziale [0, 1] i rozwiąż równanie F(X) = R lub F(X) = 1-R . Wtedy X ma szukany rozkład i nazywa się liczbą losową o dystrybuancie F(x).

F(x) = 1-e^-lx (x>=0, wartość oczekiwana 1/l).

Weź liczbę losową R o rozkładzie jednostajnym w przedziale [0, 1] i oblicz X = -ln(R)/l.

F(X) = 1-R
1-e^-lX = 1-R
e^-lX = R
-lX = ln(R)
X = -ln(R)/l

Ważnym zastosowaniem liczb losowych o rozkładzie wykładniczym jest generowanie tzw. procesów Poissona.

Liczby losowe o rozkładzie normalnym

Przy użyciu dwóch niezależnych liczb losowych R₁ i R₂ o rozkładzie jednostajnym w [0, 1] można otrzymać dwie niezależne liczby losowe o rozkładzie normalnym N(0,1). Jest to tzw. przekształcenie Boxa-Mullera:

N₁ = (-2 ln(R₁))^1/2 cos(2piR₂)

N₂ = (-2 ln(R₁))^1/2 sin(2piR₂)

Tworząc liczby m+s N₁ i m+s N₂ otrzymujemy zmienne losowe o rozkładzie N(m,s).

Analiza wariancji opiera się na rozkładzie estyma-torów wariancji wokół prawdziwych wariancji z populacji normalnych. Istotą a.w. jest rozbicie na addytywne składniki sumy kwadratów wariancji całego zbioru wyników. Porównanie wariancji wynikającej z działania danego czynnika oraz waiancji resztowej (mierzącej losowy błąd) daje odpowiedź, czy dany czynnik odgrywa istotną rolę w kształtowaniu się wyników eksperymentu.

Klasyfikacja pojedyncza

Sumę kwadratów wariancji ogólnej rozbija się na dwa składniki mierzące zmienność między grupami i wewnątrz grup (resztową). Porównując te wariancje testem F rozstrzygamy, czy średnie grupowe różnią się istotnie od siebie czy nie. Jeśli podział na grupy przebiegał ze względu na różne poziomy badanego czynnika, to można wykryć w ten sposób wpływ poziomu na wartość badanej cechy.

Danych jest k populacji normalnych N(m_i,s_i), i=1,...,k. Wariancje wszystkich populacji są równe (nie muszą być znane). Z każdej z tych populacji wylosowano niezależnie próby o liczebności n_i. Wyniki prób oznaczone są x_ij (j=1,...,n_i), przy czym x_ij=m_i+e_ij, gdzie e_ij jest wartością zmiennej losowej nazywanej składnikiem losowym o rozkładzie N(0,s).

H₀: m₁=m₂=...=m_k wobec H₁: nie wszystkie średnie są równe

Jeśli F>=F_a, to hipotezę o równości średnich w badanych populacjach należy odrzucić, co oznacza udowodnienie istotnego wpływu poziomu czynnika na te populacje.

Jeśli odrzucono hipotezę H₀ należy w dalszym etapie analizy wyników zastosować metodę porównywania wielokrotnego (badanie istotności różnic między wartościami średnimi dla wszystkich par czynnika).

Znane są różne metody zmniejszania nakładu pracy (liczby eksperymentów) niezbędnego do osiągnięcia danego poziomu ufności wyników. Jeśli wykona się n niezależnych obserwacji pewnej wielkości, których odch. stand. jest równe s, to błąd standardowy średniej tych obserwacji wyniesie s/n^1/2. Jeśli wykonamy dwa warianty eksperymentu powtarzając je n₁ i n₂ razy, ich wyniki mają odch. stand. s₁ i s₂, to jednakową dokładność otrzymamy gdy

s₁/n₁^1/2=s₂/n₂^1/2 czyli n₁/n₂=s₁²/s₂².

Ogólnie: jeśli pewien rodzaj eksperymentu redukuje wariancję k-krotnie, to liczbę powtórzeń można zmniejszyć również k-krotnie.

Powtarzanie ciągów liczb losowych

Celem symulacji jest zazwyczaj porównanie różnych możliwości. W takim przypadku eksperymentator powinien odtwarzać i ponownie używać tego samego ciągu zdarzeń do różnych przebiegów (ciąg taki jest funkcją liczb pseudolosowych). W ten sposób uzyskuje pożądane wyniki za pomocą znacznie mniejszej próbki, niż gdyby generował niezależne ciągi w każdym przebiegu.

Ciągi przeciwne liczb losowych R’=1-R

Ten rodzaj symulacji nazywa się od zdarzenia do zdarzenia, gdyż kolejne kroki symulacji związane są z pojawianiem się kolejnych zdarzeń. W tym przypadku zdarzeniami są przybycie jednostki, rozpoczęcie i zakończenie obsługi, a zegar symulacji przesuwa się o czas potrzebny na zajście następnego zdarzenia.

Alternatywnym sposobem reprezentacji upływu czasu jest dzielenie badanego okresu na ściśle określone niezmienne przedziały i obserwowanie zachowań modelu w kolejnych chwilach czasu. To podejście do symulacji nazywane jest symulacją ze stałym krokiem.

Jednym z najszerzej stosowanych modeli zapasów jest RPM (Reorder Point Model); należy tak dobrać punkt ponawiania zamówień i ilość zamawianą, by zminimalizować sumę średnich kosztów utrzymywania, zamawiania i braku zapasów w jednostce czasu.

K_u - jednostkowy koszt utrzymania zapasu
K_z - koszt realizacji zamówienia,
K_b - jednostkowy koszt braku pozycji w magazynie.

Zarządzający pragną zminimalizować łączne koszty KR związane z zapasami. Zaproponowano dwie polityki:

Q = 20 sztuk, R = 2 sztuki,
Q = 10 sztuk, R = 5 sztuk.

Cel: minimalizacja średniego kosztu KR:

KR = K_z + W_m*K_u + B_p*K_b

Zmienne decyzyjne: Q i R.

Zmienne wejściowe niezależne: P (zapotrzebowanie) i CD (czas dostawy).