osungsgutesungsgute12.125section*.105 alt-nissskalaltnissskala22.150section*.221

1

Glossar

Mike Huftle

28. Juli 2006

Inhaltsverzeichnis

1 A 21.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2 B 42.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

3 C 63.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

4 D 74.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

5 E 105.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

6 F 136.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

7 G 147.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

8 H 168.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

9 I 179.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

10 J 1810.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

11 K 1911.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2

12 L 2412.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

13 M 2713.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

14 N 3114.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

15 O 3315.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

16 P 3616.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

17 Q 3917.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

18 R 4018.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

19 S 4219.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

20 T 4720.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

21 U 4821.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

22 V 4922.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

23 W 5123.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

24 X 5324.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

25 Y 5425.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

26 Z 5526.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

3

1 A

1.1

AbbruchkriteriumSiehe Stoppregel

AbhangigesMerkmal

(abhangigeVariable)

In der Statistik wird zwischen unabhangigen und abhangigen Merkmalen (Va-riablen) unterschieden. Erstere sind die Einflussgroßen eines statistischen Mo-dells, letztere die beeinflussten Großen. Wird z.B. das Wachstum einer Pflan-ze betrachtet, so ist der Niederschlag ein unabhangiges (beeinflussendes) Merk-mal und die Große der Pflanze ein abhangiges (beeinflusstes) Merkmal.

Adjazenzmatrix Die Adjazenzmatrix ist eine Darstellung von Kantenbeziehungen gerichte-ter und ungerichteter Graphen in Form einer Matrix. Bei n Knoten ergibt sicheine nn-Adjazenzmatrix. Gibt es eine Kante von Knoten A nach B, so wird ander Postion (A,B) in der Matrix eine 1 eingetragen, andernfalls eine 0. Adja-zenzmatrizen sind immer symmetrisch.

Bei Graphen mit bewerteten Kanten wird anstelle der 1 die Bewertung derKante in der Adjazenzmatrix eingetragen. Nicht vorhandene Kanten werden -je nach Anwendungsfall - z.B. mit einer großen negativen Zahl bewertet (dieverhindern soll, dass diese ”Kante“ benutzt wird).

Algorithmus Ein Algorithmus ist eine genau definierte Verarbeitungsvorschrift zur Losungeines Problems oder einer bestimmten Problemklasse. Typischerweise wird einAlgorithmus durch eine endliche Folge von Anweisungen beschrieben, die nach-einander ausgefuhrt und oft in festgelegter Weise wiederholt werden. Sehr ver-breitet sind Algorithmen in der Informatik und der Mathematik.

Algorithmusvon Dijkstra

Der Algorithmus von Dijkstra, benannt nach seinem Erfinder, Edsger Dijkstra,sucht den kurzesten Weg zwischen zwei Knoten in einem zusammenhangen-den, bewerteten Graphen. Ebenfalls lasst sich der kurzeste Weg von einem Kno-ten zu allen anderen Knoten eines Graphen berechnen. Das Laufzeitverhaltendes Algorithmus ist O(n¡sup¿2¡/sup¿).

4

Algorithmusvon Kruskal

Der Algorithmus von Kruskal ist ein Algorithmus zur Berechnung von mi-nimal spannenden Baumen in zusammenhangenden, ungerichteten und be-werteten Graphen. In unzusammenhangenden Graphen findet der Algorithmuseinen Wald von spannenden Baumen fur jede der Zusammenhangskomponenten.Das Laufzeitverhalten ist O (m log n).

Algorithmusvon Prim

Der Algorithmus von Prim ist ein Algorithmus zur Berechnung von mini-mal spannenden Baumen in zusammenhangenden, ungerichteten, bewer-teten Graphen. Das Laufzeitverhalten des Algorithmus von Prim kann mitO(n¡sup¿2¡/sup¿) abgeschatzt werden. Durch eine verbesserte Implementierungreduziert sich dies auf O(m log n).

ArithmetischesMittel

Das arithmetische Mittel (Mittelwert) wird berechnet, indem n Werte eines me-trisch skalierten Merkmals addiert werden und das Ergebnis durch n geteilt wird.Das Arithmetische Mittel beschreibt die mittlere Große eines Merkmals in einemDatensatz. Fur verschiedene Fragestellungen konnen jedoch andere Mittelwert-bildungen aussagekraftigere Ergebnisse liefern (z.B. geometrischer Mittelwert).

AssoziationsregelnAssoziationsregeln sind Methoden des Data Mining und dienen dazu, Bezie-hungen innerhalb großer Datenmengen zu entdecken. Bekanntestes Bei-spiel ist die so genannte Warenkorbanalyse, mit der Beziehungen der Form

”wenn Produkt A gekauft wird, dann wird mit Wahrscheinlichkeit p auch Pro-dukt B gekauft“, gefunden werden konnen.

Ausreißer Ein Ausreißer im Sinne der Statistik ist ein Merkmalswert, der fur die vorliegen-den Daten unplausibel ist bzw. nicht den Erwartungen an dieses Merk-mal entspricht. Welche Werte als Ausreisser definiert werden, wird durch einenStreuungsbereich um den Erwartungswert definiert. Werte außerhalb dieses In-tervalls werden als Ausreißer bezeichnet. Die Ursache von Ausreißern sindin der Regel fehlerhafte Messungen, ein falsches Ablesen von Messgeraten odereine fehlerhafte Dateneingabe. Zur statistischen Uberprufung auf Ausreißer exi-stieren verschiedene Tests, z.B. der Ausreißertest nach Grubbs.

5

2 B

2.1

Baum Ein Baum ist in der Graphentheorie ein zusammenhangender Wald. Jede Zusam-menhangskomponente eines Waldes ist ein Baum, so dass ein Wald aus einemoder mehreren Baumen besteht.

Bayes-Theorem

Das Bayes-Theorem (oder auch Satz von Bayes) ist nach dem Mathemati-ker Thomas Bayes benannt. Es gibt an, wie mit bedingten Wahrscheinlichkeiten gerechnet wird. Der Satz von Bayes erlaubt in gewissem Sinn das Um-kehren von Schlussfolgerungen: Die Berechnung von P(Ereignis — Ursache) isthaufig einfach, aber oft ist eigentlich P(Ursache — Ereignis) gesucht, also einVertauschen der Argumente. Dies kann folgendermaßen berechnet werden:

P (A/B) =P (B/A) · P (A)

P (B)(1)

Hierbei ist P(A) die A-Priori-Wahrscheinlichkeit fur ein Ereignis A und P( B— A) die Wahrscheinlichkeit fur ein Ereignis B, unter der Bedingung, dass Aauftritt. Die Korrektheit des Satzes folgt unmittelbar aus der Definition derbedingten Wahrscheinlichkeit.

BeschreibendeStatistik

Die beschreibende Statistik (deskriptive Statistik) ist ein Teilgebiet der Statistik,welches die (grafische) Aufbereitung und die Charakterisierung der zuanalysierenden Daten durch Kenngroßen beinhaltet. Wichtige Darstellungs-formen der beschreibenden Statistik sind Histogramme, Streudiagramme undBoxplots. Haufig verwendete Kenngroßen sind Lagemaße und Streuungsmaße.

BewertungsmodellBei Bewertungsmodellen sind im Gegensatz zu den Optimierungsmodellen dieHandlungsalternativen explizit gegeben und es muss eine Entscheidung zwi-schen diesen Handlungsalternativen anhand der Praferenzen der oder desEntscheider(s) getroffen werden. Einige der Modelle berucksichtigen auch meh-rere Umweltzustande, deren Eintrittswahrscheinlichkeiten unsicher oder stocha-stisch sind.

6

Bin-Packing-Problem

Das Bin Packing-Problem beschreibt eine Problemklasse der kombinatorischenOptimierung, welche hauptsachlich bei der Verladung und Verpackung vonWaren Bedeutung hat.In der Grundform des Bin Packing-Problems wird eine minimale Anzahl anBehaltern (z.B. LKWs) gesucht, in die eine bestimmte Anzahl von Gegenstandenverpackt werden. Die Gegenstande werden durch Große und/oder Gewicht be-schrieben, die Behalter durch ein maximales Volumen bzw. ein maximal auf-nehmbares Gewicht.

Boxplot Ein Boxplot ist ein Instrument der beschreibenden Statistik. Er fasst verschie-dene Maße der zentralen Tendenz, Streuung und Schiefe eines minde-stens intervallskalierten Merkmals zusammen. Meist werden in einem Boxplotdas obere und untere Quantil, der Median, der untere und obere Extremwertsowie - falls vorhanden - Ausreißer eines Merkmals dargestellt. Die Lange derBox gibt den Interquartilsabstand (interquartile range, IQR) an. Dieser ist einMaß fur die Streuung der Verteilung. Die Lage des Medians in der Box gibteinen Eindruck von der Schiefe der Verteilung des Merkmals. Die Extremwertesind beobachtete Merkmalswerte, die noch innerhalb eines bestimmten Abstan-des von der Box liegen (in der Regel der 1,5-fache IQR).

Brieftrager-problem

Das Brieftragerproblem (Chinese Postman Problem) ist ahnlich dem Tourenpla-nungsproblem aufgebaut. Es werden ebenfalls kurzeste Touren gesucht, wobeijedoch jede Kante (Straße) des Graphen mindestens ein- oder sogar zweimaldurchlaufen werden muss. Oft lasst es sich auch nicht vermeiden, dass mancheStraßen ein weiteres Mal durchlaufen werden mussen, ohne Post zu verteilen(Leerwege,unproduktive Wege). In der Regel liegt das Ziel eines Brieftragerpro-blems darin, diese Leerwege zu minimieren.

7

3 C

3.1

Chi-Quadrat-Test

Der Chi-Quadrat-Test ist ein Maß fur den Zusammenhang zwischen zwei Merk-malen. Der Chi-Quadrat-Test vergleicht die beobachteten Haufigkeiten der Aus-pragungskombinationen zweier Merkmale mit den theoretisch Haufigkeiten, diebei Unabhangigkeit der Merkmale zu erwarten waren. Der Wert des Chi-Quadrat-Tests ist bei empirischer Unabhangigkeit der Merkmale 0.

Clusteranalyse Das Wort Clusteranalyse ist der Oberbegriff fur eine Vielzahl verschiedener Me-thoden, mit denen Daten in aussagekraftige Klasseneingeteilt werdenkonnen ohne die Klassen von vornherein zu kennen. Beispielsweise werden in derBiologie die verschiedenen Arten nach Ahnlichkeitskriterien in zusammengehori-ge Stamme, Klassen, Familien usw. eingeteilt. Die verschiedenen Methoden derClusteranalyse unterscheiden sich hauptsachlich nach dem Unahnlichkeitsmaß(welches die Unterschiedlichkeit zwischen zwei Objekten bewertet) und nachdem Vorgehen bei der Clusterung.

ColumnGeneration

Der Column Generation-Ansatz ist eine Moglichkeit, auch sehr große lineareProgramme relativ effizient zu losen. Es werden nur die Variablen des Optimie-rungsmodells in der Losungsfindung berucksichtigt, die das Potential haben, dieWerte der Zielfunktion zu verbessern. Das ursprungliche Problem wird hierzuin ein so genanntes Masterproblem undSubprobleme aufgeteilt. Das Ma-sterproblem ist das ursprungliche Problem, jedoch nur mit einer Teilmenge derVariablendes Optimierungsmodells. Das Subproblem ist ein neu erzeugtes Opti-mierungsproblem, mittels dessen eine neu in das Masterproblem aufzunehmendeVariable bestimmt wird.

Cross-Impact-Analyse

Die Cross-Impact-Analyse ist eine Prognosetechnik, die in der Szenarioanaly-se eingesetzt wird. Sie modelliert und analysiert die Zusammenhange zwischenmoglicherweise auftretenden Ereignissen. Dabei liegt der Schwerpunkt auf denWechselwirkungen zwischen verschiedenen Ereignissen.

Mittels der Cross-Impact-Analyse kann die Wahrscheinlickeiten des Eintretenseines Ereignisses in Abhangigkeiten von anderen Ereignissen bestimmt werden.

8

4 D

4.1

Data Mining Data Mining ist ein analytischer Prozess zur Datenexploration. Es werdengroße Datenmengen auf systematische, nicht-offensichtliche Zusam-menhange oder Muster untersucht. Sind solche Zusammenhange gefunden, sokonnen diese auch auf neue Daten angewendet werden. Die meisten Anwen-dungen des Data Mining haben das Ziel Zusammenhange zu erklaren um Vor-hersagen treffen zu konnen. Methoden des Data Mining sind beispielsweise dieClusteranalyse, die Klassifikation oder die Regressionsanalyse.

DataWarehouse

Ein Data Warehouse ist ein umfassendes Konzept zur Entscheidungsun-terstutzung. Kern ist eine integrierte Datenbank mit entscheidungsrelevantenInformationen, die aus den operativen Datenbanken und externen Quellen be-darfsgerecht entnommen und aufbereitet werden. Wichtige Komponenten desData Warehouse sind Softwarewerkzeuge und Anwendungsprogramme (z.B. On-line Analytical Processing, Data Mining), mit denen die Daten des Data Ware-house abgefragt, analysiert und prasentiert werden konnen.

Datenbank,objektorien-

tierte

Im Gegensatz zu den in der Praxis am haufigsten eingesetzten relationalen Da-tenbanksystemen bestehen objektorientierte Datenbanksysteme aus einer hier-archisch organisierten Menge von Objekten. Hierbei ist ein Objekt ein realerGegenstand oder Sachverhalt, welcher durch Attribute beschrieben wird, undder mittels Methoden angesprochen werden kann. Methoden sind die Aktionen,welche auf einem Objekt durchgefuhrt werden konnen.

Datenbank,relationale

Eine relationale Datenbank basiert auf einem relationalen Datenbankmodell,das von E. F. Codd 1970 prasentiert wurde. Relation ist ein mathematischerAusdruck, welcher eine Tabelle beschreibt. Die meisten in der Praxis eingesetz-ten Datenbanksysteme basieren auf relationalen Datenbanken. SQL ist eine weitverbreitete Abfragesprache fur relationale Datenbanken.

DeskriptiveStatistik

Siehe Beschreibende Statistik

9

Determinanteeiner Matrix

Die Determinante det(A) einer nxn-Matrix A ist nach dem Laplace’schen Ent-wicklungssatz definiert als:

det(A) =n∑

j=1

(−1)i+j aij · det(Aij) (2)

wobei A¡sub¿ij¡/sub¿ die (n-1)(n-1)-Untermatrix ist, die aus A durch Streichender i-ten Zeile und der j-ten Spalte entsteht. Wenn A eine obere (untere) Drei-ecksmatrixist, d.h. es gibt nur Nullen unterhalb (oberhalb) der Hauptdiagonale,dann ist det(A) das Produkt der Elemente der Hauptdiagonale.

Die Determinate gibt Auskunft daruber, ob eine Gleichung eindeutig losbarist oder nicht: Ist det(A) = 0, dann heißt die Matrix A singular und die Glei-chung Ax = b ist nicht eindeutig losbar. Wenn det(A) ungleich 0 ist, dann ist Aregular, die Gleichung ist eindeutig losbar und alle Spalten (Zeilen) der Matrixsind linear unabhangig.

DichotomesMerkmal

Ein dichotomes Merkmal besitzt genau zwei Merkmalsauspragungen (z.B.Geschlecht: mannlich-weiblich).Manchmal ist es erforderlich Merkmale kunstlich zu dichotomisieren. Dann wirdbeispielsweise ein rationalskaliertes Merkmal in zwei Gruppen unterteilt (z.B.Große: ¡ 180 cm, ≥ 180 cm).

DiskretesMerkmal(diskreteVariable)

Ein diskretes Merkmal (eine diskrete Variable) hat endlich oder abzahlbar un-endlich viele Auspragungen.

DiskursiveEntschei-

dungsmetho-den

Diskursive Entscheidungsmethoden sind inexakte Methoden der systema-tischen Problemstrukturierung. Sie dienen der Abgrenzung und Zerlegungschlecht strukturierter oder schlecht definierter Probleme.

DispersionsproblemeAufgabe bei Dispersionsproblemen ist, eine Anzahl vorgegebener Objekte ineinem definierten Raum moglichst weit voneinander entfernt zu platzie-ren. Solche Probleme treten auf, wenn sich Objekte so wenig wie moglich storensollen (Rundfunksender, Standortwahl im Einzelhandel).Fast alle Dispersionsprobleme sind NP-schwer und daher nur mit heurstischenMethoden losbar.

10

Divide andConquer-

Prinzip

In der Informatik steht Divide and Conquer fur die Vorgehensweise, große Pro-bleme effizienter zu losen, indem diese in kleinere Teilprobleme zerlegt werden,die einfacher zu handhaben sind als das Ausgangsproblem. Die Losungen derTeilprobleme fließen in die Losung des Gesamtproblems ein. Diese Vorgehens-weise kann rekursiv erfolgen, d.h. die Teilprobleme konnen wiederum in nocheinfacher zu handhabende Teilprobleme zerlegt werden und so weiter.

DualeVerfahren

Duale Verfahren gehen von einer dual zulassigen Losungaus, die zunachstbestimmt wird. Unter Beibehaltung der dualen Zulassigkeit wird die primaleZulassigkeit iterativ verbessert, bis mit der ersten, primal und dual zulassigenLosung die optimale Losung bestimmt wurde. Beispiele fur duale Verfahrensind das duale Simplexverfahren fur lineare Optimierungsprobleme oder derAlgorithmus von Dijkstra zur Bestimmung kurzester Wege in einem Graphen.

Dualitat Zu vielen primalen Optimierungsmodellen lasst sich ein duales Modell kon-struieren. Anschaulich entspricht die Dualisierung einer Spiegelung des Pro-blems: Nebenbedingungs- werden zu Zielfunktionskoeffizienten und umgekehrt.Die Anzahl der Nebenbedingungen im primalen Modell bestimmt die Anzahlder Variablen im dualen Modell und umgekehrt. Es lasst sich beweisen, dassprimales und duales Modell denselben optimalen Zielfunktionswert haben. Au-ßerdem gibt es enge Beziehungen zwischen den jeweiligen optimalen Losungen(z.B. Satz vom komplementaren Schlupf). Das duale Modell ist oftmals ein-facher zu losen als das primale. Daher wird die Dualitatsbeziehung in dualenVerfahren ausgenutzt.

DynamischeOptimierung

Bei der Dynamischen Optimierung werden Optimierungsmodelle betrachtet, dieso in einzelne Stufen (z.B. Zeitabschnitte) zerlegt werden konnen, dass die Ge-samtoptimierung durch eine stufenweise, rekursiveOptimierung ersetzbarist. Es handelt sich also um Methoden zur Losung mehrstufiger Prozesse, beidenen die Entscheidung jeder Stufe die Ausgangslage der nachsten Stufe beein-flusst. Anwendungen sind u.a. die Bestellmengen- und Losgroßenplanung.

11

5 E

5.1

Effizienz vonAlgorithmen

Eine wichtige Eigenschaft von Algorithmen ist ihre Effizienz. Diese wird durchmehrere Kriterien bestimmt: DieLaufzeiteffizienz, die Speichereffizienz unddie Kognitive Effizenz (d.h. Verstandlichkeit der Implementierung). Laufzeit-und Speichereffizienz hangen nicht nur vom Algorithmus, sondern auch von derHardware und den konkreten Eingabedaten ab. Die theoretische Berechnungder Effizienz eines Algorithmus erfolgt anhand der Anzahl an benotigten Re-chenschritten.

Eigenvektoren Eigenvektoren x einer Matrix A sind Vektoren, fur die gilt:

A · x = λ · x, x 6= 0 (3)

x wird Eigenvektor von A zum Skalar λ genannt, dem so genannten Eigenwert.

Symmetrische Matrizen haben die Eigenschaft, dass zu jedem k-fachen Eigen-wert λ1, λ2, ..., λk genau k linear unabhangige Eigenvektoren x1, x2, ..., xk

existieren. Diese sind orthogonal zueinander.

Eigenwerte Siehe Eigenvektoren

Entscheider Entscheider ist in der Entscheidungstheorie die Bezeichnung fur eine Person,welche eine Entscheidung trifft. Der Entscheider wird bei seiner Entscheidungs-findung durch Methoden aus unterschiedlichen Bereichen unterstutzt (z.B. Ent-scheidungstheorie, Spieltheorie, Optimierung).

Entscheidung Unter einer Entscheidung wird in der Entscheidungstheorie die Auswahl einervon mehreren moglichen Handlungsalternativen verstanden. Eine Ent-scheidung soll rational und (sub)optimal sein. Sie ist (sub)optimal, wenn sie furden Entscheider zum (naherungsweise) großtmoglichen Nutzen fuhrt. Rationalist sie, wenn sie nicht zu Widerspruchen in den Vorstellungen des Entscheidersfuhrt.

12

EntscheidungsmodellEntscheidungsmodelle dienen der Vorbereitung und dem Treffen von Entschei-dungen. Sie bestehen im Allgemeinen aus Handlungsalternativen(Entscheidungsvariablen),verschiedenen Umweltzustanden und einer Zielfunktion (oder mehreren Ziel-funktionen) des Entscheiders.

EntscheidungsproblemDas Entscheidungsproblem ist das Problem, wie man vorgehen sollte, um diebeste Entscheidungzu treffen. D.h. welche Methoden konnen angewandtwerden? Welche Fragen konnen gestellt werden? Welche Schritte sollten unter-nommen werden und wie sieht die beste Entscheidung aus?

EntscheidungstheorieDie Entscheidungstheorie beschaftigt sich mit der Formulierung von Ent-scheidungsmodellen sowie mit Methoden und Verfahren zur Bestimmung(sub)optimaler Entscheidungen.

EntscheidungsvariableEine Entscheidungsvariable ist eine Einflussgroße eines realen Systemsbzw.eines Optimierungsmodells oder Entscheidungsmodells, die vom Entschei-der beeinflusst werden kann. Im Unterschied hierzu kann ein Parameter nichtbeeinflusst werden.

Erklarungsmo-dell

Erklarungsmodelle geben eine formale Darstellung eines Systemsund sei-ner Komponenten sowie der kausalen, zeitlichen oder raumlichen Zusam-menhange zwischen abhangigen und unabhangigen Variablen sowie Parameterndes Systems.

Erlangverteilung Die Erlangverteilung ist eine statistische Wahrscheinlichkeitsverteilung (genau-er: eine Gammaverteilung), die zur Modellierung der Intervalle zwischen Tele-fonanrufen entwickelt wurde. Sie wird vor allem in der Warteschlangentheorieeingesetzt, um die Verteilung der Wartezeiten zwischen zwei Kunden zubeschreiben.

Eroffnungsver-fahren

Eroffnungsverfahren sind Heuristikenzur Berechnung einer zulassigen (Ausgangs-) Losung eines Optimierungsmodells. Die zulassige Losung wird durch sukzes-sive Aufnahme von Losungselementen konstruiert. Beispiele sind die Nordwe-steckenregel, die Sweep-Heuristik oder Greedy-Heuristiken.

13

Erwartungswert Der Erwartungswert einer Zufallsvariablen ist eine Große der Wahrscheinlich-keitstheorie. Er ergibt sich (gemaß dem Gesetz der großen Zahl) bei einer sehrgroßen Anzahl von Wiederholungen eines Experiments als der Mittelwert dergemessenen Werte. Formal ist der Erwartungswert einer diskreten Zufalls-große definiert als Summe der Produkte aus einem zufalligen Wert und derentsprechenden Wahrscheinlichkeit:

E(X) =∑

i

xi · p(xi) (4)

Im Fall stetiger Zufallsgroßen ist der Erwartungswert definiert als:

E(x) =∫ ∞

−∞x · f(x)dx (5)

mit der Dichtefunktion f(x).

Expertensystem Ein Expertensystem ist ein Informationssystem, das fachspezifische Kennt-nisse (das Wissen von Experten) in einem abgegrenzten Anwendungsbereichverfugbar macht. Wesentliche Bestandteile sind eine Wissensbasis (Datenbankmit Expertenwissen), eine Problemlosungskomponente (Inferenzkomponen-te) und eine Erklarungskomponente, welche das Zustandekommen der Pro-blemlosung erlautert.

ExplorativeDatenanalyse

Die explorative Datenanalyse ist ein wichtiges Teilgebiet der Statistik. Sie um-fasst Methoden zur Analyse von Daten mittels graphischer Verfahren oder ma-thematischer Methoden, welche (unbekannte) Zusammenhange innerhalbder Daten aufdecken sollen.

14

6 F

6.1

Faktorenanalyse Die Faktorenanalyse ist ein statistisches Verfahren zur Datenreduktion. Eswird haufig in der sozialwissenschaftlichen und psychologischen Forschung ein-gesetzt. Mit der Faktorenanalyse wird nach Dimensionen gesucht, mittels dererVariablen mit statistisch ahnlichen Eigenschaften zu Faktoren zusammengefasstwerden konnen. Die wichtigsten Verfahren sind:

• Hauptkomponentenanalyse, Hauptfaktorenanalyse (deskriptiv, explorativ)

• konfirmatorische Faktorenanalyse (strukturprufend)

Funktional-effiziente

Losung

Bei Entscheidungs- und Optimierungsproblemen mit mehreren Zielenspricht man von einer funktional-effizienten Losung, wenn eine Verbesserung ineinem Zielkriterium nur durch die Verschlechterung in einem anderen Zielkrite-rium erreicht werden kann.

Fuzzy-Set(Fuzzy-Menge,

UnscharfeMenge)

Ein Fuzzy Set (Fuzzy-Menge, Unscharfe Menge) ist eine unscharfe Menge -im Gegensatz zur klassischen Mengenlehre (bei der ein Element nur ineiner Menge liegen kann oder nicht, z.B. ”kalt“ - ”warm“). In der unscharfenMengenlehre gehort ein Element jedoch nur graduell zu einer Fuzzy-Menge (z.B.gehort ”lauwarm“ zu ”warm“ und auch etwas zu ”kalt“). Die Zugehorigkeit zusolch einem Fuzzy-Set wird durch eine Zugehorigkeitsfunktion beschrieben.

15

7 G

7.1

GanzzahligeOptimierung

Bei ganzzahligen Optimierungsproblemen durfen einige oder alle Variablennur ganzzahlige Werte annehmen. Beispiele sind die Bestimmung der Pro-duktionsmengen von Stuckgutern oder die Entscheidung uber die Annahme oderAblehnung eines Auftrages. Im ersten Fall ergibt sich ein (gemischt-) ganzzah-liges, im zweiten ein (gemischt-) binares Optimierungsmodell. Ein gemischt-ganzzahliges Modell hat sowohl ganzzahlige als auch nicht-ganzzahlige (re-ellwertige) Variablen.

Gemischt-ganzzahlige

Optimierung

Siehe Ganzzahlige Optimierung

GenetischeAlgorithmen

Genetische Algorithmen bilden den Evolutionsprozess der Natur nach,bei dem sich die besten Arten weiterentwickeln und schlecht angepasste Artenaussterben. In Optimierungs- und Entscheidungsmethoden werden genetischeAlgorithmen als Heuristiken zur Suche nach (sub) optimalen Problemlosungeneingesetzt.

GeometrischesMittel

Das geometrische Mittel ist ein Lagemaß der beschreibenden Statistik. Es wirdals n-te Wurzel aus dem Produkt aller n Werte eines Merkmals berechnet. Eswird insbesondere bei der Beschreibung von Wachstumsprozessen eingesetzt undlaßt sich als mittlere Wachstumsrate interpretieren.

Gradient Ein Gradient ist ein Vektor, welcher in die Richtung des steilsten Anstieges einerFunktion zeigt. Der Betrag des Gradienten entspricht der Starke des Anstieges.

GradientenverfahrenViele Verfahren zur Losung nichtlinearer Optimierungsprobleme sind Gra-dientenverfahren. Sie beruhen darauf, dass der Gradientenvektor einer zu ma-ximierenden Zielfunktionf immer die Richtung des steilsten Anstiegs von f aneiner Stelle x angibt. Gradientenverfahren fur Maximierungsprobleme bewegensich iterativ so lange in Richtung eines Anstiegs der Zielfunktion, bis sie einenPunkt erreichen, in dem die Funktion nicht mehr ansteigt. Dann beginnt dernachste Iterationsschritt mit der Neuberechnung des Gradienten. Bei konvexenOptimierungsproblemen konnen Gradientenverfahren eine optimale Losung

16

mit beliebiger Genauigkeit bestimmen. Andernfalls liefern diese Verfahren inder Regel nur suboptimale Losungen.

Graph Ein Graph G besteht aus einer Menge V von Knoten (z.B. Orten) und einer Men-ge von Kanten, welche die Knoten verbinden (z.B. Strassen). Es wird zwischenungerichteten Kanten [i,j] und gerichteten Kanten (Pfeilen, Bogen)(i,j) von i nach j unterschieden. Ein Graph mit ungerichteten Kanten wird einungerichteter Graph genannt, einer mit gerichteten Kanten ein gerichte-ter Graph. Die Kanten eines Graphen konnen bewertet sein (z.B. mit Kosten,Streckenlangen, Kapazitaten).

Graph,vollstandiger

Ein Graph ist vollstandig, wenn jedes Knotenpaar i und j durch eine Kante [i,j]bzw. zwei Pfeile (i,j) und (j,i) verbunden ist.

Graph, zusam-menhangender

Ein Graph ist zusammenhangend, wenn jedes Knotenpaar i und j durch einenWeg im Graphen verbunden ist. Ein zusammenhangender Teilgraph wird auchZusammenhangskomponente genannt.

Graphentheorie Die Graphentheorie ist ein Teilgebiet der Mathematik, das die Eigenschaften vonGraphen untersucht und Algorithmenzur Losung von Graphenproblemenbereitstellt.

Greedy-Heuristik

Greedy-Heuristiken streben in jedem Schritt eines Algorithmus nach derbestmogli-chen Verbesserung des Zielfunktionswertesoder der bestmoglichen Erfullungvon Nebenbedingungen, ohne die folgenden Schritte zu berucksichtigen. Ein Bei-spiel eines Greedy-Verfahrens ist die Methode des nachsten Nachbarn furdas Traveling Salesman-Problem. Beginnend beim ersten Knoten wird stets derKnoten neu in die Rundreise aufgenommen, der vom zuletzt eingefugten Knotendie geringste Entfernung aufweist.

GrundgesamtheitDie Grundgesamtheit ist eine in der Statistik haufig verwendete Men-ge. Sie umfasst alle Objekte, die fur eine zu analysierende Fragestellung rele-vant sind. Wird beispielsweise die Sterblichkeit von mannlichen Rauchern inDeutschland untersucht, so bilden alle mannlichen Raucher in Deutschland dieGrundgesamtheit. Ublicherweise wird nur eine Stichprobe aus der Grundge-samtehit untersucht.

17

8 H

8.1

HandlungsalternativeEine Handlungsalternative ist eine von mehreren moglichen Handlungen, die einEntscheider zur Losung eines Entscheidungsproblems durchfuhren kann.

Handlungsreisendenproblem(TravellingSalesmanProblem)

Das Handlungsreisendenproblem gehort zu den Problemen der kombinatori-schen Optimierung. Die grundlegende Vorstellung ist die, dass ein Handlungs-reisender n Kunden besucht und am Ende seiner Reise wieder zum Ausgangs-punkt zuruckkehrt. Dabei muss jeder Kunde mindestens einmal besucht werden.Die Lange der gesamten Reise soll dabei minimiert werden. Es stellt sich also dieFrage, in welcher Reihenfolge die Kunden besucht werden sollen. In der Praxistritt das Problem z.B. in der Tourenplanung auf.

Haufigkeits-verteilung

Eine Haufigkeitsverteilung ist eine Darstellungsform der beschreibenden Sta-tistik. Zu jedem, in den Daten vorkommenden Wert eines Merkmals, gibt dieHaufigkeitsverteilung an, wie oft dieser Wert vorkommt. Haufigkeitsverteilungenkonnen als Grafik, als Wertetabelle oder als mathematische Funktion dargestelltwerden.

Hesse-Matrix Die Hesse-Matrix ist die Matrix der zweiten partiellen Ableitungen einer min-destens zweimal differenzierbaren Funktion.

Heuristik Als Heuristik werden in der Optimierung nicht-exakte Methoden fur schlechtstrukturierte Problemstellungen bezeichnet. Heuristiken reduzieren den Losungs-aufwand und konnen somit auch Probleme losen, die fur exakte Optimierungs-methoden zu komplex sind. Heuristiken suchen im potentiellen Losungsraumnach bestimmten Regeln und schließen zur Komplexitatsreduktion Teile desLosungsraumes von der Suche aus. Deshalb kann das Auffinden einer Opti-mallosung nicht garantiert werden.

18

9 I

9.1

InformationssystemInformationssystem sind technische Systeme, zur computergestutzten (oder auchcomputergesteuerten) Erfassung, Speicherung, Verarbeitung, Analyse,Darstellung und Ubertragung von Informationen. Sie bestehen im We-sentlichen aus der hierfur notwendigen Computerhardware, aus Software (meistauch Datenbanken) und den Informationen (Daten).

Zu den Informationssystemen gehoren beispielsweise Expertensysteme, Management-Informationssysteme, Geoinformationssysteme oder Produktionssteuerungssy-steme.

Initialisierung Als Initialisierung wird die Bestimmung erster, initialer Werte fur die Ent-scheidungsvariablen bei der Losung eines Optimierungsmodells bezeichnet. Auf-bauend auf dieser ersten Losung konnen - gemaß dem jeweiligen Verfahren -weitere Losungen erzeugt werden.

Intervallskala Bei der Intervallskala ist die Reihenfolge der Merkmalsauspragungen festgelegt,und der Abstand zwischen zwei Auspragungen laßt sich sachlich begrunden. DerNullpunkt der Skala und die Einheiten der Skalierung sind mehr oder wenigerwillkurlich festgelegt. Siehe auch Skalierung.

Inverse einerMatrix

Eine quadratische nxn-Matrix ist invertierbar (regular), wenn ihre Determi-nante ungleich 0 ist. Nicht invertierbare Matrizen werden als singular bezeich-net. Wenn eine Matrix invertierbar ist, dann gibt es eine Matrix A¡sup¿-1¡/sup¿,die Inverse von A, so dass gilt:

AA−1 = A−1A = I (6)

mit der Einheitsmatrix I. Die Inverse kann mit dem Gaußschen Eliminations-verfahren berechnet werden.

19

10 J

10.1

20

11 K

11.1

Kennzahl Kennzahlen fassen bestimmte, interessante Sachverhalte zusammen. Informatio-nen werden zu Kennzahlen aufbereitet, indem sie ”verdichtet“ werden, d.h. dieInformationen werden so zusammengefasst, dass ihr Informationsgehalt zu-nimmt. Kennzahlen werden insbesondere in der Betriebswirtschaft und Technikzur Analyse und Steuerung von Prozessen eingesetzt.

Klasse Eine Klasse im Sinne der Statistik fasst eine Gruppe von gleichartigen Ob-jekten zusammen. Die Objekte innerhalb einer Klasse sind sich ahnlich, wohin-gegen sich die Objekte verschiedener Klassen unahnlich sind. Die Ahnlichkeitoder Unahnlichkeit von Objekten wird anhand von Klassifikationskriterien fest-gemacht.

Klassifikation Bei der Klassifikation werden einzelne Objekte bereits bekannten Klassen zuge-ordnet (im Gegensatz zur Clusteranalyse, bei der die Klassen nicht von vorn-herein bekannt sind).

Knapsackproblem(Rucksackpro-

blem)

Das Knapsackproblem gehort zu den Problemen der kombinatorischen Opti-mierung. Die grundlegende Vorstellung, von der das Knapsackproblem ausgeht,ist die eines Wanderers, der seinen Rucksack fur eine Wanderung packenwill. Er mochte n Gegenstande (i=1, ..., n) mitnehmen, die jeweils ein Volumena¡sub¿i¡/sub¿ und einen Nutzen c¡sub¿i¡/sub¿ haben. Es sollen nun Gegenstandeim Rucksack mit dem Volumen B untergebracht werden, so dass der Gesamtnut-zen fur den Wanderer maximiert wird. In der Praxis kommen solche Problemez.B. bei der Maschinenbelegung, in der Beschaffung oder bei der Verschnittop-timierung vor.

Knotengrad Als Grad eines Knotens in einem Graphen wird die Anzahl der von ihmausgehenden und bei ihm eingehenden Kanten bezeichnet. Bei gerichte-ten Graphen wird zwischen Eingangsgrad (Anzahl der eingehenden Bogen) undAusgangsgrad (Anzahl der ausgehenden Bogen) unterschieden.

21

KnowledgeDiscovery

Als Knowledge Discovery wird die automatische (maschinelle) Extraktionvon Wissen aus großen Datenbestanden bezeichnet. Knowledge Discovery wirdhaufig synonym mit Data Mining verwendet.

Komplexitats-theorie

Die Komplexitatstheorie beschaftigt sich damit, generelle Aussagen uberdie Komplexitat von Problemen sowie uber den Rechenaufwand von Al-gorithmen zu treffen. Beide Aspekte sind eng miteinander verbunden. Lasstsich der Rechenaufwand eines Algorithmus durch ein, von der Problemgroßeabhangiges, Polynom nach oben beschranken, so spricht man von einem effizi-enten Verfahren. Bei nicht-effizienten Verfahren wachst die Rechenzeit ebensowie die Losungsmenge mit zunehmender Problemgroße exponentiell.

Probleme bzw. Modelle, fur die ein effizientes Losungsverfahren bekannt ist,werden als polynomial losbar und die ubrigen werden als NP-schwer, NP-hartoder NP-vollstandig bezeichnet. Wahrend z.B. lineare Optimierungsmodelle undKurzeste-Wege-Probleme polynomial losbar sind, gehoren die meisten Proble-me der kombinatorischen Optimierung zur Klasse der NP-schweren Probleme.Fur polynomial losbare Probleme konnen exakte Verfahren angewendet wer-den. Bei NP-schweren Problemen in praxisrelevanten Großenordnungen werdenHeuristiken eingesetzt.

KombinatorischeOptimierung

Gegenstand der Kombinatorischen Optimierung ist es, unter der Vielzahl mogli-cher kombinatorischer Anordnungen von Objekten die optimale Anord-nung zu finden, also beispielsweise eine optimale Platzierung von Personen amTisch oder eine kurzeste Rundtour. Ein typisches Problem der kombinatori-schen Optimierung ist das Tourenplanungsproblem. Die meisten kombinatori-schen Probleme sind NP-schwer und werden deshalb mit Heuristiken gelost.

KonfidenzintervallKonfidenz- oder Vertrauensintervalle sind aus einer Stichprobe berechnete Inter-valle, in denen ein geschatzter Parameter der Verteilung der Grundgesamtheitmit großer Wahrscheinlichkeit liegt. Solche Parameter sind z.B. das arith-metische Mittel oder die Varianz.Die untere (obere) Grenze eines Konfidenzintervalls heißt untere (obere) Konfi-denzgrenze.

22

KonkaveFunktion

Eine Funktion f ist konkav, wenn fur alle x¡sub¿1¡/sub¿ , x¡sub¿2¡/sub¿ und alleλ aus [0, 1] gilt:

f(λ · x1 + (1− λ)x2) ≥ λ · f(x1) + (1− λ) · f(x2) (7)

D.h. der Raum auf und unter dem Graphen von f ist konvex.

KontingenztabelleEine Kontingenztabelle (Kontingenztafel) ist eine Darstellungsform der beschrei-benden Statistik fur nominalskalierte oder ordinalskalierte Merkmale. Sie zeigtdie gemeinsame empirische Verteilung von zwei oder mehr Merkmalen. In denFeldern der Kontingenztabelle werden die Haufigkeiten fur die einzelnen Aus-pragungskombinationen zweier oder mehrerer Merkmale ausgewiesen. Siehe auchChi-Quadrat-Test.

KonvergenzgeschwindigkeitUnter Konvergenzgeschwindigkeit versteht man die Geschwindigkeit, mit dersich die Glieder einer konvergenten Folge (x¡sub¿i¡/sub¿) dem Grenzwert xnahern. Es wird zwischen linearer, superlinearer sowie p-ter Konvergenzordnungunterschieden.

Lineare Konvergenzgeschwindigkeit liegt vor, falls es ein 0 ¡ c ¡ 1 gibt,so dass:

||xi+1 − x|| ≤ c · ||xk − x||, k = 0, 1, ...

Es handelt sich um superlineare Konvergenz, falls die Folge schneller als li-near konvergiert. Dies liegt beispielsweise vor, falls die obige Ungleichung nichtnur mit einem konstanten c gilt, sondern mit einer gegen Null strebenden Zah-lenfolge (c¡sub¿k¡/sub¿) konvergiert.

Konvergenz der Ordnung p mit p¿1 bedeutet, dass ein c¿0 existiert, sodass

||xi+1 − x|| ≤ c · ||xk − x||p, k = 0, 1, ... (8)

Fur p=2 spricht man von quadratischer Konvergenz.

23

KonvexeFunktion

Eine Funktion f ist konvex, wenn fur alle x¡sub¿1¡/sub¿ , x¡sub¿2¡/sub¿ und alleλ aus [0, 1] gilt:

f(λ · x1 + (1− λ)x2) ≤ λ · f(x1) + (1− λ) · f(x2) (9)

D.h. der Raum auf und uber dem Graphen von f (der Epigraph von f) ist kon-vex.

KorrelationsanalyseDie Korrelationsanalyse ist eine Methode der Statistik und untersucht den Zu-sammenhang zwischen Merkmalen von Objekten. Zur Quantifizierung solcherZusammenhange werden Korrelationskoeffizienten verwendet.

KorrelationskoeffizientDer Korrelationskoeffizient ist ein Maß fur die Starke von Zusammenhangenzwischen Merkmalen von Objekten, wobei eine ganze Reihe solcher Maße exi-stiert. Welches Maß angewendet wird, hangt von der Skalierung der untersuchtenMerkmale ab.

Kovarianz Die Kovarianz cov (X,Y) ist ein Maß fur den Zusammenhang zwischenzwei ZufallsgroßenX und Y. Sie beschreibt den Grad des miteinander Variie-rens von X und Y.

Die Kovarianz wird berechnet zu:

cov(X, Y ) = E[(X − µx)(Y − µY )] (10)

Durch die Normierung der Kovarianz cov(X,Y) mit dem Produkt der Standard-abweichungen von X und Y werden die Maßstabs- bzw. Streuungsunterschiedezwischen den Merkmalen X und Y relativiert. Dies fuhrt auf den Korrelations-koeffizienten.

Kreis Siehe Zyklus

24

Kuhn-Tucker-Bedingungen

Das Theorem von Kuhn und Tucker charakterisiert die Eigenschaften eineroptimalen Losung fur ein nichtlineares Optimierungsmodell und wirdvon vielen Methoden der nichtlinearen Optimierung als Optimalitatskriteriumverwendet.Wenn die Zielfunktionf und die Nebenbedingungen g¡sub¿i¡/sub¿ eines Optimie-rungsmodells stetig differenzierbar sind, so kommt mit der Lagrange-Funktion

L(x, u) = f(x)− uT · g(x) (11)

x* nur als optimale Losung in Frage, wenn hierzu ein Vektor u* so genannterLagrange-Multiplikatoren existiert, so dass folgende Gleichungen gelten:

Lx(x∗, u∗) ≤ 0, x ∗T ·Lx(x∗, u∗) ≤ 0, x∗ ≥ 0Lu(x∗, u∗) ≥ 0, u ∗T ·Lu(x∗, u∗) = 0, u∗ ≥ 0

wobei L¡sub¿x¡/sub¿ bzw. L¡sub¿u¡/sub¿ die ersten partiellen Ableitungen vonL nach x bzw. u sind. Ist ausserdem f konkav, sind alle g¡sub¿i¡/sub¿ konvex, undbesitzt die Losungsmenge einen inneren Punkt, so ist x* eine optimale Losungdes Problems.

KunstlicheIntelligenz

(KI)

Die Kunstliche Intelligenz ist ein Teilgebiet der Informatik mit interdisziplinaremCharakter. Ziel der KI ist es, Maschinen zu entwickeln, die sich verhalten, alsverfugten sie uber menschliche Intelligenz. Hierzu gehort insbesondere eine intel-ligente Wissensreprasentation und Wissensverarbeitung sowie die Nachahmungdes menschlichen Problemloseverhaltens mit Computern.

Kurzeste-Wege-Problem

Das Kurzeste-Wege-Problem besteht darin, kurzeste Wegezwischen einigenoder allen Knotenpaaren eines gerichteten Graphen zu bestimmen. Kurzeste-Wege-Probleme lassen sich mit verschiedenen Algorithmen der Graphentheorieeffizient losen (z.B. Algorithmus vonn Dijkstra, A*-Algorithmus).

25

12 L

12.1

Lagemaße Lagemaße sind statistische Kenngroßen fur die Lage der Merkmalswerte.Sie sollen Auskunft daruber geben, wo sich das ”Zentrum“ der Merkmalswertebefindet. Wichtige Lagemaße sind der Arithmetische Mittelwert, der Medianund der Modalwert.

LaufzeitverhaltenMit dem Laufzeitverhalten eines Algorithmus wird die benotigte Anzahl ele-mentarer Rechenschritte in Abhangigkeit von der Problemgroße nbeschrieben. Wenn Anweisungen einmal oder hochstens einige Male ausgefuhrtwerden, dann hat ein Algorithmus eine konstante Laufzeit (1).Ist die Laufzeit eines Algorithmus logarithmisch (log n), so wird er mit wach-sender Problemgroße n allmahlich langsamer.

Wenn sich bei einem Algorithmus mit linearer Laufzeit (n) die Problemgroßen verdoppelt, so verdoppelt sich auch die Laufzeit.

Die Laufzeit-Funktion n log n findet man beispielsweise beim Divide-and-Conquer-Verfahren. Verdoppelt sich n, so wird die Laufzeit mehr als doppeltso groß, aber auch nicht wesentlich großer (sie wachst z.B. nicht auf das 3-fache).

Algorithmen, die doppelt verschachtelte Schleifen verwenden, haben eine qua-dratische Laufzeit (n¡sup¿2¡/sup¿). Verdoppelt sich n, dann steigt die Laufzeitauf das 4-fache an.

Algorithmen, die dreifach verschachtelte Schleifen benutzen, haben eine kubi-sche Laufzeit (n¡sup¿3¡/sup¿). Ist n beispielsweise 100, dann liegt die Laufzeitbei 1 Million Schritte.

Algorithmen mit exponentieller Laufzeit (2¡sup¿n¡/sup¿) haben in der Praxisnur eine geringe Bedeutung, da sie nur fur sehr kleine Problemgroßen losbar sind.

LineareOptimierung

Die lineare Optimierung befasst sich mit Methoden zur Losung von Opti-mierungsproblemen mit linearer Zielfunktionund linearen Nebenbe-dingungen. Die wichtigste Losungsmethode ist das Simplexverfahren.

26

Lineare Pro-grammierung

Wird synonym mit linearer Optimierung verwendet

LinearesModell

Modellmit linearer Zielfunktionund linearen Nebenbedingungen.

LP-Relaxation Wird bei einem ganzzahligen linearen Optimierungsmodell die Bedingung derGanzzahligkeit weggelassen, so ergibt sich ein lineares Optimierungsmodellmit reellwertigen Variablen. Dieses nennt man die LP-Relaxation des ganzzah-ligen Modells. Das relaxierte Modell kann beispielsweise mit dem Simplexver-fahren gelost werden.

Losung Allgemein handelt sich bei einer Losung um eine Handlungsalternative odereinen Plan, der ein Entscheidungsproblem losen kann. Im Sinne eines Optimie-rungsmodells ist eine Losung eine konkrete Wertzuweisung an alle Varia-blen des Modells.

Losung,optimale

Optimal ist diejenige Losung unter allen zulassigen Losungen, bei welcher derZielfunktionswertmaximal (minimal) ist, d.h. es gibt in einer Umgebungkeine großeren (kleineren) Zielfunktionswerte.

Losung,zulassige

Eine Losung ist fur ein Optimierungsmodell primal zulassig, wenn sie alleNebenbedingungendes Modells erfullt. Eine Losung ist dual zulassig, wennsie das Optimalitatskriterium erfullt.

Losungsgute Die Losungsgute ist vor allem fur heuristische Verfahren relevant, da bei diesennur eine naherungsweise optimale Losung berechnet wird. Die Losungsgute gibtan, wie gut die berechnete Losung im Vergleich zu einer bereits bekanntenLosung des Problems ist.

Losungsmenge Die Gesamtheit aller zulassigen Losungen wird auch als Losungsmenge(Losungsraum) bezeichnet.

27

Losungsraum Siehe Losungsmenge

Losungsraum,beschrankter

Ein Losungsraum ist beschrankt, wenn es eine Kugel mit endlichem Radius gibt,welche den Losungsraum enthalt.

Losungsver-fahren

Siehe Verfahren

28

13 M

13.1

MaschinellesLernen

Unter dem Begriff des Maschinellen Lernens werden verschiedene Methoden undVerfahren zusammengefasst, die automatisch aus einer großen Datenmen-ge fur den Benutzer interessante Informationen extrahieren konnen. Verfahrendes Maschinellen Lernens sind z.B. Entscheidungsbaume (ID3-Algorithmus) ,Clusterverfahren (Chameleon) oder Klassifikationsverfahren.

Matrix Eine Matrix ist in der linearen Algebra eine Anordnung von Zahlen in tabel-larischer Form. m Zeilen(vektoren) und n Spalten(vektoren) bilden eine mxn-Matrix, deren Elemente als Eintrage oder Komponenten der Matrix bezeichnetwerden. Beispielsweise wird eine 2x3-Matrix folgendermaßen dargestellt:

Matrix,Definitheit

Eine symmetrische nxn-Matrix ist positiv definit, wenn alle ihre Eigenwer-te großer Null sind. Sie ist positiv semidefinit, wenn alle Eigenwerte großeroder gleich Null sind. Eine symmetrische nxn-Matrix ist negativ definit, wennalle ihre Eigenwerte kleiner Null sind, sie ist negativ semidefinit, wenn alleEigenwerte kleiner oder gleich Null sind. Indefinit wird eine solche Matrix ge-nannt, wenn positive und negative Eigenwerte existieren. Die Definitheit einerMatrix hat bei der Berechnung der Extremalstellen (Minima und Maxima) einewichtige Bedeutung

Matrix,orthogonale

Eine Matrix ist orthogonal, wenn gilt: A A¡sup¿T¡/sup¿=I, wobei A¡sup¿T¡/sup¿die Transponierte der Matrix A und I die Einheitsmatrix ist.

Matrix,symmetrische

Eine Matrix ist symmetrisch, wenn sie identisch mit ihrer Transponierten ist:A=A¡sup¿T¡/sup¿

Matrix,transponierte

Die transponierte einer mxn-Matrix A ist die nxm-Matrix A¡sup¿T¡/sup¿, derenEintrage a¡sub¿ij¡/sub¿ identisch mit den Eintragen a¡sub¿ji¡/sub¿ der Matrix Asind. Eine quadratische Matrix ist symmetrisch, wenn gilt: A=A¡sup¿T¡/sup¿,

29

Median Der Median ist ein Lagemaß der empirischen Verteilung eines zumindestordinalskalierten Merkmals. Der Median reprasentiert die Mitte der nach Großegeordneten Werte eines Merkmals. Die Halfte der Werte ist also großer als derMedian, die andere Halfte kleiner. Bei ungerader Anzahl an Werten ist der Me-dian eindeutig festgelegt. Bei gerader Anzahl an Werten wird der Mittelwert derzwei zentralen Werte als Median bestimmt. Im Gegensatz zum arithmetischenMittelwert ist der Median stabil gegenuber Ausreißern.

Merkmal Die Eigenschaften eines Objektes werden in der Statistik als Merkmalebezeichnet. Haufig werden an einem Objekt mehrere Merkmale gleichzeitig be-obachtet. Die Werte, welche ein Merkmal annehmen kann, heißen Merkmals-auspragungen oder Realisationen. Hat ein Merkmal endlich viele Auspragungen,so heißt dies ein diskretes Merkmal. Hat es unendlich viele Auspragungen,so wird dies ein stetiges Merkmal genannt. Beispiel fur ein diskretes Merk-mal ist ”Geschlecht“ mit zwei Auspragungen, wohingegen das Merkmal ”Große“unendlich viele Werte in einem Intervall annehmen kann.

MerkmalsauspragungDie Werte, die ein Merkmal eines Objektes in der Statistik annehmen kann,heißen Merkmalsauspragungen oder Realisationen.

Merkmalswerte Die beobachteten Auspragungen eines Merkmals heißen Merkmalswerte (odereinfach: Werte).

Meta-Heuristik

Eine Meta-Heuristik ist ein allgemein anwendbares Verfahren um lokale Heuri-stiken (wie die lokale Suche) oder exakte Optimierungverfahren in Erfolg ver-sprechende Regionen des Suchraums zu leiten. Hierbei sind meist neben ver-bessernden auch verschlechternde Losungen erlaubt. Zu den Meta-Heuristikengehoren Tabu-Search, Simulated Annealing sowie genetische Algorithmen.

Methode Eine Methode beschreibt eine systematische Vorgehensweise zur Losungeines Problems. Ist diese Verfahrensvorschrift exakt und vollstandig formu-liert, so handelt es sich um einen Algorithmus.

30

Methodengruppe Eine Methodenklasse setzt sich aus mehreren Methodengruppen zusammen.Diese umfassen jeweils Methoden zur Losung einer bestimmten Modellgruppebeinhalten.

Methodenklasse Ein Methodenklasse ist eine Sammlung von Methoden, welche gleiche oderahnliche Probleme losen.

Methodik Eine Methodik ist eine Gesamtheit von Methodenals Teildisziplin einerFachwissenschaft. Methodik bezeichnet auch die Lehre von den in einer Wis-senschaft angewandten Methoden.

Methodologie Methodologie ist die Lehre von den Methoden. Unter einer Methodologiewird, in Anlehnung an den amerikanischen Sprachgebrauch, eine Sammlungvon Methoden verstanden, ein Methodenbundel. Manchmal wird im Ameri-kanischen methodology auch als Bezeichnung fur eine komplexe Methode ver-wendet.

MetrischeSkala

Als metrische Skalen werden Intervallskalen und Verhaltnisskalen (Rationalska-len) bezeichnet.

MinimalkostenflussproblemDas Minimalkostenflussproblem ist ein Optimierungsproblem bei dem in einemGraphen ein Fluss mit minimalen Kosten zwischen einer gegebenen Quelleund einer Senke gesucht wird. Auf den Kanten des Graphen sind Restriktionenfur den maximalen Fluss auf einer Kante gegeben.

MinimalSpannender

Baum

Ein Minimal Spannender Baum (Minimum Spanning Tree, MST) ist der span-nende Baum in einem Graphen mit der kleinsten Summe der Kantenbewertun-gen. Ein Minimal Spannender Baum kann mit dem Algorithmus von Kruskaloder dem Algorithmus von Prim bestimmt werden.

Modalwert Der Modalwert (Modus) ist die Merkmalsauspragung mit der großten Haufigkeitin einem Datensatz. Der Modalwert kann auch bei nominal- oder ordinalskalier-ten Merkmalen bestimmt werden (im Gegensatz zu Median oder Mittelwert).

31

Modell Ein Modell ist ein (vereinfachtes) Abbild eines realen Systemsoder Pro-blems. Die semantische Beschreibung eines realen Tatbestandes und dessensubjektive Wertung wird als verbales Modell des Problems bezeichnet. Aufdas verbale Modell folgt das mathematische Realmodell bzw. das den algo-rithmischen Moglichkeiten entsprechende Rechenmodell.

Modellgruppe Eine Modellgruppe fasst Modelle mit ahnlicher Struktur zusammen. Bei-spielsweise beinhaltet die Modellgruppe ”Graphenmodelle“ alle Modelle, welcheauf einer Graphenstruktur beruhen.

Modellparameter Siehe Parameter

MorphologischeMethoden

Morphologische Methoden dienen der systematischen Analyse eines Pro-blems und dem systematischen Auffinden moglicher Problemlosungen durchKombination von Problemelementen.

MultikriteriaproblemEin Multikriteriaproblem ist ein Entscheidungsproblemmit mehreren Zie-len, welche verfolgt werden. In Folge dessen gibt es in der Regel Zielkonflikte. DieEntscheidungsfindung bei Multikriteria-Problemen ist Aufgabe der Multikriteria-Analyse.

32

14 N

14.1

NachfolgerknotenEin Knoten j ist Nachfolger eines anderen Knotens i in einem gerichtetenGraphen G=(V,E), wenn es einen Bogen (i,j) von i nach j in G gibt.

NebenbedingungenNebenbedingungen oder Restriktionen sind meist Teil eines Optimierungsmo-dells. Sie schranken die Zulassigkeit der Werte der Zielfunktion ein.

Netzwerk Ein Netzwerk ist ein gerichteter, zyklenfreier Graph mit genau einer Quelle undeiner Senke sowie mit Kantenbewertungen.

NeuronaleNetze

Mit kunstlichen Neuronalen Netzen werden naturliche biologische NeuronaleNetze (wie beispielsweise im Gehirn) als informationsverarbeitende Syste-me nachgeahmt. Der Lernprozess kognitiver Systeme und die neurologischenFunktionen des Gehirns werden benutzt, um Zusammenhange zwischen Datenzu analysieren und Vorhersagen treffenzu konnen.

NichtlineareOptimierung

Die nichtlineare Optimierung befasst sich mit Methodenzur Losung von Op-timierungsproblemen mit nichtlinearer Zielfunktionund/oder nicht-linearen Nebenbedingungen. In der Realitat auftretende Wirkungszusam-menhange zwischen verschiedenen Großen sind in der Regel nichtlinear (z.B.degressive Kostenfunktionen) und werden uber nichtlineare Optimierungsmo-delle abgebildet.

Nichtnegativitats-bedingungen

Die Nichtnegativitatsbedingungen gehoren in vielen Optimierungsmodellen zuden Nebenbedingungen und schranken den zulassigen Losungsraumaufdie positiven Zahlen ein. Dies ist sinnvoll, da in vielen Problemstellungennegative Werte der Variablen nicht realisierbar sind (z.B. Personaleinsatz, Stuck-zahlen).

NormalverteilungDie Gauß- oder Normalverteilung ist die am haufigsten verwendete stetigeVerteilung. Ihre Dichtefunktion wird auch als Gauß-Kurve oder Glockenkur-ve bezeichnet.

33

Der zentrale Grenzwertsatz der Wahrscheinlichkeitsrechnung besagt, dass jedeSumme von unabhangigen, identisch verteilten Zufallsgroßen normalverteilt ist.Dies bedeutet, wenn z.B. eine Messung sehr oft durchgefuhrt wird, dass dann dieMesswerte normalverteilt sind. Somit lassen sich viele Vorgange in den Natur-,Wirtschafts- und Ingenieurwissenschaften durch die Normalverteilung gut be-schreiben.Die Normalverteilungsannahme ist Voraussetzung vieler statistischer Ver-fahren. Sollen diese Verfahren angewendet werden, so muss diese Annahmebewiesen werden.

Nominalskala Die Nominalskala beinhaltet qualitative Merkmale fur die nur die Vergleichs-operationen ”gleich“ oder ”ungleich“ moglich sind. Es kann also nur entschiedenwerden, ob zwei Merkmalsauspragungen gleich oder ungleich sind. Beispiele sinddas Geschlecht oder die Religionszugehorigkeit.

NP-schwer Siehe Komplexitatstheorie

34

15 O

15.1

Okonometri-sche

Modelle

Ein okonometrisches Modell ist ein abstrahierendes und vereinfachendesAbbild okonomischer Phanomene und eine mehr oder weniger gute Appro-ximation des realen okonomischen Geschehens.

OperationsResearch

Operations Research (OR) ist die Wissenschaft von der Anwendung ma-thematischer Methodenzur Vorbereitung optimaler Entscheidungen.OR arbeitet mit Modellen und bedient sich mathematischer Methoden zur For-mulierung und Losung der Modelle.Es gibt es im wesentlichen zwei Auffassungen vom Begriff ”Operations Rese-arch“:

• Operations Research aus Sicht des Praktikers (angewandte Richtung):

”modellgestutzte Vorbereitung von Entscheidungen zur Lenkung von Mensch-Maschine-Systemen“ (Muller-Merbach 1979). Operations Research dientder Vorbereitung einer Entscheidung im Rahmen eines Planungspro-zesses.

• Operations Research aus Sicht des Mathematikers (theoretische Richtung):

”Teilgebiet der angewandten Mathematik“ (Gaede 1974)

Opportunitats-kosten

Opportunitatskosten (Schattenpreise) sind fiktive Kosten, die entstehen, wenndurch Ressourcenknappheit ein Nutzen (z.B. Geld, Zeit) nicht realisierbarist. In vielen Optimierungsproblemen sind die Ressourcen (z.B. Menschen, Ma-schinen, Rohstoffe) in ihrer Verfugbarkeit beschrankt, so dass die vorhandenenRessourcen moglichst effizient eingesetzt werden mussen. Die Opportunitasko-sten geben fur jede Ressource an, um wieviel der Nutzen gesteigert werdenkonnte, wenn eine bestimmte Menge der Ressource zusatzlich zur Verfugungstehen wurde.

Bei der linearen Optimierung lassen sich die Opportunitatskosten der einzelnenRessourcen (Variablen der Nebenbedingungen) aus dem optimalen Simplexta-bleau ablesen (vgl. hierzu Zimmermann, H.J.: Operations Research, 2005, S. 99f.)

Optimalitats-prinzip

Das Optimalitatsprinzip ist ein Grundprinzip der dynamischen Optimie-rung von R. Bellmann. Nach diesem Prinzip setzt sich bei der dynamischen

35

Optimierung eine optimale Entscheidung immer nur aus optimalen Teilentschei-dungen zusammen.

Optimierung Unter Optimierung oder optimieren versteht man:

1. Im Sinne der Mathematik die Bestimmung optimaler,zulassigerLosun-gen eines Optimierungsproblems hinsichtlich einer gegebenen Zielfunktion

2. In der Informatik die Verbesserung des Laufzeitverhaltens eines Com-puterprogramms

3. Umgangssprachlich meist eine Verbesserung eines Vorgangs oder Zu-stands bzgl. Qualitat, Kosten, Geschwindigkeit, Effizienz oder Effekti-vitat.

Optimierung,globale

Die meisten Probleme der nichtlinearen Optimierung besitzen mehrere loka-le Optima, von denen jedoch in der Regel nur eines die Anforderung an einglobales Optimum erfullt, d.h. der Zielfunktionswert des globalen Optimumsist kleiner (bzw. großer) als alle anderen Zielfunktionswerte des Problems. Mitden Standardmethoden der nichtlinearen Optimierung (z.B. Newton-Verfahren,Strafkostenverfahren) konnen nur lokale Optima bestimmt werden, da nur loka-le Informationen ausgewertet werden. Zur globalen Optimierung werden meistheuristische Verfahren eingesetzt, so genannte Meta-Heuristiken.

Optimierung,lokale

Als lokale Optimierung wird eine Optimierung bezeichnet, bei der die Suche nacheinem Optimalpunkt nur in einem Teil des Losungsraumes durchgefuhrt wird.D.h. es konnen in einem anderen Teil des Losungsraumes durchaus Punkte mitbesseren Zielfunktionswerten exisitieren, die von der lokalen Suche nicht erfasstwerden. Die Standardmethoden der nichtlinearen Optimierung (z.B. Gradien-tenverfahren, Strafkostenverfahren) sind lokale Optimierungsmethoden. Mit derSuche nach der optimalen Losung im gesamten Losungsraum beschaftigt sichdie globale Optimierung.

Optimierungsmethode,exakte

Eine exakte Optimierungsmethode findet fur ein Optimierungsmodell eine op-timale (exakte) Losung. Nicht-exakte (heuristische) Methoden finden hingegennur eine naherungsweise optimale Losung.

36

OptimierungsmodellOptimierungsmodelle sind mathematisch-analytische Modellemit einerZielfunktionund eventuell einer oder mehreren Nebenbedingungen.Die Handlungsalternativen sind also nicht explizit von vornherein bekannt, son-dern werden durch eine zulassigen Menge beschrieben. Als Ergebnis von Mo-dellberechnungen werden optimale oder naherungsweise optimale Losungen alsVorschlage fur eine Entscheidung berechnet.

Ordinalskala Die Ordinalskala erlaubt lediglich qualitative, jedoch keine quantitativen Aus-sagen uber die Beziehung zweier Merkmalsauspragungen (im Gegensatz zurmetrischen Skala). Uber Abstande auf der Skala kann keine Aussage getroffenwerden, auf den Auspragungen konnen also nur Vergleichsoperationen (großer,kleiner, starker, schwacher etc.) durchgefuhrt werden. Beispiele sind Merkmaleder Einschatzung, wie z.B. das Befinden eines Patienten (gut - zufriedenstellend- schlecht).

37

16 P

16.1

Parameter Parameter sind Großen, die ein System bzw. ein Modell beschreiben und nichtdurch eine Entscheidung (z.B. fur eine bestimmte Handlungsalternative) beein-flussbar sind. Typische Parameter sind z.B. die Zeit, der Niederschlag oder dieAbsatzmenge.

ParetooptimierungIn der Mathematik bezeichnet man mit Paretooptimierung das Losen einesOptimierungsproblems mit mehreren Zielen (multikriterielles Problem).Hierbei ist es oft nicht moglich, alle Ziele gemeinsam zu optimieren. Die Verbes-serung eines Zieles wird meist mit der Verschlechterung in einem anderen Zielkompensiert. Eine Losung des multikriteriellen Optimierungsproblems ist pa-retooptimal, wenn die Verbesserung eines Zielfunktionswertes nur noch durchVerschlechterung eines anderen erreicht werden kann. Die Menge aller pareto-optimalen Losungen bezeichnet man als Pareto-Menge des zugrunde liegendenParetooptimierungsproblems.

Poisson-Verteilung

Die Poisson-Verteilung ist eine diskrete Wahrscheinlichkeitsverteilung, welcheden Zahlen n = 0, 1, 2, ... die Wahrscheinlichkeiten

pk =λk

k!e−λ (12)

zuordnet. Diese Verteilung wird haufig zur Beschreibung diskreter zeitlicher Er-eignisse in der Warteschlangentheorie benutzt, wie z.B. bei der Ankunft vonKunden in einem Warenhaus, oder auch fur Zerfallsprozesse. Die Wahl des Pa-rameters λ beeinflusst wesentlich die Schiefe der Verteilung.

Primal-DualeVerfahren

Primal-duale Verfahren verbessern abwechselnd eine primal zulassigeund eine dual zulassige Losung eines Optimierungsproblems. D.h. diese Ver-fahren arbeiten gleichzeitig mit zwei voneinander unabhangigen Losungen. Diesesind in der Regel nicht zulassig. Die primale und duale Zulassigkeit wird erst amEnde des Verfahrens, in der optimalen Losung, hergestellt. Beispiel fur ein sol-ches Verfahren ist der Out-of-Kilter-Algorithmus zur Losung des Minimalkosten-Flussproblems.

38

PrimaleVerfahren

Primale Verfahren zur Losung von Optimierungsproblemen gehen von einerzulassigen Losungaus und bestimmen darauf aufbauend systematisch neuezulassige Losungen. Diese Iterationen verbessern so lange den Zielfunktionswert,bis eine optimale Losung (oder naherungsweise optimale Losung) gefunden ist.Beispiele fur primale Verfahren sind das Simplexverfahren zur Losung linearerProbleme oder der Ford-Fulkerson-Algorithmus zur Bestimmung eines maxima-len Flusses in einem Graphen.

Prinzip Unter einem Prinzip wirdein allgemeingultiger Grundsatz verstanden, wel-cher aus der Verallgemeinerung von Gesetzen und wesentlichen Eigenschaftender Realitat abgeleitet ist.

Problem Ein Problem ist in der Umgangssprache eine Situation, Sache oder Person, wel-che Schwierigkeiten bereitet. Im mathematischen Sinne ist ein Problem eineFrage, die man versucht zu analysieren und zu losen und damit zu be-antworten.

Problemklasse Eine Problemklasse fasst mehrere, gleichartige Probleme zusammen.

Prognosemodell Prognosemodelle dienen der Abschatzung von voraussichtlichen Entwick-lungen. Sie konnen nicht klar gegen Erklarungsmodelle oder Modelle der Da-tenanalyse abgegrenzt werden, sondern sind vielmehr eine Erweiterung dieserModelltypen zum Zweck der Prognose.

Prozedur Der Begriff der Prozedur (von lat procedere=vorwarts gehen) ist dem Begriffdes Verfahrens ahnlich und bezeichnet eine Folge von Anweisungen. In der In-formatik ist eine Prozedur eine Funktion, die keinen Wert zuruckgibt.

Prozess Der Begriff des Prozesses hat mehrere Bedeutungen. Umgangssprachlich wirdmit Prozess ein Verlauf, ein Ablauf oder eine Entwicklung bezeichnet.In der Systemtheorie ist ein Prozess eine dynamische Folge von verschiedenenSystemzustanden und in der Informatik der Ablauf eines Computerprogram-mes.In der Betriebswirtschaft steht der Prozess-Begriff fur eine logische Folge von

39

Aktivitaten (und Ereignissen), um zu einem bestimmten Ergebnmis zu kommen(beispielsweise in der Produktion).

40

17 Q

17.1

QuadratischeOptimierung

Die quadratische Optimierung ist ein Spezialfall der nichtlinearen Optimie-rungmit quadratischer Zielfunktionund linearen Nebenbedingungen.Die Losung solcher Optimierungsaufgaben ist aufgrund der einfach zu behan-delnden quadratischen Nichtlinearitat prinzipiell nicht schwieriger als die Losungvon linearen Problemen.

Quantil Ein p-Quantil oder auch Quantil der Ordnung p (0 ¡ p¡ 1) zerlegt einegeordnete Liste von Merkmalswerten eines mindestens ordinalskalierten Merk-mals in zwei Teile, so dass ein Anteil p kleiner x¡sub¿p¡/sub¿ und ein Anteil 1-pgroßer als x¡sub¿p¡/sub¿ ist. x¡sub¿p¡/sub¿ ist die Merkmalsauspragung, welchedas obere vom unteren Quantil trennt. Beispielsweise trennt das Quantil derOrdnung 0,25 25% der Werte im unteren Quantil von 75% der Werte im oberenQuantil. Die Quantile der Ordnung 0,25 bzw. 0,75 heißen auch unteres Quartilbzw. oberes Quartil.

Quelle Als Quelle wird in der Graphentheorie ein Knoten eines gerichteten Graphenbezeichnet, der nur ausgehende Bogen besitzt. Alle Flusse fuhren also aus die-sem Knoten heraus.

41

18 R

18.1

Rang einerMatrix

Der Rang rg(A) einer mxn-Matrix A ist die maximale Anzahl der linearunabhangigen Spalten bzw. der linear unabhangigen Zeilen von A. Wennrg(A)=min{m,n} gilt, so hat A vollen Rang.

Rationalskala Siehe Verhaltnisskala

Rekursion In der Informatik wird als Rekursion der Aufruf einer Funktion oder eines Algo-rithmus durch sich selbst bezeichnet. Damit ein solcher rekursiver Aufruf nichtin eine so genannte Endlosschleife gerat, muss eine geeignete Abbruchbedingungformuliert werden.

Relaxation Ein komplexes Optimierungsmodell wird durch Relaxation verein-facht, indem komplizierte Nebenbedingungen weggelassen oder abgeschwachtwerden. Durch Weglassen der Ganzzahligkeitsforderung entsteht beispielswei-se die LP-Relaxation; durch Weglassen von Nebenbedingungen und Einfuhreneines Straftermes in der Zielfunktion entsteht die Lagrange-Relaxation.

Regelkreis Ein Regelkreis ist ein verkettetes Input-Output-System mit Ruckkopplung undeinem Kontrollmechanismus.

Regelungsmodell Regelungsmodelle werden auf Grundlage von Wirkungsmodellen formuliert. Hier-bei geht es darum, die beobachtbaren, abhangigen Variablen im Zeitablauf in-nerhalb einer definierten Bandbreite zu halten, indem man die unabhangigenVariablen des Wirkungsmodells gezielt verandert.

Regelstrecke Eine Regelstrecke ist eine beeinflusste Komponente eines Regelkreises.

Regler Als Regler wird eine beeinflussende Komponente eine Regelkreises bezeichnet.

42

RegressionsanalyseDie Regressionsanalyse ist eine statistische Methode, die den Zusammenhangzwischen einem oder mehreren unabhangigen Merkmal(en)und einem abhangi-gen Merkmal modelliert. Hierzu bestimmt sie eine Regressionsfunktion, welchediesen Zusammenhang formal ausdruckt.

Restriktion Siehe Nebenbedingung

Richtlinien Richtlinien geben Handlungsmuster vor, die in bestimmten Situationen miteiner gewissen Entscheidungsfreiheit zu befolgen sind.

43

19 S

19.1

Schattenpreise siehe Opportunitatskosten

Scheduling-Problem

Ein Scheduling-Problem ist eine moglichst gunstige (Kosten, Ressourcenver-brauch, Zeit) Zuordnung von gegebenen Auftragen zu Ressourcen unddie Bestimmung einer zeitlichen Reihenfolge, in der die Auftrage bearbeitet wer-den sollen.

Schiefe Die Schiefe ist in der Statistik ein Maß fur die Symmetrie der beobachtetenVerteilung der Merkmalswerte zum Mittelwert. Die Gaußsche Normalverteilunghat die Schiefe 0, d.h. sie ist immer symmetrisch zum Mittelwert. Ist die Schiefegroßer 0, so ist die Verteilung rechtsschiefe, ist sie kleiner 0, so ist sie linksschief.

Senke Als Senke wird in der Graphentheorie ein Knoten eines gerichteten Graphenbezeichnet, in den nur Bogen eingehen.

Sensitivitats-analyse

Eine Sensitivitatsanalyse untersucht, inwiefern die Werte der Losungsvariableneines Optimierungsmodells um ihren optimalen Wert schwanken durfen,ohne dass die optimale Losung des Modells ihre Gultigkeit verliert. Dies gibtdem Entscheider eine Vorstellung davon, in welchem Schwankungsbereich die,unter bestimmten Annahmen berechnete, optimale Losung optimal bleibt.

Signifikanz,statistische

Die Signifikanz ist in der Statistik ein Konzept, um die Wahrscheinlichkeitvon Unterschieden bzw. Abweichungen (z.B. zwischen zwei Messmetho-den) auszudrucken.Eine Abweichung ist wenig signifikant, wenn diese mit hoher Wahrscheinlich-keit zufallig ist. Sie ist signifikant, wenn sie nur mit geringer Wahrscheinlichkeitdurch Zufall entstanden ist.Die Uberprufung der Signifikanz wird mit statistischen Tests durchgefuhrt.

44

Simplextableau Das Simplextableau ist eine anschauliche Darstellung in Tableauform, die zeigt,wie das Simplexverfahren bei der Losung linearer Optimierungsprobleme vor-geht.

SimplexverfahrenDas Simplexverfahren (auch Simplex-Algorithmus) ist das wichtigste Verfah-ren der linearen Optimierung. Es wurde 1947 von George Dantzig entwickeltund lost ein lineares Optimierungsproblem nach endlich vielen Schritten exaktoder stellt die Unlosbarkeit des Problems fest. Der Name des Simplexverfah-rens beruht darauf, dass die Nebenbedingungen des linearen Problems einenSimplex beschreiben, dessen Ecken zur Losungssuche durchlaufen werden. Vieleandere Optimierungsverfahren greifen auf die Grundlagen des Simplexverfah-rens zuruck.

Simulation Die Simulation ist eine Methode zur Analyse einzelner Alternativen inkomplexen, meist stochastischen Modellen. Mittels der Simulation wirdversucht, reale Systeme und Situationen mathematisch nachzubilden. Es findetkeine Optimierung statt, sondern der Entscheider kann lediglich aufgrundder Simulationsergebnisse zwischen verschiedenen Alternativen wahlen. Haufigwird eine Entscheidung dadurch erschwert, dass mehrere Entscheidungskriteriengleichzeitig zu berucksichtigen sind. Die Simulation kommt insbesondere dannzum Einsatz, wenn eine exakte Analyse des Systems zu aufwandig, zu teuer odernicht durchfuhrbar ist.

Skala Eine Skala in der Statistik ist eine regelmaßig eingeteilte Anzeige, mit dereine Menge von Merkmalsauspragungen geordnet werden kann. Es werden imallgemeinen folgende Skalenniveaus unterschieden:

• Verhaltnisskala oder Rationalskala (hochstes Skalenniveau)

• Intervallskala

• Ordinalskala

• Nominalskala (niedrigstes Skalenniveau)

Ein Merkmal, das auf einem bestimmten Niveau sklaiert ist, kann auch auf allenniedrigeren Skalenniveaus dargestellt werden.

45

Skalierbarkeit Mit dem Begriff der Skalierbarkeit wird in der Informatik die Eigenschaft vonAlgorithmen und Verfahren bezeichnet, mit unterschiedlich große Daten-mengen umgehen zu konnen. D.h. gut skalierbare Verfahren arbeiten sowohlmit kleinen als auch mit sehr großen Datenmengen effizient.

SpannenderBaum

In der Graphentheorie ist ein spannender Baum (Spannbaum, aufspannenderBaum, englisch spanning tree) ein Teilgraph eines ungerichteten Graphen,derein Baum ist und alle seine Knoten enthalt. Spannende Baume existieren nurin zusammenhangenden Graphen.

Spieltheorie Die Spieltheorie im engeren Sinne ist ein Teilgebiet der Mathematik (oder auchder Wirtschaftswissenschaften), das sich mit der Analyse von Handlungs-strategien in Systemen mit vorgegebenen Regeln beschaftigt. Die Spieltheorieuntersucht das Verhalten von Akteuren in solchen Systemen und leitet darausoptimale Verhaltensstrategien ab.

StandardabweichungDie Standardabweichung s ist ein Maß dafur, wie sehr die Merkmalswerteei-nes Datensatzes streuen. Sie wird berechnet, indem fur alle Merkmalswertedie Abweichungen vom Mittelwert summiert werden und diese Summe durch dieAnzahl der Werte (n-1) geteilt wird. Hieraus wird die Quadratwurzel gezogen.

s =

√√√√ 1N − 1

N∑i=1

(xi − x)2 (13)

Durch Quadrieren der Standardabweichung s erhalt man die Varianz s¡sup¿2¡/sup¿.

Steuerung Als Steuerung wird die Beeinflussung einer veranderlichen Große durcheine oder mehrere andere Große(n) eines Systems bezeichnet.

Stichprobe Eine Stichprobe ist eine Teilmenge der statistischen Grundgesamtheit,die nach verschiedenen Verfahren ausgewahlt wird, wenn die gesamte Grundge-samtheit nicht untersucht werden kann. Eine Stichprobe soll immer reprasen-tativ fur die Grundgesamtheit sein, so dass aus den Ergebnissen statistischerUntersuchungen fur die Stichprobe auf die Eigenschaften der Grundgesamtheitgeschlossen werden kann.

46

Stochastik Stochastik ist die Lehre von der Wahrscheinlichkeit. Als Teigebiet der Ma-thematik beschreibt sie Vorgange, Entwicklungen und Strukturen, die vom Zu-fall beeinflusst werden.

StochastischerProzess

Ein stochastischer Prozess ist eine zeitliche oder raumliche Folge von Zu-fallsgroßen. Ist die Folge abzahlbar, so ist dies ein diskreter stochastischerProzess oder eine zufallige Folge. Ist sie nicht abzahlbar, so ist dies ein stetigerstochastischer Prozess.

Stoppkriterium Siehe Stoppregel

Stoppregel Eine Stoppregel beinhaltet ein vorgegebenes oder durch den Benutzer einstell-bares Abbruchkriterium fur einenAlgorithmus. Dies ist vor allem bei heu-ristischen Verfahren notwendig, bei denen der Losungsaufwand in der Nahe desOptimalpunktes stark ansteigt. Hier begnugt man sich mit einer naherungsweiseoptimalen Losung, um den Rechenaufwand zu begrenzen.

Streudiagramm Ein Streudiagramm ist eine zwei- oder mehrdimensionale Darstellung der Vertei-lung der Objekte einer Stichprobe anhand von zwei oder mehreren ihrer Merk-male. Streudiagramme sind wichtige Darstellungen fur die beschreibende Stati-stik und die explorative Datenanalyse.

Streuungsmaße Streungsmaße sind statistische Kenngroßen fur die Streuung der Daten,d.h. wie sehr die Merkmalswerte um das Lagemaß (z.B. den Mittelwert) streuen.Die wichtigsten Streuungsmaße sind die Standardabweichung, die Varianz, derInterquartilsabstand und der Standardfehler.

Suchraum Der Suchraum umfasst alle zulassigen und unzulassigen Losungen fur ein Pro-blem. Um eine bestimmte Losung zu finden, wird der Suchraum durchsucht.Der Suchraum kann dabei nach bestimmten Kriterien strukturiert sein.

System Ein System ist eine Gesamtheit von Objekten, die sich aufgrund der Bezie-hungen der Objekte untereinander von ihrer Systemumwelt abgrenzen lasst.

47

System,dynamisches

Ein dynamisches System ist ein System, bei dem sich die Zustande des Systemsmit der Zeit andern konnen.

System,geschlossenes

Ein geschlossenes System ist ein System, bei dem kein Austausch mit der Sy-stemumwelt erfolgt.

Systemanalyse Die Systemanalyse erfasst systematisch komplexe, schlecht-strukturierteProbleme. Hierzu werden intuitive und diskursive Problemlosungsmethodensowie - wenn moglich - Methoden des Operations Research eingesetzt.

48

20 T

20.1

Tourenplanungsproblem(VehicleRouting

Problem)

Beim Tourenplanungsproblem geht man davon aus, dass mit einer Anzahl vonFahrzeugen (mit maximal moglichen Ladungsmengen) von einem Ort (Depot)aus eine Anzahl von Kunden beliefert werden soll. Hierbei sollen alle Fahr-ten im Depot beginnen und enden. Die einzelnen Fahrzeugtouren werden sobestimmt, dass z.B. jeder Kunde nur in einer Tour vorkommt, die Ladungsmen-gen der Fahrzeuge nicht uberschritten werden und eine maximale Tourlange(z.B. Arbeitszeit) nicht uberschritten wird. Ziel der Optimierung ist z.B. dieMinimierung der Anzahl von Fahrzeugen oder die Minimierung der Lange allerTouren. In der Praxis tritt das Problem unter anderen bei der Tourenplanungvon Speditionen oder bei der postalischen Zustellung auf.

Transformation Unter einer Transformation versteht man in der Mathematik eine Abbildung.Beispielsweise ist eine Koordinatentransformation eine Vorschrift zur Verande-rung der Koordinatenwerte beim Wechsel von einem Koordinatensystem zu ei-nem anderen.

TransportproblemBei der Grundform des klassischen Transportproblems (TPP) soll eine Mengeeines Produktes von einer Anzahl an Lieferanten mit moglichst geringen Ko-sten zu einer Anzahl von Nachfragern transportiert werden. Dabei entsprichtdas gesamte Angebot aller Lieferanten eines Produktes der gesamten Nachfra-ge. Zur Losung des TPP gibt es neben dem Simplex-Algorithmus verschiedenespezialisierte Heuristiken, wie Eroffnungsverfahren (Nordwesteckenregel, Vogel-sche Approximationsmethode), Verbesserungsverfahren (MODI-Methode) odergenetische Algorithmen.Die Losung des TPP wird in der Praxis durch zusatzliche Nebenbedingungenerschwert, wie z.B. den Transport mehrerer Produkte oder die Berucksichtigungverschiedener Transportfahrzeuge.

TravellingSalesman-

Problem

Siehe Handlungsreisenden-Problem

49

21 U

21.1

Umladeproblem Das Umladeproblem ist eine Verallgemeinerung des Transportproblems-auf den Fall mehrerer Distributionsstufen. D.h. zusatzlich zu den Liefe-ranten und Nachfragern gibt es Umschlagsorte (z.B. Lager), in denen Produktein andere LKWs umgeladen oder auch gelagert werden. Aus den Umschlags-orten werden immer dieselben Mengen eines Produktes weggebracht, die auchdorthin gebracht wurden.

UnabhangigesMerkmal

Siehe abhangiges Merkmal

Unabhangig-keit,

empirische

Zwei Merkmale X und Y sind empirisch unabhangig, wenn die empirischenHaufigkeiten der Auspragungskombinationen mit den theoretisch berechnetenHaufigkeiten bei Unabhangigkeit ubereinstimmen. Man geht dann davon aus,dass sich die Merkmale nicht gegenseitig beeinflussen.

Unabhangig-keit,

stochastische

Die Stochastische Unabhangigkeit beschreibt die Unabhangigkeit zweier Ereig-nisse in der Wahrscheinlichkeitstheorie, d.h. bei stochastischer Unabhangigkeitwird die Wahrscheinlichkeit des Auftretens des einen Ereignisses nichtdurch das Auftreten des anderen Ereignisses beeinflusst. Beispielsweisesind zwei Wurfe eines Wurfels voneinander unabhangig, d.h. das Ergebnis desersten Wurfes beeinflusst das Ergebnis des zweiten Wurfes nicht. Formal wirddie stochastische Unabhangigkeit wie folgt formuliert:

P (A ∩B) = P (A) · P (B) (14)

d.h. stochastische Unabhangigkeit gilt, wenn die Wahrscheinlichkeit, dass beideEreignisse zusammen auftreten, gleich dem Produkt ihrer Einzelwahrscheinlich-keiten ist.

UnscharfeMenge

Siehe Fuzzy-Set

50

22 V

22.1

Variable Allgemein beschreiben Variablen die Handlungsalternativenim Rahmen ei-nes Entscheidungsproblems. Bei einem Optimierungsmodell sind Variablendiejenigen Großen, deren Werte zur Bestimmung einer optimalen Losung zuermitteln sind.

Varianz Die Varianz s¡sup¿2¡/sup¿ wird als Quadrat der Standardabweichung s berech-net.

Varianzanalyse Die Varianzanalyse ist ein statistisches Verfahren der Datenanalyse undMustererkennung. Das Verfahren untersucht, ob (und gegebenenfalls wie)sich der Erwartungswert eines metrischen Merkmals in verschiedenen Gruppen(Klassen) unterscheidet. Es wird getestet, ob die Varianz zwischen den Grup-pen großer ist als die Varianz innerhalb der Gruppen. Dadurch kann ermitteltwerden, ob die Gruppeneinteilung sinnvoll ist oder nicht bzw. ob sich die Grup-pen signifikant unterscheiden oder nicht. Beispiele fur die Anwendung der Va-rianzanalyse sind die Untersuchung der Wirksamkeit von Medikamenten in derMedizin oder die Untersuchung des Einflusses von Dungemitteln auf den Ertragin der Landwirtschaft.

VehicleRoutingProblem

Siehe Transportproblem

VerbesserungsverfahrenVerbesserungsverfahren sind Heuristiken, die von einer zulassigen Losung-ausgehend versuchen, diese sukzessive durch kleine Veranderungen zuverbessern. Dies wird so lange fortgesetzt bis ein Abbruchkriterium erreichtist. Beispiel fur Verbesserungsverfahren sind k-opt-Verfahren. Reine Verbesse-rungsverfahren fuhren haufig sehr schnell dazu, dass die Suche in einem lokalenOptimum endet, wo keine Verbesserungen mehr moglich sind. Um dies zu um-gehen werden Meta-Heuristiken eingesetzt.

Verfahren Verfahren sind ausfuhrbare Vorschriften oder Anweisungen zum geziel-ten Einsatz von Methoden. Ein Verfahren beschreibt einen konkreten Weg zurLosung bestimmter Probleme oder Problemklassen.

51

Verhaltnisska-la

Bei der Verhaltnisskala (Rationalskala) ist wie bei der Intervallskala die Rei-henfolge der Merkmale festgelegt. Im Unterschied zur Intervallskala besitzt siejedoch einen absoluten Nullpunkt. Beispiele sind das Alter oder die Große. Le-diglich bei dieser Skala sind Multiplikation und Division (Verhaltnisse) erlaubt.

52

23 W

23.1

Wald In der Graphentheorie wird als Wald ein ungerichteten Graph bezeichnet, derkeinen Zyklus besitzt. Ist der Wald zusammenhangend, so heißt dies ein unge-richteter Baum. Jede Zusammenhangskomponente eines Waldes ist ein Baum,so dass ein Wald aus einem oder mehreren Baumen besteht.

WarteschlangentheorieMittels der Warteschlangentheorie wird das Verhaltens von Warteschlangenanalysiert (z.B. Kunden an der Kasse, Auftrage vor Maschinen). Ein Optimie-rungsproblem ergibt sich dadurch, dass verschiedene Variablen einstellbar sind,die das Verhalten in der Warteschlange und somit eine Zielfunktionsgroße be-einflussen (z.B. die Wartezeit). Solche Entscheidungsvariablen sind die Anzahlder Bedienstationen, an denen Kunden oder Auftrage abgefertigt werden, oderdie Warteschlangendisziplin (z.B. FIFO, LIFO).

WarehouseLocationProblem

Beim Warehouse Location Problem (WLP) ist die Standortverteilung vonLagerhausern (Warehouses) so zu bestimmen, dass die Summe aus Trans-portkosten und Lagerkosten minimal wird. Die Transportkosten setzen sich ausTransporten von Lieferanten in die Lager, Transporten von den Lagern zu denKunden und evtl. Transporten zwischen den Lagern zusammen. WLP konnenein- oder mehrstufig sein (mehrere Lagerstufen) sowie unter Vernachlassigungoder Berucksichtigung von Kapazitatsbeschrankungen formuliert werden.

Weg Eine Folge von Knoten j¡sub¿0¡/sub¿ , j¡sub¿1¡/sub¿ ,... , j¡sub¿t¡/sub¿ in ei-nem gerichteten Graphen heißt Weg, wenn die Knoten in der Folge (j¡sub¿0¡/sub¿, j¡sub¿1¡/sub¿ ,... , j¡sub¿t¡/sub¿) durchlaufen werden konnen. Die Lange desWeges ist durch die Summe der Bewertungen auf seinen Bogen gegeben.

Wirkungsmodell Wirkungsmodelle sind spezielle Erklarungsmodelle, bei denen mindestens eineunabhangige Variable vorhanden ist, und die Untersuchung der Auswirkungenvon Anderungen der unabhangigen Variablen auf die abhangigen Variablen imVordergrund steht.

53

WissensbasiertesSystem

Ein wissensbasiertes System ist ein Software-System, das eine Wissensbasis er-stellt und erweitert sowie Wissen daraus bereitstellt. Die Wissenbasis stellt dabeieine Sammlung von Wissen dar, die durch eine formale Notation reprasentiertwird. Wissen unterscheidet sich von bloßen Daten oder Informationen dadurch,dass durch logische Schlussfolgerungen weiteres Wissen aus bestehendem Wissengewonnen werden kann.

WissensmanagementWissensmanagement umfasst alle moglichen Maßnahmen, um die Wissen-sproduktion, -reproduktion, -distribution, -verwertung und -logistikin einem Unternehmen optimieren zu konnen. Das Wissensmanagementbeschaftigt sich hierzu mit der Mobilisierung der individuellen und kollektivenWissensbestande und mit den Lernprozessen zur Verbesserung der Wissenspo-tentiale im Unternehmen.

54

24 X

24.1

55

25 Y

25.1

56

26 Z

26.1

Zielfunktion Die Zielfunktion ist eine mathematische Funktion zur Beschreibung desOptimierungsziels. Bezeichnet x eine Losungsvariable, so lautet die Zielfunk-tion: Minimiere (bzw. maximiere) f(x). Es wird eine optimale Losung des Op-timierungsmodells gesucht, d.h. eine solche mit kleinst- bzw. großtmoglichem(Zielfunktions-) Wert. Die Variablen der Zielfunktion reprasentieren Gewinne,Kosten oder andere Zielkriterien des Entscheiders.

ZielfunktionskoeffizientDie Entscheidungsvariablen in der Zielfunktion werden mit Zielfunktionsko-effizienten gewichtet. Diese werden in der Regel im Optimierungsmodell alsc¡sub¿ij¡/sub¿ bezeichnet und stellen den positiven oder negativen Nutzen einerEinheit einer Variablen in der Zielfunktion dar.

ZielfunktionswertDie mittels einer Zielfunktion f bewertete Losung x eines Optimierungs-modells ergibt den Zielfunktionswert f(x).

ZuordnungsproblemDas allgemeine Zuordnungsproblem beinhaltet Probleme, bei denen zwei Men-gen elementweise so zugeordnet werden, dass die hierdurch entstehendenKosten minimiert werden. Beispiele hierfur sind die Zuordnung von Fahrern zuLKWs oder von Maschinen zu Arbeitsgangen. Das Zuordnungsproblem ist einespezielle Form des Transportproblems, bei dem die Kapazitaten der Nebenbe-dingungen 1 sind.

Zufallsstichprobe Eine Zufallsstichprobe ist eine Methode, eine Stichprobe anhand eines Zufalls-mechanismus aus der Grundgesamtheit zu ziehen.

Zyklus Ein Zyklus (Kreis) ist ein geschlossener Weg in einem Graphen, d.h. ein Wegmit gleichem Anfangs- und Endknoten.

57