Vorlesung Simulation Kapitel 1: Simulationsmodelle System, Modell

Vorlesung Simulation
Kapitel 1: Simulationsmodelle
• Modelle von Systemen
• Analyse durch Imitieren der Realität, Durchspielen,
Simulieren
- Alternative:Analytisches Modell
• Beim Simulieren: Daten erfassen und protokollieren
• Daraus Parameter schätzen (estimate), z. B. Maße für Leistung
(performance), Zuverlässikeit (reliability)
Sim1
1
Literatur
• Law & Kelton, Simulation modeling and analysis,
Mc Graw Hill, 3. Auflage, 2000 (auch Paperback)
• Banks, Handbook of simulation, Wiley and Sons, 1998
Sim1
2
System, Modell, Simulation
Gebiet der Angewandten Informatik
• System, konzeptuelles Modell, ausführbares Modell,
mathematische Methoden
Kritische Punkte
• Sehr komplexe Modelle, aber mächtige Werkzeuge
• Rechenaufwand, aber immer schnellere Rechner
• "Eigentlich nur Programmieren", aber für verläßliche Aussagen ist
die sorgfältige Anwendung über Jahrzehnte erarbeiteter Methoden
erforderlich
Sim1
Einige Anwendungsbereiche:
• Produktionsanlagen
• Kommunikationssysteme
• Rechensysteme
• Verkehrssysteme
• Logistik, Transport
• Organisationen wie Call-Center, Krankenhäuser,
Postämter
• Geschäftsprozesse
• Lagerhaltung, Auftragsstrategien
• Finanzsysteme
• Ökologische Systeme
• Militärische Systeme
3
• System: Ausschnitt aus der Lebenswelt, spezieller:
Interagierende Gegenstände mit festen Eigenschaften und
zeitlich sich ändernden Zuständen
- Änderungen sprunghaft zu Zeitpunkten: diskret
- oder stetig mit der Zeit
- oft beides
• Eigenschaften eines Systems können mit einem Modell
untersucht werden: Ein gedachtes oder materielles,
vereinfachtes (abstraktes) Abbild, das die interessierenden
Aspekte so genau wie nötig und möglich wiedergibt.
- Beispiele: Nachbildung im Windkanal
- Strecke s = Geschwindigkeit g * Zeit t oder s = ∫ g dt
- Warteschlangensystem, Warteraum für Kunden, Bediener,
Ankunftsprozeß, Bedienstrategie, Bediendauern
- Umfang = π * Durchmesser
Sim1
4
• Modellklassen
* Statisch - Dynamisch
* Deterministisch - stochastisch
* Stetig (kontinuierlich) - diskret
• Modelle werden
- entworfen
- analysiert (Lösung)
- validiert
• Analytische Lösung: Auflösbare Formel, auch numerisch
• Dynamische Simulation: Durchspielen des Modells
• Statische Simulation: Zuordnung von Eigenschaften zu
Objekten (die modellierten Gegenstände) - „Monte-CarloSimulation“ wenn stochastisch
1.1
Sim1
5
Sim1
6
1
WSS-
Diskrete Ereignissimulation
•
•
•
•
Variabl
en
(DES, discrete-event simulation)
Die Zustände ändern sich sprunghaft zu diskreten Zeitpunkten
Simulationsuhr t für die Modellzeit
Ereignisliste für zukünftige Ereignisse
Beispiel: Warteschlangensystem, Warteraum für Kunden,
Bediener, Ankunftsprozeß, Bedienstrategie, Bediendauern
WSS
Sim1
7
Sim1
8
1.2
Programmkomponenten
• Systemzustand, Variablen
• Simulationsuhr
• Ereignisliste
• Statistische Zähler (statistical counters)
• Initialisierungsroutine
• Zeitführung
• Ereignisroutine
• Bibliotheksprogramme, z.B Zufallszahlen(ZZ)-Generatoren
• Berichtgenerator (report generator)
Sim1
9
Sim1
10
Sim1
11
Sim1
12
1..3
2
1.5
Sim1
13
1.6
Sim1
14
1.7 a - g
Sim1
15
Sim1
16
Sim1
17
Sim1
18
3
Sim1
19
Sim1
20
Sim1
21
Sim1
22
Sim1
24
• Aus (0,1)-gleichverteilten Zufallszahlen solch einer
vorgegebenen Verteilung (random variates) berechnen
• Die Gegenstände des Systems entsprechen Modellobjekten mit
festen Eigenschaften (Attributen) und (Objekt-)zuständen.
Speicherung in Verbunden (record), Listen
• Beispiel: Simulation des Warteschlangensystems
Sim1
23
4
Sim1
25
Sim1
26
Sim1
27
Sim1
28
#include <stdio.h>
#include <math.h>
#include "lcgrand.h" /* Header file for random-number
generator. */
#define Q_LIMIT 100 /* Limit on queue length. */
#define BUSY
1 /* Mnemonics for server's being busy */
#define IDLE
0 /* and idle. */
int
next_event_type, num_custs_delayed, num_delays_required,
num_events, num_in_q, server_status;
float area_num_in_q, area_server_status, mean_interarrival,
mean_service, sim_time, time_arrival[Q_LIMIT + 1],
time_last_event, time_next_event[3], total_of_delays;
FILE *infile, *outfile;
void initialize(void);
void timing(void);
void arrive(void);
void depart(void);
void report(void);
void update_time_avg_stats(void);
float expon(float mean);
Sim1
29
Sim1
30
5
main() /* Main function. */
{
/* Open input and output files. */
infile = fopen("mm1.in", "r");
outfile = fopen("mm1.out", "w");
/* Specify the number of events for the timing function. */
num_events = 2;
/* Read input parameters. */
fscanf(infile, "%f %f %d", &mean_interarrival, &mean_service,
&num_delays_required);
/* Write report heading and input parameters. */
fprintf(outfile, "Single-server queueing system\n\n");
fprintf(outfile, "Mean interarrival time%11.3f minutes\n\n",
mean_interarrival);
fprintf(outfile, "Mean service time%16.3f minutes\n\n",
mean_service);
fprintf(outfile, "Number of customers%14d\n\n", num_delays_required);
/* Initialize the simulation. */
initialize();
Sim1
31
void initialize(void) /* Initialization function. */ {
/* Initialize the simulation clock. */
sim_time = 0.0;
/* Initialize the state variables. */
server_status
= IDLE;
num_in_q
= 0;
time_last_event = 0.0;
/* Initialize the statistical counters. */
num_custs_delayed = 0;
total_of_delays
= 0.0;
area_num_in_q
= 0.0;
area_server_status = 0.0;
/* Initialize event list. Since no customers are present, the
departure
(service completion) event is eliminated from consideration. */
time_next_event[1] = sim_time + expon(mean_interarrival);
time_next_event[2] = 1.0e+30;
}
Sim1
Sim1
35
32
void timing(void) /* Timing function. */
{
int
i;
float min_time_next_event = 1.0e+29;
next_event_type = 0;
/* Determine the event type of the next event to occur. */
for (i = 1; i <= num_events; ++i)
if (time_next_event[i] < min_time_next_event) {
min_time_next_event = time_next_event[i];
next_event_type
= i;
}
/* Check to see whether the event list is empty. */
if (next_event_type == 0) {
/* The event list is empty, so stop the simulation. */
fprintf(outfile, "\nEvent list empty at time %f", sim_time);
exit(1);
}
/* The event list is not empty, so advance the simulation clock. */
sim_time = min_time_next_event;
}
33
void arrive(void) /* Arrival event function. */
{
float delay;
/* Schedule next arrival. */
time_next_event[1] = sim_time + expon(mean_interarrival);
/* Check to see whether server is busy. */
if (server_status == BUSY) {
/* Server is busy, so increment number of customers in queue. */
++num_in_q;
/* Check to see whether an overflow condition exists. */
if (num_in_q > Q_LIMIT) {
/* The queue has overflowed, so stop the simulation. */
fprintf(outfile, "\nOverflow of the array time_arrival at");
fprintf(outfile, " time %f", sim_time);
exit(2);
}
/* There is still room in the queue, so store the time of arrival
of the arriving customer at the (new) end of time_arrival. */
time_arrival[num_in_q] = sim_time;
}
Sim1
/* Run the simulation while more delays are still needed. */
while (num_custs_delayed < num_delays_required) {
/* Determine the next event. */
timing();
/* Update time-average statistical accumulators. */
update_time_avg_stats();
/* Invoke the appropriate event function. */
switch (next_event_type) {
case 1: arrive();
break;
case 2: depart();
break;
}
}
/* Invoke the report generator and end the simulation. */
report();
fclose(infile);
fclose(outfile);
return 0;
}
Sim1
34
else {
/* Server is idle, so arriving customer has a delay of zero.(The
following two statements are for program clarity and do not
affect the results of the simulation.) */
delay = 0.0;
total_of_delays += delay;
/* Increment the number of customers delayed, and make
server busy. */
++num_custs_delayed;
server_status = BUSY;
/* Schedule a departure (service completion). */
time_next_event[2] = sim_time + expon(mean_service);
}
}
Sim1
36
6
void depart(void)
{
int
i;
float delay;
/* Departure event function. */
/* The queue is nonempty, so decrement the number of customers
in queue. */
--num_in_q;
/* Compute the delay of the customer who is beginning service
and update the total delay accumulator. */
delay = sim_time - time_arrival[1];
total_of_delays += delay;
/* Increment the number of customers delayed, and schedule
departure. */
++num_custs_delayed;
time_next_event[2] = sim_time + expon(mean_service);
/* Move each customer in queue (if any) up one place. */
for (i = 1; i <= num_in_q; ++i)
time_arrival[i] = time_arrival[i + 1];
/* Check to see whether the queue is empty. */
if (num_in_q == 0) {
/* The queue is empty so make the server idle and eliminate the
departure (service completion) event from consideration. */
server_status
= IDLE;
time_next_event[2] = 1.0e+30;
}
}
}
else {
Sim1
37
void report(void) /* Report generator function. */
{
/* Compute and write estimates of desired measures of performance. */
Sim1
void update_time_avg_stats(void)
38
/* Update area accumulators for timeaverage statistics. */
{
float time_since_last_event;
/* Compute time since last event, and update last-event-time marker.
*/
time_since_last_event = sim_time - time_last_event;
time_last_event
= sim_time;
/* Update area under number-in-queue function. */
area_num_in_q
+= num_in_q * time_since_last_event;
/* Update area under server-busy indicator function. */
area_server_status += server_status * time_since_last_event;
fprintf(outfile, "\n\nAverage delay in queue%11.3f minutes\n\n",
total_of_delays / num_custs_delayed);
fprintf(outfile, "Average number in queue%10.3f\n\n",
area_num_in_q / sim_time);
fprintf(outfile, "Server utilization%15.3f\n\n",
area_server_status / sim_time);
fprintf(outfile, "Time simulation ended%12.3f minutes", sim_time);
}
}
Sim1
39
float expon(float mean) /* Exponential variate generation function. */
{
/* Return an exponential random variate with mean "mean". */
return -mean * log(lcgrand(1));
}
/* The following 3 declarations are for use of the random-number
generator
lcgrand and the associated functions lcgrandst and lcgrandgt for seed
management. This file (named lcgrand.h) should be included in any
program
using these functions by executing
#include "lcgrand.h"
before referencing the functions. */
float lcgrand(int stream);
void lcgrandst(long zset, int stream);
long lcgrandgt(int stream);
Sim1
41
Sim1
40
/* Prime modulus multiplicative linear congruential generator
Z[i] = (630360016 * Z[i-1]) (mod(pow(2,31) - 1)), based on Marse and
Roberts‘ portable FORTRAN random-number generator UNIRAN. Multiple
(100) streams are supported, with seeds spaced 100,000 apart.
Throughout, input argument
"stream" must be an int giving the
desired stream number. The header file lcgrand.h must be included in
the calling program (#include "lcgrand.h")before using these
functions.
Usage: (Three functions)
1. To obtain the next U(0,1) random number from stream "stream,"
execute
u = lcgrand(stream);
where lcgrand is a float function. The float variable u will
contain the next random number.
2. To set the seed for stream "stream" to a desired value zset,
execute
lcgrandst(zset, stream);
where lcgrandst is a void function and zset must be a long set to
the desired seed, a number between 1 and 2147483646 (inclusive).
Default seeds for all 100 streams are given in the code.
Sim1
42
7
3. To get the current (most recently used) integer in the sequence being
generated for stream "stream" into the long variable zget, execute
zget = lcgrandgt(stream);
where lcgrandgt is a long function. */
/* Generate the next random number. */
float lcgrand(int stream)
{
long zi, lowprd, hi31;
/* Define the constants. */
zi
lowprd
hi31
zi
zrng[stream];
(zi & 65535) * MULT1;
(zi >> 16) * MULT1 + (lowprd >> 16);
((lowprd & 65535) - MODLUS) +
((hi31 & 32767) << 16) + (hi31 >> 15);
if (zi < 0) zi += MODLUS;
lowprd = (zi & 65535) * MULT2;
hi31
= (zi >> 16) * MULT2 + (lowprd >> 16);
zi
= ((lowprd & 65535) - MODLUS) +
((hi31 & 32767) << 16) + (hi31 >> 15);
if (zi < 0) zi += MODLUS;
zrng[stream] = zi;
return (zi >> 7 | 1) / 16777216.0;
#define MODLUS 2147483647
#define MULT1
24112
#define MULT2
26143
/* Set the default seeds for all 100 streams. */
static long zrng[] =
{
1,
1973272912, 281629770, 20006270,1280689831,2096730329,1933576050,
913566091, 246780520,1363774876, 604901985,1511192140,1259851944,
824064364, 150493284, 242708531, 75253171,1964472944,1202299975,
233217322,1911216000, 726370533, 403498145, 993232223,1103205531,
762430696,1922803170,1385516923, 76271663, 413682397, 726466604,
336157058, ... }
Sim1
}
43
void lcgrandst (long zset, int stream) /* Set the current zrng for stream
"stream" to zset. */
{
zrng[stream] = zset;
}
long lcgrandgt (int stream) /* Return the current zrng for stream
"stream". */
{
return zrng[stream];
}
Sim1
=
=
=
=
Sim1
Simulationsergebnisse, Diskussion
Ergebnisse sind abhängig von:
- Systemparametern, hier mittlere Zwischenankunftszeit = 1 min und
mittlere Bedienzeit = 0.5 min
- der Stoppregel: Nach n=1000 Kundenbedienungen
- der Systeminitialisierung, hier leeres System
- den gewählten ZZ-Generatoren und ihrer Initialisierung (seed,
stream)
Zahlen für einen konkreten Simulationslauf:
Mittlere Wartezeit: 0.430 min
Mittlere Anzahl von Kunden in der Warteschlange (WS): 0.418
Auslastung des Bedieners: 0.460
Ende nach 1027.915 min
Schätzungen (estimate); gut oder schlecht?
45
Man könnte auch an stationären Leistungsmaßen (steady-state)
interessiert sein, die sich im allgemeinen nach (sehr) langer
Simulation ergeben. Um diese möglichst kurz halten zu können,
läßt man untypische Zahlen am Anfang der Simulation außer
Betracht
44
Sim1
46
Ereignisgraphen
- Knoten (node, edge): Ereignisse
- Kanten, gerichtet, durchgezogen: Vorplanung eines Ereignisses
-- gezackt: Vorgeplant bei der Initialisierung
- Bsp. WSS:
Die Stoppregel war durch ein bestimmtes Ereignis definiert: Der
1000. Kunde ist fertig bedient
Alternative: Eine feste Endzeit
Sim1
47
Sim1
48
8
Alternative: Eigenes Ereignis für den Bedienungsbeginn:
Sim1
Alternative: Eigenes Ereignis für das Simulationsende:
49
Simulation einer Lagerhaltungsstrategie
Sim1
50
- Zu Beginn jeden Monats werden Z Stück beim Großhändler
bestellt gemäß einer Strategie (s,S)
(policy, inventory system)
• Modell: - Ein Produkt
- Betrachtungszeitraum n Monate
- Kundenbestellungen (demand): D Stück, Zeit dazwischen iid
exponentiell verteilt, im Mittel 0.1 Monate
- Die Kosten dafür sind K + i Z; K: Festkosten (setup cost),
i: Stückkosten (incremental)
- Die Lieferung erfolgt nach einer Zeit, die gleichverteilt zwischen
0.5 und 1 Monat ist
- I(t): Lagerbestand, auch negativ bei unbefriedigten Bestellungen
- Kundenbestellungen werden so weit wie möglich sofort
befriedigt, ein Rest sobald vom Großhändler geliefert wird
- Was nicht geliefert werden kann, erzeugt einen negativen
Lagerbestand I
Sim1
51
Sim1
52
- Lagerkosten (holding cost) h = 1$ pro Stück und Monat
- Festkosten der Lagerung werden nicht berücksichtigt, da bei
allen Strategien gleich
- Auslallkosten bei nicht möglicher Lieferung (shortage): π = 5$
pro Stück und Monat
- Gesamte Lagerkosten und Ausfallkosten pro Monat im Mittel:
Sim1
53
Sim1
54
9
- 9 Strategien:
s = 20 | 20 | 20 | 20 | 40 | 40 | 40 | 60 | 60
S = 40 | 60 | 80 | 100 | 60 | 80 | 100 | 80 | 100
- Simulation, Ereignisse
-- Lieferung vom Großhändler (order arrival)
-- Kunde bestellt (demand)
-- Simulationsende nach n Monaten (end simulation)
-- Bestandsprüfung am Monatsanfang (Evaluate)
1
2
3
4
Sim1
55
Sim1
56
Sim1
57
Sim1
58
Sim1
59
Sim1
60
10
/* External definitions for inventory system. */
#include <stdio.h>
#include <math.h>
#include "lcgrand.h" /* Header file for random-number generator. */
int
amount, bigs, initial_inv_level, inv_level, next_event_type,
num_events, num_months, num_values_demand, smalls;
float area_holding, area_shortage, holding_cost, incremental_cost,
maxlag, mean_interdemand, minlag, prob_distrib_demand[26],
setup_cost, shortage_cost, sim_time, time_last_event,
time_next_event[5], total_ordering_cost;
FILE *infile, *outfile;
void initialize(void);
void timing(void);
void order_arrival(void);
void demand(void);
void evaluate(void);
void report(void);
void update_time_avg_stats(void);
float expon(float mean);
int
random_integer(float prob_distrib []);
float uniform(float a, float b);
Sim1
61
Sim1
main() /* Main function. */ {
int i, num_policies;
/* Open input and output files. */
infile = fopen("inv.in", "r");
outfile = fopen("inv.out", "w");
/* Specify the number of events for the timing function. */
num_events = 4;
/* Read input parameters. */
fscanf(infile, "%d %d %d %d %f %f %f %f %f %f %f",
&initial_inv_level, &num_months, &num_policies,
&num_values_demand, &mean_interdemand, &setup_cost,
&incremental_cost, &holding_cost, &shortage_cost, &minlag,
&maxlag);
for (i = 1; i <= num_values_demand; ++i)
fscanf(infile, "%f", &prob_distrib_demand[i]);
/* Write report heading and input parameters. */
fprintf(outfile, "Single-product inventory system\n\n");
fprintf(outfile, "Initial inventory level%24d items\n\n",
initial_inv_level);
fprintf(outfile, "Number of demand sizes%25d\n\n",
num_values_demand);
Sim1
62
fprintf(outfile, "Distribution function of demand sizes ");
for (i = 1; i <= num_values_demand; ++i)
fprintf(outfile, "%8.3f", prob_distrib_demand[i]);
fprintf(outfile, "\n\nMean interdemand time%26.2f\n\n",
mean_interdemand);
fprintf(outfile, "Delivery lag range%29.2f to%10.2f months\n\n",
minlag, maxlag);
fprintf(outfile, "Length of the simulation%23d months\n\n",
num_months);
fprintf(outfile, "K =%6.1f
i =%6.1f
h =%6.1f
pi =%6.1f\n\n",
setup_cost, incremental_cost, holding_cost, shortage_cost);
fprintf(outfile, "Number of policies%29d\n\n", num_policies);
fprintf(outfile, "
Average
Average");
fprintf(outfile, "
Average
Average\n");
fprintf(outfile, " Policy
total cost
ordering cost");
fprintf(outfile, " holding cost
shortage cost");
63
Sim1
/* Run the simulation varying the inventory policy. */
for (i = 1; i <= num_policies; ++i) {
/* Read the inventory policy, and initialize the simulation.
*/
fscanf(infile, "%d %d", &smalls, &bigs);
initialize();
/* Run the simulation until it terminates after an endsimulation event
(type 3) occurs. */
do {
/* Determine the next event. */
timing();
/* Update time-average statistical accumulators. */
update_time_avg_stats();
/* Invoke the appropriate event function. */
64
switch (next_event_type) {
case 1: order_arrival();
break;
case 2: demand();
break;
case 4: evaluate();
break;
case 3: report();
break;
}
/* If the event just executed was not the end-simulation event
type 3), continue simulating. Otherwise, end the simulation
for the current (s,S) pair and go on to the next pair (if
any). */
} while (next_event_type != 3);
}
/* End the simulations. */
fclose(infile);
fclose(outfile);
return 0;
}
Sim1
65
Sim1
66
11
void initialize(void) /* Initialization function. */
{
/* Initialize the simulation clock. */
sim_time = 0.0;
/* Initialize the state variables. */
inv_level
= initial_inv_level;
time_last_event = 0.0;
/* Initialize the statistical counters. */
total_ordering_cost = 0.0;
area_holding
= 0.0;
area_shortage
= 0.0;
/* Initialize the event list. Since no order is outstanding, the
order-arrival event is eliminated from consideration. */
time_next_event[1] = 1.0e+30;
time_next_event[2] = sim_time + expon(mean_interdemand);
time_next_event[3] = num_months;
time_next_event[4] = 0.0;
}
Sim1
void timing(void) /* Timing function. */
{
int
i;
float min_time_next_event = 1.0e+29;
next_event_type = 0;
/* Determine the event type of the next event to occur. */
for (i = 1; i <= num_events; ++i)
if (time_next_event[i] < min_time_next_event) {
min_time_next_event = time_next_event[i];
next_event_type
= i;
}
/* Check to see whether the event list is empty. */
if (next_event_type == 0) {
/* The event list is empty, so stop the simulation */
fprintf(outfile, "\nEvent list empty at time %f", sim_time);
exit(1);
}
/* The event list is not empty, so advance the simulation clock.*/
sim_time = min_time_next_event;
}
67
void order_arrival(void) /* Order arrival event function. */
{
/* Increment the inventory level by the amount ordered. */
Sim1
68
void demand(void) /* Demand event function. */
{
/* Decrement the inventory level by a generated demand size. */
inv_level += amount;
inv_level -= random_integer(prob_distrib_demand);
/* Since no order is now outstanding, eliminate the order-arrival
event from consideration. */
time_next_event[1] = 1.0e+30;
}
/* Schedule the time of the next demand. */
time_next_event[2] = sim_time + expon(mean_interdemand);
}
Sim1
69
Sim1
70
void evaluate(void) /* Inventory-evaluation event function. */
{
/* Check whether the inventory level is less than smalls. */
if (inv_level < smalls) {
/* The inventory level is less than smalls, so place an order
for the appropriate amount. */
amount = bigs - inv_level;
total_ordering_cost += setup_cost + incremental_cost * amount;
/* Schedule the arrival of the order. */
time_next_event[1] = sim_time + uniform(minlag, maxlag);
}
/* Regardless of the place-order decision, schedule the next
inventory evaluation. */
time_next_event[4] = sim_time + 1.0;
}
void report(void) /* Report generator function. */
{
/* Compute and write estimates of desired measures of performance.
*/
Sim1
Sim1
71
float avg_holding_cost, avg_ordering_cost, avg_shortage_cost;
avg_ordering_cost = total_ordering_cost / num_months;
avg_holding_cost = holding_cost * area_holding / num_months;
avg_shortage_cost = shortage_cost * area_shortage / num_months;
fprintf(outfile, "\n\n(%3d,%3d)%15.2f%15.2f%15.2f%15.2f",
smalls, bigs,
avg_ordering_cost + avg_holding_cost + avg_shortage_cost,
avg_ordering_cost, avg_holding_cost, avg_shortage_cost);
}
72
12
void update_time_avg_stats(void) /* Update area accumulators for
time-average
statistics. */
{
float time_since_last_event;
/* Compute time since last event, and update last-event-time
marker. */
time_since_last_event = sim_time - time_last_event;
time_last_event = sim_time;
/* Determine the status of the inventory level during the previous
interval. If the inventory level during the previous interval
was negative, update area_shortage. If it was positive,
update area_holding. If it was zero, no update is needed. */
if (inv_level < 0)
area_shortage -= inv_level * time_since_last_event;
else if (inv_level > 0)
area_holding += inv_level * time_since_last_event;
}
Sim1
float expon(float mean)
73
int random_integer(float prob_distrib[])
/* Random integer generation
function. */
{
int
i;
float u;
/* Generate a U(0,1) random variate. */
u = lcgrand(1);
/* Return a random integer in accordance with the (cumulative)
distribution function prob_distrib. */
for (i = 1; u >= prob_distrib[i]; ++i)
;
return i;
}
Sim1
74
Sim1
76
/* Exponential variate generation function.
*/
{
/* Return an exponential random variate with mean "mean". */
return -mean * log(lcgrand(1));
}
float uniform(float a, float b)
/* Uniform variate generation
function. */
{
/* Return a U(a,b) random variate. */
return a + lcgrand(1) * (b - a);
}
Sim1
75
Diskussion der Ergebnisse:
Die günstigsten Gesamtkosten kann man nicht raten, die Simulation
ist schon erforderlich.
Man darf aus diesem einen Simulationslauf (run) nicht schließen, daß
die Strategie (s,S) = (20,60) die beste ist, weil dabei die gesamten
Kosten am niedrigsten sind.
Weitere Läufe können niedrigste Kosten bei einer anderen Strategie
ergeben.
Um zu einer zuverlässigeren Aussage zu kommen, muß man viele
Simulationsläufe machen und diese statistisch auswerten.
Sim1
77
Sim1
78
13
Durchführung einer Simulationsstudie
• Ähnlich wie beim Software-Engineering ist auch hier die
Herstellung des Simulationsprogramms nur ein kleiner Teil.
• Wichtige andere Aspekte betreffen die Analyse des Problems,
• das konzeptionelle Modell,
• die eingehenden Parameter und Verteilungen,
• die Validierung des Modells,
• den Entwurf der Experimente,
• die Statistik der Ergebnisse,
• die Analyse der Ergebnisse,
• die Dokumentation,
• die Präsentation der Resultate.
Sim1
79
1 Problem formulieren und Studie planen
a Projektmanager benennt ein Problem
b Treffen Projektmanager, Simulationsfachleute, Problemfachleute
- Ziel der Studie
- Genaue Fragen, die die Studie beantworten soll
- Leistungsmaße zum Vergleich verschiedener
Systemkonfigurationen
- Was soll das Modell erfassen?
- Welche Systemkonfigurationen sollen modelliert werden?
- Welche Software?
- Terminplanung
2 Informationen sammeln, Modellieren
a Information über das System und die operationellenVorgänge
- Eine Person, ein Dokument sind unzureichend
Sim1
81
- Ansichten der Problemfachleute
- Zeitliche und finanzielle Randbedingungen
f Es muß keine eins-zu-eins-Korrespondenz zwischen
Systemelementen und Modellelementen geben
g Regelmäßige Abstimmung mit dem Projektmanager oder anderen
leitenden Beteiligten
3 Ist das konzeptuelle Modell adäquat (valid)?
a Strukturierte Inspektion des konzeptuellen Modells
b Kritische Begutachtung mit Projektmanager und Problemfachleuten
- Vor Beginn der Programmierung zur Vermeidung von
Mehrfacharbeit
- Überprüfung der Annahmen auf Korrektheit und Vollständigkeit
Sim1
83
Sim1
80
- Problemfachleute könnten ungenaue Informationen haben kompetente Gesprächspartner suchen
- Operationelle Vorgänge nur informell definiert?
b Daten für Modellparameter und Verteilungen von Eingangsgrößen
c Die gesammelten Informationen kommen in ein Dokument und
bilden das konzeptuelle Modell
d Ggf. Leistungsdaten des existierenden Systems sammeln, zur
Modellvalidierung
e Detailliertheit des Modells hängt ab von:
- Ziele des Projekts
- Leistungsmaße
- Verfügbaren Daten
- Aspekten der Glaubwürdigkeit des Modells
- Rechnerbeschränkungen
Sim1
82
4 Programm und Verifikation
a Universelle Programmiersprache (C, MODULA 2, Java,...)
- Billiger bereitzustellen, schneller, flexibler, Entwicklung
umständlicher daher teurer
b Simulationssoftware (Arena, Simplex 2 oder 3,...)
- Teuer in der Anschaffung (Demo-Ware manchmal umsonst),
komfortabler, einfachere Entwicklung daher billiger, weniger
transparente Modelle daher schlechter zu validieren, aber
abstrakter daher besser zu validieren
c Verifikation gegen das konzeptuelle Modell
5 Pilot-Läufe (pilot run)
a Zur Validierung
6 Ist das programmierte Modell adäquat?
a Wenn möglich, Ergebnisse der Pilotläufe mit Meßergebnissen am
System vergleichen
Sim1
84
14
b Kritische Begutachtung mit Projektmanager und Problemfachleuten
hinsichtlich Korrektheit
c Welche Modellteile beeinflussen die Leistungsmaße stark
(Sensibilitätsanalyse, sensivity analysis) und müssen daher
besonders sorgfältig modelliert werden?
7 Experimente planen
a Welche Tupel von Eingangsparametern und Verteilungen
(Konfiguration)?
b Für jedes Tupel:
- Länge der einzelnen Läufe
- Länge der Einschwingphase
- Anzahl unabhängiger Simulationsläufe mit unterschiedlichen ZZ;
dient der statistischen Relevanz (Genauigkeit, Zuverlässigkeit) der
Ergebnisse
8 Produktionsläufe
Sim1
85
Andere Simulationsarten: Kontinuierliche Simulation
Zeit ist Kontinuum
Zustandsvariablen ändern sich stetig oder auch in Sprüngen
Beschreibung oft durch (Systeme von) Differentialgleichungen
(DGln.)
Gegeben: Zustand zur Zeit 0, gesucht danach
Einfacher Fall, selten: Analytische Lösung
Sonst: Numerische Lösungen, z.B. mit Runge-Kutta
Manche Simulationspakete können auch das, z.B. Arena, Simplex 2
Bekanntes Beispiel: Parasit-Wirt-Modelle
t Zeit
x(t) Größe der Wirt-Population
y(t) Größe der Parasit-Population
stetig!
Sim1
87
9 Analyse der Ergebnisse
a Leistung einer Konfiguration
b Vergleich mehrerer
10 Dokumentation, Präsentation, Nutzung der simulierten Resultate
a Alle Schritte dokumentieren
b Präsentation:
- Modellbildungsprozeß, Validierung, simulierte Resultate vorstellen
- dient der Glaubwürdigkeit (credibility)
- Animation zur Kommunikation mit (wichtigen) Personen, die nicht
vertraut mit den Details sind
c Die simulierten Ergebnisse gehen in Entscheidungsprozesse ein,
sofern sie adäquat und glaubwürdig sind
Sim1
86
DGl für die Wirtspopulation: dx/dt = r x(t) - a x(t) y(t)
r Geburts- minus natürliche Sterberate der Wirte
a x(t) y(t) Verlust pro Zeit durch Gefressen werden
DGl für die Parasitpopulation: dy/dt = -s y(t) + b x(t) y(t)
- s y(t) Abnahme pro Zeit der Parasiten in Abwesenheit von Beute
b x(t) y(t) Zunahme der Parasiten pro Zeit durch Fressen von
Wirten
Gegeben: x(0) > 0, y(0) > 0 (Anfangswertproblem für die DGln.)
Sim1
88
Gemischte Simulation (diskret - kontinuierlich)
Diskretes Ereignis
- ändert kontinuierliche Zustandsvariable
- ändert die Veränderungsregel einer kontinuierlichen
Zustandsvariablen
Eine kontinuierliche Zustandsvariable überschreitet einen
Schwellwert und löst so ein diskretes Ereignis aus
Beispiel: Tanker werden im Dock gelöscht und füllen dort Behälter
Tanker- und Behälterfüllung verändert sich stetig
Diskrete Ereignisse: Tanker leer, Behälter voll, Mitternacht - Dock
schließt, 6 Uhr morgens - Dock öffnet
Sim1
89
Sim1
90
15
Monte-Carlo-Simulation
Statische stochastische Modelle, Zeit spielt keine besondere Rolle
Beispiel Integral
Sei die ZV X zwischen a und b gleichverteilt, U(a,b), und
Y = (b-a) g(X). Dafür ist der Erwartungswert
Man schätzt nun der Erwartungswert von Y:
Sim1
91
Simulation: Vorteile, Nachteile, typische Fehler
• Die meisten Modelle realer Systeme sind so kompliziert,
daß es keine analytische Lösung gibt
• Es können Leistungsmaße nichtexistierender Systeme
geschätzt werden
• Dabei können Alternativen verglichen werden
• Simulation ist in der Regel viel einfacher als Messungen
am System
• Die Zeit kann gedehnt oder gerafft werden
• Simulationsmodelle sind sehr intuitiv, analytische oft kaum
Sim1
93
Typische Fehler
• Bei Beginn der Studie sind die Ziele nicht klar
• Der Detailliertheitsgrad des Modells ist nicht angemessen
• Während der Studie wird nicht mit den Auftraggeber kommuniziert
• Die Ergebnisse werden vom Auftraggeber mißverstanden
• Die Simulationsstudie wird als Programmierübung mißverstanden
• Sie wird von Leuten durchgeführt, die zu wenig von der
Methodologie verstehen
• Die Datenbasis ist zu spärlich
• Die Software ungeeignet
• Die Software zu benutzerfreundlich, sodaß versteckt ist, was im
einzelnen im Modell vor sich geht
• Der Glaube, solche komfortable Software ersetzt Kompetenz der
Modellierer
Sim1
95
Sim1
92
Nachteile
• Stochastische Simulation ermöglicht nur Schätzungen
• Daher ist Simulation nicht gut für Optimierung
• Simulationsmodell sind im Allgemeinen teuer und
zeitraubend
• Die viele berechneten Zahlen, noch mehr Animationen,
bewirken manchmal ein ungerechtfertigtes Vertrauen in
die ermittelten Ergebnisse, auch wenn das Modell nicht
adäquat ist und somit nichts Relevantes aussagen kann
Sim1
94
• Mißbrauch von Animation
• Mißverständnis der zufälligen Modellelemente
• Beliebige, falsche Zufallsverteilungen für externe
Eingaben, zum Beispiel Lasten
• Falsche Unabhängigkeitsannahmen bei der statistischen
Analyse von Ergebnissen
• Die Ausgabe einer Replikation als wahres Ergebnis
ansehen
• Alternativen auf der Basis je einer Replikation vergleichen
• Falsche Leistungsmaße benutzen
Sim1
96
16
Konstante Zeitinkremente
Sinnvoll bei regelmäßigen Ereignissen, zum Beispiel im
Bereich Ökonomie (jeden Monat, jedes Jahr,...)
Sim1
97
17