Modelle des Operations Research - Universität Graz · der 1980er Jahre begannen Narendra Karmarkar und andere mit der Entwicklung von Innere-Punkte-Verfahren zur L¨osung linearer

Modelle des Operations Research

Prof. Hans Kellerer

Inhaltsverzeichnis

Inhaltsverzeichnis

1 Grundlagen 3

1.1 Einfuhrung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.2 Definitionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.3 Graphische Losung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.4 Formen eines LP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.4.1 Standardform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.4.2 Normalform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.4.3 Kanonische Form . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

1.5 Eigenschaften eines LP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

1.6 Der Simplex Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

1.6.1 Prinzip des Simplex . . . . . . . . . . . . . . . . . . . . . . . . . . 18

1.6.2 Interpretationen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

1.7 Sensitivitatsanalyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

1.7.1 Anderungen der Zielfunktionskoeffizienten . . . . . . . . . . . . . . 28

1.7.2 Anderungen der Restriktionen . . . . . . . . . . . . . . . . . . . . 29

2 Erweiterungen 31

2.1 Modell mit Uberstunden . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2.2 Modell mit intensitatsmaßiger Anpassung . . . . . . . . . . . . . . . . . . 33

2.3 Mehrperiodiges Modell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

2.4 Modell mit Teilefertigung . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

2.5 Kuppelproduktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

2.6 Personalplanung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

2.7 Finanzierungs- und Investitionsprogramm . . . . . . . . . . . . . . . . . . 44

Literatur 48

2

1.1 Einfuhrung

1 Grundlagen

1.1 Einfuhrung

Die lineare Optimierung oder auch lineare Programmierung beschaftigt sich mit Verfah-ren, die den maximalen oder minimalen Wert einer linearen Funktion unter Einbeziehungeinschrankender linearer Gleichungen und Ungleichungen bestimmen. Der Begriff

”linea-

re Programmierung“ sollte dabei nicht mit dem Begriff”Programmieren“ im Sinne des

Erstellens eines Computerprogramms verwechselt, sonder eher als Synonym fur Planungverstanden werden. Anwendungen der linearen Optimierung finden sich heute unter an-derem

- in der Produktionsprogrammplanung (optimale Kapazitatsauslastung von Maschi-nen, optimale Ausnutzung vorhandener Rohstoffe)

- in der Losung von Transportproblemen,

- im Routing in Telekommunikations- oder Verkehrsnetzen,

- zur Losung von Mischungsproblemen,

- zur Losung von Schichtarbeitsproblemen,

- in spieltheoretischen Problemstellungen.

Die ersten Arbeiten zur linearen Optimierung wurden 1939 vom sowjetischen Mathema-tiker Leonid Witaljewitsch Kantorowitsch in seinem Buch

”Mathematische Methoden in

der Organisation und Planung der Produktion“ veroffentlicht.

Die Grundlage fur den richtigen Durchbruch der linearen Optimierung schaffte Dantzig1947, mit der Entwicklung des Simplex Algorithmus, der heute eines der meistgenutztenVerfahren zur Losung linearer Programme ist. Das Hauptinteresse lag dabei zunachstin der Anwendung auf militarische Problemstellungen. In den darauf folgenden Jahrenentwickelten Dantzig, John von Neumann, Oscar Morgenstern, Tjalling Koopmans undandere das Verfahren weiter. Mit dem Aufkommen von Computern Mitte der 1950erJahre war man in der Lage auch großere Probleme losen zu konnen. Schon im Jahre1956 etwa konnten mit einer IBM-Maschine Probleme der linearen Optimierung mitmehr als 200 Gleichungen mit großer Genauigkeit gelost werden. Erste wirtschaftlicheAnwendungen erfolgten insbesondere bei der Produktionsplanung in Olraffinerien.

Im Jahre 1979 veroffentlichte Leonid Khachiyan die Ellipsoidmethode, mit der lineareProgramme erstmals - zumindest theoretisch - polynomial gelost werden konnten. Mitteder 1980er Jahre begannen Narendra Karmarkar und andere mit der Entwicklung vonInnere-Punkte-Verfahren zur Losung linearer Programme.

Die Verbesserung der Algorithmen und die gleichzeitige Zunahme der Rechenleistungvon Computern ermoglicht es inzwischen lineare Programme mit mehreren MillionenVariablen oder Ungleichungen zu losen.

3

1.2 Definitionen

1.2 Definitionen

Definition

Lineare Optimierung ermoglicht es also Maxima oder Minima von linearen Funktionenunter Einschrankung durch gegebene Nebenbedingungen zu finden. Unter einem LPversteht man die Aufgabe, eine lineare Zielfunktion

z = F (x1, x2, . . . , xn) = c1 · x1 + c2 · x2 + · · ·+ cn · xn

zu maximieren oder zu minimieren und zwar unter Beachtung von linearen Nebenbedin-gungen (Restriktionen) der Form

a11 · x1 + a12 · x2 + · · ·+ a1n · xn {<, >, =} b1a21 · x1 + a22 · x2 + · · ·+ a2n · xn {<, >, =} b2

. . .

am1 · x1 + am2 · x2 + · · ·+ amn · xn {<, >, =} bm

und zumeist unter Berucksichtigung der so genannten Nichtnegativitatsbedingungen:

xj > 0 fur alle j

Man nennt:

z die Zielfunktionc1, . . . , cn die Koeffizienten der Zielfunktionx1, . . . , xn die Variablenaij die Koeffizienten der Nebenbedingung

Definition

a) Einen Punkt (x1, . . . , xn) des Rn der alle Nebenbedingungen und die Nichtnega-

tivitatsbedingungen erfullt, heißt zulassige Losung

b) Die Menge aller zulassigen Losungen nennt man den zulassigen Bereich

c) Eine zulassige Losung heißt optimale Losung, wenn es keine weitere Losung mit(bei einem Maximierungsproblem) großerem, (bei einem Minimierungsproblem)kleinerem Zielfunktionswert gibt.

4

1.2 Definitionen

Formuliert man obige Darstellung in Matrizenschreibweise, so erhalt man:

Max (Min) z = cT · x

unter A · x ≤ b

x > 0

wobei:

c =

c1...

cn

. . . den Zielfunktionsvektor,

b =

b1...

bn

. . . den Beschrankungsvektor

A =

a11 · · · a1n...

...

am1 · · · amn

. . . eine m× n Matrix symbolisieren.

5

1.3 Graphische Losung


Ist die Zielfunktion F nur von zwei Variablen abhangig, so lasst sich das Optimierungs-problem mittels eines graphischen Verfahrens losen. (Fur hoherdimensionale Aufgaben(mit moglicherweise tausenden Variablen) kann mit Hilfe des Simplexverfahrens eineLosung gefunden werden; doch dazu spater).

Ein Beispiel:

max 10x1 + 12x2bzgl. x1 + 3x2 6 15

2x1 + x2 6 20

x1 > 0

x2 > 0

Um den zulassigen Bereich zu bestimmen, betrachten wir zunachst welche Menge vonPunkten des R2 durch die Ungleichung x1+3x2 6 15 beschrieben wird. Wir konstruierendazu die Randgerade, die durch die Gleichung x1 + 3x2 = 15 gegeben ist. Diese lasstsich recht einfach zum Beispiel durch ermitteln ihrer Schnittpunkte mit den Koordina-tenachsen bestimmen. Wir setzen dazu abwechselnd x1 = 0 und x2 = 0 und erhalten diePunkte (0/5) bzw. (15/0). Verbinden liefert die gewunschte Gerade (Abbildung 1).

x2

x1

0 10 20

10

20

15

155

5

Abbildung 1: Lineare Funktion

6


Diese teilt nun den R2 in zwei Halbebenen. Um festzustellen, welche”Seite“ der Ge-

raden durch die Ungleichung x1 + 3x2 6 15 beschrieben wird, bedient man sich einesTestpunktes z.B. (0/0). Auch dieser erfullt die gegebene Ungleichung, somit erhalt manden in Abbildung 2 dargestellten schraffierten Bereich.

x2

x1

0 10 20

10

20

15

155

5

Abbildung 2: Lineare Ungleichung

Analog verfahrt man mit 2x1 + x2 6 20. Beachtet man nun auch, dass durch x1, x2 > 0nur Punkte des ersten Quadranten zulassig sind, ergibt sich der in Abbildung 3 markiertezulassige Bereich.

Zur Bestimmung des optimalen Wertes ist nun jene Isoquante der Zielfunktion zu be-stimmen, die den großtmoglichen Funktionswert liefert und den zulassigen Bereich ge-rade noch beruhrt. Wir wahlen z.B. die Isoquante zum Niveau z = 60. Das heißt wirmussen die Gerade mit der Gleichung 10x1 + 12x2 = 60 zeichnen. Man bestimmt dazu,wie oben, die Schnittpunkte mit den Koordinatenachsen durch abwechselndes Nullsetzender Variablen. x1 = 0 und x2 = 0 ergibt die Punkte (0/5) bzw. (6/0). Verbinden liefertdie gewunschte Gerade. Parallelverschieben in Richtung des Gradienten der Zielfunk-

tion, hier: grad (F ) =

(

10

12

)

, ergibt maximalen Funktionswertzuwachs. Wir erhalten

als Optimallosung den Punkt (9/2)(Abbildung 4). Der zugehorige Optimalwert betragtz = 10 · 9 + 12 · 2 = 114.

Ein lineares Programm muss aber nicht immer eine eindeutige Losung besitzen. Es sindauch Falle mit endlich vielen, unendlich vielen, sowie keinen Losungen denkbar.

7


x2

x1

0 10 20

10

20

15

155

5

Abbildung 3: Zulassiger Bereich

x2

x1

0 10 20

10

20

15

155

5

OL (9/2)

Abbildung 4: Optimallosung

8


Beispiele:

1. Das Programm

max 3x1 + 4x2bzgl −x1 + x2 6 3

−x1 + 3x2 6 13

x1, x2 > 0

besitzt keine Losung, da der zulassige Bereich (Abbildung 5) unbeschrankt ist.

x2

x1

0 10 20

10

20

15

155

5

Abbildung 5: unbeschrankter zulassiger Bereich

2. Das Programm

max 3x1 + 4x2bzgl −x1 + 2x2 > 8

−x1 + 6x2 6 6

x1, x2 > 0

besitzt keine Losung, da der zulassige Bereich (Abbildung 6) leer ist.

9


x2

x1

0 10 20

10

20

15

155

5

Abbildung 6: leerer zulassiger Bereich

3. Das Programm

max 10x1 + 12x2bzgl. x1 + 3x2 6 15

2x1 + x2 6 20

x1 > 0

x2 > 0

besitzt unendlich viele Losungen (Abbildung 7), namlich alle Punkte der Strecke[(9/2); (0/5)].

10

1.4 Formen eines LP

x2

x1

0 10 20

10

20

15

155

5

(9/2)

(0/5)

Abbildung 7: unendlich viele Losungen

1.4 Formen eines LP

1.4.1 Standardform

Jedes LP lasst sich schreiben als:

Max z =n∑

j=1

cj · xj

untern∑

j=1

a1j · xj 6 b1

......

n∑

j=1

amj · xj 6 bm

xj > 0 fur j = 1, . . . , n

denn

• jede zu minimierende Zielfunktion lasst sich durch Multiplikation mit (-1) in einezu maximierende Funktion uberfuhren.

11

1.4 Formen eines LP

Beispiel: Min 2x1 − 5x2 wird zu Max −2x1 + 5x2

• eine”> “Nebenbedingung wird durch Multiplikation beider Seiten mit (-1) zu ei-

ner”6 “Nebenbedingung.

Beispiel: 2x1 − 3x2 > 5 wird zu −2x1 + 3x2 6 −5

• eine Gleichung kann durch zwei Ungleichungen ersetzt werden.

Beispiel: 2x1 − 3x2 = 5 ⇒

{

2x1 − 3x2 6 5

2x1 − 3x2 > 5wobei die zweite Ungleichung

wiederum durch Multiplikation mit (-1) in eine”6 “Ungleichung umgewandelt

werden kann.

• falls eine Variable xj beliebige Werte aus R annehmen darf (also nicht vorzeichen-beschrankt ist), so kann man sie durch zwei neue Variable x′j > 0 und x′′j > 0substituieren, wobei xj = x′j − x′′j gilt.

Beispiel: Liegt eine Beschrankung der Form 2x1 − 3x2 6 5 vor und ist z.B. x2nicht vorzeichenbeschrankt (x2 <> 0), so setzt man x2 = x′2 − x′′2 mit x′2, x′′2 > 0.Eingesetzt in die gegebene Ungleichung ergibt sich: 2x1 − 3 · (x′2 − x′′2) 6 5 also2x1 − 3x′2 + 3x′′2 6 5

12

1.4 Formen eines LP

Wir wollen nun anhand eines Beispieles die Umformungen im Einzelnen betrachten.

Gegeben sei folgendes Problem:

min 2x1 + 2x2bzgl. 6x1 + x2 = 90

4x1 + 9x2 > 5

2x1 + 14x2 6 6

x1 > 0, x2 < > 0

In einem ersten Schritt wird die Zielfunktionszeile durch eine Multiplikation mit (-1)von einem Minimumproblem in ein Maximumproblem umgeformt. Die neue Zielfunkti-on lautet somit: max −2x1 − 2x2

Betrachten wir nun die erste Nebenbedingung: 6x1 + x2 = 90

Wir ersetzen diese durch zwei Ungleichungen, namlich6x1 + x2 6 90

6x1 + x2 > 90wobei die

zweite Ungleichung noch durch Multiplikation mit (-1) in die”6 “ Form gebracht werden

muss! Wir erhalten: −6x1 − x2 6 −90

Die zweite Nebenbedingung ist ebenfalls von der”> “ Form. Sie ist somit auch mit (-1)

zu multiplizieren. Es ergibt sich: −4x1 − 9x2 6 −5

Da nun aber x2 nicht vorzeichenbeschrankt ist, muss noch eine Substitution vorgenom-men werden. Wir setzen: x2 = x′2 − x′′2 mit (x′2 > 0, x′′2 > 0).

Wir erhalten daher das neue Problem:

max −2x1 − 2x′2 + 2x′′2bzgl. 6x1 + x′2 − x′′2 6 90

−6x1 − x′2 + x′′2 6 90

−4x1 − 9x′2 + 9x′′2 6 −5

x1 + 7x′2 − 7x′′2 6 3

x1, x′2, x′′2 > 0

13

1.4 Formen eines LP

1.4.2 Normalform

Der erste Schritt um ein LP mittels eines Algorithmus zu losen, ist es die Ungleichun-gen in den Nebenbedingungen der Standardform in Gleichungen umzuwandeln. Diesgeschieht mit Hilfe so genannter Schlupfvariablen. Es ergibt sich folgendes Modell:

Max z =n∑

j=1

cj · xj

untern∑

j=1

a1j · xj + y1 = b1

......

n∑

j=1

anj · xj + ym = bm

xj > 0 fur j = 1, . . . , n und yk > 0 fur k = 1, . . . , m

beziehungsweise in Matrizenschreibweise:

Max z = cT · x

unter A · x = b

x > 0

Fur unser Einfuhrungsbeispiel ergibt dies:

Aus:

max 10x1 + 12x2bzgl. x1 + 3x2 6 15

2x1 + x2 6 20

x1 > 0

x2 > 0

wird:

max 10x1 + 12x2bzgl. x1 + 3x2 + y1 = 15

2x1 + x2 + y2 = 20

x1, x2, y1, y2 > 0

14

1.5 Eigenschaften eines LP

1.4.3 Kanonische Form

Gelten fur die Matrix A, die Vektoren b und c zusatzlich die Eigenschaften:

b > 0, c =

c1...

cn−m

0...

0

und A =

a11 · · · a1,n−m 1 · · · 0...

.... . .

am1 · · · am,n−m 0 · · · 1

so spricht man vom einem LP in kanonischer Form. Diese ist notig, um den so genanntenSimplex Algorithmus anwenden zu konnen.


Der durch die Nebenbedingungen begrenzte Bereich entspricht geometrisch einem sogenannten konvexen Polyeder.

Zur Erinnerung: Eine Punktmenge X ⊂ Rn heißt konvex, wenn sie mit zwei beliebigenPunkten P1 und P2 auch alle Punkte der Verbindungsstrecke P1P2 enthalt.

Die Eckpunkte (auch Extrempunkte) eines solchen Polyeders spielen eine besondere Rol-le; sie sind dadurch charakterisiert, dass sie auf keiner Verbindungslinie zweier beliebigerPunkte der Menge X liegen. Wie erhalt man nun diese Eckpunkte rechentechnisch? Dazubenotigen wir zunachst die folgende

Definition

Eine Menge {(x1, . . . , xn ) ∈ Rn |a1x1 + · · ·+ anxn 6 b} heißt Halbraum.

Eine Menge {(x1, . . . , xn ) ∈ Rn |a1x1 + · · ·+ anxn = b} heißt Hyperebene.

Eine Hyperebene wird im Fall n = 3 durch die Gleichung einer Ebene im R3 beschrieben:3x1+2x2+5x3 = 10. Im Fall n = 2 ergibt sich die Gleichung einer Geraden: 3x1+7x2 = 17

Man beachte: eine Hyperebene stellt immer die Begrenzung der zugehorigen Halbebenedar.

15


Man erhalt nun die Ecken des Polyeders, indem man Hyperebenen schneidet. Es gilt: einPunkt heißt Eckpunkt des zulassigen Bereichs im Rn, wenn er zulassig und der Schnitt-punkt von n linear unabhangigen Hyperebenen ist. Eine Ecke heißt dabei entartet,wenn sie durch Schnitt von mehr als n Hyperebenen entsteht.

In der kanonischen Form besteht ein LP aus n + m Nebenbedingungen. Davon sind m

”normale“ und n Nichtnegativitatsbedingungen. Man kann nun die Ecken bestimmen,indem man n - m Variablen (diese werden als Nichtbasisvariable bezeichnet) gleich Nullsetzt und mit den ubrigen m Variablen (Basisvariablen) das verbliebene Gleichungssys-tem lost.

Zusammengefasst ergibt sich folgende

Definition

Fur ein LP in Normalform

Max z = cT · x

unter A · x = b

x > 0

a) heißt eine zu einer Basis(

ai1, . . . , aim)

der Matrix A berechnete spezielle Losungvon A · x = b eine Basislosung

b) Die zugehorigen Variablen xi1, . . . , xim heißen Basisvariable (BV). Die ubrigenVariablen heißen Nichtbasisvariable (NBV), sie haben den Wert Null.

c) Eine Basislosung heißt zulassig, wenn alle Variablen xij > 0 fur alle j = 1, . . . , m

und nicht zulassig, wenn mindestens ein xij < 0.

Hintergrund dieser Uberlegungen sind die folgenden Satze:

Satz

Fur ein LP in Normalform gilt

1. Die Menge der zulassigen Losungen des LP ist konvex mit endlich vielen Eckpunk-ten

2. Eine lineare Funktion F, die auf einem konvexen Polyeder X definiert ist, nimmtihr Optimum in mindestens einem Eckpunkt des Polyeders an.

Bemerkung: Man kann zeigen, dass auch bei einem unbeschrankten zulassigen Bereich Xeines LP, mindestens eine Ecke von X optimale Losung ist, falls uberhaupt eine optimaleLosung des Problems existiert. Daher kann man sich bei der Losung von LPs auf dieUntersuchung der Eckpunkte des zulassigen Bereichs beschranken!

16


Unser Einfuhrungsbeispiel hat, in kanonische Form gebracht, das folgende Aussehen:

max 10x1 + 12x2bzgl. x1 + 3x2 + y1 = 15

2x1 + x2 + y2 = 20

x1, x2, y1, y2 > 0

x2

x1

0 10 20

10

A

B

C

D

20

15

155

5

Abbildung 8: Ecken des zulassigen Bereichs

Eckpunkt BV NBV BL (x1, x2, y1, y2)

A(0/0) y1, y2 x1, x2 (0,0,15,20)

B(0/5) x2, y2 x1, y1 (0,5,0,15)

C(9/2) x1, x2 y1, y2 (9,2,0,0)

D(10/0) x1, y1 x2, y2 (10,0,5,20)

Alle zulassigen Basislosungen (BL) sind in obiger Tabelle ablesbar. Jeder Eckpunkt wirddabei durch die Basisvariablen (BV) und die Nichtbasisvariablen (NBV) beschrieben.Wie oben erklart besteht unser LP in der kanonischen Form aus n + m = 4 + 2 = 6Nebenbedingungen. Davon sind m = 2

”normale “und n = 4 Nichtnegativitatsbedin-

gungen. Man kann nun die Ecken bestimmen, indem man n - m = 4 - 2 = 2 Variablen(diese werden als Nichtbasisvariable bezeichnet) gleich Null setzt und mit den ubrigenm = 2 Variablen (Basisvariablen) das verbliebene Gleichungssystem lost. Geometrischentspricht dies in unserem Beispiel dem Schnitt je zweier Geraden.

17

1.6 Der Simplex Algorithmus

Nun kann mit den Ecken der jeweilige Zielfunktionswert bestimmt und auf Optimalitathin gepruft werden. Jeder zulassige Bereich besitzt nur endlich viele Ecken. Es gilt:wird der zulassige Bereich durch n Ungleichungen und m Gleichungen gebildet, so kann

er hochstens

(

n+m

n

)

Ecken haben. Trotz dieser Obergrenze ist eine solche direkte

Variante zur Losung eines LP, indem man also alle Ecken uberpruft, in der Regel jedochsehr aufwendig, da die Anzahl der zu uberprufenden Falle rasch sehr groß wird. Manverwendet daher einen Algorithmus zur Bestimmung der optimalen Losung.


Der Simplex Algorithmus zahlt nach wie vor zu einem der leistungsfahigsten Verfahrenvon LPs in der Praxis. Der Algorithmus durchsucht den Rand des zulassigen Bereichesnach einer optimalen Losung. Die Grundidee besteht darin, so lange von einer Ecke deszulassigen Bereichs zu einer benachbarten Ecke zu gehen und dabei einen besseren Ziel-funktionswert zu erzielen, bis dies nicht mehr moglich ist. Im schlechtesten Fall benotigtder Algorithmus exponentielle Laufzeit. Probleme treten in der Praxis dann auf, wenneine der Ecken degeneriert ist, also als Schnitt von mehr Hyperebenen entsteht als notig(z.B. drei Geraden des R2, die einander in einem Eckpunkt schneiden).

1.6.1 Prinzip des Simplex

Betrachten wir nun das Simplexverfahren im Detail. Wir beschranken uns dabei aufden so genannten primalen Simplex Algorithmus, der von einer bekannten zulassigenBasislosung ausgeht.Der Algorithmus setzt sich aus drei Schritten wie folgt zusammen:

1. Man startet mit einer (beliebigen) zulassigen Basislosung

2. Nun uberpruft man, ob diese Losung optimal ist. Wenn nicht erfolgt ein Austauscheiner Basisvariablen gegen eine Nichtbasisvariable, sodass eine Verbesserung desZielfunktionswertes eintritt (geometrisch: Ubergang zu einer benachbarten Ecke)

3. Danach druckt man die Zielfunktion und jede Basisvariable in den Nebenbedin-gungen durch Nichtbasisvariable aus und beginnt wieder mit 2).

Ein Beispiel:

max 4x1 + 3x2bzgl x1 + x2 6 7

3x1 + 2x2 6 18

x1 + 3x2 6 15

x1, x2 > 0

18


Betrachten wir nun die geometrische Losung des Problems (diese lasst sich wie in Ab-schnitt 1.3 beschrieben, einfach bestimmen)(Abbildung 9).

x2

x1

0 10 20

10

20

15

155

5

OL (4/3)

Abbildung 9: Optimale Losung

Nun formen wir das Programm in kanonische Form um. Hinweis: wir verwenden diesmalals Bezeichnung fur die Schlupfvariablen x3, x4 und x5

max 4x1 + 3x2bzgl x1 + x2 + x3 = 7

3x1 + 2x2 + x4 = 18

x1 + 3x2 + x5 = 15

x1, . . . , x5 > 0

Der Start erfolgt nun mir einer beliebigen zulassigen Basislosung. Wir wahlen z.B. dieSchlupfvariablen x3, x4 und x5 als Basisvariablen und die Variablen x1 und x2 (dieStrukturvariablen des Problems) als Nichtbasisvariablen (das heißt, sie erhalten denWert Null und wir befinden uns im Punkt (0/0)). Dadurch ergibt sich folgende erstezulassige Basislosung:

x1 = 0, x2 = 0, x3 = 7, x4 = 18, x5 = 15 mit dem Ziefunktionswert z = 0

Die Berechnung der Werte fur die Variablen x3, x4, und x5 erfolgt dabei durch geeigneteUmformung der Nebenbedingungen. Man erhalt:

19


x3 = 7 − x1 − x2

x4 = 18 − 3x1 − 2x2

x5 = 15 − x1 − 3x2

z = 4x1 + 3x2

Nun erfolgt die Uberprufung auf Optimalitat. Da aber beide Koeffizienten in der Ziel-funktion positiv sind, kann die momentane Losung noch nicht optimal sein, denn z wachstum 4, wenn man x1 um eine Einheit und um 3, wenn man x2 um eine Einheit erhoht.(x1 und x2 sind ja momentan Null!) Man wird also einen Basistausch vornehmen.

Als neue BV wahlt man am besten diejenige bisherige NBV aus, die den großten positivenKoeffizienten in der Zielfunktion besitzt, denn dies verspricht einen hochstmoglichenFunktionswertzuwachs. In unserem Fall wird also x1 neue Basisvariable. (Man beachte,x2 bleibt NBV und hat daher nach wie vor den Wert Null!). Da alle anderen Variablenpositiv bleiben mussen erhalt man aus obigem Gleichungssystem:

x3 = 7 − x1 > 0

x4 = 18 − 3x1 > 0

x5 = 15 − x1 > 0

dass x1 hochstens den Wert 6 annehmen kann (zweite Gleichung), ansonsten ware x4bereits negativ. Fur x1 = 6 ergibt sich:

x3 = 1, x4 = 0 und somit neue Nichtbasisvariable x5 = 9, x2 = 0 bleibt Nichtbasisvaria-ble. Die neue Basislosung (wir befinden uns nun im Punkt (6/0)) lautet daher:

x1 = 6, x2 = 0, x3 = 1, x4 = 0, x5 = 9 mit dem Zielfunktionswert z = 24

Nun muss die Zielfunktion und jede Basisvariable in den Nebenbedingungen durch dieneuen Nichtbasisvariablen x2 und x4 ausgedruckt werden.

Man erhalt aus der zweiten Nebenbedingung:

x4 = 18− 3x1 − 2x2

durch Umformen:

x1 = 6−2

3x2 −

1

3x4

Eingesetzt in die ubrigen Gleichungen der ersten Basislosung (einschließlich der Ziel-funktion) ergibt sich:

x3 = 1 − 13x2 + 1

3x4

x1 = 6 − 23x2 − 1

3x4

x5 = 9 − 73x2 + 1

3x4

z = 24 + 13x2 − 4

3x4

20


Es erfolgt wiederum die Prufung auf Optimalitat. Der positive Koeffizient der Variablenx2 in der Zielfunktion bewirkt, dass bei einer Erhohung der Variablen x2 um eine Einheit,der Funktionswert sich um ein Drittel erhoht. Wurde man hingegen x4 um eine Einheiterhohen, so wurde sich der Funktionswert um vier Drittel verringern!

Somit ist ein weiterer Basistausch moglich. Die Variable x2 wird neue Basisvariable, x4bleibt Nichtbasisvariable und hat somit nach wie vor den Wert Null. Da alle Variablennichtnegativ sein mussen, ergibt sich aus unserem Gleichungssystem:

x3 = 1 − 13x2 > 0

x1 = 6 − 23x2 > 0

x5 = 9 − 73x2 > 0

aus der Gleichung eins, dass x2 hochstens den Wert 3 annehmen kann. x3 wird neueNichtbasisvariable. (Wie befinden uns im Punkt (4/3)). Die neue Basislosung lautetdaher:

x1 = 4, x2 = 3, x3 = 0, x4 = 0, x5 = 2 mit dem Zielfunktionswert z = 25

Nun muss, analog zu vorhin, die Zielfunktion und jede Basisvariable in den Nebenbedin-gungen durch die neuen Nichtbasisvariablen x3 und x4 ausgedruckt werden.

Man erhalt aus der ersten Gleichung der zweiten Basislosung

x3 = 1−1

3x2 +

1

3x4

durch Umformen:x2 = 3 + x4 − 3x3

Eingesetzt in die ubrigen Gleichungen der zweiten Basislosung (einschließlich der Ziel-funktion) ergibt sich:

x2 = 3 − 3x3 + x4

x1 = 4 + 2x3 − x4

x5 = 2 + 7x3 − 2x4

z = 25 − x3 − x4

Man erkennt, dass die Losung nun optimal sein muss, da eine Erhohung von x3 bzw. x4eine Verringerung des Funktionswertes zur Folge haben wurde.

Man kann nun auch anhand der Abbildung 9 gut das Fortschreiten des Algorithmus geo-metrisch nachvollziehen. Man gelangt vom Startpunkt (0/0) zunachst zum Punkt (6/0)und daraufhin zur Optimallosung (4/3). Nach drei Iterationen ist somit die optimaleLosung gefunden.

21


Bemerkung: Es ist naturlich sinnvoll zunachst nur die Zielfunktion durch NBV auszu-drucken und auf Optimalitat hin zu untersuchen, denn ist eine Verbesserung nicht mehrmoglich, mussen die Nebenbedingungen nicht mehr durch NBV ausgedruckt werden.

Ublicherweise erfolgt die Darstellung des Simplex Algorithmus ubersichtlicher durch einso genanntes Simplex Tableau. Fur unser Beispiel

max 4x1 + 3x2bzgl x1 + x2 + x3 = 7

3x1 + 2x2 + x4 = 18

x1 + 3x2 + x5 = 15

x1, . . . , x5 > 0

hatte dies folgendes Aussehen:

BV x1 x2 x3 x4 x5 b

x3 1 1 1 0 0 7

x4 3 2 0 1 0 18

x5 1 3 0 0 1 15

z 4 3 0 0 0 0

Sehen wir uns dieses Tableau nun ein wenig genauer an.In der ersten Zeile findet man alle Variablen, die in diesem Problem auftreten (einschließ-lich der Schlupfvariablen).In der ersten Spalte befinden sich die Basisvariablen der ersten Iteration (hier x3, x4und x5). In den entsprechenden Zeilen stehen die Koeffizienten der einzelnen Variablen,abgelesen an den Gleichungen (Restriktionen) der kanonischen Form.In der außerst rechten Spalte findet man die Werte des Beschrankungsvektors b. Auchdiese lassen sich an den Gleichungen ablesen.In der letzten Zeile befinden sich die Koeffizienten der Variablen in der Zielfunktion.(man beachte, die Basisvariablen x3, x4 und x5 gehen mit dem Wert Null in die Ziel-funktion ein).Im rechts unten befindlichen Feld kann der (momentane) Zielfunktionswert abgelesenwerden. Er besitzt hier den Wert Null.

Da in den Spalten der Basisvariablen stets die zugehorigen Einheitsvektoren stehen, kannman auch eine verkurzte Form des Tableaus erstellen, welche nur noch die Spalten derNichtbasisvariablen enthalt und zwar wie folgt:

22


x1 x2 b

x3 1 1 7

x4 3 2 18

x5 1 3 15

z 4 3 0

Nach Durchfuhrung der ersten Iteration ergibt sich folgendes Tableau:

x1 x2 x3 x4 x5 b

x1 1 23

0 13

0 6

x3 0 13

1 -13

0 1

x5 0 73

0 -13

1 9

z 0 13

0 -43

0 24

Die Werte dafur konnen aus unserer zweiten Basislosung abgelesen werden. In derverkurzten Form sieht dies wie folgt aus:

x2 x4 b

x123

13

6

x313

-13

1

x573

-13

9

z 13

-43

24

Die dritte Iteration wurde schlussendlich folgendes Tableau ergeben:

x1 x2 x3 x4 x5 b

x2 0 1 -3 1 0 3

x1 1 0 2 -1 0 4

x5 0 0 7 -2 1 2

z 0 0 -1 -1 0 25

Beziehungsweise dessen Kurzform:

x3 x4 b

x2 -3 1 3

x1 2 -1 4

x5 7 -2 2

z -1 -1 25

23


Auf eine einfachere Form der Berechnung der einzelnen Tableaus, etwa mit Hilfe desGauss-Jordan Verfahrens, wird hier verzichtet. Naheres dazu findet man etwa in Huls-mann et al. oder bei Domschke/Drexl.

1.6.2 Interpretationen

Wir wollen nun eine okonomische Interpretation der einzelnen Werte in einem SimplexTableau vornehmen. Wir betrachten dazu ein Produktionsprogrammplanungsmodell mitfolgenden Angaben:

Zwei Guter werden auf drei Anlagen A, B und C gefertigt, die jedoch Kapazitatsrestrik-tionen unterliegen. Die verfugbaren Kapazitaten betragen auf Anlage A 220 Stunden,in Anlage B 240 Stunden und in Anlage C 260 Stunden. Produkt 1 beansprucht AnlageA 4 Stunden, Anlage B 2 Stunden, Anlage C ist zur Herstellung von Produkt 1 nichtnotig. Die Beanspruchungen durch Produkt 2 sind auf Anlage A mit 2 Stunden, AnlageB mit 6 Stunden und Anlage C mit 8 Stunden gegeben. Der jeweilige Deckungsbeitrag,welchen die Produkte liefern, betragt bei Produkt 1 3000 GE, bei Produkt 2 4000 GE.Zusatzlich sind Fixkosten in Hohe von 19000 gegeben. Welche Mengen von Produkt 1und Produkt 2 sind herzustellen, damit der Gesamtgewinn moglichst groß wird?

Das Problem kann wie folgt als LP formuliert werden:

max 3000x1 + 4000x2 − 19000

bzgl 4x1 + 2x2 6 220 Kapazitatsrestriktion AnlageA

2x1 + 6x2 6 240 Kapazitatsrestriktion AnlageB

8x2 6 260 Kapazitatsrestriktion AnlageC

x1, x2 > 0

Umgeformt in die kanonische Form ergibt sich:

max 3000x1 + 4000x2 − 19000

bzgl 4x1 + 2x2 + x3 = 220 Kapazitatsrestriktion AnlageA

2x1 + 6x2 + x4 = 240 Kapazitatsrestriktion AnlageB

8x2 + x5 = 260 Kapazitatsrestriktion AnlageC

x1, x2, x3, x4, x5 > 0

Das Endtableau (auf dessen Berechnung wir hier verzichten) hatte nun folgendes Aus-sehen:

x1 x2 x3 x4 x5 b

x1 1 0 310

- 110

0 42

x2 0 1 - 110

15

0 26

x5 0 0 45

-85

1 52

z 0 0 -500 -500 0 230000

24


beziehungsweise in der verkurzten Form:

x3 x4 b

x1310

- 110

42

x2 - 110

15

26

x545

-85

52

z -500 -500 230000

Aus diesem Endtableau kann nun die optimale Losung entnommen werden:

Es sollten von Produkt 1 42 Stuck und von Produkt 2 26 Stuck produziert werden. Derdabei erzielte Gewinn betragt 230000 GE.

Wir erhalten als BV also die Variablen x1, x2 und x5, sowie als NBV die Variablenx3 und x4. Die Schlupfvariablen x3 und x4 sind NBV, dies bedeutet, sie besitzen denWert Null. Dies heißt aber wiederum, dass auf Anlage A und Anlage B keine Kapazitatmehr frei ist. Sie sind somit voll ausgelastet. Um die optimalen Mengen zu produzierenbenotigt man genau 220 Stunden auf Anlage A und 240 Stunden auf Anlage B, wie durchEinsetzen in die zugehorigen Restriktionen leicht verifiziert werden kann. Auf Anlage Cist hingegen noch Kapazitat frei (die zugehorige Schlupfvariable ist ja BV und besitztlaut Endtableau den Wert x5 = 52) und zwar in Hohe von 52 Stunden. 26 Stuck desProduktes 2 benotigen nur 8 · 26 = 208 Stunden auf Anlage C.

Die Koeffizienten der Zielfunktion im Endtableau bezeichnet man (hier x3: - 500 und x4: -500) als

”Opportunitatskosten “oder als

”Schattenpreise “. Negative Koeffizienten zeigen

dabei eine Verschlechterung, positive eine Verbesserung des Ergebnisses an. Wurde manin unserem Beispiel etwa die Kapazitat der Anlage A um eine Einheit erhohen (manbeachte: dies entspricht x3 = -1! ersichtlich aus der Nebenbedingungsgleichung fur dieAnlage A, denn dies fuhrt zu einem Wert von 221 auf der rechten Seite der Gleichung), sobrachte dies einen zusatzlichen Gewinn in Hohe von (−1)·(−500) = 500 GE. Analog dazubewirkt eine Verringerung der Kapazitat um eine Stunde (x3 = 1) eine Verringerung desGewinns um 500 GE. Dies bedeutet, eine Erhohung der Kapazitat von Anlage A lohntsich nur, wenn die Kosten dafur geringer sind als 500 GE.

Nun zur Interpretation der ubrigen Zahlen im Endtableau:

Die Koeffizienten in den Spalten der beiden Nichtbasisvariablen, lassen sich als Ande-rungsfaktoren fur die Restriktionen interpretieren (vgl. Ewert/ Wagenhofer).

Betrachten wir zunachst die Spalte fur x3: Eine Erhohung der Kapazitat von Anlage Aum eine Einheit (x3 = -1) ermoglicht es die Produktion von Produkt 1 (x1 = 42+ 3

10) um

310

zu erhohen. Produkt 2 musste um 110

eingeschrankt werden und die freie Kapazitatvon Anlage C wurde sich um 4

5Stunden verringern. (x5, Schlupfvariable von Anlage C

hat dann einen Wert von x5 = 52− 45).

25

1.7 Sensitivitatsanalyse

Fur Spalte x4 formulieren wir zu Ubungszwecken eine Interpretation im Falle einer Ver-ringerung der Kapazitat von Anlage B (x4 hatte dann den Wert 1): Diese Verringerungder Kapazitat bewirkt eine Produktionssteigerung bei Produkt 1 in Hohe von 1

10, sowie

eine Verringerung der Produktion von Produkt 2 um 15. Zusatzlich erhoht sich die freie

Kapazitat von Anlage C um 85.


Die Sensitivitatsanalyse gibt Auskunft daruber, wie sich die optimale Losung eines Opti-mierungsmodells bei Veranderungen der Ausgangsdaten verhalt. Sie stellt in der Praxisein wesentliches Hilfsmittel dar, da die sich andernden Parameter in der Regel außerhalbdes Modells bestimmt werden und selten mit Sicherheit bekannt sind. Wie untersuchennun Reaktionen auf Veranderungen der Zielfunktionskoeffizienten cj , sowie der rechtenSeite bj der Restriktionen.

Betrachten wir dazu zunachst folgendes Produktionsplanungsproblem (wiederum zweiProdukte, die auf drei Anlagen gefertigt werden):

max 2x1 + 3x2bzgl 4x1 + 3x2 6 600 Kapazitatsrestriktion AnlageA

2x1 + 2x2 6 320 Kapazitatsrestriktion AnlageB

3x1 + 7x2 6 840 Kapazitatsrestriktion AnlageC

x1, x2 > 0

Umgeformt in die kanonische Form ergibt sich:

max 2x1 + 32bzgl 4x1 + 3x2 + y1 = 600 Kapazitatsrestriktion AnlageA

2x1 + 2x2 + y2 = 320 Kapazitatsrestriktion AnlageB

3x1 + 7x2 + y3 = 840 Kapazitatsrestriktion AnlageC

x1, x2, y1, y2, y3 > 0

Das Endtableau, diesmal in der verkurzten Form, hat folgendes Aussehen:

y2 y3 b

y1 -198

-14

50

x178

-14

70

x2 -38

14

90

z -58

-14

410

26


x2

x1

0 100 200

OL (70/ 90)

250

250

100

200

150

15050

50

A

B

C

Abbildung 10: Sensitivitatsanalyse

Die optimale Losung lautet also: Von Produkt eins sind 70 Stuck, von Produkt zwei90 Stuck herzustellen; auf der Anlage A besteht eine Restkapazitat in Hohe von 50Einheiten. (BV: x1 = 70, x2 = 90, y1 = 50) Auf Anlage B und C gibt es einen Engpass,sie sind also vollig ausgelastet (NBV: y2 = y3 = 0)

Bevor wir nun mit der Analyse beginnen,”ubersetzen“ wir das Endtableau in Gleichun-

gen. Wir erhalten:

y1 = 50 + 198y2 − 1

4y3

x1 = 70 − 78y2 + 1

4y3

x2 = 90 + 38y2 − 1

4y3

z = 410 − 58y2 − 1

4y3

27


1.7.1 Anderungen der Zielfunktionskoeffizienten

Wir wollen nun untersuchen, wie stark sich die Koeffizienten der Zielfunktion andernkonnen, ohne dass sich die optimale Losung andert. Geometrisch entspricht dies in un-serem Beispiel der Fragestellung, wie stark sich die Isoquanten der Zielfunktion drehenkonnen, ohne dass sich der optimale Beruhrpunkt verandert, denn der zulassige Bereichbleibt ja unverandert! Es ist dabei zu unterscheiden, ob die betreffende Variable eineBasisvariable oder eine Nichtbasisvariable ist. Anmerkung: fur die folgenden Betrach-tungen ist es eventuell sinnvoll sich die ursprungliche Zielfunktion in folgender Form zudenken:

max 2x1 + 3x2 + 0y1 + 0y2 + 0y3

1) xj ist Basisvariable

Betrachten wir zunachst den Fall einer Basisvariablen zum Beispiel x1 Eine Anderung desDeckungsbeitrages von Produkt eins von 2 auf etwa (2 + t) ergibt folgende Zielfunktionim Ausgangstableau: max (2 + t) · x1 + 3x2 = 2x1 + t · x1 + 3x2

Nun muss aber auch im Endtableau t · x1 addiert werden, was zu folgender Zielfunktionfuhrt:

z = 410−5

8y2 −

1

4y3 + t · x1

Wir finden also die Basisvariable x1 wieder in der Zielfunktion und mussen diese daherdurch NBV ausdrucken! Dies geschieht mit Hilfe der zweiten Gleichung unseres Endta-bleaus und wir erhalten mit x1 = 70− 7

8y2 +

14y3 durch Einsetzen:

z = 410−5

8y2 −

1

4y3 + t ·

(

70−7

8y2 +

1

4y3

)

Auflosen der Klammer:

z = 410−5

8y2 −

1

4y3 + 70t−

7

8· t · y2 +

1

4· t · y3

Nun werden gleichnamige Terme zusammengefasst und Variablen entsprechend, wennmoglich, herausgehoben:

z = 410 + 70t−

(

5

8+

7

8· t

)

· y2 −

(

1

4−

1

4· t

)

· y3

28


Beachtet man nun, dass die Losung nur dann optimal ist, wenn die Koeffizienten der Va-riablen negativ sind (dies bedeutet hier, dass die Klammerausdrucke positiv sein mussen,da sie negatives Vorzeichen besitzen), so fuhrt dies auf:

58+ 7

8· t > 0 ⇔ t > −5

714− 1

4· t > 0 ⇔ t 6 1

}

zusammengefasst : −576 t 6 1

Addiert man diesen Bereich nun zum ursprunglichen Deckungsbeitrag in Hohe von 2, soerhalt man: Bleibt der Deckungsbeitrag von Gut 1 zwischen 2 − 5

7= 9

7und 2 + 1 = 3,

gibt es keine Anderung der bestehenden optimalen Losung.

2) xj ist Nichtbasisvariable

Betrachten wir nun eine Nichtbasisvariable, z.B. y2. Fur diese gilt: im Bereich]

−∞; 58

]

gibt es keine Anderung, da man bis zu 58y2 addieren kann, ohne dass der Koeffizient

in der Zielfunktionszeile des Endtableuas positiv wird. Erst wenn mehr als 58y2 addiert

werden, wird der Koeffizient positiv und erfordert dann einen Basistausch.

1.7.2 Anderungen der Restriktionen

Wir wollen nun untersuchen, wie sich die rechte Seite einer Beschrankung veranderndarf, ohne dass ein Basistausch notig wird, das heißt sich die Optimalitat der Losungverandert. Geometrisch entspricht eine solche Anderung einer Anderung des zulassigenBereiches, die entsprechenden Geraden werden dabei ja parallel verschoben. Auch hiersind zwei Falle zu unterscheiden:

1) Die Schlupfvariable der geanderten Nebenbedingung ist Basisvariable

Das heißt, die entsprechende Beschrankung ist inaktiv, es sind noch Restkapazitatenvorhanden. Betrachten wir etwa die Schlupfvariable y1. Sie besitzt, laut Endtableauin der optimalen Losung den Wert 50, die Anlage A hat also noch 50 Einheiten freieKapazitat. Dies bedeutet aber, dass die ursprungliche Kapazitat von Anlage A, 600Stunden, um bis zu 50 Einheiten erniedrigt oder um beliebig viele Einheiten erhohtwerden kann, ohne dass sich die optimale Losung verandert.Fur die Kapazitat von Agilt somit folgender Bereich:

[600− 50; 600 +∞[ = [550; ∞[

29


2) Die Schlupfvariable der geanderten Nebenbedingung ist Nichtbasisvariable

Dies bedeutet, es liegt eine aktive Restriktion vor. Auf der entsprechenden Anlage gibtes einen Engpass! Zur Demonstration betrachten wir etwa die Variable y2. Da y3 nachwie vor Nichtbasisvariable ist und somit den Wert Null besitzt aber auch alle anderenVariablen nicht negativ sein mussen, ergibt sich folgendes aus dem Gleichungssystem desEndtableaus:

y1 = 50 + 198y2 > 0

x1 = 70 − 78y2 > 0

x2 = 90 + 38y2 > 0

Daraus ergibt sich fur y2:

y2 > −40019

y2 6 80

y2 > −240

zusammengefasst: −40019

6 y2 6 80

Die Kapazitat von Anlage B kann also um 40019

Einheiten erhoht (man beachte die Schlupf-variable der ursprunglichen Restriktion steht auf der linken Seite der Gleichung, der Wertfur die Beschrankung jedoch auf der rechten) beziehungsweise um maximal 80 Einhei-ten erniedrigt werde, ohne dass sich etwas an der optimalen Losung andert. Fur dieKapazitat von B gilt somit folgender Bereich:

[

320− 80; 320 +400

19

]

= [240; 341, 1]

30

2.1 Modell mit Uberstunden

2 Erweiterungen

Um einen Eindruck von den vielfaltigen Anwendungsmoglichkeiten der linearen Optimie-rung auf okonomische Fragestellungen zu vermitteln, werden wir im Folgenden Erwei-terungen des linearen Produktionsplanungsmodells naher beschreiben. Die dazu in denAbschnitten 2.1 bis 2.5 beschriebenen Beispiele sind mit den jeweiligen Erklarungen aus

”Stepan, A. und Fischer E. (2001): Betriebswirtschaftliche Optimierung“ entnommen.

Als Basis dient folgendes Problem:

Es werden zwei Produkte, 1 und 2, hergestellt. Der Deckungsbeitrag fur Produkt 1moge 30 Geldeinheiten je Stuck, fur Produkt 2 40 Geldeinheiten je Stuck betragen. Dieverfugbaren Kapazitaten in Abteilung I und Abteilung II betragen 7000 bzw. 8000 Ein-heiten. Produkt 1 beansprucht je Stuck 5 Kapazitatseinheiten in Abteilung I und 4 Ka-pazitatseinheiten in Abteilung II - die Beanspruchungen durch ein Stuck des Produktes2 sind in Abteilung I mit 4 und in Abteilung II mit 3 Kapazitatseinheiten gegeben. VonProdukt 1 konnen maximal 1000 Stuck, von Produkt 2 maximal 2000 Stuck abgesetztwerden.

Das Problem kann folgendermaßen als LP formuliert werden:

max 30x1 + 40x2bzgl. 5x1 + 4x2 6 7000 Kapazitatsrestriktion Abteilung I

4x1 + 3x2 6 8000 Kapazitatsrestriktion Abteilung II

x1 6 1000 Absatzhochstmenge Produkt 1

x2 6 2000 Absatzhochstmenge Produkt 2

x1 > 0

x2 > 0


Nehmen wir nun an, die Kapazitat der Abteilung I(II) kann durch Uberstunden ummaximal 1000 (1500) Zeiteinheiten erweitert werden, wobei die zusatzlichen variablenKosten je Uberstunde in der Abteilung I(II) 1(2) GE betragen. Pro Produkt stehen somit4 Produktionsverfahren zur Verfugung, die sich dadurch unterscheiden, ob das Produktin den Abteilungen I und II in den Normalstunden oder in den Uberstunden gefertigtwird. Um das Problem zu formulieren, fuhren wir neue Variable ein, die genau diesberucksichtigen. Die Variable xj wird zu diesem Zweck in vier neue Variable aufgespalten,und wir erhalten (fur j=1,2):

xNNj xNU

j xUNj xUU

j

So bedeutet hier etwa xNU1 , die Anzahl der Stucke von Produkt 1, die in Abteilung 1 in

Normalstunden und in Abteilung 2 durch Uberstunden hergestellt werden.

31


Die Deckungsbeitrage je EH bei den einzelnen Verfahren erhalt man aus dem DB beiFertigung in Normalstunden durch Abzug der durch die Uberstunden verursachten Mehr-kosten, z.B.

DB von PNN1 30

−Mehrkosten in Abteilung I (5 · 1) −5

−Mehrkosten in Abteilung II (4 · 2) −8

=DB von P UU1 = 17

Das Problem kann somit folgendermaßen formuliert werden

max 30xNN1 + 25xUN

1 + 22xNU1 + 17xUU

1 + 40xNN2 +38xUN

2 + 34xNU2 + 32xUU

2

Allerdings sind nun auch neue Nebenbedingungen zu formulieren:

5xNN1 + 5xNU

1 + 2xNN2 + 2xNU

2 6 7000

4xNN1 + 4xUN

1 + 3xNN2 + 3xUN

2 6 8000

5xUN1 + 5xUU

1 + 2xUN2 + 2xUU

2 6 1000

4xNU1 + 4xUU

1 + 3xNU2 + 3xUU

2 + 6 1500

xNN2 + xUN

2 + xNU2 + xUU

2 + 6 2000

xNN1 + xUN

1 + xNU1 + xUU

1 + 6 1000

xabj > 0; j = 1, 2; a, b ∈{

N, U}

Ungleichung 1 stellt dabei eine Kapazitatsschranke fur alle Produktionsmengen dar, diein Abteilung 1 ohne Uberstunden gefertigt werden. Analoges gilt fur die Ungleichung 2in Abteilung 2.

Ungleichung 3 und 4 sind nun die zusatzlich notigen Nebenbedingungen, die aufgrundder Uberstundenproduktion entstehen.

Ungleichung 5 und 6 stellen die Absatzschranken dar.

32

2.2 Modell mit intensitatsmaßiger Anpassung

2.2 Modell mit intensitatsmaßiger Anpassung

Besteht zur Uberwindung moglicher Engpasse die Moglichkeit einer intensitatsmaßigenAnpassung der Aggregate, so sind die uber der optimalen Intensitat liegenden Inten-sitaten in so genannte Intensitatsstufen einzuteilen und jeder moglichen Kombination vonIntensitatsstufen der verschiedenen Abteilungen eigene Variable zuzuordnen. Es sind 2Intensitatsstufen gegeben. Konnen beispielsweise die Intensitaten der Abteilungen I undII um jeweils 25 % erhoht werden, so stehen fur jedes Produkt 4 Produktionsverfah-ren zur Verfugung. Die

”alten“Variablen sind somit in je vier neue aufzuspalten. Wir

erhalten fur das Produkt j (j = 1, 2):

Produkt j Abteilung I Abteilung II

x11j Int.-stufe 1 Int.-stufe 1




Die Produktionskoeffizienten der Produkte in den Abteilungen bei erhohten Intensitatenerhalt man durch Division der Koeffizienten bei optimaler Intensitat durch (1 + Inten-sitatserhohungsprozentsatz). Beispielsweise benotigt Produkt 1 in Abteilung I bei Inten-sitatsstufe 5

1+0,25= 5

1,25= 4 ZE je EH. Wir erhalten somit eine neue Matrix fur Stufe

2:

4 85

165

125

Da durch die erhohten Intensitaten auch die variablen Stundensatze der Abteilungensteigen, mussen fur alle Verfahren die geanderten Deckungsbeitrage errechnet werden.Betragen die variablen Kosten je ZE in Abteilung I(II) anstelle von 10(15) GE beierhohter Intensitat 15(20)GE, so errechnet man

DB von P 111 30

− Mehrkosten in Abteilung I (4 · 15− 5 · 10) −10

− Mehrkosten in Abteilung II (3, 2 · 20− 4 · 15) −4

= DB von P 221 =16

33

2.3 Mehrperiodiges Modell

Das LP lautet daher:

max 30x111 + 20x211 + 26x121 + 16x221 + 40x112 + 36x212 + 37x122 + 33x222

unter den Nebenbedingungen:

5x111 + 5x121 + 4x211 + 4x221 + 2x112 + 2x122 + 1, 6x212 + 1, 6x222 6 7000

4x111 + 4x211 + 165x121 + 416

5x221 + 3x112 + 3x212 + 12

5x212 + 12

5x222 6 8000

x111 + x211 + x121 + x221 6 1000

x112 + x212 + x122 + x222 6 2000

xabj > 0; a, b, j ∈ {1, 2}

2.3 Mehrperiodiges Modell

Soll sich die Planung des Produktionsprogramms nicht wie bisher uber eine einzige, son-dern uber mehrere Perioden mit unterschiedlichen Kapazitats- und Absatzrestriktionenerstrecken, so empfiehlt sich folgende Definition der Modellvariablen:xabj . . . Anzahl der Stucke von Produkt j, die in Periode a erzeugt und in Periode bverkauft werden

1 2 3 4

Kapazitat Abt.I 7000 6000 7000 6000

Abt.II 8000 8000 9000 9000

Absatzmenge Produkt1 1000 800 800 800

Produkt2 2000 2000 2200 2300

Nettoerlos Produkt1 87 97 97 97

Produkt2 67 67 77 87

die direkten Kosten pro EH (ohne Lagerkosten) betragen fur Produkt1(2) 57(27) GE.Pro Periode sind Lagerkosten in der Hohe von 6(8) GE fur Produkt 1(2) je EH zuverrechnen. Somit ergibt sich folgendes LP:

34

2.4 Modell mit Teilefertigung

max 30x111 + 34x121 + 28x131 + 22x141 + 40x221 + 34x231 + 28x241 + 40x331 + 34x341 + 40x441 +

+40x112 + 32x122 + 34x132 + 36x142 + 40x222 + 42x232 + 44x242 + 50x332 + 52x342 + 60x442

bezuglich der Nebenbedingungen:

5x111 + 5x121 + 5x131 + 5x141 + 2x112 + 2x122 + 2x132 + 2x142 6 7000

5x221 + 5x231 + 5x241 + 2x222 + 2x232 + 2x242 6 6000

5x331 + 5x341 + 2x332 + 2x342 6 7000

5x441 + 2x442 6 6000

4x111 + 4x121 + 4x131 + 4x141 + 3x112 + 3x122 + 3x132 + 3x142 6 8000

4x221 + 4x231 + 4x241 + 3x222 + 3x232 + 3x242 6 8000

4x331 + 4x341 + 3x332 + 3x342 6 9000

4x441 + 3x442 6 9000

x111 6 1000

x121 + x221 6 800

x131 + x231 + x331 6 800

x141 + x241 + x341 + x441 6 800

x112 6 2000

x122 + x222 6 2000

x132 + x232 + x332 6 2200

x142 + x242 + x342 + x442 2300

xabj > 0

j = 1, 2

a = 1, . . . , 4

b = 1, . . . , 4


Bestehen die gefertigten Endprodukte aus eigengefertigten Einzelteilen und Baugruppen,so ist bei unserem Grundmodell unterstellt, dass die angegebenen Produktionskoeffizi-enten nicht nur den direkten Zeitbedarf fur die Fertigstellung der Endprodukte, sondernauch die benotigten Zeiten zur Herstellung der in den Endprodukten enthaltenen Teilenbeinhalten.

Die Abbildung 11 stellt die fur die Endprodukte P1 und P2 benotigen EH von derBaugruppe B und den Einzelteilen E1 und E2 sowie die fur die Baugruppe benotigtenEH an Einzelteilen dar (Gozinto-Graph). Daraus ableitbar oder direkt ablesbar, ist die

35


Direktbedarfsmatrix, sowie die Verflechtungsmatrix (= Produktspalten einer Gesamtbe-darfsmatrix).

E1

1

2

1

1

3

P1

B

P2

E2

Abbildung 11: Produktionsverflechtung

Direktbedarfsmatrix

0 0 1 1 0

0 0 3 0 0

0 0 0 2 1

0 0 0 0 0

0 0 0 0 0

Verflechtungsmatrix

P1P2

1 0

0 1

2 1

3 1

6 3

P1

P2

B

E1

E2

Der direkte Zeitbedarf in den beiden Abteilungen zur Bearbeitung der Einzelteile derBaugruppe und der Endprodukte sei

36


P1 P2 B E1 E2

Abteilung I 3/2 1/2 1/2 1/2 1/6

Abteilung II 1/3 4/3 4/3 1/3 0

Die Materialkosten der Einzelteile E1(E2)betragen 3(1)GE, die variablen Kosten je Stun-de in der Abteilung I(II) sind 6(3) GE.

Zunachst wird fur die obigen Angaben das Grundmodell hergeleitet. Die aggregiertenProduktionskoeffienten fur die Zeitrestriktionen erhalt man aus Multiplikation der Ma-trix der direkten Koeffizienten mit der Verflechtungsmatrix

(

3/2 1/2 1/2 1/2 1/6

1/3 4/3 4/3 1/3 0

)

1 0

0 1

2 1

3 1

6 3

=

(

5 2

4 3

)

Die Kalkulation der Deckungsbeitrage erfolgt durch:

Gut1 Gut2

Materialkosten E1 3 · 3 = 9 1 · 3 = 3

Materialkosten E2 6 · 1 = 6 3 · 1 = 3

Variable Kosten in Abteilung I 5 · 6 = 30 2 · 6 = 12

Variable Kosten in Abteilung II 4 · 3 = 12 3 · 3 = 9

Variable Kosten je EH 57 27

Nettoerlos je EH 87 67

Deckungsbeitrag je EH 30 40

Unter Berucksichtigung der Absatzhochstmengen erhalt man daher folgendes Grundmo-dell:

max x0 = 30x1 + 40x2

Unter den Nebenbedingungen

5x1 + 2x2 6 7000

4x1 + 3x2 6 8000

x1 6 1000

x2 6 2000

xj > 0 j = 1, 2

37


Eine alternative Modellformulierung, die zwar weniger Vorarbeiten verursacht, dafurjedoch auch Variablen fur die Mengen an Einzelteilen und die Mengen der Baugruppebeinhaltet,hat folgendes Aussehen. Wir fuhren gemaß Abbildung 12 neue Variable ein:x1; x2; x3; x4; x5

Die Beziehungen zwischen den Einzelteilen, der Baugruppen und den Endproduktenerhalt man dann aus der folgenden Graphik:

E1x4

x3

x2x1

x5

1

2

1

1

3

P1

B

P2

E2

Abbildung 12: Produktionsverflechtung 2

x3 = 2x1 + x2x4 = x1 + x3x5 = 3x3

Die Koeffizienten der Zielfunktion sind in der folgenden Tabelle dargestellt.

P1 P2 B E1 E2

Materialkosten E1 0 0 0 3 0

Materialkosten E2 0 0 0 0 1

Variable Kosten in Abteilung I 9 3 3 3 1

Variable Kosten in Abteilung II 1 4 4 1 0

Nettoerlos 57 87 0 0 0

DB 77 60 -7 -7 -2

38

2.5 Kuppelproduktion

Das LP lautet daher:

max 77x1 + 60x2 − 7x3 − 7x4 − 2x5

Unter den Nebenbedingungen:

3/2x1 + 1/2x2 + 1/2x3 + 1/2x4 + 1/6x5 6 7000

1/3x1 + 4/3x2 + 4/3x3 + 1/3x4 6 8000

x1 6 1000

x2 6 2000

2x1 + x2 − x3 = 0

x1 + x3 − x4 = 0

3x3 − x5 = 0

xj > 0 fur j = 1, . . . , 5


Kuppelproduktion liegt vor, wenn bei Produktion eines Gutes automatisch ein zwei-tes Gut anfallt, oder mehrere Guter anfallen, die entweder marktfahig sind oder alsZwischenprodukte in anderen Prozessen Verwendung finden. Ein Beispiel dafur ist dieRaffination von Erdol, wo bei der fraktionierten Destillation gleichzeitig zwei bzw. dannmehrere Produkte anfallen(etwa Kerosin, Benzin, Leichtole,etc).

Die Probleme der Kuppelproduktion fur die Produktionsplanung bestehen erstens dar-in, dass keine variablen Kosten den einzelnen Produkten eindeutig zugerechnet werdenkonnen und daher auch keine Deckungsbeitrage ermittelbar sind und zweitens, dass diekomplexen Abhangigkeiten zwischen den Gutermengen abgebildet werden mussen.

Zur Demonstration sei von folgendem Beispiel ausgegangen:

Ein Unternehmen der Kuppelproduktion stellt die Endprodukte A, B und C her, die zuPreisen von 2200(A), 2000(B) und 1800(C) GE je t absetzbar sind. Hochstmenge: 60000tvon A, 40000t von B, und beliebig viel von C. Kapazitatsgrenzen der Endstufe: 90000tvon A, 50000t von B und 90000t von C (jedes Produkt wird in der Endstufe auf eigenenAnlagen hergestellt).

Fur die Produktion von 1t des Produktes A vermengt man 300 kg vom ZwischenproduktP und 700 kg von Q. Fur 1t des Produktes B mischt man 400 kg von Q und 600 kgvon S. das Produkt C erhalt man, wenn man dem Zwischenprodukt S den Rohstoff Vbeimengt, wobei in 1t des Produktes C nicht mehr als 300 kg von V enthalten sein darf.

Das Zwischenprodukt S entsteht in einem Veredelungsprozeß des Rohstoffes V, wobei 900kg S aus 1t V gewonnen werden konnen. Die Zwischenprodukte P und Q (Fraktionen)

39


entstehen bei Trennung (Destillation)des Rohstoffes U, so dass bei der Verarbeitung von2t von U jeweils 1t von P und 1t von Q gewonnen werden. Es konnen aber nur maximal70000t von U verarbeiten werden.

U V S P Q A B C

Rohstoffkosten bzw. Fertigungs-

der Zwischenprodukte und

Endprodukte 400 500 200 500 800 400 300 300

Zunachst wird der besseren Ubersicht halber ein Verflechtungsgraph ermittelt:

A C

2 2

0,3 0,7 > 0,70,4 0,6

£ 0,3

U V

B

P Q S

10

9

Abbildung 13: Kuppelproduktion

Fur Verflechtungen mit konstanten Relationen konnen folgende Restriktionen formuliertwerden:

2xP − xU 6 0

2xQ − xU 6 0

0, 3xA − xP 6 0

0, 7xA + 0, 4xB − xQ 6 0

Da nur der Anteil von S in B konstant ist, jener in C aber flexibel, kann nicht mit einerVariablen fur S,xS , gearbeitet werden. Wir haben daher fur die jeweiligen Endproduktezwei Variablen xSB und xSC zu definieren.

0, 6xB − xSB 6 0

0, 7xC − xSC 6 0

40


Die Aufspaltung von Variablen ist auch fur den Rohstoff V wegen der variablen Einsatz-verhaltnisse fur C zweckmaßig.

xS − xSB − xSC = 0

xS − 0, 9xV S 6 0

0, 3xC − xV C > 0

xC − xSC − xV C = 0

− xV S − xV C + xV = 0

Schlussendlich sind als Restriktionen noch die Hochstmengenvorschriften zu beachten.

xA 6 60000

xB 6 40000

xC 6 90000

xU 6 70000

Die Zielfunktion erhalt man nicht aus der Summierung von Stuckdeckungsbeitragensondern aus der Differenz von Umsatz und variablen Kosten.

max 1800xA + 1700xB + 1500xC − 500xP − 800xQ− 400xU − 200xSB − 200xSC − 500xV

Unter den Nebenbedingungen

0, 7xA + 0, 4xB − xQ 6 0

0, 3xA − xP 6 0

2xP − xU 6 0

2xQ − xU 6 0

0, 6xB − xSB 6 0

0, 7xC − xSC 6 0

xC + 109xSB + 1

9xSC − xV 6 0

xA 6 60000

xB 6 40000

xC 6 90000

xU 6 70000

wobei die Restriktionen zusammengefasst wurden.

41

2.6 Personalplanung

2.6 Personalplanung

Im folgenden Beispiel soll der Frage nachgegangen werden, wie ein Konzern seine Pro-duktion einer fluktuierenden Nachfrage anpassen soll, wenn ihm dabei folgende Akti-onsmoglichkeiten zur Verfugung stehen:

1. einstellen oder entlassen von Mitarbeitern (”hiring and firing“)

2. temporare Engpasse durch Sonderschichten (Uberstunden) ausgleichen

3. auf Lager produzieren, um zukunftige Engpasse abzudecken

zusatzlich sind noch folgende Anforderungen zu berucksichtigen:

• Zur Herstellung eines Produktes sind 20 EH pro Arbeiter notig

• Die Anzahl der Mitarbeiter kann pro Monat hochstens um 40 erhoht oder erniedrigtwerden, wobei

– Einstellungskosten in Hohe von 300 pro Mitarbeiter

– Entlassungskosten in Hohe von 420 pro Mitarbeiter

zu berucksichtigen sind

• die Anzahl der Uberstunden betragt hochstens 30 % der normalen Arbeitszeit.Uberstundenkosten kosten 20 GE zusatzlich pro Stunde im Vergleich zur normalenProduktion

• die Lagerkosten pro Einheit und Monat betragen 8 GE

• das Lager ist von Anfang bis zum Ende Leer

• die Anfangsanzahl an Arbeitern betragt 290

• die Hochstuberstundenproduktion betragt 6 EH

Wir verwenden folgende Variable bzw. Parameter

dj · · · Nachfrage in j-ten Monat 1 6 j 6 12

xj · · · Umfang der normalen Produktion im j-ten Monat

yj · · · Umfang der Uberstundenproduktion im j-ten Monat

zj · · · Lagerbestand im j-ten Monat ; Z0 = 0

wj =xj

20· · · Anzahl der Beschaftigten ; w0 = 290 da Ausstoß x0 = 290 · 20 = 5800

42

2.6 Personalplanung

Wir erhalten somit folgende Bedingungen:

∣

∣

xj

20−

xj−1

20

∣

∣ 6 40 ⇔

|xj − xj−1| 6 800 ⇔

−800 6 xj − xj−1 6 800 ⇔

xj − xj−1 6 800

xj − xj−1 ≥ −800

yi 6 0, 3xj

tj = 300 ·xj−xj−1

20= 15 · (xj − xj−1)

tj = 420 ·xj−1−xj

20= 21 · (xj−1 − xj)

zj = Zj−1 + xj + yj − dj (Erhaltungsgesetz)

tj > 15(xj − xj−1)

tj > 21(xj−1 − xj)

Annahme:

xj − xj−1 ist positiv, dann wird die 2. Ungleichung nicht berucksichtigt, da (xj−1 − xj)negativ und tj nicht negativ ist.

Die erste Ungleichung wird vom Programm minimiert also tj = 15 (xj − xj−1) liefern.

Somit lautet die Zielfunktion:

Min12∑

j=1

(20yj + 8zj + tj)

43

2.7 Finanzierungs- und Investitionsprogramm


Betrachten wir folgendes Investitions- und Finanzierungsbeispiel:

Welche Investitions- und Finanzierungsentscheidungen sind zu treffen, wenn am Endeeines Zeitraums von 4 Perioden ein maximales Endkapital angestrebt wird, zu Beginn des1. Jahres liquide Mittel in Hohe von 20 vorhanden sind und die folgenden Investitions-und Finanzierungsmoglichkeiten gegeben sind?

1. Es stehen vier Realinvestitionen (n) zur Verfugung

t 1 2 3 4

1 -90 -20

2 10 -50 30

3 50 25 -50

4 70 40 60

Projekt 1, 2, 3 kann dabei nur einmal durchgefuhrt werden, Projekt 4 zweimal.

2. Es besteht die Moglichkeit einer einjahrige Anlage (g):

Periode 1: 4% Rendite



Die Projekte konnen finanziert werden durch

1. einen einjahrigen Kredit (f) zu 12% p.a beschrankt auf 100 GE

2. Ausgabe einer Anleihe (m) zu 40 GE in Periode 1, 3 Jahre in Laufzeit 10% Ver-zinsung (Am Ende der Laufzeit)

Fassen wir nun die genannten Moglichkeiten ubersichtlich zusammen:

n1 n2 n3 n4 m1 f1 f2 f3 g1 g2 g3

t=1 −90 0 −20 0 40 1 - - −1 - - 20

t=2 10 −50 30 0 −4 −1, 12 1 - 1,04 −1 - -

t=3 50 25 0 −50 −4 - −1, 12 1 - 1, 05 −1 -

t=4 70 40 0 60 −44 - - −1, 12 - - 1, 06 -

44


Weiters sind folgende Einschrankungen zu beachten:

n16 1 m1 6 1

n26 1 f16 100

n36 1 f26 100

n46 2 f36 100

Wobei hier

f1· · · Hohe des Kreditsg1· · · Hohe der Anlage

Da alles, was ausgegeben wird, finanziert werden muss:

−90n1 − 20n3 + 40m1 + f1 − g1 > −20

10n1 − 50n2 + 30n3 − 4m1 − 1, 12f1 + f2 + 1, 04g1 − g2 > 0

50n1 + 25n2 − 50n4 − 4m1 − 1, 12f2 + f3 + 1, 05g2 − g3 > 0

Die Zielfunktion erhalt man aus der letzten Zeile der Tabelle. Sie zeigt die Geldmenge,die in der letzten Periode vorhanden ist und gerade diese soll ja maximiert werden!

max 70n1 + 40n2 + 60n4 − 44m1 − 1, 12f3 + 1, 06g3

Durch Einfuhrung von Schlupfvariablen lasst sich nun das Problem in kanonische Formtransformieren:

−90n1 − 20n3 + 40m1 + f1 − g1 + y1 = −20

10n1 − 50n2 + 30n3 − 4m1 − 1, 12f1 + f2 + 1, 04g1 − g2 + y2 = 0

50n1 + 25n2 − 50n4 − 4m1 − 1, 12f2 + f3 + 1, 05g2 − g3 + y3 = 0

n1 + y4 = 1

n2 + y5 = 1

n3 + y6 = 1

n4 + y7 = 2

m1 + y8 = 1

f1 + y9 = 100

f2 + y10 = 100

f3 + y11 = 100

45


Wir erhalten folgendes Endtableau:

BV y1 y2 y6 y3 y8 y5 y4 y7 g1 g2 g3 RS

n1 1 1

f1 −1 20 −40 90 −1 50

n4 1 1

f2 −1, 12 −1 −7, 6 −40, 8 50 90,8 −0, 08 −1 70

n2 1 1

n3 1 1

f3 −1, 25 −1, 12 −8, 51 −1 −41, 70 31 51,70 50 −0, 09 −0, 07 -1 57,4

m1 1 1

y9 1 −20 40 −90 1 50

y10 1,12 1 7,6 40,8 −50 −90, 8 0, 08 1 30

y11 1,25 1,12 8,51 1 41,70 −31 −51, 70 −50 0,09 0,07 1 42,6

y12 −1 1

Z −1, 41 −1, 25 −9, 53 −1, 12 −2, 70 −5, 28 −12, 10 −4 −0, 10 −0, 08 −0, 06 −61, 71

Die Losungen des Problems lassen sich nun ablesen:

n1 = 1 bedeutet, dass Projekt 1 einmal durchgefuhrt werden sollte. Analoges gilt fur dieProjekte 2, 3 und 4.m1 = 1 heißt die Anleihe ist zu begeben.f1 = 50 . . . in der ersten Periode ist ein Kredit in Hohe von 50 aufzunehmenf2 = 70 . . . in der zweiten Periode ist ein Kredit in Hohe von 70 aufzunehmenf1 = 57, 4 . . . in der dritten Periode ist ein Kredit in Hohe von 57,4 aufzunehmen

g1, g2 und g3 sind NBV und besitzen daher den Wert Null; das heißt es ist keine Anlagezu tatigen

Die Zielfunktion besitzt den Wert 61,71, man erhalt also diesen Betrag am Ende derletzten Periode, wenn man die entsprechenden Entscheidungen durchfuhrt.

Versuchen wir nun im Folgenden Veranderungen einer Basisvariablen (z.B. f1) und einerNichtbasisvariablen (z.B. g1) zu untersuchen.

Angenommen der Kredit in Periode 1 wird um 1 GE erhoht (d.h.f1 = 51)

Die Schlupfvariable von Kredit 1 (y9) erhalt dann den Wert 49, was sich unmittelbar ausder Nebenbedingung f1 + y9 = 100 ergibt. Mit anderen Worten: der nicht ausgeschopfteKredit verringert sich auf 49 GE.

Welche Folgen hatte nun eine Anderung von g1? Wir interpretieren also die Werte derSpalte g1.

46


Wird 1EH in Anlage 1 zu 4% angelegt, wird g1 = 1. Dies fuhrt zu einer Verringerung desZielfunktionswertes in Hohe von 0,10 GE, was am Koeffizienten der Zielfunktionszeileabgelesen werden kann.

Der Koeffizient von f1 ist −1; das heißt, die Anlage in g1 muss durch einen Kredit inPeriode 1 finanziert werden.Korrespondierend dazu sieht man, dass der Koeffizient von y9 gleich 1 ist, also das nichtausgeschopfte Kreditvolumen in Periode 1 sich um 1 EH verringert.

Wird nun 1 EH wird zu 4% angelegt (g1 = 1), so erwirtschaftet man am Ende der Peri-ode 1 einen Gewinn in Hohe von 1,04, mußte die Einheit aber mit einem Kredit zu 12%finanzieren (Koeffizient von f1 ist −1), was zu Kosten in Hohe von 1,12 fuhrt und somitinsgesamt einen Verlust von 8% oder 0,08 EH ergibt.Dieser Betrag muss durch einen Kredit in Periode 2 finanziert werden, der Koeffizientvon f2 betragt −0, 08

Der Kredit in Hohe von 0,08 muss nun in Periode 3 durch einen neuen Kredit in derHohe von 0, 08 · 1, 12 = 0, 0896 finanziert werden, daher ist der Koeffizient von f3 gleich−0, 0896.

47

Literatur

Literatur

[1] Stepan, A. und Fischer E. (2001): Betriebswirtschaftliche Optimierung. Einfuhrung

in die quantitative Betriebswirtschaftslehre. 7.Aufl., Oldenbourg Verlag, Munchen,

Wien

[2] Domschke, W. und Drexl A. (2005): Einfuhrung in Operations Research. 6.Aufl.,

Springer, Berlin u.a

[3] Hulsmann et al, (1998): Einfuhrung in die Wirtschaftsmathmatik., Springer, Berlin

u.a

[4] Jensen, P. und Bard J. (2003): Operations Research.Models and Methods., John

Wiley & Sons, New York

[5] Ewert, R. und Wagenhofer A. (2005): Interne Unternehmensrechnung. 6.Aufl.,Springer, Berlin u.a

48

Documents

Modelle des Operations Research - Universität Graz · der 1980er Jahre begannen Narendra Karmarkar und andere mit der Entwicklung von Innere-Punkte-Verfahren zur L¨osung linearer