Kurs:Einführung in Produktionsmanagement/Exkurs: Lineare Optimierungsmodelle

Da für Produktionsmanagement linearer Optimierungsmodelle außerordentlich wichtig sind, soll zunächst eine kurze Einführung in selbige gegeben. Es werden hier nur die nötigsten Grundlagen dargestellt, wer schon einmal mit solchen Modellen gearbeitet hat, kann dieses Kapitel getrost überspringen.

Sollte später einmal ein Kurs „Lineare Optimierungsmodelle“ entstehen, wäre dieses Kapitel gut als Einführung geeignet.

Wozu gibt es diese Modelle?

Lineare Optimierungsmodelle haben den Vorteil, dass sie relativ schnell zu lösen sind. Es existiert eine umfangreiche Theorie zu ihnen und mit modernen Solvern lassen sich Lösungen mit Millionen von Variablen in annehmbarer Zeit finden.

Diese Modelle haben immer den gleichen Aufbau: Es existiert eine sogenannte Zielfunktion, welche entweder minimiert oder maximiert werden soll. Innerhalb der Zielfunktion sind einige sogenannte Entscheidungsvariablen definiert, die das Programm, welches das Modell löst, beliebig variieren kann. Weiterhin unterliegen die Entscheidungsvariablen bestimmten Einschränkungen, diese werden über Gleichungen als sogenannte Nebenbedingungen dargestellt. Abschließend werden oftmals noch Bereiche definiert, in denen sich die Entscheidungsvariablen lediglich befinden dürfen.

Linear heißen die Modelle, wenn alle Entscheidungsvariablen sowohl in Zielfunktion als auch in den Nebenbedingungen grundsätzlich nur per Addition miteinander verknüpft sind, und sie selber nicht potenziert werden, oder sich gar in einer Potenz befinden, doch dazu später mehr.

Ein Beispiel

Im folgenden wollen wir uns ein einfaches Beispiel ansehen und daran die wesentlichen Merkmale linearer Optimierungsmodelle erläutern. Die Zahlen sind im Beispiel der Übersicht halber klein gehalten.

Wir stellen uns eine Fabrik vor, welche zwei Arten von Kieselsteinen herstellt: Feingemahlene Kieselsteine und grobe Kieselsteine. Dieses Mahlen erfolgt vollautomatisch in einer Maschine, diese Maschine läuft pro Tag 12 Stunden, dann muss sie für 12 Stunden abkühlen. Für die Herstellung einer Tonne feingemahlener Kieselsteine braucht die Maschine 2 Stunden, für eine Tonne grober dagegen nur 1 Stunde. Allerdings können pro Tag nur 5 Tonnen feingemahlener und 9 Tonnen grobgemahlener Kieselsteine auf dem Markt abgesetzt werden und aus Gründen der Vereinfachung soll Lagerhaltung ausgeschlossen werden. Für jede Tonne feingemahlener Kieselsteine ist nach Abzug der Materialkosten ein Gewinn von 10 Euro, für jede Tonne grober Kieselsteine ein Gewinn von 7 Euro zu erwarten.

Im folgenden soll ein lineares Optimierungsmodell aufgestellt werden, welches wenn wir es lösen lassen, uns den Gewinn maximiert.

Hierzu werden wir folgende Punkte durchführen:

1. Indexmengen definieren
2. Parameter definieren
3. Entscheidungsvariablen festlegen
4. Zielfunktion aufstellen
5. Nebenbedingungen definieren

Definition der Indexmengen

Da oftmals sehr viele Produkte vorhanden sind, ist es eigentlich immer sinnvoll, Indexmengen zu definieren. Wenn beispielsweise alle Produkte mit der Indexmengen $i\in I$ zusammengefasst sind, so kann man, wenn $x_{i}$ die Produktionsmenge des Produktes i bezeichnet, die Gesamtproduktionsmenge bequem als $\sum _{i\in I}x_{i}$ schreiben und muss nicht bei zehn verschiedenen Produkten $x_{1}+x_{2}+x_{3}+x_{4}+x_{5}+x_{6}+x_{7}+x_{8}+x_{9}+x_{10}$ schreiben. Weiterhin werden wir später und in weiterführenden Kursen völlig auf konkrete Zahlenbeispiele verzichten, und die Modelle nur noch mit allgemeinen Indexmengen beschreiben.

Für unser Beispiel brauchen wir nur eine Indexmenge; eben jene für die beiden Produkte. Wären mehrere Maschinen vorhanden, wäre es beispielsweise sinnvoll auch für diese eine eigene Indexmenge anzulegen.

$i\in I=\lbrace$feingemahlene Kieselsteine (F), grobgemahlene Kieselsteine (G)$\rbrace$

beziehungsweise wenn wir es allgemein formulieren:

$i\in I$ Kieselsteinarten

Definition der Parameter

Wenn wir das Modell mit den konkreten Werten aufstellen, kann dieser Schritt entfallen - doch wie bereits geschrieben, wird das Modell in der Regel allgemein aufgestellt. Das gilt gerade auch dann, wenn das Modell für die Verarbeitung am Computer aufgeschrieben wird - dann hat man in der Regel eine Datei mit dem allgemeinen Modell und eine Datei, in der sich alle Werte befinden.

Bei der Definition der Parameter geht es darum, aufzuschreiben, welche Symbole für welche Parameter stehen. In unserem Fall haben wir 4 Parameter:

• den Gewinn je Tonne Kieselsteine
• die Zeit, die die Herstellung Tonne Kieselsteine in Anspruch nimmt
• die Gesamtzeit, die die Maschine zur Verfügung steht
• die maximalen Absatzmengen der Produkte

Folglich sieht die Definition der Parameter wie folgt aus:

$p_{i}$	Gewinn je Tonne Kieselsteine i (p für Preis)
$a_{i}$	Zeit, die die Herstellung einer Tonne der Kieselsteinsorte i auf der Maschine in Anspruch nimmt
$c$	verfügbare Gesamtzeit auf der Maschine je Tag (c für capacity - Kapazität)
$d_{i}$	Nachfrage nach Kieselsteinen i je Tag (d für demand - Nachfrage)

Festlegung der Entscheidungsvariablen

Entscheidungsvariablen sind jeweils die Variablen, welche variiert werden können. In unserem Beispiel handelt es sich um die Produktionsmengen an Kieselsteinen pro Tag. In der Regel werden Entscheidungsvariablen mit den hinteren Buchstaben des Alphabets bezeichnet, die wichtigste in der Regel mit x. Dementsprechend lautet unsere Entscheidungsvariable hier:

$x_{i}$ Produktionsmenge der Kieselsteinsorte i in Tonnen

Aufstellen der Zielfunktion

Nun kommen wir zum eigentlichen Modell. Das erste, was wir hier aufstellen ist eine Gewinn- oder Kostenfunktion, die wir jeweils maximieren bzw. minimieren.

In unserem Fall wollen wir, da die Produktionskapazität ja begrenzt ist, den Gewinn maximieren. Dementsprechend setzt sich unsere Zielfunktion aus der Summe der Produkte der Produktionsmenge einer Kieselsteinart mit dem jeweiligen Gewinn je Tonne zusammen, also konkret ausformuliert:

${\text{max}}\quad 10x_{F}+7x_{G}$

beziehungsweise in allgemeiner Schreibweise:

${\text{max}}\quad \sum _{i\in I}p_{i}x_{i}$

Aufstellen der Nebenbedingungen

Die Nebenbedingungen sind dazu da, reale Einschränkungen mathematisch darzustellen. In diesem Beispiel gibt es insgesamt folgende Einschränkungen:

1. es darf insgesamt nicht mehr produziert werden, als die Maschine hergibt
2. es kann täglich nur eine begrenzte Menge je Sorte verkauft werden
3. es dürfen keine negativen Mengen an Kieselsteinen produziert werden

Die letzte Bedingung ist sehr wichtig, da andernfalls durch die Produktion „negativer Mengen“ eventuell eine Erhöhung der Maschinenkapazität denkbar ist. Bedingungen dieser Art kommen sehr oft in linearen Modellen vor, es ist eher selten, dass eine Entscheidungsvariable nicht einer sogenannten Nicht-Negativitätsbedingung unterliegt.

Wie bisher beginnen wir auch diesmal mit der Aufstellung der Nebenbedingungen mit den konkreten Werten:

Einhaltung der Maschinenkapazität

$2x_{F}+1x_{G}\leq 12$

Beachtung der maximalen Verkaufsmengen

$x_{F}\leq 5$

$x_{G}\leq 9$

Nicht-Negativitätsbedingung

$x_{F},x_{G}\geq 0$

Allgemein formuliert sehen die Nebenbedingung so aus:

Einhaltung der Maschinenkapazität

$\sum _{i\in I}a_{i}x_{i}\leq c$

Beachtung der maximalen Verkaufsmengen

$x_{i}\leq d_{i}\qquad \forall i\in I$

Nicht-Negativitätsbedingung

$x_{i}\geq 0\qquad \forall i\in I$

fertiges Modell

Damit ist das Modell fertig aufgestellt. Abschließend sei noch einmal eine Zusammenfassung des fertigen Modells dargestellt, auf der linken Seite die ausführliche, auf der rechten Seite die allgemeine Variante:

Indexmengen $i\in I=\lbrace$feingemahlene Kieselsteine (F), grobgemahlene Kieselsteine (G)$\rbrace$	Indexmengen $i\in I$ Kieselsteinarten
Parameter in dieser Variante nicht nötig	Parameter $p_{i}$ Gewinn je Tonne Kieselsteine i (p für Preis) $a_{i}$ Zeit, die die Herstellung einer Tonne der Kieselsteinsorte i auf der Maschine in Anspruch nimmt $c$ verfügbare Gesamtzeit auf der Maschine je Tag (c für capacity - Kapazität) $d_{i}$ Nachfrage nach Kieselsteinen i je Tag (d für demand - Nachfrage)
Entscheidungsvariablen $x_{i}$ Produktionsmenge der Kieselsteinsorte i in Tonnen	Entscheidungsvariablen $x_{i}$ Produktionsmenge der Kieselsteinsorte i in Tonnen
Zielfunktion ${\text{max}}\quad 10x_{F}+7x_{G}$	Zielfunktion ${\text{max}}\quad \sum _{i\in I}p_{i}x_{i}$
Nebenbedingungen Einhaltung der Maschinenkapazität $2x_{F}+1x_{G}\leq 12$ Beachtung der maximalen Verkaufsmengen $x_{F}\leq 5$ $x_{G}\leq 9$ Nicht-Negativitätsbedingung $x_{F},x_{G}\geq 0$	Nebenbedingungen Einhaltung der Maschinenkapazität $\sum _{i\in I}a_{i}x_{i}\leq c$ Beachtung der maximalen Verkaufsmengen $x_{i}\leq d_{i}\qquad \forall i\in I$ Nicht-Negativitätsbedingung $x_{i}\geq 0\qquad \forall i\in I$

Linearität

Wenn das Beispiel, insbesondere das ausführliche Modell, gut verstanden wurde, sind schon einmal die Grundlagen für das Verständnis weiterer linearer Modelle gelegt. Für den Fall, dass mit dem Begriff „linear“ noch Schwierigkeiten auftreten, wollen wir uns im Folgenden noch einmal kurz damit beschäftigen, was lineare Gleichungen bzw. Ungleichungen eigentlich sind. Es wird hier ganz bewusst auf die korrekte mathematische Formulierung und Beweise verzichtet. Entscheidungsvariablen werden im folgenden immer mit „x“ und eventuell einem Index bezeichnet.

Damit eine Gleichung linear ist, muss sie folgende Eigenschaften haben:

Entscheidungsvariablen dürfen nur addiert, jedoch nicht multipliziert oder anderweitig verknüpft werden

zulässig: $x_{1}+x_{2}=10$

nicht zulässig: $x_{1}\cdot x_{2}=10$

nicht zulässig: $x_{1}^{x_{2}}=10$

Entscheidungsvariablen dürfen nur mit 1 potenziert werden

zulässig: $x^{1}\leq 10$

nicht zulässig: $x^{2}\leq 10$

nicht zulässig: ${\sqrt {x}}\leq 10$

Nur Größer-gleich-, Kleiner-gleich- und Gleichheitszeichen sind erlaubt

zulässig: $x=5$

zulässig: $x\leq 5$

nicht zulässig: $x<5$

Entscheidungsvariablen dürfen mit beliebig vielen Parametern multipliziert werden

zulässig: $3\cdot 5\cdot x=3$

Man bekommt nach ein paar Modellen, auch wenn man mit Mathematik ansonsten nicht viel anfangen kann, recht schnell ein Gefühl dafür, wann eine Gleichung linear ist, also keine Angst. Das war es auch schon fast, eine Kleinigkeit fehlt allerdings noch, und dass sind

ganzzahlige Entscheidungsvariablen

Ganzzahlige Entscheidungsvariablen können beispielsweise festlegen, ob eine Maschine benutzt wird oder nicht oder wieviele Autos genau produziert werden - 3,782 Autos ergäben schließlich wenig Sinn. Prinzipiel gelten alle oben formulierten Regeln, der Einsatz in Modellen ist in der Regel jedoch anders. Am Häufigsten kommen sogenannte „binäre Entscheiungsvariablen“ vor. Diese können nur 0 und 1 annehmen und werden oft als eine Art „Schalter“ benutzt. Eher selten dagegen sind dagegen größere Intervalle. Dies liegt daran, dass die Komplexität und damit die Zeit, die der Computer zur Lösung benötigt, mit jeder neuen zulässigen ganzen Zahl stark ansteigt.

Normalerweise werden ganzzahlige Entscheidungsvariablen mit dem Buchstaben „y“ bezeichnet. Anstelle einer Nichtnegativitätsbedingung schreibt man bei ganzzahligen Entscheidungsvariablen den zulässigen Wertebereich, also beispielsweise $y_{i}\in \lbrace 0,1\rbrace$ für binäre Entscheidungsvariablen oder $y_{i}\in \lbrace 5,...,9\rbrace$. Dieser Bereich muss vorgeschrieben werden, ein unendlich großer Lösungsraum wie $y_{i}\in \mathbb {N} \rbrace$ ist nicht zulässig.

Im folgenden sollen zwei kleine Beispiele für Nebenbedingungen mit ganzzahligen Variablen folgen. Es wird hier stets auf die allgemeine Formulierung verzichtet - wenn die obigen Beispiele verstanden wurden, kann man sich diese aber schnell selbst herleiten.

Beispiel: Kapazitätsvergrößerung

Wir stellen uns vor, wir könnten noch die Maschine des Nachbarbetriebes für 4 Stunden zur Produktion mitnutzen. Dies würde uns jedoch einen Pauschalbetrag von 25 Euro kosten. In diesem Fall führen wir „y“ als Entscheidungsvariable ein, welche anzeigt, ob wir das Angebot annehmen oder nicht. Der Wert „1“ soll für die Annahme des Angebots, der Wert „0“ für die Ablehnung stehen. Dementsprechend ergibt sich als neue Zielfunktion:

${\text{max}}\quad 10x_{F}+7x_{G}-25y$

Wenn nun wir die Maschine nutzen, wird der Gewinn um 25 gemindert. Auch die erste Nebenbedingung muss abgeändert werden, bei Nutzung der Maschine, steht schließlich eine um 4 Stunden größere Kapazität zur Verfügung:

$2x_{F}+1x_{G}\leq 12+4y$

Nicht Vergessen werden darf der zulässige Wertebereich, der, da die Zufallsvariable binär ist, wie oben aussieht:

$y\in \lbrace 0,1\rbrace$

Beispiel: Extra-Mahlstein für feingemahlene Kieselsteine

Ein zweites typisches Beispiel für die Anwendung von binären Entscheidungsvariablen ist folgendes Szenario: Wenn wir uns entscheiden, feingemahlene Kieselsteine herzustellen, so brauchen wir täglich einen neuen Mahlstein, der erst die Produktion ermöglicht und uns 35 Euro kostet. Die Kapazitätserweiterung des vorherigen Beispiels steht uns in diesem Szenario nicht zur Verfügung. Unsere binäre Entscheidungsvariable sei wieder „y“, und nehme 1 an, wenn wir den Mahlstein kaufen bzw. 0, wenn wir ihn nicht kaufen und damit auf die Produktion der feingemahlenen Kieselsteine verzichten.

In diesem Fall wird die Zielfunktion wie im vorherigen Beispiel ergänzt:

${\text{max}}\quad 10x_{F}+7x_{G}-35y$

Nun führen wir eine zusätzliche Nebenbedingung ein, die sogenannte BIG-M-Bedingung. Diese Bedingung soll sicherstellen, dass wir feingemahlene Kieselsteine wirklich nur dann produzieren, wenn wir y = 1 setzen:

$x_{F}\leq M\cdot y$

M sei hier eine hinreichend große Zahl - also eine Zahl, die so groß ist, dass sie die denkbare Menge an zu produzierenden feingemahlenen Kieselsteinen nicht einschränkt, also beispielsweise 5, denn mehr dürfen wir aufgrund mangelnder Nachfrage ohnehin nicht produzieren.

Aufmerksame Teilnehmer haben sicher gemerkt, dass wir nach Einführung dieser Nebenbedingung bequem die Nebenbedinung $x_{F}\leq 5$ wegfallen lassen könnten. Dies ist zwar prinzipiell korrekt, aber moderne Optimierer suchen ohnehin nach Redundanzen dieser Art, und tun dies so schnell, dass faktisch die Rechenzeit davon nicht erhöht wird. Bei allgemeiner Formulierung ist es allerdings oftmals deutlich übersichtlicher, auf solches Wegkürzen „per Hand“ zu verzichten.

Abschließend darf wieder die Definition des Wertebereiches für y nicht vergessen werden, also

$y_{i}\in \lbrace 0,1\rbrace$

Damit ist auch dieses Szenario vollständig implementiert worden und könnte nun von einem Optimierer, welcher mit ganzzahligen Entscheidungsvariablen umgehen kann, gelöst werden.

Wie geht's weiter?

Hiermit sind wir am Ende dieses kleinen Exkurses angelangt. Auch wenn er stellenweise vielleicht etwas trocken geraten ist, bildet er die Grundlage eines großen Teils moderner Optimierungsverfahren. Ist dieses Kapitel vollständig verstanden, werden die kommenden Kapitel ein wesentlich leichter zu verstehen sein.

Nun geht es mit dem eigentlichen Produktionsmanagement los, als erstes kommen wir zur ...

ICH WEISS NOCH NICHT, WIE ES WEITERGEHT, ICH WILL DEMNÄCHST DIE KONZEPTION DES KURSES NOCH EINMAL ÜBERARBEITEN. --Sepp 09:16, 5. Mär. 2007 (CET)