Zum Inhalt springen
Zurück zu den Suchergebnissen

Mehrkriterielle Lineare Programmierung (MOLP)

Eingeführt von
Steuer, R. E.; Charnes, A.; Cooper, W. W.
Jahr
1955–1986
Typ
Mathematical optimization / vector optimization
Familie
Simulation / optimization

Dieser Text ist eine maschinelle Übersetzung und wurde noch nicht geprüft. Original auf Englisch lesen

Schriftgröße

Was leistet sie?

Die Mehrkriterielle Lineare Programmierung (MOLP) erweitert die klassische Lineare Programmierung, um mehrere widerstreitende lineare Zielfunktionen gleichzeitig über einem durch lineare Nebenbedingungen definierten zulässigen Bereich zu behandeln.

Anstelle einer einzelnen optimalen Lösung erzeugt MOLP eine Pareto-effiziente Grenze, aus der ein Entscheidungsträger einen bevorzugten Kompromiss auswählt. Sie ist grundlegend für die Unternehmensforschung und das Management Science bei Problemen der Ressourcenallokation, Planung und Gestaltung mit konkurrierenden Zielen.

Die Intuition hinter der Methode

In der gewöhnlichen linearen Programmierung minimiert man eine Kostenfunktion oder maximiert eine Gewinnfunktion, aber reale Entscheidungen beinhalten fast immer mehrere konkurrierende Ziele – Kosten minimieren bei gleichzeitiger Maximierung des Serviceniveaus und Minimierung der Emissionen. MOLP erkennt an, dass keine einzelne Lösung bei allen Zielen gleichzeitig die beste ist. Es bildet die vollständige Grenze der nicht-dominierten (Pareto-effizienten) Lösungen ab, bei denen die Verbesserung eines Ziels notwendigerweise ein anderes verschlechtern würde. Der Entscheidungsträger verwendet dann Präferenzinformationen – Gewichte, Aspirationsniveaus oder interaktive Abfragen –, um eine endgültige Lösung aus dieser Grenze auszuwählen, wodurch Kompromisse explizit gemacht werden, anstatt sie in einem zusammengesetzten Score zu verbergen.

Geschichte

Die theoretischen Grundlagen der mehrkriteriellen linearen Programmierung gehen auf die Arbeiten von Charnes und Cooper zur Zielprogrammierung und Koopmans zur effizienten Produktion in den 1950er Jahren zurück. Steuers Lehrbuch von 1986 konsolidierte das Feld und systematisierte die gewichtete Summen-, Epsilon-Constraint- und interaktiven Methoden, die bis heute Standard sind. MOLP ist heute ein Kernthema in den Lehrplänen der Unternehmensforschung weltweit.

Wann wird sie eingesetzt?

Verwenden Sie MOLP, wenn das Problem mehrere konkurrierende lineare Ziele und lineare Nebenbedingungen aufweist, Daten kontinuierlich und präzise bekannt sind (oder als deterministisch behandelt werden können) und der Entscheidungsträger Kompromisse explizit verstehen muss, anstatt einen vorab aggregierten Score zu akzeptieren. Typische Anwendungsbereiche sind Produktionsplanung, Portfolioallokation, Transportroutenplanung und öffentliche Haushaltsplanung. NICHT verwenden, wenn Ziele oder Nebenbedingungen nicht-linear sind (verwenden Sie stattdessen mehrkriterielle nicht-lineare Programmierung oder Metaheuristiken), wenn Daten diskret oder binär sind (verwenden Sie mehrkriterielle ganzzahlige Programmierung), wenn die Anzahl der Ziele fünf oder sechs übersteigt (die effiziente Grenze wird rechnerisch unhandlich) oder wenn der Entscheidungsträger nicht bereit ist, sich an einer iterativen Präferenzermittlung zu beteiligen.

Grenzen und Hinweise

  • Beschränkt auf lineare Zielfunktionen und lineare Nebenbedingungen; reale Probleme sind oft nicht-linear.
  • Die effiziente Grenze kann exponentiell viele Extrempunkte in höheren Dimensionen enthalten, was eine umfassende Aufzählung unpraktisch macht.
  • Erfordert präzise numerische Daten; Unsicherheit oder Unschärfe in Koeffizienten wird nicht nativ behandelt.
  • Interaktive Methoden hängen stark von der Verfügbarkeit und Fähigkeit des Entscheidungsträgers ab, Präferenzen konsistent zu artikulieren.

Die Bedingungen der Quelle ersetzen weder eine unabhängige wissenschaftliche Prüfung noch die Validierung durch eine Analyse-Engine.

Stärken

  • Erzeugt die vollständige Pareto-effiziente Grenze und gibt Entscheidungsträgern ein vollständiges Bild der Kompromisse.
  • Rechnerisch handhabbar für moderate Problemgrößen mittels Simplex-basierter Solver.
  • Garantiert die mathematische Optimalität jedes Punktes auf der effizienten Grenze.
  • Gut unterstützt durch ausgereifte Software (CPLEX, Gurobi, Open-Source-Alternativen).
  • Kompromisse werden explizit gemacht, anstatt in einem undurchsichtigen zusammengesetzten Index zusammengefasst zu werden.

Anwendungen

  • Produktionsplanung, die Kosten, Durchsatz und Ressourcennutzung ausbalanciert.
  • Portfoliooptimierung, die Rendite, Risiko und Liquidität abwägt.
  • Transport- und Logistiknetzwerkdesign mit konkurrierenden Kosten- und Servicezielen.
  • Planung von Energiesystemen zur Minimierung der Kosten bei gleichzeitiger Erfüllung von Emissions- und Zuverlässigkeitszielen.
  • Ressourcenallokation im Gesundheitswesen, die Gerechtigkeit, Effizienz und Budgetbeschränkungen ausbalanciert.
  • Umweltmanagement, das ökonomische und ökologische Leistung gleichzeitig optimiert.

So funktioniert es

So funktioniert es

1

Formulieren Sie k lineare Zielfunktionen f1(x) bis fk(x) und einen zulässigen Bereich X, der durch lineare Ungleichheits- und Gleichheitsrestriktionen (Ax <= b, x >= 0) definiert ist. Identifizieren Sie, welche Ziele minimiert und welche maximiert werden sollen. Bestätigen Sie, dass alle Zielfunktionen und Nebenbedingungen linear in den Entscheidungsvariablen sind.

Formel
\min_{x \in X} \mathbf{f}(x) = (f_1(x), f_2(x), \ldots, f_k(x))^T \text{ s.t. } Ax \leq b,\; x \geq 0
2

Generieren Sie die Menge der Pareto-effizienten (nicht-dominierten) Lösungen. Gängige Ansätze umfassen die gewichtete Summenmethode (Variieren der Gewichte über den Simplex), die Epsilon-Constraint-Methode (Optimierung eines Ziels bei gleichzeitiger Begrenzung der anderen) und die Tschebyscheff-Methode. Jeder Ansatz bildet einen Teil oder die gesamte effiziente Grenze ab.

3

Wenden Sie eine Skalarisierungstechnik an, um das Vektorproblem in eine Sequenz von Einzelziel-LPs umzuwandeln. Beim gewichteten Summenansatz lösen Sie min sum(wi * fi(x)) für systematisch variierte Gewichtsvektoren. Notieren Sie jeden effizienten Extrempunkt des Zielraums.

Formel
\min_{x \in X} \sum_{i=1}^{k} w_i f_i(x), \quad w_i \geq 0, \; \sum w_i = 1
4

Sammeln Sie die effizienten Extrempunkte und die sie verbindenden Kanten, um die Pareto-Grenze zu charakterisieren. Analysieren Sie den Bereich jedes Ziels über die Grenze hinweg, um das Ausmaß der Kompromisse zu verstehen. Präsentieren Sie die Grenze dem Entscheidungsträger mittels Tabellen oder bi-objektiven Diagrammen.

5

Beziehen Sie den Entscheidungsträger ein, um eine bevorzugte Lösung aus der effizienten Menge auszuwählen. Interaktive Methoden (STEM, NIMBUS) wechseln zwischen der Präsentation von Lösungen und der Aufforderung an den Entscheidungsträger, Präferenzen auszudrücken, um zu einer endgültigen Wahl zu konvergieren, die seine Prioritäten am besten widerspiegelt.

Häufige Fallstricke

  • Die Verwendung fester Gewichte bei der gewichteten Summen-Skalarisierung und die Berichterstattung nur einer Lösung verschleiert die Grenze und verfehlt den Zweck von MOLP.
  • Verwechslung von Pareto-Effizienz mit Optimalität: Jeder Punkt auf der Grenze ist effizient, aber keiner ist ohne Präferenzinformationen global „am besten“.
  • Versäumnis zu prüfen, ob der zulässige Bereich beschränkt ist; ein unbeschränktes Problem liefert keine endliche effiziente Menge.
  • Die Behandlung von MOLP als Black Box ohne Einbeziehung des Entscheidungsträgers in die Auswahl führt zu willkürlichen Endentscheidungen.
  • Anwendung von MOLP auf inhärent ganzzahlige Probleme, ohne auf mehrkriterielle ganzzahlige Programmierung umzusteigen, was zu Lösungen führt, die die Ganzzahligkeit verletzen.

Häufig gestellte Fragen

Wie unterscheidet sich MOLP von der Zielprogrammierung?

Die Zielprogrammierung ist ein Spezialfall oder eine Variante: Sie wandelt jedes Ziel in ein Aspirationsniveau um und minimiert dann Abweichungen von diesen Zielen, wodurch eine einzelne Lösung entsteht. MOLP in ihrer allgemeinen Form versucht, die vollständige effiziente Grenze zu charakterisieren, ohne Zielniveaus vorzugeben, was dem Entscheidungsträger mehr Flexibilität bietet.

Kann MOLP mehr als zwei Ziele verarbeiten?

Ja, aber die Pareto-Grenze wird jenseits von zwei oder drei Zielen schwieriger zu visualisieren, und die Anzahl der effizienten Extrempunkte kann exponentiell ansteigen. Interaktive Methoden und Techniken für repräsentative Teilmengen werden für vier oder mehr Ziele empfohlen.

Was ist, wenn meine Daten unsicher sind?

Standard-MOLP geht von deterministischen Koeffizienten aus. Unsicherheit kann durch Erweiterung auf stochastische mehrkriterielle lineare Programmierung (Chance Constraints, szenariobasierte Ansätze) oder robuste mehrkriterielle Optimierung behandelt werden, die separate Methoden sind.

Ist MOLP dasselbe wie mehrkriterielle Optimierung?

MOLP ist ein Spezialfall der mehrkriteriellen Optimierung, bei dem alle Ziele und Nebenbedingungen linear sind. Mehrkriterielle Optimierung ist das breitere Feld, das auch nicht-lineare, ganzzahlige und kombinatorische Varianten umfasst.

Welche Skalarisierungsmethode sollte ich verwenden?

Die gewichtete Summenmethode ist einfach, verfehlt aber nicht-konvexe Teile der Grenze. Die Epsilon-Constraint-Methode kann die gesamte Grenze auch für nicht-konvexe Bereiche wiederherstellen und wird im Allgemeinen für eine gründliche Analyse bevorzugt. Interaktive Methoden sind am besten geeignet, wenn die Einbindung des Entscheidungsträgers möglich ist.

Verwandte Methoden

Quellen

  1. Steuer, R. E. (1986). Multiple Criteria Optimization: Theory, Computation, and Application. John Wiley & Sons, New York.

    ISBN: 9780471888468
    Kopiert.
  2. Chankong, V., Haimes, Y. Y. (1983). Multiobjective Decision Making: Theory and Methodology. North-Holland, New York.

    Publikationsreferenz öffnen
    Kopiert.