Häufig liegen die Daten bei großen Modellen nicht in einer sehr dichten Form, sondern nur sehr dünn besetzt (engl.: sparse) vor. Dichtbesetzte Datenstrukturen werden meist nur für zweidimensionale Tabellen verwendet, in der alle Kombinationen aus Zeilen und Spalten gefüllt sind.
Dünnbesetzte Datenstrukturen eignen sich besonders für n-dimensionale Datenvektoren, in denen nicht allen Indexkombinationen ein Wert zugewiesen ist. Sie werden meist in Form von Tabellen mit n+1 Spalten gespeichert, in denen die ersten n Spalten jeweils einen Index bezeichnen und die letzte Spalte den dieser Indexkombination zugeordneten Wert enthält. Der Vorteil bei der Verwendung mit dünnbesetzten Datenstrukturen besteht darin, dass man sich um viele irrelevanten Indexkombinationen gar nicht erst kümmern muss; sie tauchen in der Tabelle nicht auf.
Bei der Formulierung von Produktionsplanungsproblemen kommt es häufig vor, dass zu entscheiden ist, wieviel von welchem Produkt auf welcher Anlage zu produzieren ist. Da aber nicht unbedingt alle Anlagen an allen Standorten vertreten sind, hat man in natürlicherweise eine dünnbesetzte Datenstruktur. Nutzen wir bei der Definition der Daten- und Variablenvektoren die dünnbesetzte Struktur der Daten aus, so lässt sich die Größe des Modells begrenzen. Um dieses Ziel zu erreichen, kann z.B. der WHERE-Befehl zur Formulierung logischer Bedingungen oder der IN-Operator zur Verknüpfung der relevanten Indizes verwendet werden.
MPL stellt den IN-Operator zur Verfügung, um gezielt die Indexelemente einer mehrdimensionalen bzw. zusammengesetzten Indexmenge auszuwählen. Als Beispiel sei eine zusammengesetzte Indexmenge betrachtet, die spezifiziert, welche Anlage an welchem Standort verfügbar ist. Mit Hilfe des IN-Operator lässt sich nun leicht die Summe über alle Anlagen eines bestimmten Standortes bilden.
INDEX
plant := (p1, p2, p3, p4);
machine := (m11, m12, m13, m21, m22, m31, m32, m41);
PlantMach[plant,machine] :=
(p1.m11, p1.m12, p1.m13,
p2.m21, p2.m22,
p3.m31, p3.m32,
p4.m41);
In obigem Beispiel wurde die mehrdimensionale Indexmenge PlantMach definiert, die die an einem Standort existierenden Anlagen mit dem Standort verknüpft.
Mit Hilfe des PlantMach-Indexes werden im folgenden Beispiel nur die Anlagen angesprochen, die an einem bestimmten Standort vorhanden sind:
SUBJECT TO
PlantCapacity[plant] :
SUM(machine IN PlantMach: Produce[machine]) <= MaxCapacity[plant];
Die Summe berechnet die über alle Anlagen eines Standortes produzierte Menge; diese wird dann durch die Kapazität des Standortes beschränkt.
In den vorherigen Lektionen wurde der Umgang mit Daten erläutert, die in Datei gespeichert wurden. In ähnlicher Weise können Indizes in Index-Dateien gespeichert werden. Damit bleibt das Modell übersichtlich und leichter wartbar. Index-Dateien werden mit Hilfe des Schlüsselwortes INDEXFILE und einem zugeordneten Dateinamen eingeführt. Hierzu ein Beispiel:
INDEX
product := INDEXFILE("Product.idx");
month := INDEXFILE("Month.idx");
plant := INDEXFILE("Plant.idx");
Index-Dateien sind einfache ASCII-Dateien, die die Elemente einer speziellen Indexmenge enthalten. Die Indizes in dieser Datei können durch Komma, Leerzeichen oder beides getrennt werden. Nachfolgend nun hierzu ein Beispiel für den product-Index:
! Product.idx - Index element for the product index
A1, A2, A3
Im Umgang mit Modellen, die dünnbesetzte Datenstrukturen enthalten, stellt man meist fest, dass die Menge der Daten sehr groß ist und die Daten meist aus bestehenden, firmenumfassenden Datenbanken extrahiert werden. In den vorherigen Lektionen wurden die Daten explizit im Modell spezifiziert oder aus tabellarischen, zweidimensionalen ASCII-Dateien entnommen. Um auf große Datenbestände zuzugreifen, bietet MPL spezielle Möglichkeiten, Daten von dünnbesetzten Datendateien zu lesen. Dies hat den Vorteil, die Daten in geeigneter Form zu halten, z.B. in relationalen Datenbanken. Nun ein Beispiel:
ProdCost[plant, machine, product] := SPARSEFILE("ProdCost.dat");
Die Datei ProdCost.dat enthält spaltenweise die Indizes und in der letzten Spalte den zugeordneten Kostenwert:
p1, m11, A1, 73.30,
p1, m11, A2, 52.90,
p1, m12, A3, 65.40,
.
.
.
p4, m41, A2, 63.30,
p4, m41, A3, 53.80
Zu beachten ist, dass MPL erlaubt, mehrere Datenspalten, z.B. Produktionskosten und Produktionsraten, in einer einzigen dünnbesetzten Datei zu speichern. Die Spalte mit den entsprechenden Werten wird nach dem Dateinamen in Klammern durch Hinzufügung eines Kommas und einer Zahl, die die Wertespalte auswählt, spezifiziert.
ProdCost[plant, machine, product] := SPARSEFILE("ProdCost.dat", 2);
Zusammenfassend ist festzuhalten: Dünnbesetzte Datenstrukturen treten häufig in in praktischen Problemen auf. Sie können zu großen Modellen mit mehrfachen Indizes und riesigen Datenbeständen führen. Idealerweise strukturiert man das Modell so, dass mehrere Indexdateien das Modell dimensionieren, die Modelldaten von externen Dateien oder Datenbanken eingelesen werden, und das Modell sich im wesentlichen auf die Beschreibung der notwendigen Modellstrukturen beschränkt, d.h. Variablen, Zielfunktionen und Nebenbedingungen.
In dieser Lektion wird das Modell um den Anlagenindex erweitert. Hierzu wird das Modell aus Lektion 6 aufgegriffen und entsprechend modifiziert.
Da nun jeder Standort mit seiner Feinstruktur, d.h. seinen individuellen Anlagen betrachtet wird, werden die Produktionskosten und Produktionsraten abhängig vom Anlagenindex. Die folgende Tabelle enthält zeilenweise die Produktionskosten und Produktionsraten für jede existierende Kombination aus Standort, Anlage und Produkt.
| Plant | Product | Product | ProdCost | ProdRate |
|---|---|---|---|---|
| p1 | m11 | A1 | $73.30 | 500 |
| m11 | A2 | $52.90 | 450 | |
| m12 | A3 | $65.40 | 550 | |
| m13 | A3 | $47.60 | 350 | |
| p2 | m21 | A1 | $79.00 | 550 |
| m21 | A3 | $66.80 | 450 | |
| m22 | A2 | $52.00 | 300 | |
| p3 | m31 | A1 | $75.80 | 450 |
| m31 | A3 | $50.90 | 300 | |
| m32 | A1 | $79.90 | 400 | |
| m32 | A2 | $52.10 | 350 | |
| p4 | m41 | A1 | $82.70 | 550 |
| m41 | A2 | $63.30 | 400 | |
| m41 | A3 | $53.80 | 350 |
Die Produktionsentscheidungen müssen nun berücksichtigen, dass das Produkt an einem Standort durch mehrere Produktionsanlagen bzw. Maschinen hergestellt werden kann. Daher ist die Produktionsvariable Produce um den Anlagenindex machine zu ergänzen. Mit Hilfe der durch WHERE eingeführten logischen Bedingung werden die Indexelemente ausgeschlossen, die nicht existieren, so z.B. die Kombination aus Standort p1, Anlage m11 und Produkt A3.
Nachstehend ist das vollständige Modell für das Problem Planning7 aufgelistet. Gegenüber der Formulierung in Lektion 6 sind einige Erweiterungen erkennbar; sie sind im Fettdruck hervorgehoben und leicht zu verfolgen.
TITLE
Production_Planning7;
INDEX
product := (A1, A2, A3);
month := (Jan, Feb, Mar, Apr);
plant := (p1, p2, p3, p4);
toplant := plant;
fromplant := plant;
machine := (m11, m12, m13, m21, m22, m31, m32, m41);
DATA
Price[product] := (120.00, 100.00, 115.00);
Demand[plant, product, month] := DATAFILE("Demand6.dat");
ProdCost[plant, machine, product] := SPARSEFILE("Produce.dat", 1);
ProdRate[plant, machine, product] := SPARSEFILE("Produce.dat", 2);
ProdDaysAvail[month] := (23, 20, 23, 22);
InvtCost[plant, product] := DATAFILE("InvtCost.dat");
InvtCapacity[plant] := (800, 400, 500, 400);
ShipCost[fromplant, toplant] := DATAFILE ("ShipCost.dat");
VARIABLES
Produce[plant, machine, product, month] -> Prod
WHERE (ProdCost > 0);
Inventory[plant, product, month] -> Invt;
Sales[plant, product, month] -> Sale;
Ship[product, month, fromplant, toplant]
WHERE (fromplant <> toplant);
MACROS
TotalRevenue := SUM(plant, product, month: Price * Sales);
TotalProdCost := SUM(plant, machine, product,month: ProdCost * Produce);
TotalInvtCost := SUM(plant, product, month: InvtCost * Inventory);
TotalShipCost := SUM(product, month, fromplant, toplant: ShipCost * Ship);
TotalCost := TotalProdCost + TotalInvtCost + TotalShipCost;
MODEL
MAX Profit = TotalRevenue - TotalCost;
SUBJECT TO
ProdCapacity[plant, machine, month] -> PCap:
SUM(product: Produce / ProdRate) <= ProdDaysAvail;
PlantBal[plant, product, month] -> PBal:
SUM(machine: Produce) + Inventory[month-1]
+ SUM(fromplant: Ship[fromplant, toplant:=plant])
=
Sales + Inventory
+ SUM(toplant: Ship[fromplant:=plant, toplant]);
MaxInventory[plant, month] -> MaxI:
SUM(product: Inventory) <= InvtCapacity;
BOUNDS
Sales < Demand;
END
Start der MPL Applikation..
Wähle File | Open und öffne die Modelldatei Planning6.mpl aus der vorherigen Lektion.
Wähle File | Save As zum Speichern der neuen Modelldatei Planning7.mpl.
Der Titel des Modells soll geändert werden um klarzustellen, dass nun mit der Modelldatei Planning7 gearbeitet wird.
TITLE
Production_Planning7;
In diesem Modell besteht nun jeder Index aus mehreren Anlagen. Um den Anlagenindex hinzuzufügen, wird im INDEX-Abschnitt die folgende Definition hinzugefügt:
INDEX
product := (A1, A2, A3);
month := (Jan, Feb, Mar, Apr);
plant := (p1, p2, p3, p4);
toplant := plant;
fromplant := plant;
machine := (m11, m12, m13, m21, m22, m31, m32, m41);
Sowohl die Produktionskosten als auch die Produktionsraten hängen nun von der Anlage ab. Da nicht alle Indexkombination aus Standort und Anlage existieren, werden die Daten in einer entsprechenden dünnbesetzten Datendatei gespeichert, wobei MPL erlaubt, in dieser Datei mehrere Datenvektoren zu speichern. Hierzu muss nach dem Dateinamen ein Komma und die entsprechende Spaltenzahl eingegeben werden.
In den folgendenen Zeilen sollen nun die Definitionen für den ProdCost- und den ProdRate-Datenvektor aktualisiert und um den Anlagenindex machine erweitert, sowie die entsprechenden Dateireferenzen auf die neue, dünnbesetzte Datei Produce.dat bezogen werden. Um auf die Spalte der Produktionskosten zuzugreifen, wird hierzu 1 eingegeben; für den Zugriff auf die Produktionsraten dagegen 2.
DATA
Price[product] := (120.00, 100.00, 115.00);
Demand[plant, product, month] := DATAFILE("Demand6.dat");
ProdCost[plant, machine, product] := SPARSEFILE("Produce.dat", 1);
ProdRate[plant, machine, product] := SPARSEFILE("Produce.dat", 2);
ProdDaysAvail[month] := (23, 20, 23, 22);
InvtCost[product] := DATAFILE("InvtCost.dat");
InvtCapacity[plant] := (800, 400, 500, 400);
ShipCost[fromplant, toplant] := DATAFILE("ShipCost.dat");
Nachfolgend soll nun die dünnbesetzte Datei Produce.dat gemäß der in der Problembeschreibung spezifizierten Daten erzeugt werden.
Um diese Datei Produce.dat zu erzeugen, wird ein neues Editorfenster geöffnet und die folgenden Daten eingegeben:
!
! Produce.dat - Production Cost and Rate
!
! ProdCost[plant, machine, product]:
! ProdRate[plant, machine, product]:
!
p1, m11, A1, 73.30, 500,
p1, m11, A2, 52.90, 450,
p1, m12, A3, 65.40, 550,
p1, m13, A3, 47.60, 350,
p2, m21, A1, 79.00, 550,
p2, m21, A3, 66.80, 450,
p2, m22, A2, 52.00, 300,
p3, m31, A1, 75.80, 450,
p3, m31, A3, 50.90, 300,
p3, m32, A1, 79.90, 400,
p3, m32, A2, 52.10, 350,
p4, m41, A1, 82.70, 550,
p4, m41, A2, 63.30, 400,
p4, m41, A3, 53.80, 350,
Die Produce-Variable hängt nun zusätzlich vom Anlagenindex machine ab. Da nicht alle Indexkombinationen aus Standort und Anlagen existieren, werden sie mit einer logischen Bedingung auf den ProdCost-Datenvektor ausgeschlossen, indem nur die Kombinationen akzeptiert werden, für die die Produktionskosten, also die Werte des Datenvektors ProdCost größer als Null sind. Im folgenden nun die Eingaben zur Aktualisierung der Produktions-Variablen:
VARIABLES
Produce[plant, machine, product, month] -> Prod
WHERE (ProdCost > 0);
Im Makro für die gesamten Produktionskosten wird der Index machine hinzugefügt, da die Produktionsvariablen nun vom Anlagenindex abhängen.
MACROS
TotalRevenue := SUM(plant, product, month: Price * Sales);
TotalProdCost := SUM(plant, machine, product,month: ProdCost * Produce);
TotalInvtCost := SUM(plant, product, month: InvtCost * Inventory);
TotalShipCost := SUM(product, month, fromplant,toplant: ShipCost * Ship);
TotalCost := TotalProdCost + TotalInvtCost + TotalShipCost;
In der Kapazitätsbeschränkung 'ProdCapacity' muss der Index machine aufgenommen werden, da für jede Anlage eine eigene Kapazitätsbeschränkung existiert. Dazu sind die folgenden Änderungen in der ProdCapacity-Nebenbedingung vorzunehmen:
SUBJECT TO
ProdCapacity[plant, machine, month] -> PCap:
SUM(product: Produce / ProdRate) <= ProdDaysAvail;
In der Standortbilanzgleichung existiert nun für jede Anlae eine entsprechende Produktionsvariable. Zur Berechnung der gesamten Produktionsmenge für einen bestimmten Produktionsstandort müssen daher die Produktionsvariablen über alle Anlagen summiert werden. Daher sind in der PlantBal-Bedingung die folgenden Änderungen erforderlich:
PlantBal[plant, product, month] -> PBal:
SUM(machine: Produce) + Inventory[month-1]
+ SUM(fromplant: Ship[fromplant, toplant:=plant])
=
Sales + Inventory
+ SUM(toplant: Ship[fromplant:=plant, toplant]);
Der nächste Schritt besteht darin, das durch 'Planning7.mpl' kodierte Problem zu lösen. 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.
Wie schon in Lektion 6, sollen mit Hilfe des Modelldefinitionsfensters lediglich die hier interessierenden Aspekte der Lösung angezeigt werden. Dazu wird für das Planning7-Modell Model Definitions aus dem View-Menu gewählt.
Das Modell-Definitions-Fenster für das Planning7-Modell
Um die Werte der Produktions-Variablen zu inspizieren, wird das Produce-Objekt im Baum gewählt und mit der View-Taste bestätigt. Dies erzeugt ein Fenster, das die von Null verschiedenen Produktions-Variablen anzeigt.
VARIABLE Produce[plant,machine,product,month] :
plant machine product month Activity Reduced Cost
--------------------------------------------------------------------
p1 m11 A1 Jan 4300.0000 0.0000
p1 m11 A1 Feb 4200.0000 0.0000
p1 m11 A1 Mar 5487.5000 0.0000
p1 m11 A1 Apr 5300.0000 0.0000
p1 m11 A2 Jan 6480.0000 0.0000
p1 m11 A2 Feb 5220.0000 0.0000
p1 m11 A2 Mar 5411.2500 0.0000
p1 m11 A2 Apr 5130.0000 0.0000
p1 m12 A3 Feb 9049.3506 0.0000
p1 m12 A3 Mar 916.1616 0.0000
p1 m12 A3 Apr 10803.1169 0.0000
p1 m13 A3 Jan 8050.0000 0.0000
p1 m13 A3 Feb 7000.0000 0.0000
p1 m13 A3 Mar 8050.0000 0.0000
p1 m13 A3 Apr 7700.0000 0.0000
p2 m21 A1 Jan 5100.0000 0.0000
p2 m21 A1 Feb 6200.0000 0.0000
p2 m21 A1 Mar 6538.8889 0.0000
p2 m21 A1 Apr 7600.0000 0.0000
p2 m21 A3 Jan 4422.6136 0.0000
p2 m21 A3 Feb 3927.2727 0.0000
p2 m21 A3 Mar 5000.0000 0.0000
p2 m21 A3 Apr 3681.8182 0.0000
p2 m22 A2 Jan 6900.0000 0.0000
p2 m22 A2 Feb 6000.0000 0.0000
p2 m22 A2 Mar 6900.0000 0.0000
p2 m22 A2 Apr 6600.0000 0.0000
p3 m31 A1 Jan 3300.0000 0.0000
p3 m31 A1 Feb 5964.9351 0.0000
p3 m31 A1 Mar 2550.0000 0.0000
p3 m31 A1 Apr 4477.4026 0.0000
p3 m31 A3 Jan 4700.0000 0.0000
p3 m31 A3 Feb 2023.3766 0.0000
p3 m31 A3 Mar 5200.0000 0.0000
p3 m31 A3 Apr 3615.0649 0.0000
p3 m32 A1 Jan 800.0000 0.0000
p3 m32 A1 Feb 135.0649 0.0000
p3 m32 A1 Mar 2150.0000 0.0000
p3 m32 A1 Apr 1322.5974 0.0000
p3 m32 A2 Jan 7350.0000 0.0000
p3 m32 A2 Feb 6881.8182 0.0000
p3 m32 A2 Mar 6168.7500 0.0000
p3 m32 A2 Apr 6542.7273 0.0000
p4 m41 A1 Jan 4300.0000 0.0000
p4 m41 A1 Feb 4100.0000 0.0000
p4 m41 A1 Mar 5073.6111 0.0000
p4 m41 A1 Apr 4500.0000 0.0000
p4 m41 A2 Jan 2270.0000 0.0000
p4 m41 A2 Feb 5018.1818 0.0000
p4 m41 A2 Mar 2500.0000 0.0000
p4 m41 A2 Apr 5527.2727 0.0000
p4 m41 A3 Jan 3327.3864 0.0000
p4 m41 A3 Mar 2633.8384 0.0000
--------------------------------------------------------------------
Die Produce-Variable ist nun von vier Indizes abhängig: plant, machine, product und month. Für jeden Standort wird optimal entschieden, welche Anlage die effizienteste ist, um die Produkte an einem bestimmten Standort herzustellen. Die Ergebnisse in dieser Tabelle können daher als Ausgangsbasis für einen Produktionsplanungs- und Schedulingansatz für die gesamte Firma dienen.
Besonders interessant ist es auch, die Lagervariable genauer anzusehen. Verwendet man das Modell-Definitions-Fenster nun, um die Inventory-Variablen genauer anzuschauen, so erhält man die folgenden Werte:
VARIABLE Inventory[plant,product,month] :
plant product month Activity Reduced Cost
-----------------------------------------------------------
p1 A2 Jan 800.0000 0.0000
p2 A2 Jan 400.0000 0.0000
p3 A3 Jan 500.0000 0.0000
p4 A3 Jan 400.0000 0.0000
-----------------------------------------------------------
Diesmal sollen die Produkte A2 und A3 im Januar produziert werden, um sicherzustellen, dass im Februar genug verfügbar ist.
Die meisten Standorte und ihre Anlagen produzieren fast mit voller Kapazität. Verwendet man das Modell-Definitions-Fenster zur Inspektion der ProdCapacity-Variablen, so erhält man die folgenden Werte:
CONSTRAINT ProdCapacity[plant,machine,month] :
plant machine month Slack Shadow Price
-----------------------------------------------------------
p1 m12 Jan 23.0000 0.0000
p1 m12 Feb 3.9595 0.0000
p1 m12 Mar 20.2682 0.0000
p1 m12 Apr 1.2033 0.0000
p2 m21 Jan 3.6947 0.0000
-----------------------------------------------------------
Offensichtlich hat der Standort p1 noch etwas überschüssige Kapazität in Anlage m12 und am Standort p2 ist die Anlage m21 nicht voll ausgelastet. Alle anderen Anlagen produzieren mit voller Kapazität, um die Nachfragen zu erfüllen.