Pro-2.lineare Optimierung

Ein Optimierungsproblem ist ein Problem, bei dem nach einer gemäß Zielsetzung (ZS) optimale Lösung und/oder deren Zielfunktionswert gefragt wird.

Ein Entscheidungsproblem ist ein Problem, bei dem die Frage nur mit “ja” oder “nein” beantwortet werden kann.

Eine Probleminstanz ist eine Belegung aller Daten der Eingabe mit Werten.

Ist eine Kombination aus:

• Eingabe

• Lösungsraum (LR)

• Zulässigkeitsbedingungen (ZB)

• Zielsetzung (ZS)

• Frage

Struktur der vorliegenden Daten/Information (für die Gesamtheit aller relevanten Situationen)

Menge aller “Lösungen” in Abhängigkeit von der Ausprägung der Eingabe (Struktur der “Lösungen”)

Menge von Bedingungen, sodass für jede Lösung aus LR und jede Bedingung entschieden werden kann, ob die Lösung die Bedingung erfüllt.

Zulässige Lsg: erfüllt alle Zulässigkeitsbedingungen

Unzulässige Lsg: verletzt mind. eine Zulässigkeitsbdingung

Bzeogen auf LR, ZB und ZS - gibt mitten die Struktur der Antwort vor, die wir als Ausgabe bezeichnen

Bewertung jeder Lösung mit einem numerischen Wert (Zielfkt. Wert) und Ausgabe darüber, ob hohe oder niedrige Werte präferiert werden (Orientierung)

Optimale Lösung Lösung mit bestmöglichem Zielfunktionswert unter allen zulässigen Lösungen

• Vorab festgelegete Vorgehensweise zur Bewertung der Frage eines Problems

• In der Regel eingesetzt für konkrete Probleminstanzen

• Sollte für alle denkbaren Instanzen eine Ausgabe liefern

Ein Algorithmus ist eine präzise und eindeutige Handlungsvorschrift, mittels derer eine Eingabe in eine Ausgabe transformiert wird

Finden garantiert eine optimale Lösung zu jeder Probleminstanz

Zielen auf die Bestimmung einer Lösung zu einer instanz

• Ziel ist die Bestimmung einer möglichst guten Lösung

• Im Allgemeinen kann der Wert beliebig schlecht im Vergleich zum Wert einer optimalen Lösung sein

• Es können aber eventuell auch Eigenschaften bewiesen werden, z.B. über die Worst-Case Performance

• bildet ein Original ab

• welche EIgenschaften des Originals abgebilidet werden, hängt vom verfolgten Ziel ab

• Ein Modelltyp gibt einen sprachlichen und strukturellen Rahmen für Modelle vor

• bilden Problem ab

• bilden Eingabe, LR, ZB, ZS und Fragen durch numerische Werte und deren Verknüpfung ab

Eingabe und Lösungen werden representiert durch:

• Paramter: Symbole, die im Rahmen des Problems unveränderlich sind

• Variablen: Symbole, die Lösungen representieren und somit veränderlich sind

• Domänen: Domänen von Variablen geben vor, welche Werte die Variablen annehemen dürfen

• NB: eine lsg. ist zulässig, wenn alle NB erfüllt sind

• Zielfunktion: Ordnet jede lsg. einen Wert zu

• untersucht den Rand des zulässigen Bereichs nach einer optimalen Lösung

• zählt zu den leistungsfähigsten Verfahren zur Lösung von LP

Jede (zulässige) Basislösung entspricht einem (zulässigen) Eckpunkt und jeder (zulässige) Eckpunkt entspricht einer (zulässigen) Basislösung

Eckpunkte sind Schnittpunkte der (n-1) dimensionalen Unterräume von n linear unabhängigen NB. Wir nennen einen Eckpunkt zulässig, wenn er eine zulässige Lösung representiert

Primale degeneration: bei vorliegen von n=2 Variablen, schneiden sich mehr als 2 Restriktionen (NB) in einem Punkt

• Der algorithmus muss eventuell “kreisen”, d.h. wiederholt zu einer Basislösung zurückkehren und so niemals terminieren

• Dies kann durch alternative Regelen bei der Wahl des Pivoelement vermieden werden. es existieren deratige Regeln, bei denen unter Garantie keine Basis mehrfach betrachtet wird

Ein Problem ist eine Kombination aus Eingabe, LR, ZB, ZS und Frage