In dieser Lektion 4 wird das Modell der vorherigen Lektion zu einem mehrperiodischen Modell erweitert. Hierzu werden ein neuer Index, der die Zeitperiode indiziert, eingeführt und die betroffenen Vektoren aktualisiert. Zudem werden Bilanzgleichungen konstruiert, die Produktion-, Verkaufs- und Lagervariablen verknüpfen.
Um das Modell zu einem mehrperiodischen Modell zu erweitern, muss zunächst ein weiterer Index bzw. eine weitere Indexmenge erzeugt werden, die die Zeitperioden enthält. Die Indices, d.h. Elemente dieser Indexmenge könnten beispielsweise Monate, Quartale oder Jahre sein.
Während bei einperiodischen Modellen ohne Lagermöglichkeit Verkaufs- und Produktionsmengen identisch sind, können diese in den einzelnen Zeitperioden mehrperiodischer Modelle mit Lagermöglichkeit verschieden sein. Daher müssen nun auch zwei neue Variablen eingeführt werden, die die jeweilige Verkaufsmenge und den aktuellen Lagerbestand in einer Zeitperiode repräsentieren.
In vielen Fällen sind mengenabhängige Lagerkosten je Zeitperiode zu berücksichtigen. In anderen Fällen handelt es sich eher um operative Kosten, etwas in ein Lager einzulagern bzw. wieder zu entnehmen; diese Kosten könnten z.b. Personalkosten repräsentieren. Damit kann es erforderlich sein, Variablen für die Einlagerung und andere für die Entnahme einzuführen.
Da nicht mehr verkauft werden kann als verfügbar ist, verknüpfen die Lagervariablen die Verkaufs- und Produktionsvariablen und insbesondere benachbarte Zeitperioden. Die Nebenbedingungen, die dies leisten, werden auch Bilanzgleichungen genannt; sie stellen sicher, dass sich für jede Zeitperiode die Ein- und Ausgänge in ein Lager gerade ausgleichen.
Typische Lagerbilanzgleichungen stellen für jede Zeitperiode sicher, dass die gesamte Produktionsmenge zuzüglich des Lagerbestandes der vorherigen Periode der Summe aus Verkaufsmenge und übrig gelassen Lagerbestand entsprechen. Nachstehend ein Beispiel für eine typische Lagerbilanzgleichung:
Produce + Inventory[month-1] = Sales + Inventory
In diesem Falle wird die Lagervariable bilanziert. Hierbei bezeichnet Inventory[month-1] den Lagerbestand der vorherigen Periode. Sind Einlagerungs- und Entnahmekosten zu berücksichtigen, so werden zwei Bilanzgleichungen benötigt, z.b.:
Produce + OutInvt = Sales + PutInvt
PutInvt + Inventory[month-1] = OutInvt + Inventory
Die erste Gleichung betrachtet die Anlage bzw. den Standort und bilanziert Produktion und Verkauf mit Ein- und Auslagerungen im Lager. Die zweite Gleichung fokussiert auf das Lager und bilanziert die dortigen Ein- und Ausgänge.
Fast immer sind bei einem Problem Anfangslagerbestände zu berücksichtigen, manchmal auch spezielle Bedingungen an den Endlagerbestand. MPL setzt standardmässig den Anfangslagerbestand, d.h. Inventory[month-1] für Monat 1 auf den Wert Null. Soll ein von Null verschiedener Anfangslagerbestand berücksichtigt werden, so kann man dies wie folgt tun:
INDEX
month := (Jan, Feb, Mar, Apr)
DATA
StartInvt := 450
SUBJECT TO
InitInvt[month=Jan]:
produce + StartInvt = sales + Inventory
InvtBal [month>Jan]:
produce + Inventory[month-1] = sales + Inventory
Für den Monat Januar wird eine Bilanzgleichung mit einem Anfangslagerbestand von 450 Mengeneinheiten erzeugt, wobei der Anfangslagerbestand explizit berücksichtigt wird; für alle übrigen Monate entspricht die Lagerbilanzgleichung der aus dem vorherigen Beispiel. MPL bietet alternative Formulierungen, bei denen die Nebenbedingung nicht dupliziert werden muss; hierbei werden Subindizes verwendet.
In dieser Lektion wird eine neue Formulierung für ein mehrperiodisches Produktionsplanungsproblem entwickelt, wobei auf die Modellformulierung in Lektion 3 zurückgegriffen wird und entsprechende Ergänzungen und Modifikationen vorgenommen werden.
In diesem Problem soll ein Planungshorizont von vier Monaten betrachtet werden; in diesem Fall Januar bis April. Deshalb ist ein Index mit den vier Einträgen Jan, Feb, Mar und Apr zu erzeugen und dieser Index den entsprechenden Vektoren hinzuzufügen.
Wie in Lektion 3 betragen die Verkaufspreise wieder $120.00, $100.00 und $115.00. Statt einer einzelnen Nachfrage, sind jetzt produkt- und monatsspezifische Nachfragen zu berücksichtigen, wie sie in der nachfolgenden Tabelle zusammengestellt sind.
| Production Demand | Jan | Feb | Mar | Apr |
|---|---|---|---|---|
| A1 | 4300 | 4200 | 6400 | 5300 |
| A2 | 4500 | 5400 | 6500 | 7200 |
| A3 | 5400 | 6700 | 7800 | 8200 |
Die Produktionsraten und Produktionskosten bleiben unverändert wie in der Tabelle aus Lektion 3 spezifiziert. Die Anzahl der verfügbaren Produktionstage hängt vom Monat ab: 23 Tage für Januar, 20 für Februar, 23 für März und 22 für April.
Für die zur Verfügung stehenden Lagermöglichkeiten sind die folgenden produktspezifischen Lagerkosten bekannt: für A1 $3.50/Monat, für A2 $4.00/Monat und für A3 $3.00/Monat.
Jedes Produkt benötigt etwa den gleichen Lagerplatz; der gesamt zur Verfügung stehende Lagerplatz bietet Platz für 800 Mengeneinheiten pro Monat.
Nachstehend ist das vollständige Modell für das Problem Planning4 aufgelistet. Gegenüber der Formulierung in Lektion 3 sind einige Erweiterungen erkennbar; sie sind im Fettdruck hervorgehoben und leicht zu verfolgen.
TITLE
Production_Planning4;
INDEX
product := (A1, A2, A3);
month := (Jan, Feb, Mar, Apr);
DATA
Price[product] := (120.00, 100.00, 115.00);
Demand[product, month] := (4300, 4200, 6400, 5300,
4500, 5400, 6500, 7200,
5400, 6700, 7800, 8200);
ProdCost[product] := (73.30, 52.90, 65.40);
ProdRate[product] := (500, 450, 550);
ProdDaysAvail[month] := (23, 20, 23, 22);
InvtCost[product] := (3.50, 4.00, 3.00);
InvtCapacity := 800;
VARIABLES
Produce[product, month] -> Prod;
Inventory[product,month] -> Invt;
Sales[product, month] -> Sale;
MACROS
TotalRevenue := SUM(product, month: Price * Sales);
TotalProdCost := SUM(product, month: ProdCost * Produce);
TotalInvtCost := SUM(product, month: InvtCost * Inventory);
TotalCost := TotalProdCost + TotalInvtCost;
MODEL
MAX Profit = TotalRevenue - TotalCost;
SUBJECT TO
ProdCapacity[month] -> PCap:
SUM(product: Produce / ProdRate) <= ProdDaysAvail;
InvtBal[product, month] -> IBal:
Produce + Inventory[month-1] = Sales + Inventory;
MaxInventory[month] -> MaxI:
SUM(product: Inventory) <= InvtCapacity;
BOUNDS
Sales <= Demand;
END
Start der MPL Applikation.
Wähle File | Open und öffne die Modelldatei Planning3.mpl aus der vorherigen Lektion.
Wähle File | Save As zum Speichern der neuen Modelldatei Planning4.mpl
Der Titel des Modells soll geändert werden um klarzustellen, dass nun mit der Modelldatei Planning4 gearbeitet wird.
TITLE
Production_Planning4;
In diesem Beispiel beträgt der Planungshorizont vier Monate. Die neu zu erstellende Indexmenge soll month heissen und die vier Element Jan, Feb, Mar und Apr enthalten. Zunächst soll die Definition für den Index month, wie sie in Fettdruck hervorgehoben ist, zum INDEX-Abschnitt hinzugefügt werden:
INDEX
product := (A1, A2, A3);
month := (Jan, Feb, Mar, Apr);
In Abschnitt DATA bleiben die meisten Definitionen gegenüber Lektion 3 unverändert. Der Datenvektor Demand muss jedoch um den Index month erweitert werden, da, wie weiter oben definiert, für jeden Monat andere Nachfragen vorliegen. Nun soll der Index month zur Deklaration des Demand Datenvektors hinzugefügt und von der Liste der folgenden Werte gefolgt werden:
DATA
Price[product] := (120.00, 100.00, 115.00);
Demand[product,month] := (4300, 4200, 6400, 5300,
4500, 5400, 6500, 7200,
5400, 6700, 7800, 8200);
Die bisherige Datenkonstante ProdDaysAvail muss nun, ähnlich wie der Demand-Datenvektor, zeitabhängig werden. Durch Hinzufügung des month-Indexes wird sie daher von einer Datenkonstante in einen Datenvektor umgewandelt. Mit den vorliegenden Daten über die zur Verfügung stehenden Tage wird ProdDaysAvail durch die folgenden Eingaben aktualisiert:
ProdCost[product] := (73.30, 52.90, 65.40);
ProdRate[product] := (500, 450, 550);
ProdDaysAvail[month] := (23, 20, 23, 22);
Zur Berücksichtigung der Lagerkosten und der Lagerkapazitäten soll nun der zusätzliche Datenvektor InvtCost und die neue Datenkonstante InvtCapacity hinzugefügt werden. An das Ende des DATA-Abschnittes sollen daher die folgenden Definitionen hinzugefügt werden:
InvtCost[product] := (3.50, 4.00, 3.00);
InvtCapacity := 800;
Es sind nun zwei neue Variablen in das Modell einzubauen: eine Verkaufs-Variable wird benötigt, um zu beschreiben wieviel monatlich verkauft wird, und eine Lager-Variable repräsentiert, wieviel Produkt in jedem Monat gespeichert werden soll. Zudem muss die Produce-Variable um den month-Index erweitert werden, um zu berücksichtigen, dass auch die Produktion zeitabhängig ist. Im VARIABLES-Abschnitt sind daher die folgenden änderungen vorzunehmen:
VARIABLES
Produce[product, month] -> Prod;
Inventory[product,month] -> Invt;
Sales[product, month] -> Sale;
Wie schon im vorherigen Modell in Lektion 3 werden mit Hilfe des Symbols '->' (lese: alias) Abkürzungen für die Variablen definiert, um Konflikte mit Namensbeschränkungen einiger LP-Solver zu vermeiden.
Das einperiodische Modell enthielt bereits die gesamten Erlöse und Produktionskosten in der Zielfunktion. Allerdings müssen diese Einträge nun auch durch Hinzufügung des month-Indexes zeitabhängig gemacht werden. Neu hinzu kommen die Lagerkosten. Auch hier ist es wieder wie in Lektion 3 sinnvoll, für die Darstellung der Summenterme Makros zu benutzen.
Bei der Berechnung der Erlöse und Produktionskosten werden die Produce durch die Verkaufs--Variablen ersetzt und, ebenso wie die Produce-Variablen in den Produktionskosten, in den Summationen um den month-Index erweitert. Die gesamten Lagerkosten berechnen sich als Summe aller Produkte aus Lagerkosten und Lagerbestand.
Im MACROS-Abschnitt sind zunächst die Produce- durch die Verkaufs-Variablen zu ersetzen. Dann ist bei der Summation der Produktionskosten der month-Index hinzuzufügen. Schließlich ist eine neue Makrodefinition für die gesamten Lagerkosten erforderlich:
MACROS
TotalRevenue := SUM(product, month: Price * Sales);
TotalProdCost := SUM(product, month: ProdCost * Produce);
TotalInvtCost := SUM(product, month: InvtCost * Inventory);
TotalCost := TotalProdCost + TotalInvtCost;
Zu beachten ist, dass der Makro für die gesamten Produktionskosten in TotalProdCost umbenannt wurde. Zusätzlich wurde der neue Makro TotalCost hinzugefügt; er liefert als Summe zweier Makros die gesamten Kosten. Damit bleibt die Zielfunktion selbst unverändert:
MODEL
MAX Profit = TotalRevenue - TotalCost;
In der Nebenbedingung, die die Beschränkung der Produktionskapazität ausdrückt, wird lediglich der month-Index zur Definition hinzugefügt; der übrige Teil der Nebenbedingung bleibt unverändert.
SUBJECT TO
ProdCapacity[month] -> PCap:
SUM(product: Produce / ProdRate) <= ProdDaysAvail;
Wie dieses Beispiel zeigt, ist es in MPL nicht nötig, die Indizes in den algebraischen Ausdrücken bei den Daten- oder Variablenvektoren mitzuführen. Dies bietet den Vorteil, dass bei Modelländerungen, in den ein Vektor von einem zusätzlichen Index abhängen soll, der Anpassungsaufwand sich nur auf die Definition der Vektoren beschränkt. MPL sorgt danach selbst für die konsistente Handhabung der Vektoren.
Fügt man ein Lagerbestands-Variable zu einem Modell hinzu, so ist notwendigerweise auch eine Lagerbilanzgleichung erforderlich. Im vorliegenden Fall wird diese für alle Kombinationen aus Produkten und Monaten erzeugt und stellt sich, dass die Summe aus aktueller Produktionsmenge und vorhandenem Lagerbestand entspricht. Nun soll die nachfolgende Bedingung InvtBal zu der bereits bestehenden Nebenbedingung ProdCapacity hinzugefügt werden:
InvtBal[product, month] -> IBal:
Produce + Inventory[month-1] = Sales + Inventory;
MPL unterstützt den Zugriff auf die Elemente einer Indexmenge unter Berücksichtigung der Reihenfolge, in der diese Elemente definiert wurden. Damit ist es möglich, Ausdrücke wie [month-1] zu konstruieren. Dabei ist [month-1] nicht als numerischer Ausdruck, also Differenz zu interpretieren, sondern, relativ zur aktuellen Periode month auf die vorherige Periode.
Da in diesem Beispiel nur ein begrenzter Lagerplatz, d.h. eine limitierte Lagerkapazität zur Verfügung steht, muss das Modell um eine Lagerkapazitätsbeschränkung ergänzt werden. Eingangs wurde erwähnt, dass alle Produkte denselben Lagerplatz beanspruchen. Unter der Annahme, dass die Lagerkapazität in denselben Mengeneinheiten wie die der Produktionsvariablen gemessen wird, ergibt die Summe über alle Produktionsvariablen bereits den beanspruchten Lagerbedarf und kann dann in Relation zur verfügbaren Lagerkapazität gesetzt werden. Diese Bedingung soll nun dem Modell hinzugefügt werden:
MaxInventory[month] -> MaxI:
SUM(product: Inventory) <= InvtCapacity;
In der bisher existierenden oberen Schranke für die Nachfragen müssen die Produktions-Variablen noch durch die Verkaufs-Variable ersetzt werden:
BOUNDS
Sales <= Demand;
Nach dieser Ersetzung sind nun alle Korrekturen beendet und die Modelldatei kann durch Wahl von Save im File-Menu gespeichert werden.
Nachdem nun das Modell vollständig eingegeben wurde, soll das durch 'Planning4.mpl' kodierte Problem gelöst werden. Hierzu wird im Run-Menu die Option Solve CPLEX gewählt. Sofern alle Daten richtig eingegeben und alle Modifikationen korrekt durchgeführt wurden, meldet sich MPL mit der Meldung Optimal Solution Found zurück. 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 die Standardlösungsdatei 'Planning4.sol'. Die Lösungsdatei kann im View Fenster durch Drücken der View Taste im unteren Bereich des Status Fensters angezeigt werden. Nachstehend ist die vollständige Lösungsdatei zu sehen:
MPL Modeling System - Copyright (c) 1988-2001, Maximal Software, Inc.
--------------------------------------------------------------------------------
MODEL STATISTICS
Problem name: Production_Planning4
Filename: Planning4.mpl
Date: April 17, 1998
Time: 22:52
Parsing time: 0.15 sec
Solver: CPLEX
Objective value: 2246007.27273
Iterations: 26
Solution time: 0.04 sec
Constraints: 20
Variables: 36
Nonzeros: 69
Density: 10 %
SOLUTION RESULT
Optimal solution found
MAX Profit = 2246007.2727
MACROS
Macro Name Values
-----------------------------------------------
TotalRevenue 5386045.4545
TotalProdCost 3139078.1818
TotalInvtCost 960.0000
TotalCost 3140038.1818
-----------------------------------------------
DECISION VARIABLES
VARIABLE Produce[product,month] :
product month Activity Reduced Cost
----------------------------------------------------
A1 Jan 4300.0000 0.0000
A1 Feb 4200.0000 0.0000
A1 Mar 4409.0909 0.0000
A1 Apr 3545.4545 0.0000
A2 Jan 1800.0000 0.0000
A2 Feb 0.0000 -3.6667
A2 Mar 0.0000 -4.7889
A2 Apr 0.0000 -0.7889
A3 Jan 5720.0000 0.0000
A3 Feb 6380.0000 0.0000
A3 Mar 7800.0000 0.0000
A3 Apr 8200.0000 0.0000
----------------------------------------------------
VARIABLE Inventory[product,month] :
product month Activity Reduced Cost
----------------------------------------------------
A1 Jan 0.0000 -0.2000
A1 Feb 0.0000 -2.4900
A1 Mar 0.0000 -3.5000
A1 Apr 0.0000 -123.5000
A2 Jan 0.0000 -4.0000
A2 Feb 0.0000 -4.0000
A2 Mar 0.0000 0.0000
A2 Apr 0.0000 -108.0000
A3 Jan 320.0000 0.0000
A3 Feb 0.0000 -2.0818
A3 Mar 0.0000 -3.0000
A3 Apr 0.0000 -110.8545
----------------------------------------------------
VARIABLE Sales[product,month] :
product month Activity Reduced Cost
----------------------------------------------------
A1 Jan 4300.0000 4.3100
A1 Feb 4200.0000 1.0100
A1 Mar 4409.0909 0.0000
A1 Apr 3545.4545 0.0000
A2 Jan 1800.0000 0.0000
A2 Feb 0.0000 0.0000
A2 Mar 0.0000 0.0000
A2 Apr 0.0000 -4.0000
A3 Jan 5400.0000 11.0636
A3 Feb 6700.0000 8.0636
A3 Mar 7800.0000 7.1455
A3 Apr 8200.0000 7.1455
----------------------------------------------------
CONSTRAINTS
CONSTRAINT ProdCapacity[month] :
month Slack Shadow Price
-------------------------------------------
Jan 0.0000 -21195.0000
Feb 0.0000 -22845.0000
Mar 0.0000 -23350.0000
Apr 0.0000 -23350.0000
-------------------------------------------
CONSTRAINT InvtBal[product,month] :
product month Slack Shadow Price
----------------------------------------------------
A1 Jan 0.0000 115.6900
A1 Feb 0.0000 118.9900
A1 Mar 0.0000 120.0000
A1 Apr 0.0000 120.0000
A2 Jan 0.0000 100.0000
A2 Feb 0.0000 100.0000
A2 Mar 0.0000 100.0000
A2 Apr 0.0000 104.0000
A3 Jan 0.0000 103.9364
A3 Feb 0.0000 106.9364
A3 Mar 0.0000 107.8545
A3 Apr 0.0000 107.8545
----------------------------------------------------
CONSTRAINT MaxInventory[month] :
month Slack Shadow Price
-------------------------------------------
Jan 480.0000 0.0000
Feb 800.0000 0.0000
Mar 800.0000 0.0000
Apr 800.0000 0.0000
-------------------------------------------
END
In der Lösung des Problems Planning3 ist der Wert der Zielfunktion, also der Gewinn, mit $2.2M wesentlich höher als der, der sich bei Lösung des Problems Planning3 ergab. Dieser hohe Gewinn resultiert aus einem gesamten Erlös von $5.4Mio bei Geamtkosten von $3.1Mio, die im wesentlichen Produktionskosten darstellen, da sich lediglich im Januar ein moderater Lagerbestand aufbaut.
Bei näherer Betrachtung der Produktions-Variablen in der Lösungsdatei zeigt sich, dass während des gesamten Planungszeitraums die Produkte A1 und A3 produziert werden, allerdings nicht immer genug, um alle Nachfragen zu befriedigen. Vom Produkt A2, werden lediglich im January 1800 Mengeneinheiten hergestellt, da nicht genug Kapazität vorhanden ist, um alle drei Produkte herzustellen.
In Januar werden 320 Mengeneinheiten vom Produkt A3 mehr hergestellt als in diesem Monat nachgefragt. Die zusätzliche Menge wird gelagert, um den Bedarf für den Monat Februar zu erfüllen.