Kurs:Algorithmen und Datenstrukturen/Vorlesung/Opimierung Grundlagen

Aus Wikiversity
Zur Navigation springen Zur Suche springen




Grundlagen der Optimierung[Bearbeiten]

Auf dieser Seite gibt es eine Einführung in das Thema Optimierung.

Die (Mathematische) Optimierung beschreibt eine Familie von Lösungsstrategien zur Maximierung/Minimierung einer Zielfunktion unter Nebenbedingungen. Viele der bisher untersuchten Probleme können als Optimierungsproblem modelliert werden. Zum Beispiel das Kürzeste Wege Problem: Minimiere die Länge eines Pfades unter der Nebenbedingung, dass der Pfad zwei gegebene Knoten verbindet. Oder das Rucksackproblem: Maximiere den Gesamtnutzen der Gegenstände unter der Nebenbedingung, dass die Kapazität des Rucksacks eingehalten wird. Oder das Flussprobleme: Maximiere den Fluss unter der Nebenbedingung, dass Kantenkapazitäten eingehalten werden.

Algorithmen wie Djikstra und Ford-Fulkerson sind domänenspezifische Algorithmen zur Lösung ihrer jeweiligen Optimierungsprobleme. Mathematische Optimierungsverfahren sind allgemeine Verfahren, die auf eine Vielzahl von Problemen anwendbar sind, dabei aber eventuell nicht immer so effizient wie speziellere Algorithmen sind.

Optimierung ist eine weites Feld, wir werden uns in dieser Vorlesung auf einen kleinen Ausschnitt konzentrieren:

  • Grundlagen der Optimierung
  • Kombinatorische Optimierung
  • Lineare Optimierung
  • Das Simplex‐Verfahren

Begriffe[Bearbeiten]

Ein allgemeines (reelles) Optimierungsproblem ist gegeben durch P: Minimiere f(x)unter der Nebenbedingung . f ist dabei die Zielfunktion. heißt zulässig für P, falls . X ist die zulässige Menge und heißt globales Minimum von P, falls . Äquivalent gilt P: Minimiere f(x) unter der Nebenbedingung und P': Maximiere -f(x) unter der Nebenbedingung .

Beispiel Gewinnmaximierung[Bearbeiten]

Eine Firma produziert zwei verschiedene Waren. Ware x1 erbringt einen Gewinn von einem Euro. Ware x2 erbringt einen Gewinn von 6 Euro.

Frage: Welches Verhältnis von x1 und x2 führt zum größten Gewinn?

Nebenbedingungen:

Die Firma kann täglich maximal 200 Einheiten der Ware x1 produzieren und maximal 300 Einheiten der Ware x2 .

Insgesamt kann die Firma maximal 400 Einheiten pro Tag produzieren.

Zuerst wird nun die Zielfunktion formuliert: Maximiere Gewinn (1 Euro pro , 6 Euro pro ) : .

Anschließend werden die Nebenbedingungen formuliert.

Maximal 200 Exemplare von x1

Maximal 300 Exemplare von x2

Insgesamt maximal 400 Exemplare

Es müssen Waren produziert werden

Der Punkt ist zulässig mit Funktionswert 0

Der Punkt ist zulässig mit Funktionswert 1400

Der Punkt ist zulässig mit Funktionswert 1900 und globales Maximum

Der Punkt ist unzulässig

Dieses Beispiel ist ein lineares Optimierungsproblem.

Beispiel Kürzester Weg[Bearbeiten]

Beispielgraph

Es soll die Distanz von s nach y bestimmt werden. Dafür sollen folgende Variablen und Bezeichner betrachtet werden.

  • : die Kante von a nach b ist Teil des kürzesten Pfades von s nach y für alle Kanten (a,b)
  •  : Das Gewicht der Kante von a nach b, zum Beispiel
  • Die Zielfunktion ist

Es gelten folgende Nebenbedingungen:

  1. Die Gewichte müssen wie im Graph sein
  2. Alle Kanten (a,b) mit müssen einen Pfad von s nach y bilden:
    1. Es gibt genau eine Kante mit Startpunkt s:
    2. Es gibt genau eine Kante mit Zielpunkt y:
    3. Für jeden anderen Knoten gilt, falls eine Kante in diesen Knoten reinführt, muss er auch wieder eine rausführen, zum Beispiel für

Beachte durch die Minimierung werden Kreise auf dem Pfad automatisch verhindert.

Vollständiges Optimierungsproblem für ein kleines Beispiel von u nach x:

Kürzester Weg


Das Problem der Kürzesten-Wegfindung ist ein ganzzahliges Optimierungsproblem, allgemeiner ein kombinatorisches Optimierungsproblem.

Problemklassen[Bearbeiten]

Optimierungsprobleme sind unterschiedlich schwer lösbar

  • lineare Probleme: f,h sind linear, z.B. f/x,y)=3x+4y. Diese sind einfach zu lösen
  • Quadratische Probleme: z.B. sind auch noch einfach zu lösen.
  • Konvexe Probleme: z.B. min sind schon schwerer zu lösen.
  • Nicht-konvexe Probleme: z.B. sind ziemlich schwer zu lösen.
  • Ganzzahlige Probleme: sind überraschenderweise schwerer zu lösen als reelle Probleme. Etwa allgemeiner handelt es sich hier um kombinatorische Probleme (diskrete Elemente, nicht notwendigerweise Zahlen)
  • Weitere Parameter
    • Restringierte Probleme: zulässige Menge ist beschränkt
    • Unrestringierte Probleme: zulässige Menge ist unbeschränkt

Hier werden wir uns aber nur mit linearer Optimierung befassen.


Vorheriges Kapitel.jpg Discussion Nächstes Thema.jpg