MPL erlaubt die Verwendung einer Vielzahl von Vektoren, Daten, Nebenbedingungen und unterstützt diese mit intuitiven und flexiblen Ausdrucksformaten. Während in Lektion einfache Variablen und Nebenbedingungen sowie die Zielfunktion eingeführt wurden, werden in dieser Lektion mehrere neue Elemente behandelt, die benötigt werden, um größere Probleme zu modellieren.
Im bäckereiproblem der vorherigen Lektion wurden nur zwei Variablen benötigt, die die sinnreichen Namen Sun und Moon erhielten. Praktische Probleme können jedoch leicht hundertausende von Variablen und Nebenbedingungen enthalten, manchmal sogar millionen von Variablen. Es ist nicht leicht, diesen Variablen individuelle Namen zu geben. Daher verwendet man in solchen Problemen üblicherweise Indizes, Vektordaten, Vektorvariablen und Vektornebenbedingungen, um ein Problem kompakt und leicht lesbar zu formulieren. Es wird gezeigt, wie diese Konstrukte in MPL genutzt werden können.
Indexmengen, bzw. ihre Elemente, die Indizes, identifizieren die eigentlichen Modellobjekte und definieren so den Bereich, über den ein Modell konstruiert wird, beinhalten implizit die Dimension des Problems, und erlauben leicht, die Problemgröße zu variieren. Ein Index besteht aus seinem Namen und der zugehörigen Indexmenge. Die Begriffe Index, Indexmenge und Indizes werden je nach Kontext nahezu synonym verwendet. Sobald die Indexmengen definiert sind, ist es leicht, die Vektoren der Daten, Variablen und Nebenbedingungen zu definieren und erzeugen.
Gerade bei Problemen, die durch Indizes versehene Variablen und Nebenbedingungen enthalten, zeigt sich der eigentliche Nutzen algebraisch-strukturierter Modellierungssprachen wie z.b. MPL, die es erlauben, große Probleme lesbar zu kodieren. Beispiele von Modellobjekten bzw. Indizes sind:
Vektoren im Umfeld der Modellierungssprachen sind Zusammenfassungen gleichartiger Elemente eines Modells, d.h. solcher, denen Eigenschaften und Zweck gemein sind. Diese Vektoren werden kompakt mit Hilfe der Indizes definiert; danach brauchen die Elemente nicht einzeln angesprochen zu werden. Diese Vektoren können auch von mehreren Indizes gleichzeitig abhängen, z.b. über Produkte und Zeitperioden definiert werden
Datenvektoren werden verwendet, um die in Form von Listen oder Tabellen vorliegenden Problemdaten oder Koeffizienten des Modells zu verwalten. Für jeden Indexwert wird dem Datenvektor genau ein Wert zugeordnet, z.b. durch eine explizite Wertzuweisung in der Modelldatei oder, eleganter, durch Zugriff auf die Werte einer externen Datei. In einem Produktionsplanungsmodell mit einem Produktindex sind typische Beispiele für solche Datenvektoren:
Variablenvektoren können in ähnlicherweise wie Datenvektoren definiert werden und enthalten eine Kollektion von Variablen für die Werte eines bestimmtes Index. Derartige Variablen geben Auskunft darüber ...:
Nebenbedingungsvektoren sind entsprechend über Indizes definierte Kollektionen von Nebenbedingungen. Diese können z.b. über Produkte und Zeitperioden definiert sein und beispielsweise
repräsentieren.
Datenkonstanten werden im Modell zur Verbesserung der Lesbarkeit verwendet und erleichtern die Wartbarkeit. Ihnen werden direkt Werte zugewiesen ohne dabei auf Indizes zurückzugreifen.
In Modellen der linearen Optimierung ist häufig über die Elemente eines Vektors zu summieren. In MPL wird dazu das Befehlswort SUM verwendet, das den Vektor und die zu summierenden Beiträge umschliesst. Ihnen ist eine Liste von Indizes vorangestellt. In der Definition der Summenbeiträge tritt lediglich eine Variable je Term auf; jeder Term kann mit möglicherweise mehreren Datenvektoren multipliziert werden. Im ersten Fall des nachstehenden Beispiels wird über alle Produkte, d.h. über alle Elemente der Indexmenge product, summiert; die Summenterme sind jeweils das Produkt aus Preis und Verkaufsmenge (hier durch die Verkaufsvariable Sales repräsentiert). Im zweiten Fall wird über alle Produkte und alle Monate das Produkt aus Produktionskosten und produzierter Menge summiert.
SUM(product: Price * Sales);
SUM(product, month: ProdCost * Produce);
Zu bemerken ist hierbei, dass stets automatisch über alle Elemente, d.h. Indizes einer Indexmenge summiert wird, falls es nicht, wie in Lektion 6 und 7 beschrieben, explizit anders gefordert wird. Im folgenden wird eine Modellformulierung erzeugt, die demonstriert, wie Indizes und Vektoren in MPL verwendet werden. In der vorherigen Lektion haben wir eine kleines Produkt-Mix Problem als Modell mit zwei Variablen und drei Nebenbedingungen formuliert. In dieser Lektion wird ein ähnliches Problem formuliert, diesmal aber mit drei Produkten, die wir A1, A2 und A3 nennen. Für diese drei Produkte wird ein Index bzw. eine Indexmenge erzeugt, mit deren Hilfe wiederum eine Variablenvektor erzeugt wird, der repräsentiert, wieviel von jedem Produkt produziert werden soll.
Im folgenden wird eine Modellformulierung erzeugt, die demonstriert, wie Indizes und Vektoren in MPL verwendet werden. In der vorherigen Lektion haben wir eine kleines Produkt-Mix Problem als Modell mit zwei Variablen und drei Nebenbedingungen formuliert. In dieser Lektion wird ein ähnliches Problem formuliert, diesmal aber mit drei Produkten, die wir A1, A2 und A3 nennen. Für diese drei Produkte wird ein Index bzw. eine Indexmenge erzeugt, mit deren Hilfe wiederum eine Variablenvektor erzeugt wird, der repräsentiert, wieviel von jedem Produkt produziert werden soll.
Die neuen Begriffe Indizes und Vektoren werden auf ein kleines Produkt-Mix-Problem angewendet, in dem untersucht werden soll, wie bei gegebener Nachfrage die Produktionskapazität zwischen den um die Kapazität konkurrierenden Produkten verteilt werden soll und welche Produktionsmengen dann optimal sind.
Für jedes Produkt ist der Verkaufspreis bekannt: $120.00 für A1, $100.00, für A2 und $115.00 für A3. Die Verkausfmöglichkeiten sind diesmal beschränkt; es gibt für jedes Produkt eine maximale Nachfrage: 4300 für A1, 4500 für A2 und 5400 für A3.
Die Produktionskapazität wird durch die Produktionsrate spezifiziert, die spezifiziert, welche Menge von jedem Produkt täglich produziert werden kann. Es stehen 22 Produktionstage zur Verfügung. Produktionsraten und Produktionskosten sind produktspezifisch und in der folgenden Tabelle gegeben:
| Production | A1 | A2 | A3 |
|---|---|---|---|
| Production Cost | $73.30 | $52.90 | $65.40 |
| Production Rate | 500 | 450 | 550 |
Der nächste Schritt besteht nun darin, das oben formulierte Modell in MPL zu kodieren. Das nachstehende Listing der Modellformulierung gibt einen Überblick über die zu erzeugende Modelldatei Planning3.
TITLE
Production_Planning3;
INDEX
product := (A1, A2, A3);
DATA
Price[product] := (120.00, 100.00, 115.00);
Demand[product] := (4300, 4500, 5400);
ProdCost[product] := (73.30, 52.90, 65.40);
ProdRate[product] := (500, 450, 550);
ProdDaysAvail := 22;
VARIABLES
Produce[product] -> Prod;
MACROS
TotalRevenue := SUM(product: Price * Produce);
TotalCost := SUM(product: ProdCost * Produce);
MODEL
MAX Profit = TotalRevenue - TotalCost;
SUBJECT TO
ProdCapacity -> PCap:
SUM(product: Produce / ProdRate) <= ProdDaysAvail;
BOUNDS
Produce <= Demand;
END
Hier wird nun wieder schrittweise das Modell kodiert.
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 Planning3.mpl.
Der Titel ist zwar nur optional, aber ein geeigneter Platz, dem Modell einen Namen zu geben. Zudem wird er in der Lösungsdatei verwendet, um das Modell zu identifizieren. Es sollte nun ein leeres Editorfenster geöffnet sein, in dem die MPL Formulierung eingegeben werden kann. Um einen Titel für das Planning3 Modell einzugeben, wird der folgende Text in den Modelleditor eingegeben:
TITLE
Production_Planning3;
Ein MPL Modell beginnt meist mit einem INDEX Abschnitt, indem all Indizes des Modells definiert werden. In vorliegendem Beispielproblem bilden die drei Produkte A1, A2 und A3 den Index bzw. die Indexmenge product. Gleich nach Eingabe des Titels erfolgt im INDEX Abschnitt die Definition dieses Indexmenge product wie folgt:
INDEX
product := (A1, A2, A3);
Nach Definition der Indizes folgt in MPL meist der DATA Abschnitt, in dem die Datenvektoren und Datenkonstanten des Modells definiert werden. Als erster Datenvektor soll die Produktpreise, die in der Problembeschreibung gegeben wurden, eingegeben werden.
Dazu wird im Modelleditor gleich nach der Definition der Indizes ein DATA Abschnitt eingefügt, in dem der Datenvektor Price gefolgt vom Index [product] in eckigen Klammern eingegeben wird:
DATA
Price[product] := (120.00, 100.00, 115.00);
Dieser Deklaration folgt, verknüpft durch das Zuordnungssymbol ':=', die Wertzuweisung der Produktpreise in Form einer Liste. Hierbei ist zu beachten, dass die Liste von runden Klammern umgeben ist und die einzelnen Elemente durch Leerzeichen, Komma oder beides getrennt sind. Jeder Datenvektor muss durch ein Semikolon beendet und so von weiteren Definition getrennt werden.
Die Problembeschreibung enthällt weiter Daten, die die Nachfrage, Produktionskosten und Produktionsraten beschreiben, d.h. eine bestimmte Nachfrage für jedes Produkt, Kosten für die Produktion und die tägliche Produktionskapazität. Um diese Daten in MPL einzugeben, werden nach dem Price Datenvektor die folgenden Definitionen zum DATA Abschnitt hinzugefügt.:
Demand[product] := (4300, 4500, 5400);
ProdCost[product] := (73.30, 52.90, 65.40);
ProdRate[product] := (500, 450, 550);
In der Problembeschreibung ist weiter ausgeführt, wieviele Produktionstage zur Verfügung stehen. Die Definition des ProdRate Datenvektors wird durch die folgende Eingabe gefolgt:
ProdDaysAvail := 22;
Die Definition der Variablen erfolgt im VARIABLES Abschnitt. In der Problembeschreibung ist u.a. gefragt, wieviel von jedem Produkt produziert werden soll. hierzu wird der Variablenvektor Produce über dem Index product eingeführt. Im Modelleditor wird hierzu zunächst der VARIABLES Abschnitt und dann der Produce Vektor wie folgt definiert:
VARIABLES
Produce[product] -> Prod;
Der Name Prod, der dem Symbol '->' (lese alias) folgt, dient als mögliche Abkürzung des Vektornamens, da manche LP-Solver keine längeren Namen akzeptieren. Für Anwender, die längere Namen bevorzugen, stehen damit im MPL Modell längere Namen zur Verfügung ohne das es zu Komplikationen mit den LP-Solvern kommt.
In diesem Optimierungsproblem sollte der Gewinn für die Firma maximiert werden; der Gewinn ist hierbei als Differenz Gesamterlös - gesamte Kosten. Der gesamte Erlös ergibt sich als Summe aller Produkte aus Verkaufspreis und der produzierten Menge, die gesamten Kosten entsprechend als Summe aller Produkte aus spezifischen Produktionskosten und Produktionsmenge. Nachfolgend wird beschrieben, wie diese Summen bei Definition der Zielfunktion gebildet werden.
Statt die Summen direkt bei der Definition der Zielfunktion zu verwenden, ist es sinnvoll, die Einzelsummen als Makros zu definieren und die Zielfunktion mit Hilfe der Makros aufzubauen. Makros können überall im Modell verwendet werden und erleichtern die Lesbarkeit des Modells. Sie werden in MAKRO-Abschnitten wie folgt definiert.
MACROS
TotalRevenue := SUM(product: Price * Produce);
TotalCost := SUM(product: ProdCost * Produce);
Zielfunktion und Nebendingungen sind in MPL in einem eigenen MODELL-Abschnitt zu finden und werden dort definiert. Mit Hilfe der oben definierten Makros wird nachfolgend die zu maximierende Zielfunktion Profit definiert:
MODEL
MAX Profit = TotalRevenue - TotalCost;
Die Formel Erlös-Kosten für die Zielfunktion sieht unter Verwendung der Makros recht einfach aus. Das Kennwort MAX indiziert, dass der Wert der Zielfunktion mit dem von uns gewählten Namen Profit \maximiert werden soll.
Nach der Definition der Zielfunktion erfolgt die Eingabe der Nebenbedingungen des Modells in einem eigenen SUBJECT TO-Abschnitt. Zur Erfassung der beschränkten Produktionskapazität sind die Produktionsraten, die definieren, wieviel täglich produziert werden kann, sowie die Anzahl der verfügbaren Produktionstage zu berücksichtigen. Damit lässt sich die Kapazitätsbeschränkung in Form der Nebenbedingung, die wir hier ProdCapacity nennen wollen, implementieren.
Dazu ist im Modelleditor das Schlüsselwort SUBJECT TO sowie die Nebenbedingung selbst einzugeben:
SUBJECT TO
ProdCapacity -> PCap:
SUM(product: Produce / ProdRate) <= ProdDaysAvail;
Summiert wird das Verhältnis aus produzierter Menge und Produktionsrate über alle Produkt. Dies entspricht dem gesamten Zeitbedarf in Tagen zur Herstellung der betreffenden Produktionsmengen. Die Summe muss daher kleiner oder gleich der Anzahl der verfügbaren Produktionstage sein.
Untere und obere Schranken auf die Variablen werden im BOUNDS-Abschnitt definiert. Schranken ähneln den Nebenbedingungen, enthalten aber nur eine Variable. Die Bedingung, dass nicht mehr als die Nachfrage verkauft und damit wegen fehlender Lagermöglichkeit produziert werden kann, dann durch eine obere Schranke auf Produce-Variable im BOUNDS-Abschnitt realisiert werden.
BOUNDS
Produce < Demand;
END
Hierbei ist noch zu beachten, dass in den meisten Modellierungssprachen der Linearen programmierung implizit vorausgesetzt wird, dass die Variablen der unteren Schranke Null genügen müssen; MPL verfolgt ebenfalls diese Regelung.
Der Modell-Abschnitt muss mit Hilfe des Schlüsselwortes END explizit beendet werden. Das Modell wird schließlich durch Wahl von Save im File Menu gesichert.
Nachdem nun das Modell vollständig eingegeben wurde, soll das durch 'Planning3.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. Zur Lösung des Problem sind nun die folgenden Schritte auszuführen:
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 Statusfenster für das Planning3-Modell
Sofern kein Syntaxfehler vorliegt oder sonstige Probleme auftraten, wird sich MPL mit der Meldung "Optima Solution Found" zurückmelden. Bei Identifizierung eines Syntaxfehlers ist die Eingabe des Modells nocheinmal zu überprüfen.
Nachdem das die optimale Lösung des Problems berechnet wurde, erzeugt MPL automatisch 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 'Planning3.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 Planning3.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: Producton_Planning3
Filename: Planning3.mpl1
Date: April 18, 1998
Time: 09:59
Parsing time: 0.57 sec
Solver: CPLEX
Objective value: 544566.636364
Iterations: 3
Solution time: 0.12 sec
Constraints: 1
Variables: 3
Nonzeros: 3
Density: 100 %
SOLUTION RESULT
Optimal solution found
MAX Profit = 544566.6364
MACROS
Macro Name Values
-----------------------------------------------
TotalRevenue 1298181.8182
TotalCost 753615.1818
-----------------------------------------------
DECISION VARIABLES
VARIABLE Produce[product] :
product Activity Reduced Cost
---------------------------------------------
A1 4300.0000 4.3100
A2 1611.8182 0.0000
A3 5400.0000 11.0636
---------------------------------------------
CONSTRAINTS
PLAIN CONSTRAINTS
Constraint Name Slack Shadow Price
------------------------------------------------------
ProdCapacity 0.0000 -21195.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.
Im MACROS-Abschnitt der Lösungsdatei ist eine Auflistung aller Makros des Modells mit ihren zugehörigen Lösungswerten gegeben. So beträgt im Planning3-Problem z.b. der gesamte Erlös $1.298 Millionen, die gesamten Kosten dagegen $754,000. Daraus ergibt sich ein Gewinn von $545,000, was genau dem Wert der Zielfunktion entspricht.
Im Abschnitt DECISION VARIABLE befinden sich alle Variablen des Modells mit ihren zugehörigen optimalen Werte. In diesem Beispiel wird lediglich die Vektorvariable Produce verwendet, die für alle Elemente der Indexmenge product definiert wurde. Die Liste zeigt, dass für die Produkte A1 und A3 die Lösungswerte 4300 und 5400 Mengeneinheiten gerade den Nachfragen für diese Produkte entsprechen. Für das Produkt A2 beträgt der optimale Lösungswert dagegen nur 1612 Mengeneinheiten, also weniger als die Nachfrage. Der Grund hierfür liegt in der nicht ausreichenden Kapazität, die es nicht erlaubt, alle Nachfragen zu bedienen. Da die Produkte A1 und A3 besonders profitable sind, wählt der Solver diese beiden Produkte.
Bei der Inspektion der Ergebnisse fällt übrigens auf, dass der Wert für das Produkt A2 in der Ausgabe der Lösungen 1611.8182 Mengeneinheiten beträgt und nicht 1612. Dies resultiert aus der Tatsache, dass die Variablen in Modellen der Linearen Programmierung als kontinuierliche Variablen behandelt werden. In unserem kleinen Beispiel hat das kaum Konsequenzen und wir können einfach auf den nächsten ganzzahligen Wert 1612 runden. Das ist aber nicht immer so. In den Fällen, in denen es nicht möglich oder sinnvoll, können die Variablen der Forderung unterworfen werden, dass sie nur ganzzahlige Werte annehmen können. Im MPL User Manual finden sich weitere Informationen, wie in MPL Modelle mit ganzzahligen Variablen formuliert werden können.
Im Abschnitt CONSTRAINTS sind die Nebenbedingungen mit ihren optimalen Werten zusammengestellt. Unserer Beispiel enthält nur eine Nebenbedingung, nämlich ProdCapacity. Die mit dieser Nebenbedingung verbundene Schlupfvariable hat den Wert Null, was bedeutet, dass die Nebenbedingung aktiv ist und mit voller Kapazität produziert wird. Der Schattenpreis informiert uns über die Veränderung des Wertes der Zielfunktion, wenn wir die Wert der rechten Seite der Nebenbedingung um eine Einheit ändern. Reduzieren wir die Kapazität um einen Tag, so ist eine Abnahme des Gewinnes um $21,195 zu erwarten.