In dieser Lektion wird mit Hilfe eines einfachen Produkt-Mix-Problem, hier Better Bread Bakery genannt, gezeigt, wie lineare Optimierungsprobleme modelliert werden können.
Der Zweck dieser Lektion ist es, eine Einführung in die Modellbausteine
zu geben.
Zu Beginn der Modellformulierung eines linearen Optimierungsproblems sind diese Modellbausteine zu identifizieren.
Der erste Schritt besteht in der Identifizierung und Namensgebung der Entscheidungsvariablen, d.h. der Elemente eines Modells, über die der Entscheidungsträger verfügen kann und deren Werte die Lösung des Modells determinieren.
Der nächste Schritt ist die Bestimmung der Zielfunktion und diese mit Hilfe der Entscheidungsvariablen zu beschreiben. Die Zielfunktion enthält das Ziel, das man zu erreichen trachtet, in einer quantitativen Form. Hierbei kann die Vorgabe sein, den Wert dieser Zielfunktion zu maximieren oder zu minimieren. Sprechen wir davon, ein Problem optimieren zu wollen, so bedeutet dies, dass wir Werte der Entscheidungsvariablen finden und bestimmen wollen, die zu einem maximalen oder minimalen Wert dieser Zielfunktion führen. In vielen Fällen drückt die Zielfunktion einen Geldbetrag aus, dem es im Falle von Profit zu maximieren, im Falle von Kosen zu minimieren gilt. Es gibt aber auch andere Zielfunktion, z.b. Maximierung der Auslastung.
Nebenbedingungen sind Beschränkungen, denen die Variablen unterliegen. Eine Nebenbedingungen schränkt den Bereich der Werte ein, den eine Variable annehmen kann. Als Beispiel für eine Nebenbedingung seien bestimmte Ressourcen genannt, z.b. Anlagenkapazität oder die Anzahl von Mitarbeitern, die eben nur beschränkt zur Verfügung stehen.
Die Better Bread Bakery ist berühmt für ihre guten Brote. Sie backt zwei verschiedene Brote: "Sunshine", ein weisses Brot und "Moonlight", ein großes, dunkles Brot.
Der Markt und die Nachfrage für diese berühmten Brot ist grandios. Jeder Laib des schmackhaften Sunshine Brotes ergibt einen Nettogewinn von $0.05, beim Moonlight beträgt der Nettogewinn sogar $0.08. Die Fixkosten für den Betrieb der bäckerei belaufen sich auf $4000 je Monat unabhängig von der Menge der gebackenenen Brote.
Die bäckerei ist in zwei Abteilungen untergliedert, die für Backen und Mischen zuständig sind; beide sind Zu Beginn der Modellformulierung eines linearen Optimierungsproblems sind diese Modellbausteine zu identifizieren.
Der erste Schritt besteht in der Identifizierung und Namensgebung der Entscheidungsvariablen, d.h. der Elemente eines Modells, über die der Entscheidungsträger verfügen kann und deren Werte die Lösung des Modells determinieren.
Der nächste Schritt ist die Bestimmung der Zielfunktion und diese mit Hilfe der Entscheidungsvariablen zu beschreiben. Die Zielfunktion enthält das Ziel, das man zu erreichen trachtet, in einer quantitativen Form. Hierbei kann die Vorgabe sein, den Wert dieser Zielfunktion zu maximieren oder zu minimieren. Sprechen wir davon, ein Problem optimieren zu wollen, so bedeutet dies, dass wir Werte der Entscheidungsvariablen finden und bestimmen wollen, die zu einem maximalen oder minimalen Wert dieser Zielfunktion führen. In vielen Fällen drückt die Zielfunktion einen Geldbetrag aus, dem es im Falle von Profit zu maximieren, im Falle von Kosen zu minimieren gilt. Es gibt aber auch andere Zielfunktion, z.b. Maximierung der Auslastung.
Nebenbedingungen sind Beschränkungen, denen die Variablen unterliegen. Eine Nebenbedingungen schränkt den Bereich der Werte ein, den eine Variable annehmen kann. Als Beispiel für eine Nebenbedingung seien bestimmte Ressourcen genannt, z.b. Anlagenkapazität oder die Anzahl von Mitarbeitern, die eben nur beschränkt zur Verfügung stehen.
Die Better Bread Bakery ist berühmt für ihre guten Brote. Sie backt zwei verschiedene Brote: "Sunshine", ein weisses Brot und "Moonlight", ein großes, dunkles Brot.
Der Markt und die Nachfrage für diese berühmten Brot ist grandios. Jeder Laib des schmackhaften Sunshine Brotes ergibt einen Nettogewinn von $0.05, beim Moonlight beträgt der Nettogewinn sogar $0.08. Die Fixkosten für den Betrieb der bäckerei belaufen sich auf $4000 je Monat unabhängig von der Menge der gebackenenen Brote.
Die bäckerei ist in zwei Abteilungen untergliedert, die für Backen und Mischen zuständig sind; beide sind in ihrer Kapazität begrenzt.
In der Backabteilung stehen 10 Backöfen zur Verfügung mit einer Tageskapazität von 140 Backblechen. Auf jedem dieser Backbleche finden 10 Laib Sunshine Brot Platz, jedoch nur 5 der etwas größeren Moonlight Brote. Jede Kombination der beiden Brote ist erlaubt, wobei natürlich zu beachten gilt, dass die großen Brote doppelt so viel Platz wie die kleinen Brote bieten.
In der Mischabteilung können täglich 8000 Laib des Sunshine Brotes und 5000 Laib Moonlight Brot zubereitet werden. Da zwei Mischer zur Verfügung stehen, gibt es keinen Konflikt die beiden Teige herzustellen.
Da die Nachfrage für beide Typen Brot unbegrenz ist, ist es Aufgabe des Managements der BBB, unter den gegebenen Kapazitätsbeschränkungen die beste Mischung beider Brote zu bestimmen, d.h. die Frage zu beantworten, wieviele Laiber Brot von jeder Sorte herzustellen sind, sodass der Gewinn maximal wird.
Im folgenden wird nun gezeigt, wie die Entscheidungsvariablen, die Zielfunktion und die Nebenbedingungen für dieses Modell zu identifizieren sind und wie das Modell in MPL einzugeben ist.
Im Falle unserer bäckerei tragen die Entscheidungsvariablen die Information, wieviele Laiber Brot von jeder Sorte täglich zu backen sind. Um die Lesbarkeit der Modellformulierung zu erhöhen, ist es sinnvoll, den Entscheidungsvariablen Namen zuzuordnen, die erkennen lassen, welche Größen des praktischen Problems die Variablen repräsentieren. Daher führen wir zwei Entscheidungsvariablen mit Namen Sun und Moon ein, die die folgenden Bedeutungen haben sollen:
Sun = die täglich produzierte Anzahl der Laiber Sunshine Brot
Moon = die täglich produzierte Anzahl der Laiber Sunshine Brot
Kennt man die Werte dieser Variablen, so lässt sich der Gewinn der bäckerei berechnen.
In diesem Beispiel soll der tägliche Gewinn maximiert werden. Der spezifische Erlös betrug $0.05 je Laib Sunshine Brot; daher beträgt der Beitrag zum Gewinn, der durch den Verkauf von Sunshine Brot erzielt wird, einsichtigerweise $0.05 mal dem Wert der Sun Variablen.
Entsprechend gilt für den Gewinnbeitrag der Moonlight Brote, die Formel $0.08 mal dem Wert der Moon Variable. Die Werte $0.05 und $0.08 heissen Koeffizienten der korrespondierenden Entscheidungsvariablen in der Zielfunktion. Zur Berechnung des gesamten täglichen Gewinnbeitrags muss man lediglich die Beiträge beider Brotsorten addieren. Allerdings müssen noch die Fixkosten in Abzug gebracht werden, um den täglichen Nettogewinn zu erhalten; das sind also $4000 geteilt durch 30 Tage eines Monats. Damit lautet die zu maximierende Größe:
Profit = 0.05 Sun + 0.08 Moon - 4000/30
Für dieses spezielle Beispiel ist nun die Definition der Zielfunktion abgeschlossen. Der Solver nutzt die Zielfunktion als Kriterium zur Bestimmung der optimalen Lösung.
Die erste Nebenbedingung in der Backabteilung mag ein wenig kompliziert erscheinen, da sie beide Brottypen verknüpft. Es ist möglich, z.b. 10 Sunshine Brote oder 5 Moonlight Brote auf jedem Backbleck zu plazieren, aber auch jede beliebige Kombination der beiden Brote. Der Ausdruck 1/10 Sun + 1/5 Moon liefert uns gerade den gesamten Gebrauch der Backbleche. Misst man die Kapazität eines jeden Backofens als Anzahl der Backbleche, die er täglich bearbeiten kann (10 x 140), so lautet die Nebenbedingung:
1/10 Sun + 1/5 Moon <= 10 x 140
In der Mischabteilung können wir die Nebenbedingungen dagegen wie folgt formulieren:
Mit der Zielfunktion und all den Nebenbedingungen ergibt sich zusammengefasst die folgende Formulierung des linearen Optimierungsproblems:
Max
Profit = 0.05 Sun + 0.08 Moon - 4000/30
unter den Nebenbedingungen
1/10 Sun + 1/5 Moon <= 10 x 140
Sun <= 8000
Moon <= 5000
Hat man erst mal diese Formulierung, so ist ein Großteil der Arbeit bereits geleistet. Wie im folgenden nämlcih sichtbar wird, akzpetiert MPL nämlich eine Eingabe, die der mathematischen Formulierung sehr ähnelt.
Start der MPL Applikation.
Wähle New aus dem File Menu zur Erzeugung einer neuen, leeren Modelldatei.
Wähle Save As aus dem File Menu und speichern der Datei unter dem Namen Bakery2.mpl.
Der Kodierung des Modells in der MPL Modellierungssprache steht nun nichts mehr entgegen. Der MPL Modelleditor ist ein Standardtexteditor, der die Eingabe des Modells erlaubt und dabei verschiedene Operationen am Modelltext erlaubt. In den Modelleditor soll nun die folgende Modellformulierung eingegeben werden: in ihrer Kapazität begrenzt.
In der Backabteilung stehen 10 Backöfen zur Verfügung mit einer Tageskapazität von 140 Backblechen. Auf jedem dieser Backbleche finden 10 Laib Sunshine Brot Platz, jedoch nur 5 der etwas größeren Moonlight Brote. Jede Kombination der beiden Brote ist erlaubt, wobei natürlich zu beachten gilt, dass die großen Brote doppelt so viel Platz wie die kleinen Brote bieten.
In der Mischabteilung können täglich 8000 Laib des Sunshine Brotes und 5000 Laib Moonlight Brot zubereitet werden. Da zwei Mischer zur Verfügung stehen, gibt es keinen Konflikt die beiden Teige herzustellen.
Da die Nachfrage für beide Typen Brot unbegrenz ist, ist es Aufgabe des Managements der BBB, unter den gegebenen Kapazitätsbeschränkungen die beste Mischung beider Brote zu bestimmen, d.h. die Frage zu beantworten, wieviele Laiber Brot von jeder Sorte herzustellen sind, sodass der Gewinn maximal wird.
Im folgenden wird nun gezeigt, wie die Entscheidungsvariablen, die Zielfunktion und die Nebenbedingungen für dieses Modell zu identifizieren sind und wie das Modell in MPL einzugeben ist.
Im Falle unserer bäckerei tragen die Entscheidungsvariablen die Information, wieviele Laiber Brot von jeder Sorte täglich zu backen sind. Um die Lesbarkeit der Modellformulierung zu erhöhen, ist es sinnvoll, den Entscheidungsvariablen Namen zuzuordnen, die erkennen lassen, welche Größen des praktischen Problems die Variablen repräsentieren. Daher führen wir zwei Entscheidungsvariablen mit Namen Sun und Moon ein, die die folgenden Bedeutungen haben sollen:
Sun = die täglich produzierte Anzahl der Laiber Sunshine Brot
Moon = die täglich produzierte Anzahl der Laiber Sunshine Brot
Kennt man die Werte dieser Variablen, so lässt sich der Gewinn der bäckerei berechnen.
In diesem Beispiel soll der tägliche Gewinn maximiert werden. Der spezifische Erlös betrug $0.05 je Laib Sunshine Brot; daher beträgt der Beitrag zum Gewinn, der durch den Verkauf von Sunshine Brot erzielt wird, einsichtigerweise $0.05 mal dem Wert der Sun Variablen.
Entsprechend gilt für den Gewinnbeitrag der Moonlight Brote, die Formel $0.08 mal dem Wert der Moon Variable. Die Werte $0.05 und $0.08 heissen Koeffizienten der korrespondierenden Entscheidungsvariablen in der Zielfunktion. Zur Berechnung des gesamten täglichen Gewinnbeitrags muss man lediglich die Beiträge beider Brotsorten addieren. Allerdings müssen noch die Fixkosten in Abzug gebracht werden, um den täglichen Nettogewinn zu erhalten; das sind also $4000 geteilt durch 30 Tage eines Monats. Damit lautet die zu maximierende Größe:
Profit = 0.05 Sun + 0.08 Moon - 4000/30
Für dieses spezielle Beispiel ist nun die Definition der Zielfunktion abgeschlossen. Der Solver nutzt die Zielfunktion als Kriterium zur Bestimmung der optimalen Lösung.
Die erste Nebenbedingung in der Backabteilung mag ein wenig kompliziert erscheinen, da sie beide Brottypen verknüpft. Es ist möglich, z.b. 10 Sunshine Brote oder 5 Moonlight Brote auf jedem Backbleck zu plazieren, aber auch jede beliebige Kombination der beiden Brote. Der Ausdruck 1/10 Sun + 1/5 Moon liefert uns gerade den gesamten Gebrauch der Backbleche. Misst man die Kapazität eines jeden Backofens als Anzahl der Backbleche, die er täglich bearbeiten kann (10 x 140), so lautet die Nebenbedingung:
1/10 Sun + 1/5 Moon <= 10 x 140
In der Mischabteilung können wir die Nebenbedingungen dagegen wie folgt formulieren:
Mit der Zielfunktion und all den Nebenbedingungen ergibt sich zusammengefasst die folgende Formulierung des linearen Optimierungsproblems:
Max
Profit = 0.05 Sun + 0.08 Moon - 4000/30
unter den Nebenbedingungen
1/10 Sun + 1/5 Moon <= 10 x 140
Sun <= 8000
Moon <= 5000
Hat man erst mal diese Formulierung, so ist ein Großteil der Arbeit bereits geleistet. Wie im folgenden nämlcih sichtbar wird, akzpetiert MPL nämlich eine Eingabe, die der mathematischen Formulierung sehr ähnelt.
Start der MPL Applikation.
Wähle New aus dem File Menu zur Erzeugung einer neuen, leeren Modelldatei.
Wähle Save As aus dem File Menu und speichern der Datei unter dem Namen Bakery2.mpl.
Der Kodierung des Modells in der MPL Modellierungssprache steht nun nichts mehr entgegen. Der MPL Modelleditor ist ein Standardtexteditor, der die Eingabe des Modells erlaubt und dabei verschiedene Operationen am Modelltext erlaubt. In den Modelleditor soll nun die folgende Modellformulierung eingegeben werden:
TITLE BetterBreadBakery;
MAX
Profit = 0.05 Sun + 0.08 Moon - 4000/30;
SUBJECT TO
1/10 Sun + 1/5 Moon <= 10 * 140;
Sun <= 8000;
Moon <= 5000;
END
Der Unterschied zwischen der im vorherigen Schritt vorgestellten Modellformulierung und der Realisierung in der hier gezeigten Datei ist nur gering. Die Zielfunktion und jede Nebenbedingung wird von einem Semikolon ';' gefolgt. Damit werden in MPL die Nebenbedingung separiert.
Die Leerstellen zwischen den Einträgen und den Zeilen sind in MPL nicht bindend. Es ist jedoch sinnvoll, Leerstellen und Extrazeilen zur Verbesserung der Lesbarkeit und des Verständnisses einzufügen. Für MPL ist nur der aktuale Text einer Modelldatei relevant.
Nach vollständiger Eingabe des Modells wird mit Hilfe von Save aus dem File Menu die Modelldatei gespeichert.
Nach Eingabe der Modells in den Modelleditors kann die korrekte Syntax des Modells überprüft werden. Wenn MPL einen Fehler findet, so wird dieser im Error Message Fenster mit Hinweis auf die fehlerhafte Zeile und einer Problemerklärung angezeigt. Der Kursor zeigt automatisch auf die fehlerhafte Stelle und hebt das passende Wort hervor.
Zur Überprüfung der Syntax, wählt man Check Syntax aus dem Run Menu. Sind keine Syntaxfehler vorhanden, so bestätigt MPL die syntaktische Korrektheit des Modells. Im Falle von Syntaxfehler werden diese von MPL im Error Message Fenster angezeigt.
Sind bei der Eingabe des bäckereiproblems keine Fehler aufgetreten (Herzlichen Glückwunsch!), so mag es an dieser Stelle vielleicht doch sinnvoll sein, zu sehen, wie diese Fehlermeldungen angezeigt werden. Deshalb wollen wir einmal einen Fehler künstlich produzieren und schauen, wie MPL uns bei der Korrektur des Fehlers hilft.
Dazu entfernen wir im Modelleditor das Semikolon am Ende der ersten Nebenbedingung:
SUBJECT TO
1/10 Sun + 1/5 Moon <= 10 * 140 ! note the missing semicolon
Sun <= 8000;
Moon <= 5000;
Nun wählen wir Check Syntax im Run Menu zur Überprüfung der Syntax. MPL prüft Zeile für Zeile das Modell und entdeckt das fehlende Semikolon bei der Überprüfung der zweiten Nebenbedingung und weist die folgende Fehlermeldung aus:
Das Error-Message Fenster
Durch Drücken der OK Taste gelangt man wieder in den Modelleditor; der Kursor wird automatisch dort positioniert, wo der Syntaxfehler festgestellt wurde, im vorliegenden Falle also beim `<=' in der zweiten Nebenbedingung.
Fügen wir das Semikolon wieder zur ersten Zeile hinzu und führen einen erneuten Syntaxtest durch, so bestätigt MPL die syntaktische Fehlerfreiheit des Modells.
Nachdem nun das Modell vollständig eingegeben wurde, soll das durch 'Bakery2.mpl' kodierte Problem gelöst werden, was in MPL die folgenden Arbeitsschritte auslöst: Überprüfung der Syntax, Überführung des Modells in den Speicher und Übergabe an den Solver, Abarbeitung des mathematischen Lösungsalgorithmus des Solvers, Extraktion der Lösung und Erzeugung des Lösungsdatei. Sobald das Solve Kommando aus dem Menu gewählt wurde, beginnt die Abarbeitung dieser Schritte und entsprechende Log-Meldungen werden ausgewiesen. Dazu ist lediglich folgendes zu tun:
Wähle Solve CPLEX aus dem Run Menu bzw. drücke die Run Solve Taste in der Symbolleiste.
Während der mathematische Lösungsalgorithmus aktiv ist, ist das Status Fenster sichtbar und liefert ständig Informationen über den Lösungsverlauf.
Das Status Fenster für das Bakery2 Modell
Sofern kein Syntaxfehler vorliegt oder sonstige Probleme auftraten, wird sich MPL mit der Meldung "Optimal Solution Found" zurückmelden. Bei Identifizierung eines Syntaxfehlers ist so vorzugehen, wie im vorigen Abschnitt beschrieben.
Nachdem das die optimale Lösung des Problems berechnet wurde, erzeugt MPL eine Standardlösungsdatei, die wichtige Informationen über die Lösung enthält, u.a. den optimalen Wert der Zielfunktion, die Werte und reduzierten Kosten der Variablen sowie die Schlupfvariablen bzw. Schattenpreise der Nebenbedingungen. Die Lösungsdatei übernimmt den Namen der Modelldatei und versieht diese mit der Ergänzung '.sol'. In unserem Beispiel wird also die Lösungsdatei 'Bakery2.sol' erzeugt.
Die Lösungsdatei kann im View Fenster durch Drücken der View Taste im unteren Bereich des Status Fensters angezeigt werden.
View Fenster mit der Bakery2.sol Lösungsdatei
Das View Fenster hält die Lösung im Speicher und erlaubt bequem und leicht, die Lösung in allen Details anzuschauen. Nachstehend ist die vollständige Lösungsdatei zu sehen:
MPL Modeling System - Copyright (c) 1988-1999, Maximal Software, Inc.
--------------------------------------------------------------------------------
MODEL STATISTICS
Problem name: BetterBreadBakery
Filename: Bakery2.mpl
Date: April 2, 1998
Time: 17:29
Parsing time: 0.04 sec
Solver: CPLEX
Objective value: 506.666666667
Iterations: 3
Solution time: 0.14 sec
Constraints: 3
Variables: 2
Nonzeros: 4
Density: 67 %
SOLUTION RESULT
Optimal solution found
MAX Profit = 506.6667
DECISION VARAIBLES
PLAIN VARIABLES
Variable Name Activity Reduced Cost
------------------------------------------------------
Sun 8000.0000 0.0000
Moon 3000.0000 0.0000
------------------------------------------------------
CONSTRAINTS
PLAIN CONSTRAINTS
Constraint Name Slack Shadow Price
------------------------------------------------------
c1 0.0000 -0.4000
c2 0.0000 -0.0100
c3 2000.0000 0.0000
------------------------------------------------------
END
Der erste Teil der Lösungsdatei enthält diverse statistische Daten des Problems, so z.b. den Dateinamen, Datum und Zeit, wann das Problem gelöst wurde, welcher Solver verwendet wurde, den Wert der Zielfunktion und die Größe des Problems.
Der nächste Abschnitt der Lösungsdatei enthält die eigentliche Lösung. Hier ist ersichtlich, ob eine optimale Lösung bestimmt wurde, oder das Problem unbeschränkt oder unzulässig ist. Ausgewiesen wird zudem der Name und der optimale Wert der Zielfunktion. In unserem Fall beträgt der Gewinn der bäckerei $506 pro Tag.
Im Abschnitt DECISION VARIABLE zeigt die Liste der Variablen unsere Modellvariablen Sun und Moon. Die Sun Variable schlägt vor, jeden Tag 8000 Laib Brot zu backen; dies entspricht gerade der Mischkapazität für dieses Brot. Für das Moon Brot sollen dagegen nur täglich 3000 Laib Brot gebacken werden; dies ist weniger als die Mischkapazität.
Im Abschnitt CONSTRAINTS der Lösungsdatei finden wir die Lösungsinformationen zu den Nebenbedingungen. Unser Modell enthielt drei Nebenbedingungen: eine für die Öfen der Backabteilung und zwei für die Mischabteilung. Der Wert Null der Schlupfvariable für die erste Nebenbedingung impliziert, dass die Öfen der Backabteilung bei voller Kapazität backen. In gleicher Weise sehen wir, dass die Mischer für das Sunshine Brot bei voller Kapazität arbeiten, während beim Moonlight Brot noch ein Schlupf bzw. eine Kapazität von 2000 Laib Brot ungenutzt ist.
Da die Kapazität der Öfen der Backabteilung von beiden Broten in Anspruch genommen wird, entscheidet der spezifische Gewinnbeitrag pro Kapazität Backbleck, dass das Sunshine Brot mit voller Kapazität gebacken wird und die restliche Kapazität zum Backen des Moonlight Brotes genutzt wird.