Dies ist der (und wahrscheinlich letzte) Teil von a Lineare Programmierung Serie, die ich geschrieben habe. Mit den Kernkonzepten, die in den früheren Artikeln behandelt werden, konzentriert sich dieser Artikel auf die Zielprogrammierung, die ein weniger häufiges Anwendungsfall (Linear Programming) darstellt. Die Zielprogrammierung ist ein spezifisches lineares Programmieraufbau, das die Optimierung mehrerer Ziele in einem einzelnen LP -Drawback verarbeiten kann.
Am Ende dieses Artikels werden Sie verstehen:
1. Definition der Zielprogrammierung und wann sollte sie verwendet werden
2. Der gewichtete Ziel -Programmieransatz – illustriert mit einem Beispiel
3. Der präventive Ziel -Programmieransatz – illustriert mit einem Beispiel
Definition und Anwendungsfall der Zielprogrammierung
Zielprogrammierung ist ein spezieller Fall einer linearen Programmierung, die es ermöglicht, dass mehrere – häufig widersprüchliche – Ziele ausgeglichen werden. Bei regelmäßigen LP -Problemen wählen Sie eine einzelne Metrik aus, um Einschränkungen zu optimieren (minimieren oder maximieren), um sicherzustellen, dass die optimale Lösung möglich ist. Zielprogrammierung ist eine Technik, mit der mehrere objektive Metriken gleichzeitig gezielt werden können.
Die „Denkweise“ der Zielprogrammierung unterscheidet sich grundlegend von Problemen mit einfachem Vanille -LP. Grundlegende LP -Suche nach Möglichkeiten, um so wenig oder so viel zu bekommen einzel Metrik wie möglich – z. B. den Gewinn maximieren oder Abfall minimieren – unterliegt Einschränkungen. Oft werden widersprüchliche Prioritäten in der Zielfunktion gefunden oder die Einschränkungen. Beispielsweise maximieren Sie den Gewinn (objektiv) unter einer maximalen Abfallmenge (Einschränkung). Mit der Zielprogrammierung können wir wichtige Einschränkungen in die objektive Funktion verschieben, damit wir sie optimieren können, anstatt sie nur einzuschränken. Wir können den Gewinn maximieren und Abfall gleichzeitig minimieren!
Jetzt ist ein guter Zeitpunkt, um das Beispiel zu ermitteln, das wir für den Relaxation des Artikels untersuchen werden:
Stellen wir uns vor, wir verwalten eine Fabrik, die Kleidung herstellt. Unsere Fabrik kann Hosen, Hemden und Kleider herstellen. Jeder Kleidungsstück hat Kosten, Gewinn und Abfall, die mit ihrer Produktion verbunden sind. Wir möchten einen Produktionsplan erstellen, der aufgrund eines Umweltverpflichtung ein gewisses Maß an Gewinn und Verschwendung unter eine bestimmte Menge macht. Nehmen wir an, wir wollen einen Gewinn mit 150.000 Greenback profitieren und wir wollen auch weniger als 20.000 Meter Stoff verschwenden. Zusätzlich zu unseren Zielen können wir nicht mehr als 50.000 US -Greenback an Materialien und Arbeitskräften ausgeben.
Das obige Beispiel oben klingt ein regelmäßiges lineares Programmierungsproblem, oder? Nun, die Wendung ist, dass wir keinen Gewinn von 150.000 US -Greenback erzielen und weniger als 20.000 Yards gleichzeitig verschwenden können. Mit anderen Worten, es würde keine praktikable Lösung geben, wenn wir diese in ein regelmäßiges lineares Programmierungsproblem anschließen würden. In der Regel können die Ziele, die in den Problemen festgelegt sind, nicht alle mit einer einzigen Lösung erreicht werden, da es sonst keinen Sinn bei der Verwendung der Zielprogrammierung geben würde. Wir würden einfach eine regelmäßige alte lineare Programmierung mit unseren Zielen als Einschränkungen verwenden. Der eigentliche Wert der Zielprogrammierung besteht darin, dass sie einen Kompromiss zwischen widersprüchlichen Zielen erstellen kann, wenn eine regelmäßige lineare Programmierung eine nicht realisierbare Lösung erzeugt.
Der eigentliche Wert der Zielprogrammierung besteht darin, dass sie einen Kompromiss zwischen widersprüchlichen Zielen erstellen kann, wenn eine regelmäßige lineare Programmierung eine nicht realisierbare Lösung erzeugt.
Wie kann das Programmierprogrammierung mit widersprüchlichen Zielen ausgleichen und kompromittieren? Es gibt zwei beliebte Ansätze: (1) gewichtet und (2) Präventiv. Wir werden diese in den folgenden Abschnitten ausführlich behandeln.
Der Gewichtsansatz
Hier werden wir uns mit den Particulars des Gewichtsansatzes befassen. Die Gewichtsmethode hat eine einzelne objektive Funktion und führt eine einzelne aus Optimierung Basierend auf (Sie haben es erraten) Gewichte! Die Tatsache, dass nur eine Optimierung unter der Gewichtsmethode ausgeführt wird, magazine wie eine Selbst sein – aber die präventive Methode führt tatsächlich mehrere lineare Programmieroptimierungen aus. Wir werden im nächsten Abschnitt dazu kommen…
Die Gewichtsmethode enthält spezifische Ziele oder Ziele für mehrere Metriken – z. B. mindestens 150.000 US -Greenback in Gewinnverkaufskleidung oder verschwenden nicht mehr als 20 km Stoff. Für die reguläre LP möchten wir vollständig optimieren. Für die Gewichtsmethode der Zielprogrammierung möchten wir so nahe wie möglich an die Ziele erreichen. Nachdem wir ein Ziel erreicht haben, ist die Optimierung bei der weiteren Maximierung oder Minimierung nicht mehr Vorteile, sodass sie das nächst wichtigste Ziel priorisiert. Wenn dies jetzt verwirrend erscheint, machen Sie sich keine Sorgen, dass es sinnvoller ist, wenn wir uns mit dem Beispiel einlassen.
Der objektive Funktion Für den Gewichtsansatz ist speziell formuliert, um die zu minimieren gewichtet Unterschiede zwischen dem Ziel einer Metrik und dem tatsächlichen Wert der Metrik. Lassen Sie uns von oben zu unserem Beispiel springen. Unser Ziel ist es, zu minimieren, wie weit wir von beiden Zielen entfernt sind.
Hier ist die mathematische Formulierung für dieses Ziel:
Mit unserer Zielfunktion müssen wir unsere Einschränkungen definieren. Wir haben zwei Arten von Einschränkungen (1) zielbezogene Einschränkungen und (2) regelmäßige lineare Programmierbeschränkungen (dieselben Einschränkungen, die Sie in der einfachen Vanille -LP finden würden). Sprechen wir zuerst über die zielbezogenen Einschränkungen.
Wir müssen zwei Dinge erstellen, um unsere zielbezogenen Einschränkungen zu errichten, (1) Gewinn- und Abfallfunktionen und (2) A number of Slack Variablen. Lassen Sie uns diese jeweils durchlaufen.
Die Gewinn- und Abfallfunktionen sind sehr einfach. Sie kombinieren unsere Entscheidungsvariablen miteinander, um den Gesamtgewinn zu berechnen, und die Gesamtabfälle ergeben eine bestimmte Lösung. Im Folgenden finden Sie die Formeln, die Gewinn und Verschwendung an die Anzahl der Hosen, Hemden und Kleider, die wir produzieren:
Lassen Sie uns mit unseren Gewinn- und Abfallfunktionen über unsere Slack -Variablen sprechen. Bei der Zielprogrammierung werden Slack -Variablen verwendet, um zu messen, wie weit eine Lösung aus einem Ziel ist. In unserem Beispiel die Variablen P Und W sind beide Slack -Variablen – sie repräsentieren, wie viel niedriger unser Gewinn mit unserem Gewinnziel ist und wie viel höher unsere Abfälle mit unserem Abfallziel sind. Slack -Variablen sind in Einschränkungen eingebettet. Im Folgenden finden Sie die Einschränkungen für unsere Gewinn- und Abfallziele – wieder die P’s und die W’s sind unsere lockeren Variablen:
Beachten Sie, dass wir Plus- und Minus -Slack -Variablen haben – dies ermöglicht es uns, das Ziel an beiden Enden zu verpassen. Wir wollen nur die Slack -Variable bestrafen, die in die entgegengesetzte Richtung unseres Ziels geht (z. B. wir wollen nicht bestrafen mehr Gewinn als unser Ziel wollen wir nur bestrafen weniger Gewinn) – Deshalb befindet sich nur eine Slack -Variable professional Ziel in der objektiven Funktion. Schreiben wir mit dieser neuen Notation unsere objektive Funktion um:
Wir haben jetzt die gesamte besondere Arbeit für die Zielprogrammierung geleistet. Das Letzte, was wir tun müssen, ist schnell unsere Einschränkung des einfachen Vanille -Budgets hinzuzufügen. Wir verwenden eine regelmäßige Einschränkung für unser Funds, da dies in unserem Beispiel eine harte Einschränkung darstellt. Im Gegensatz zu Gewinn und Abfall können wir das Funds nicht verletzen.
Jetzt haben wir ein vollständig spezifiziertes Zielprogrammierungsproblem. Lassen Sie es uns in Python einrichten und lösen!
# $150,000 in revenue
drawback += revenue + profit_deviation_neg - profit_deviation_pos == 150000, "Profit_Goal"
# Waste purpose: Not more than 20,000 yards of waste
drawback += waste + waste_deviation_neg - waste_deviation_pos == 20000, "Cost_Goal"
# Funds constraint
drawback += price <= 50000
# Resolve the issue
drawback.clear up()
# Show the outcomes
print("Standing:", pulp.LpStatus(drawback.standing))
print("Pants produced:", pulp.worth(pants))
print("Shirts produced:", pulp.worth(shirts))
print("Clothes produced:", pulp.worth(attire))
print("Value :", pulp.worth(price))
print("Revenue :", pulp.worth(revenue))
print("Revenue deviation (optimistic):", pulp.worth(profit_deviation_pos))
print("Revenue deviation (destructive):", pulp.worth(profit_deviation_neg))
print("Waste :", pulp.worth(waste))
print("Waste deviation (optimistic):", pulp.worth(waste_deviation_pos))
print("Waste deviation (destructive):", pulp.worth(waste_deviation_neg))Diese Optimierung empfiehlt, dass wir 0 Hosen, 5.000 Hemden und 0 Kleider herstellen. Wir machen 150.000 US -Greenback in Gewinn, was genau zu unserem Ziel entspricht, und wir verschwenden 50 km Stoff, was unseren maximalen Abfall um 30.000 Yards übersteigt. Die vollständigen Ergebnisse werden vom Code gedruckt und unten gezeigt:
Jetzt, da wir die Grundstruktur des Gewichtsansatzes nach unten haben, sprechen wir tatsächlich darüber Gewichte! In unserem ersten Beispiel gaben wir einem Greenback Gewinn und einem Hof Abfall gleich. Dies macht wahrscheinlich nicht viel Sinn, weil sie unterschiedliche Einheiten sind. Das Festlegen der Gewichte ist eine subjektive Entscheidung, die der Praktizierende getroffen wird. In unserem Beispiel werden wir entscheiden, dass die Verschwendung von 1,5 Metern Stoff genauso schlecht ist, wie es intestine ist, 1 US -Greenback für Gewinn zu erzielen. Mit anderen Worten, wir erhöhen das Gewicht von Stoffabfällen in unserer objektiven Funktion auf 1,5.
drawback += profit_deviation_neg + 1.5*waste_deviation_posDie Optimierung mit den aktualisierten Preisen empfiehlt, dass wir ungefähr 8.572 Hosen, 7.143 Hemden und 0 Kleider herstellen. Mit dieser Lösung generieren wir Gewinn in Höhe von 107.000 US -Greenback (was ein Ziel -Fehlschlag von 43.000 US -Greenback ist) und verschwenden 20.000 Meter Stoff, das genau zu unserem Ziel passt. Die vollständigen Ergebnisse werden vom Code gedruckt und unten gezeigt:
Das Verschieben der Gewichte der Ziele kann eindeutig einen großen Einfluss auf die Optimierungsergebnisse haben. Wir müssen unsere Gewichte sorgfältig festlegen, um die relative Bedeutung unserer Ziele angemessen auszugleichen!
Jetzt, da wir ein solides Verständnis dafür haben, wie der gewichtete Ansatz funktioniert, wechseln wir auf die Zielprogrammierung mit dem präventiven Ansatz.
Präventivansatz
Während die Gewichtsmethode Ziele mit Gewichten in der objektiven Funktion ausgleichen, bietet die präventive Methode den Zielen durch iterative Optimierungen hierarchischer Priorität. Das sind viele Worte, mach dir keine Sorgen, wir werden es aufschlüsseln!
Hier sind die Schritte zum präventiven Ansatz:
1. Führen Sie eine regelmäßige lineare Programmieroptimierung für Ihr erstes Ziel durch – z. B. den Gewinn maximieren
2. Speichern Sie den objektiven Wert vor diesem Lauf
3. Führen Sie eine weitere reguläre lineare Programmierung beim nächsten wichtigsten Ziel durch – z. B. Abfall minimieren -, fügen Sie jedoch den objektiven Wert aus dem letzten Lauf als Einschränkung hinzu
4. Wiederholen Sie den Vorgang, bis Sie alle Zielmetriken durchlaufen haben
Zwei wichtige Merkmale der präventiven Methode sind (1) die Ziele nach Rang und (2) der objektive Wert eines höheren Wichtigkeitsziels kann nicht verringert werden (aufgrund der harten Einschränkung), wenn die Ziele mit niedrigerer Priorität optimiert werden. Lassen Sie uns ein Beispiel durchgehen, um Instinct aufzubauen.
Nehmen wir für unser Beispiel an, dass Gewinn das wichtigste Ziel ist und die Minimierung von Abfällen das zweite ist. Wir werden mit einer einfachen Vanilleoptimierung beginnen, die den Gewinn maximiert:
# Outline the issue
drawback = pulp.LpProblem("Clothing_Company_Goal_Programming", pulp.LpMaximize)
# Choice variables: variety of pants, shirts, and attire produced
pants = pulp.LpVariable('pants', lowBound=0, cat='Steady')
shirts = pulp.LpVariable('shirts', lowBound=0, cat='Steady')
attire = pulp.LpVariable('attire', lowBound=0, cat='Steady')
# Revenue and value coefficients
revenue = 10 * pants + 3 * shirts + 15 * attire
price = 5 * pants + 1 * shirts + 10 * attire
waste = 1.5 * pants + 1 * shirts + 3 * attire
# Goal perform: Maximize revenue
drawback += revenue
# Constraints
# Funds constraint
drawback += price <= 50000
# Resolve the issue
drawback.clear up()
# Show the outcomes
print("Standing:", pulp.LpStatus(drawback.standing))
print("Pants produced:", pulp.worth(pants))
print("Shirts produced:", pulp.worth(shirts))
print("Clothes produced:", pulp.worth(attire))
print("Value :", pulp.worth(price))
print("Revenue :", pulp.worth(revenue))Die Ergebnisse des Revenue -Maximierungs -LP -Issues sind unten:
Unsere objektive Funktion besagt additionally, dass sie 50.000 Hemden machen und einen Gewinn von 150.000 US -Greenback sammeln. Dies battle nur die erste Optimierung, die wir jedoch laufen werden! Nach dem oben beschriebenen Algorithmus werden wir nun eine weitere LP durchführen, die Abfall minimiert. Wir werden jedoch eine Gewinnbeschränkung von ≥ 150.000 US -Greenback hinzufügen, um sicherzustellen, dass wir keinen schlechteren Gewinn erzielen.
# Outline the issue
drawback = pulp.LpProblem("Clothing_Company_Goal_Programming", pulp.LpMinimize)
# Choice variables: variety of pants, shirts, and attire produced
pants = pulp.LpVariable('pants', lowBound=0, cat='Steady')
shirts = pulp.LpVariable('shirts', lowBound=0, cat='Steady')
attire = pulp.LpVariable('attire', lowBound=0, cat='Steady')
# Revenue and value coefficients
revenue = 10 * pants + 3 * shirts + 15 * attire
price = 5 * pants + 1 * shirts + 10 * attire
waste = 1.5 * pants + 1 * shirts + 3 * attire
# Goal perform: Decrease the material waste
drawback += waste
# Funds constraint
drawback += price <= 50000
drawback += revenue >= 150000
# Resolve the issue
drawback.clear up()
# Show the outcomes
print("Standing:", pulp.LpStatus(drawback.standing))
print("Pants produced:", pulp.worth(pants))
print("Shirts produced:", pulp.worth(shirts))
print("Clothes produced:", pulp.worth(attire))
print("Value :", pulp.worth(price))
print("Revenue :", pulp.worth(revenue))Und hier sind die Ergebnisse dieser endgültigen Optimierung:
Der kluge Beobachter wird feststellen, dass die Optimierung genau das gleiche ist 😅. Dies kann häufig bei der präventiven Methode der Fall sein. Die Einschränkung zuvor optimierter Ziele kann sehr restriktiv sein. Die einzige Zeit, in der iterative Optimierungen unterschiedlich sind, ist, wenn es mehrere Möglichkeiten gibt, die optimalen Werte für frühere Ziele zu erhalten. Zum Beispiel, wenn es zwei Möglichkeiten gab, 150.000 US -Greenback Gewinn zu erzielen; Einer hatte mehr Abfall und der andere hatte weniger, unsere zweite Iteration würde die Ergebnisse der Lösung mit dem niedrigeren Abfall zurückgeben. Bei der präventiven Methode gibt es keinen Kompromiss zwischen den Zielen. Selbst wenn es eine Lösung gäbe, die mit 0 Meter Abfall einen Gewinn in Höhe von 149.000 USD erzielte, würde die präventive Methode immer 150.000 US -Greenback mit Gewinn mit 50.000 Methoden Abfall wählen. Der zusätzliche Gewinn in Höhe von 1000 US -Greenback ist unendlich wichtiger als jede Menge verschwendeter Stoff.
Die präventive Methode sollte angewendet werden, wenn die Ziele eindeutig priorisiert werden, und es besteht keine Substitution zwischen ihnen. Dies bedeutet, dass kein Erfolg bei niedrigeren Prioritätszielen eine verringerte Optimierung bei höheren Priorität kompensieren kann. Bei korrekter Anwendung kann die präventive Methode dazu beitragen, ein Hauptziel zu optimieren und gleichzeitig zu versuchen, gute Lösungen für die Ziele niedrigerer Priorität sehr effektiv zu finden.
Abschluss
Die Zielprogrammierung bietet einen Framework, der die herkömmliche lineare Programmierung erweitert, um mehrere Metriken gleichzeitig zu optimieren. Der gewichtete Ansatz bilt die Prioritäten durch Gewichte in der objektiven Funktion und ist angemessen, wenn objektive Metriken eine relative Bedeutung haben, die quantifiziert werden kann. Die präventive Methode ist ein iterativer Ansatz, der den auf Hierarchie basierenden Metriken Priorität hat. Es ist angemessen, wenn einige Ziele ganz wichtiger sind als andere. Beide Ansätze können leistungsstarke Optimierungstechniken sein, wenn sie im richtigen Kontext angewendet werden!
Viel Spaß beim Optimieren!