Mathematische Programmierung – Ein einfaches Beispiel - Heidelberg Analytics, Dr. Jannik Vogel

Mathematische Programmierung ist eine Methodik zur Entscheidungsunterstützung in verschiedenen Bereichen, einschließlich Supply Chain Management und Produktion. GAMS (General Algebraic Modeling System) ist ein Softwaresystem, das es Benutzern ermöglicht, Optimierungsprobleme mithilfe mathematischer Programmierungstechniken zu modellieren und zu lösen. In diesem Artikel werden wir die Grundlagen der mathematischen Programmierung unter Verwendung von GAMS anhand eines Produktionsbeispiels untersuchen.

Beispiel zur mathematischen Programmierung

Angenommen, ein Unternehmen produziert Stühle und Tische. Jeder Stuhl erfordert 1 großes Brett und 2 kleine Bretter, während jeder Tisch 2 große Bretter und 2 kleine Bretter erfordert. Das Unternehmen hat 5 große Bretter und 8 kleine Bretter zur Verfügung. Der Gewinn für den Verkauf eines Stuhls beträgt 1000 US-Dollar und der Gewinn für den Verkauf eines Tisches beträgt 2500 US-Dollar. Das Unternehmen möchte die optimale Anzahl von Stühlen und Tischen bestimmen, die produziert werden sollen, um den Gewinn zu maximieren und gleichzeitig die verfügbaren Ressourcen zu nutzen.

Um dieses Problem mit GAMS zu lösen, müssen wir die Entscheidungsvariablen, die Zielfunktion und die Beschränkungen definieren. Verwenden wir $x_1$ , um die Anzahl der produzierten Stühle darzustellen, und $x_2$ , um die Anzahl der produzierten Tische darzustellen. Die Zielfunktion besteht darin, den Gesamtgewinn zu maximieren, was sich als $1000 x_1 + 2500 x_2$ ausdrücken lässt. Die Beschränkungen sind die verfügbaren Ressourcen, die als $1 x_1 + 2 x_2 \leq 5$ (für die großen Bretter) und $2 x_1 + 2 x_2 \leq 8$ (für die kleinen Bretter) ausgedrückt werden können.

Wir können dieses Problem in GAMS wie folgt darstellen:

SETS
   products /chairs, tables/;
   
PARAMETERS
   profit(products) /chairs 1000, tables 2500/
   available_large_boards /5/
   available_small_boards /8/;

INTEGER VARIABLES
   x(products);
VARIABLES
   total_profit;

EQUATIONS
   objective
   large_boards
   small_boards;

objective.. total_profit =E= sum(products, profit(products)*x(products));
large_boards.. 1*x('chairs') + 2*x('tables') =L= available_large_boards;
small_boards.. 2*x('chairs') + 2*x('tables') =L= available_small_boards;

MODEL m /all/;

SOLVE m USING MIP MAXIMIZING total_profit;

DISPLAY x.l, total_profit.l;

In diesem Code definieren wir zunächst eine Menge von Produkten, zu denen Stühle und Tische gehören. Wir definieren Parameter für den Gewinn jedes Produkts sowie für die verfügbaren Ressourcen (große Bretter und kleine Bretter).

Als Nächstes definieren wir die Entscheidungsvariablen. Wir definieren eine ganzzahlige Variable $x$ als Produktionsmenge für jedes Produkt. Außerdem definieren wir eine Variable $total_profit$ für den Gewinn des Herstellers.

Wir definieren die Gleichungen unseres Modells, die sich aus Zielfunktion und den Nebenbedingungen zusammen setzen. Die Zielfunktion berechnet den Gesamtgewinn, der sich aus der Summe des Produkts aus dem Gewinn jedes Produkts und der Anzahl der produzierten Einheiten ergibt. Wir definieren auch zwei Nebenbedingungen, eine für die verfügbaren großen Bretter und eine für die verfügbaren kleinen Bretter.

Anschließend definieren wir ein Modell, das alle von uns definierten Variablen, Gleichungen und Parameter enthält. Wir setzen den Optimierungsalgorithmus auf MIP (gemischt-ganzzahlige Programmierung) und verwenden das Schlüsselwort MAXIMIZING, um die Zielfunktion zu maximieren.

Dann verwenden wir die DISPLAY-Anweisung, um die Werte von $x$ und $total_profit$ in der optimalen Lösung anzuzeigen.

Ausagbe von GAMS

Wenn wir dieses Modell in GAMS lösen, erhalten wir die folgende Ausgabe:

----     29 VARIABLE x.L  

chairs 1.000,    tables 2.000


----     29 VARIABLE total_profit.L        =     6000.000

Diese Ausgabe zeigt uns, dass die optimale Lösung darin besteht, 1 Stuhl und 2 Tische zu produzieren. Das bedeutet, dass das Unternehmen 1 Stuhl und 2 Tische produzieren sollte (da wir nur eine ganzzahlige Anzahl von Tischen produzieren können), um den Gewinn zu maximieren und gleichzeitig die Ressourcenbeschränkungen zu erfüllen. Der Gesamtgewinn in der optimalen Lösung beträgt 6000 US-Dollar.

Fazit

Dieses einfache Beispiel zeigt, wie GAMS zur Lösung von Optimierungsproblemen in der Fertigung eingesetzt werden kann. Wir modellieren das Problem als mathematisches Programm, indem wir Parameter, Entscheidungsvariablen, eine Zielfunktion und Nebenbedingungen definieren und verwenden GAMS, um die optimale Lösung zu finden.

In komplexeren Produktionsproblemen können zusätzliche Beschränkungen wie Produktionskapazität, Arbeitsbeschränkungen oder Nachfragebeschränkungen auftreten. GAMS kann mit all diesen zusätzlichen Beschränkungen umgehen, was es zu einem leistungsstarken Werkzeug zur Lösung komplexer Fertigungsprobleme macht.