Beurteilung der Software XPRESS-MP Fallstudienübung

Inhaltsverzeichnis

Abbildungsverzeichnis

Symbolverzeichnis

Abkürzungsverzeichnis

1 Einführung

2 Beschreibung des Softwarepakets XPRESS-MP
2.1 LP-MODEL
2.2 IP-OPT
2.3 LP-REPRT

3 Darstellung des Problems

4 Vorgehenswe ise zur Lösung der Problemstellung mit XPRESS-MP
4.1 PROGNOS
4.2 LP-MODEL
4.3 IP-OPT
4.4 RESULT

5 Kritische Beurteilung von XPRESS-MP

6 Schlußbetrachtung

Literaturverzeichnis

Anhang A : Sourcecode

Anhang B : Lösung des Problems

Abbildungsverzeichnis

Abbildung 4-1: Eigene Grafik, schematische Darstellung des Ablaufes der Problemlösung

Symbolverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

Abkürzungsverzeichnis DOS - Disk Operating System

Abbildung in dieser Leseprobe nicht enthalten

Einführung

Diese Arbeit soll einen Einblick in die Funktionsweise des Softwarepaketes XPRESS-MP geben und die Schwächen sowie Stärken in geeigneter Weise hersauskristallisieren. Dabei gehen wir gehen wir von einem Problem der Produktionsprogrammplanung aus. Dieses wird als ganzzahliges lineares Optimierungsproblem formuliert, um mit Hilfe von XPRESS-MP den maximalen Deckungsbeitrag zu ermitteln.

Beschreibung des Softwarepakets XPRESS-MP

Das von 1984-1991 von Dash Associates entwickelte Programmpaket XPRESS-MP gliedert sich in drei Komponeneten: LP-MODEL, IP-OPT, LP- REPRT. Mit LP-MODEL wird ein bestehendes Problem formuliert und in eine MPS-Datei umgeformt. Das in MPS-Format vorliegende Problem kann nun mit IP-OPT gelöst werden. Anschließend läßt sich das Ergebnis mit LP- REPRT darstellen.

Als Plattform dient eine DOS-Umgebung mit einem 486’er Prozessor und beliebig viel Arbeisspeicher. Dieser zusätzliche Speicher, unter MS-DOS auch "Extended Memory" genannt, wird von der Software automatisch genutzt.

LP-MODEL

Dieses Programm soll dem Benutzer unterstützen, indem die eingegebenen problem-definierenden Daten in eine in der Wirtschaftschaft verbreiteten MPS- Datei fehlerfrei umgeformt werden. Dabei kann die mathematische Formulierung des Problems sowohl in einer zeilenweisen als auch in einer spaltenweisen Darstellung erfolgen, so daß dem Anwender anstelle einer aufwendigen Erstellung einer MPS-Datei die Möglichkeit gegeben wird, das Problem in Form der mathematisch gängigen Schreibweise zu formulieren.

Am Anfang jeder Modellanfertigung muß der Anwender sämtliche benötigten Variablen, Matrizen und Konstanten deklarieren, womit schon im Vorfeld Überlegungen über die Notwendigkeit der einzelnen Größen angestellt werden müssen und somit die Gefahr eines falschen Aufbaus des Problems verringert werden kann.

Durch die Definition globaler Konstanten ist eine variable Gestaltung der Problemgröße möglich. Sowohl die Anzahl der Variablen als auch die Größe der einzelnen Matrizen kann leicht modifiziert werden, indem die jeweilige Konstante auf den gewünschten Wert gesetzt wird.

Eine weitere Eigenschaft von LP-MODEL ist die Benutzung von logischen Ausdrücken zur Modellierung des Problems, die beispielsweise eine bedingte Auswahl von Restriktionen zuläßt.

Bei der Formulierung eines Problems kann eine strikte Trennung vom Modell und den verwendeten Daten erfolgen. Die benötigten Daten können aus entsprechenden Dateien in das System importiert werden. Unterstützt wird das ASCII- bzw. LOTUS123-Dateiformat.

Als Ergebnis wird eine Ausgabedatei in MPS-Format oder in binärer Form erstellt, die dann von IP-OPT weiterverarbeitet werden kann.

IP-OPT

Das Programm IP-OPT hat die Aufgabe, eine optimale Lösung für das mit LP- MODEL formulierte lineare Optimierungsproblem zu ermitteln. Die Problemformulierung kann von IP-OPT in Form einer Datei in MPS-Format oder binärer Form eingelesen werden.Eine gute Startbasis wird vom Programm vor der Lösungssuche automatisch erzeugt, kann jedoch auch optional vom Anwender vorgegeben werden. Im folgenden erfolgt eine Lösungssuche nach dem optimalen Zielfunktionswert, für die der Benutzer zuvor angeben muß, ob es sich dabei um eine Minimierungs- bzw. Maximierungsvorschrift für die Zielfunktion handelt. Existiert eine optimale Lösung, so wird diese in eine Ergebnisdatei in binärer Form gespeichert. Auf Wunsch des Benutzer kann diese Ausgabe auch durch eine ASCII-Ergebnisdatei geschehen.

Wenn die gesuchte Basislösung einer Ganzzahligkeitsrestriktion unterliegt, wird vom Programm als erstes eine optimale Lösung des Problems ohne Berücksichtigung der Ganzzahligkeitsrestriktionen bestimmt. Ausgehened von der erhaltenen Lösung wird dann mit Hilfe eines Branch&Bound-Algorithmus die optimale ganzzahlige Lösung ermittelt.

LP-REPRT

Um die erzielte optimale Lösung dem Anwender in einer verständlichen Form darzustellen, ist das Programm LP-REPRT in das Software-Paket XPRESSMP aufgenommen worden. Mit ihm ist es dem Anwender möglich, einzelne ihn besonders interessierende Sachverhalte durch Vorgabe bestimmter Filterfunktionen (wie Masken und Bounds) auf dem Bildschirm auszugeben. Dies soll zur besseren Auswertung der Lösung beitragen.

Darstellung des Problems

Die Fähigkeiten von XPRESS-MP sollen im folgenden anhand eines mittelständischen Unternehmens aus dem Modellbaubereich überprüft werden, welches 3 Typen von Modellflugzeugen herstellt und absetzen will. Diesem Unternehmen liegen Daten über die eigenen Produktionsbedingungen und Prognosen über Absatzhöchstmengen, Absatzmindestmengen und die jeweiligen Verkaufspreise der folgenden 12 Monate vor. Ziel des Unternehmens ist eine Maximierung des Deckungsbeitrages für den zu betrachtenden Planungszeitraum. Im weiteren erfolgt die mathematische Herleitung des zugehörigen linearen Optimierungsmodells.

Bei genauerer Betrachtung des Problems ist zu erkennen, daß diesem der Bereich der mehrperiodischen Produktionsprogrammplanung zugrundeliegt.

Deshalb ist nun eine Zielfunktion aufzustellen, die anhand der Variablen für die Produktion x, den Absatz ab und die Lagerung l den Deckungsbeitrag maximiert:

Abbildung in dieser Leseprobe nicht enthalten

Die Variablen n und T sind im vorliegenden Fall mit 3 als Zahl der Flugzeugmodelle bzw. 12 für den Zeitraum der Prognose von 12 Monaten zu belegen. Der Lagerkostensatz cl liegt bei 1% der Materialeinsatzkosten.

Diese Zielfunktionsgleichung ist dann unter Berücksichtigung der sich aus der Problemstellung ergebenen Restriktionen zu lösen, die im folgenden näher beschrieben werden:

Lagerbilanzgleichung :

Um Nachfragespitzen, die nicht durch die monatliche Produktion gedeckt werden können, doch zu befriedigen, ist ein Lager einzurichten, das zu Beginn und am Ende des Planungszeitraums den Wert null annehmen muß und innerhalb des Planungszeitraums nicht negativ werden darf.

Abbildung in dieser Leseprobe nicht enthalten

Lagermengengleichung :

Eine Restriktion für das betrachtete Unternehmen besteht aus der begrenzten Lagerkapazität. Die Summe der zu lagernden Flugzeugmodelle, unabhängig vom Typ, darf die Lagerobergrenze von 100 Stück pro Monat nicht überschreiten.

Abbildung in dieser Leseprobe nicht enthalten

lmax - Lagerobergrenze pro Monat

Aufgrund der Problemstellung ist die Lagerobergrenze mit 100 ModellEinheiten anzugeben.

Arbeitszeitrestriktion:

Die monatliche Gesamtarbeitszeit der Mitarbeiter wird auf zwei verschiede Produktionsabläufe verteilt.

(a) Für die Produktion von Rümpfen stehen 2 Mitarbeiter mit einer Gesamtarbeitszeit wrmax von 320 Stunden pro Monat zur Verfügung.

Abbildung in dieser Leseprobe nicht enthalten

wrj - Zeitdauer der Produktion eines Bauteiles des Flugzeugmodells j

(b) In der Produktion von Tragflächen und Höhenleitwerken sind 2 Mitarbeiter beschäftigt, die im Monat höchstens 320 Stunden als Gesamtarbeitszeit wtmax arbeiten können.

Abbildung in dieser Leseprobe nicht enthalten

wtj - Zeitdauer der Produktion eines Bauteiles des Flugzeugmodells j

Ganzzahligkeitrestriktion :

Abbildung in dieser Leseprobe nicht enthalten

Nichtnegativitätsrestriktion :

Die Systemvariablen dürfen aufgrund der Problemstellung keine negativen Werte annehmen.

Abbildung in dieser Leseprobe nicht enthalten

Vorgehensweise zur Lösung der Problemstellung mit XPRESS-MP

Abbildung in dieser Leseprobe nicht enthalten

Der Ablauf der Lösungsfindung des vorliegenden Problems soll unter Verwendung des zugrundeliegenden Softwarepakets im folgenden dargestellt werden. Die Benutzerfreundlichkeit wurde von uns durch die Entwicklung zweier zusätzlicher Programme

- PROGNOS, RESULT - gesteigert. Die kommende schematische Abbildung soll die Vorgehensweise und den Fluß der Daten verdeutlichen.

Die Lösung des Problems beginnt für den Anwender mit dem Aufruf von XPRESS. XPRESS ist ein BATCH-Datei, die nacheinander die einzelnen Teilprogramme aufruft, beginnend mit PROGNOS, dann LP-MODEL, IP-OPT und abschließend RESULT. Die Programme LP-MODEL und IP-OPT werden mit Steuerdateien aufgerufen, um programmspezifische Funktionsabläufe zu automatisieren. Der Fluß der Daten wird deshalb von der BATCH-Datei gesteuert, so daß der Anwender manuell die Prognosedaten eingeben muß und sich nachfolgend auf die Auswertung des Ergebnisses konzertrieren kann.

PROGNOS

Hauptaufgabe von PROGNOS ist es, dem Anwender die Eingabe seiner Prognosedaten zu erleichtern und diese dann in ein von LP-MODEL lesbares Format zu überführen. Um dem Anwender die Möglichkeit zu geben, bei jedem Aufruf von XPRESS seine Prognosedaten monatsweise zu aktualisieren, werden ihm von PROGNOS in verschiedenen Menüs die prognostizierten Absatzpreise, Absatzmindestmengen sowie -höchstmengen zur Änderung vorgelegt. Der erste Monat des letzten Betrachtungszeitraumes wird als verstrichen angesehen, somit muß der Anwender zumindest neue Werte für den letzten Monat des betrachteten Planungszeitraumes eingeben. Zur Unterstützung wird hinter jeder Monatsangabe der bisher vorgesehene Prognosewert in Klammern angegeben, durch ein RETURN wird dieser automatisch übernommen.

Die eingegebenen Prognosedaten werden von PROGNOS in den drei Dateien ab_min.dat, ab_max.dat, ab_preis.dat zusammengefaßt.

LP-MODEL

Die für LP-MODEL verfaßte Problemformulierung wurde in einer ASCII- Datei namens problem.mod abgelegt. Alle Werte die sich innerhalb bestimmter Zeiträume ändern könnten wurden variabel gehalten. Mit dieser ASCII-Datei und den von PROGNOS erstellten Dateien, die die Werte über die Absatzpreise (ab_preis.dat), die Absatzmindestmengen (ab_min.dat) und die Absatzhöchstmengen (ab_max.dat) beinhalten, erzeugt LP-MODEL eine Datei im MPS-Format. Dies geschieht anhand der Vorgaben der Steuerdatei @problem.mdl.

IP-OPT

Der Ablauf zur Lösung des als MPS-Datei vorliegenden linearen Optimierungssystems wird mit Hilfe der Steuerdatei (@problem.xlp), mit der IP-OPT aufgerufen worden ist, festgelegt.

Zu Beginn wird die MPS-Datei (problem.mat) eingelesen und eine optimale Lösung ohne Beachtung der Ganzzahligkeitsrestriktionenen erzeugt. Da aber eine ganzzahlige Lösung gefordert ist, wird diese unter Verwendung eines Branch&Bound-Algorithmus gesucht.

Die so ermittelte ganzzahlige Lösung wird in eine ASCII-Lösungsdatei (problem.asc) geschrieben.

RESULT

Aus der von IP-OPT erzeugten Lösungsdatei werden für den Anwender ihn interessierende Daten herausgefiltert und ihm in einer verständlichen und anschaulichen Form auf dem Bildschirm nähergebracht.

Zu Beginn wird dem Anwender ein Auswahlmenü präsentiert, welches eine Wahl zwischen zwei Ausgabeformen der Lösung ermöglicht. Zum einen wird das Lösungsergebnis für einen bestimmten Monat ausgegeben, desweiteren können alle Monate des betrachteten Planungszeitraumes nacheinander begutachtet werden.

Die Ausgabe der monatlichen Lösungswerte besteht aus der Auflistung der Produktions-, Absatz- und Lagermenge sowie des Deckungsbeitrages des jeweiligen Flugzeugtyps, des Gesamtdeckungsbeitrages aller Flugzeugtypen und der eingesetzten bzw. freien Zeitkapazitäten.

Kritische Beurteilung von XPRESS-MP

Im Verlauf der Benutzung von XPRESS-MP sind einige Punkte auffällig geworden, die die Grenzen des Softwarepakets aufzeigen bzw. seine Stärken hervorheben.

Als Stärken von XPRESS-MP können einige Punkte aufgezeigt werden.

Die Eingabe ist benutzerfreundlich, da die Notation der Problemformulierung der mathematischen Schreibweise sehr ähnlich ist, d.h. das lineare Optimierungssystem kann als ein System von Gleichung bzw. Ungleichungen in einer Infixnotation formuliert werden. Desweiteren ist es dem Benutzer aus dem soeben genannten Grund nach kurzer Einarbeitunszeit möglich, ein zu einem Problem gehörendes lineares Optimierungssystem selbständig aufzustellen und zu lösen.

Eine weitere Stärke ist die Robustheit des Systems gegenüber falschen Eingaben, die von diesem durch eine umpfangreiche Fehlererkennung abgefangen werden. Jede fehlerhafte Eingabe wird sofort mit einer Fehlermeldung angezeigt, ohne gleich einen Systemabsturz hervorzurufen.

Lineare Optimierungsprobleme bei denen in verschiedenen Perioden die Daten variieren müssen nur ein einziges Mal formuliert werden, da die sich ändernden Datenmengen aus externen Dateien eingelesen werden können. Dies erspart dem Nutzer eine ständige Neuformulierung des linearen Optimierungsproblems.

Über das Softwarepaket sind jedoch auch eine ganze Menge negative Aussagen zu machen. Sobald die Arbeit mit XPRESS-MP aufgenommen wird fallen die unkomfortablen Eingabemöglichkeiten von LP-MODEL bei der Formulierung von Problemen auf. Dazu sind folgende Punkte zu nennen:

- Bei einer fehlerhaften Eingabe wird zwar eine Fehlermeldung ausgegeben, doch weder aus der Meldung, noch aus den Angaben zur Fehlermeldung im Manual ist genau erkennbar, wo der Fehler liegt.
- Eingaben die mit RETURN bestätigt wurden, können nicht einfach editiert werden. Hier hilft nur eine Neueingabe der entsprechenden Zeile.
- Weiterhin ist bei der Formulierung von Restriktionen die Schreibweise des kleiner-gleich- Zeichens bzw. größer-gleich-Zeichens etwas unglücklich gewählt, da das kleiner-gleich- Zeichen als ‘<‘ und das größer-gleich-Zeichen als ‘>‘ geschrieben wird.
- Die Zielfunktion, sowie die Gleichungen bzw. Ungleichungen des Restriktionssystems dürfen, ohne die Blanks mitzuzählen, nur eine Länge von 5000 Zeichen haben. Dies schränkt eine Problemformulierung natürlich erheblich ein.

Wie im vorliegenden Bericht erwähnt können mit dem vorgestellten Softwarepaket auch ganzzahlige lineare Optimierungsprobleme mit Hilfe eines Branch&Bound-Algorithmus gelöst werden. Bei der vorliegenden Version von IP-OPT bricht dieser Algorithmus jedoch nach der Betrachtung von 200 Knoten selbständig die Suche nach weiteren ganzzahligen Lösungen ab.

Aufgrund dessen kann für die gefundene ganzzahlige Lösung für das vorgestellte Problem nicht mit Sicherheit gesagt werden, ob dies denn auch die optimale ganzzahlige Lösung ist.

Weitere programmspezifische Umgebungsvariablen können nur nach langwierigen Studiums des Manuals umständlich verändert werden. Beispielhaft wären hier zu nennen:

- maximale Anzahl der Restriktionszeilen (Default-Wert 100)
- maximale Größe der Summe von Zeilen und Spalten (Default-Wert 250)
- maximale Anzahl der Matrixelemente, die nicht Null sind (Default-Wert 32000)

Schlußbetrachtung

Abschließend ist über das Softwarepaket XPRESS-MP zu sagen, daß die Stärken eindeutig in der schnellen und relativ speicherplatzsparenden Lösung von kleinen, überschaubaren Problemstellungen hat, bei dem es auch einem ungeübten Benutzer durch eine kurze Einarbeitungsphase im Manual- Dokument ermöglicht wird, ein lineares Optimierungsproblem zu formulieren, zu modellieren und somit auch zu lösen.

Bei umfangreicheren Problemen kommt die Problematik der zu geringen softwarewarebedingten Rechnerressourcen voll zum Tragen, so daß schon bei der Problemstellung der Fallstudie,dessen Umfang nicht als übermäßig komplex zu bezeichnen war, nur über bestimmte Kniffe bzw. softwarespezifische Feinheiten eine einwandfreie Lösung der Problems ermittelt werden konnte.

Literaturverzeichnis

Schneeweiß , Ch. (1992)

Einführund in die Produktionswirtschaft, 4 überarbeitete Auflage, Berlin, Heidelberg, NewYork, London, Paris, Tokyo, Hong Kong, Barcelona, Budapest, Springer-Verlag

Anhang A : Sourcecode

PROGNOS

Abbildung in dieser Leseprobe nicht enthalten

RESULT

Abbildung in dieser Leseprobe nicht enthalten

1. Anhang B : Lösung des Problems

Dabei handelt es sich um die erste von IP-OPT gefundene ganzzahlige Lösung :

Abbildung in dieser Leseprobe nicht enthalten