Optimierungsproblem - Optimization problem
In Mathematik , Informatik und Wirtschaft ist ein Optimierungsproblem das Problem , aus allen möglichen Lösungen die beste Lösung zu finden .
Optimierungsprobleme lassen sich in zwei Kategorien eingeteilt werden, je nachdem , ob die Variablen sind kontinuierlich oder diskret :
- Ein Optimierungsproblem mit diskreten Variablen ist als diskrete Optimierung bekannt , bei der ein Objekt wie eine Ganzzahl , eine Permutation oder ein Graph aus einer zählbaren Menge gefunden werden muss .
- Ein Problem mit stetigen Variablen ist als kontinuierliche Optimierung bekannt , bei der ein optimaler Wert aus einer stetigen Funktion gefunden werden muss. Sie können eingeschränkte Probleme und multimodale Probleme umfassen.
Kontinuierliches Optimierungsproblem
Die Standardform eines kontinuierlichen Optimierungsproblems ist
wo
- f : ℝ n → ℝ ist die Zielfunktion , die über den n- variablen Vektor x minimiert werden soll.
- g i ( x ) ≤ 0 genannt Ungleichheitsbeschränkungen
- h j ( x ) = 0 werden Gleichheitsbeschränkungen genannt , und
- m ≥ 0 und p ≥ 0 .
Wenn m = p = 0 ist , ist das Problem ein uneingeschränktes Optimierungsproblem. Konventionell definiert das Standardformular ein Minimierungsproblem . Ein Maximierungsproblem kann durch Negieren der Zielfunktion behandelt werden .
Kombinatorisches Optimierungsproblem
Formal ist ein kombinatorisches Optimierungsproblem A ist eine Quadruple ( I , f , m , g ) , wobei
- Ich bin eine Reihe von Instanzen;
- bei einer gegebenen Instanz x ∈ I ist f ( x ) die Menge möglicher Lösungen;
- Bei einer gegebenen Instanz x und einer realisierbaren Lösung y von x bezeichnet m ( x , y ) das Maß von y , das normalerweise ein positiver Realwert ist .
- g ist die Zielfunktion und ist entweder min oder max .
Das Ziel ist dann, für einige Fälle x eine optimale Lösung zu finden , dh eine realisierbare Lösung y mit
Für jedes kombinatorische Optimierungsproblem gibt es ein entsprechendes Entscheidungsproblem, das fragt, ob es für eine bestimmte Maßnahme m 0 eine praktikable Lösung gibt . Wenn es beispielsweise einen Graphen G gibt, der die Eckpunkte u und v enthält , könnte ein Optimierungsproblem darin bestehen, "einen Pfad von u nach v zu finden , der die wenigsten Kanten verwendet". Dieses Problem könnte eine Antwort von beispielsweise 4 haben. Ein entsprechendes Entscheidungsproblem wäre "Gibt es einen Pfad von u nach v , der 10 oder weniger Kanten verwendet?" Dieses Problem kann mit einem einfachen "Ja" oder "Nein" beantwortet werden.
Auf dem Gebiet der Approximationsalgorithmen sollen Algorithmen nahezu optimale Lösungen für schwierige Probleme finden. Die übliche Entscheidungsversion ist dann eine unzureichende Definition des Problems, da nur akzeptable Lösungen angegeben werden. Obwohl wir geeignete Entscheidungsprobleme einführen könnten, wird das Problem natürlicher als Optimierungsproblem charakterisiert.
Siehe auch
- Zählproblem (Komplexität)
- Designoptimierung
- Funktionsproblem
- Handschuhproblem
- Unternehmensforschung
- Befriedigend : Das Optimum muss nicht gefunden werden, nur eine "gut genug" Lösung.
- Suchproblem
- Semi-unendliche Programmierung
Verweise
Externe Links
- "Wie Traffic Shaping die Netzwerkbandbreite optimiert" . IPC . 12. Juli 2016 . Abgerufen am 13. Februar 2017 .