Download pdf - 4Einführung in die Optimierung 4.1 Grundlagen der … · Programme an (Kapitel 4.1) Als stochastisches Problem widmen wir uns danach dem NewsvendorProblem ... Stufe 1: 2 Stunden

1

Business Computing and Operations Research 356

4 Einführung in die Optimierung

� Optimierungsproblem begegnen uns in verschiedenster Form

� So sind häufig Entscheidungen zu fällen (definiert als die Wahl von Entscheidungsvariablen), die direkte Wirkung auf unsere Ziele haben

� Allerdings gibt es meist Restriktionen, die die freie Wahl von unterschiedlichen Entscheidungsvariablen einschränken

� Im Folgenden wollen wir bestimmte Optimierungsprobleme betrachten und optimal lösen

� Als deterministische Probleme schauen wir uns dazu Lineare Programme an (Kapitel 4.1)

� Als stochastisches Problem widmen wir uns danach dem Newsvendor Problem (Kapitel 4.2)


4.1 Grundlagen der linearen Programmierung

� Häufig lassen sich praktische Optimierungsprobleme als lineare Programme abbilden

� Diese Probleme besitzen folgende Eigenschaften

� Es sind Werte für kontinuierliche Entscheidungsvariablen (oder kurz Variablen) zu finden (definiert als reelle Zahlen)

� Es sind vorher gegebene lineare Restriktionen durch die Variablenwerte einzuhalten (Zulässigkeit einer Lösung)

� Es ist eine gegebene lineare Zielfunktion, die jede Lösung bewertet, zu minimieren oder zu maximieren (Qualität einer Lösung)

� Es ist eine optimale Lösung zu finden

� D.h. es existiert keine andere zulässige Lösung im Lösungsraum, die hinsichtlich der Zielfunktion besser ist

� Bei Maximierung (Minimierung) ist also eine zulässige Lösung mit maximalem (minimalem) Zielfunktionswert zu finden


Lineare Programme – Haupteigenschaften

� Kontinuierliche Variablen

� Lineare Restriktionen, die durch die Variablenwerte einzuhalten sind

� Lineare Zielfunktion zur Bewertung einer jeden zulässigen Lösung

� Ziel ist die Ermittlung einer optimalen Lösung

Lösung Vektor von Entscheidungsvariablen

Zulässige Lösung Lösung, die alle Restriktionen erfüllt

Optimale Lösung Zulässige Lösung mit minimalem oder maximalem Zielfunktionswert


Man kann auch rechnen lassen…

� Excel Solver

� Wird aktiviert unter: Extras⇢Add-Ins (2003 Version), File⇢Options⇢Add-Ins (2010 Version)

� Danach nutzt man den Solver unter: Extras⇢Solver (2003 Version), Data⇢Solver (2010 Version)

� Der Solver ist nicht wirklich leistungsfähig aber ganz nett zum ersten Ausprobieren

� Es gibt auch freie Solver im WWW. Zum Beispiel unter:

http://www.zweigmedia.com/RealWorld/simplex.html

2


4.1.1 Zwei typische Anwendungsbeispiele

� Im Folgenden betrachten wir zwei sehr einfache Beispiele für lineare Programme

� Die Produktionsprogrammplanung

� Das Ernährungsproblem (Diet Problem)


Anwendung 1 – Produktionsprogrammplanung

� Das Produktionsmanagement eines Produzenten von Orangensaft soll das operative Produktionsprogramm für den nächsten Planungshorizont (PH) festlegen

� Dabei soll der Gesamtdeckungsbeitrag maximiert werden

� Es gibt zwei Arten von angebotenen Orangensäften, die im Werk erst gepresst und dann nach spezieller Rezeptur gemischt werden

� Aus Gründen der Einfachheit bezeichnen wir die beiden Sorten einfach als A und B

� Beide Sorten durchlaufen in gleicher Reihenfolge einen dreistufigen

Produktionsprozess

� Sie nutzen also die gleichen Anlagen

� Somit gibt es für beide Sorten die Reihenfolge 1 – 2 – 3 für die zu

durchlaufenden Produktionsstufen

� Dieser Ablauf ist der folgenden Abbildung zu entnehmen


Produktionsprogrammplanung - Illustration

Stufe 1

Stufe 2

Stufe 3

A

B

10 €

Maximaler

Absatz

50 l / PH

8 €

Maximaler

Absatz

40 l / PH

Kapazität240 h / PH




Zahlen und Fakten zusammengefasst

� Beide Sorten durchlaufen alle Stufen

� Die Kapazitäten auf den Stufen 1 und 3 umfassen jeweils 240 h

� Die Kapazität auf Stufe 2 umfasst 100 h

� Produkt A

� Absatzpreis pro Liter: 10€

� Variable Kosten pro Liter: 5€

� Damit erhalten wir einen Deckungsbeitrag pro Liter von 5 €

� Maximaler Absatz pro PH: 50 Liter

� Produktionskoeffizienten für einen Liter von Produkt A

� Stufe 1: 2 Stunden

� Stufe 2: 1 Stunde


3


… und für Produkt B

� Produkt B

� Absatzpreis pro Liter: 8€

� Variable Kosten pro Liter: 2€

� Damit erhalten wir einen Deckungsbeitrag pro Liter von 6€

� Maximaler Absatz pro PH: 40 Liter

� Produktionskoeffizienten für einen Liter von Produkt B





Bestimmung des optimalen Produktionsprogramms

� Wir wollen den Gesamtdeckungsbeitrag maximieren

� Beide Produkte lohnen sich, da sie positive Deckungsbeiträge aufweisen

� Jeder produzierte und verkaufte Liter von A bringt 5€

� Jeder produzierte und verkaufte Liter von B bringt 6€

� Also, überprüfen wir zunächst, ob wir sie gleichzeitig in ihrem maximalen Absatzmengen fertigen können

� Die maximalen Absatzmengen stellen dabei die ersten Restriktionen bereit, da wir darüber hinaus die Produkte im PH nicht mehr absetzen können (Lagerhaltung wird hier nicht berücksichtigt)


Maximale Kapazitätsnachfrage

Ermittelte Kapazitätsnachfrage auf den Stufen

� Stufe 1: 50.2+40.4=260>240

Da der Bedarf höher ist als die verfügbare Kapazität ergibt sich ein Engpass auf Stufe 1!

� Stufe 2: 50.1+40.2=130>100


� Stufe 3: 50.4+40.2=280>240



Konsequenz

� Wir können leider nicht die Produkte in ihren maximalen Absatzmengen herstellen

� Grund sind die Kapazitätsengpässe auf den Fertigungsstufen

� Ein Engpass wäre für diese Erkenntnis bereits hinreichend gewesen

� Weist eine Stufe bei dieser Prüfung keinen Engpass auf ist ihre Kapazität für die weitere Planung irrelevant

� Dies wäre eine triviale optimale Lösung gewesen

� Wir müssen also neu überlegen, um eine optimale Lösung zu finden

4


Was ist zu tun?

?

Pah! Ist doch billig! Da B mehr Deckungsbeitrag pro Liter als A bringt (6€statt nur 5€), produzieren

wir am Besten alles von B und nutzen dann die

Restkapazität für A

Pah! Ist doch billig! Da B mehr Deckungsbeitrag pro Liter als A bringt (6€statt nur 5€), produzieren

wir am Besten alles von B und nutzen dann die

Restkapazität für A


Wir probieren diesen Vorschlag aus und erhalten

� B benötigt

� auf Stufe 1 4h. Maximal kann produziert werden: min{40, 240/4} = 40



B wird somit in der Absatzhöchstmenge produziert

� Nun kommt das Produkt A. Es benötigt

� auf Stufe 1 2h. Maximal kann also noch produziert werden:

min{50, (240-160)/2} = 40

� on Stufe 2 1h. Maximal kann produziert werden: min{50, 20/1} = 20

� on Stufe 3 4h. Maximal kann produziert werden: min{50, 80/4} = 20

Somit können noch zusätzlich 20 Liter von A produziert und verkauft

werden


Damit erzielen wir

einen Gesamtdeckungsbeitrag von:

20.5€ + 40.6€ = 240€ + 100€ = 340€

� Ist das nun ein optimales Ergebnis?

� Anders gefragt: Geht es besser?

� Am Besten ist es, das Problem mal mathematisch anzugehen. Dazu müssen wir es aber erstmal mathematisch definieren.


Lineares Programm

Entscheidungsvariablen: : Produzierte Liter von Orangensaft A

: Produzierte Liter von Orangensaft B

Zielfunktion: Maximize 5 6 Maximaler

Gesamtdeckungsbeitrag

Restriktionen: subject to (s.t.)

50 A

= ⋅ + ⋅

≤

A

B

A B

A

x

x

z x x

x bsatzrestriktionen

40

2 4 240 Produktionskapazitäten

1 2 100

4 2 240

, 0 Nicht-Negativität der Variablen

≤

⋅ + ⋅ ≤

⋅ + ⋅ ≤

⋅ + ⋅ ≤

≥

B

A B

A B

A B

A B

x

x x

x x

x x

x x

5


Graphische Lösungsbestimmung

xA

10050 7525

25

50

75

100Restriktion 1

xB

Restriktion 3

Z=500Restriktion 2

Optimale Lösung


Analytische Bestimmung der optimalen Lösung

� Graphisch können wir feststellen, dass die optimale Lösung der Schnittpunkt der Restriktionen 2 und 3 ist

� Also muss dieser Punkt beide Restriktionen gleichzeitig erfüllen

� Wir müssen also das folgende Gleichungssystem lösen

( )

6,26

6,46

3/80

3/140

3/80

3/1603/300

3/80

2100

1203200

2100

1204200

2100

12021002

2100

1202

2100

24024

10021

=

=⇔

=

=⇔

=

−=⇔

=

⋅−=⇔

=⋅−

⋅−=⇔

=+⋅−

⋅−=⇔

=+⋅−⋅

⋅−=⇔

=+⋅

⋅−=⇔

=⋅+⋅

=⋅+⋅

B

A

B

A

B

A

B

BA

B

BA

BB

BA

BB

BA

BA

BA

BA

BA

x

x

x

x

x

x

x

xx

x

xx

xx

xx

xx

xx

xx

xx

xx

xx


Es ergibt sich somit

ein optimaler (also maximaler) Gesamtdeckungsbeitrag von

26.6.6€ + 46.6.5€ = 233.3€ + 159.9€ = 393.3€


Die Einsicht

OK ! Ich gebe zu, dass das wohl nicht so einfach war. Was machen wir aber bei mehr als zwei Variablen?

OK ! Ich gebe zu, dass das wohl nicht so einfach war. Was machen wir aber bei mehr als zwei Variablen?

Dann müssen wir ein lineares Programm definieren und den

SIMPLEX ALGORITHMUS

anwenden!

Dann müssen wir ein lineares Programm definieren und den

SIMPLEX ALGORITHMUS

anwenden!

6


Allgemeines LP zur Produktionsprogrammplanung

[ ]

[ ],

Gegeben

: Deckungsbeitrag pro Einheit von Produkt 1,..., GE/PE

: Produktionskoeffizient von Produkt 1,..., auf Maschine

1,..., KE/PE

: Maximale Kapazität der Maschine

j

i j

i

p j n

c j n

i m

C i

=

=

=

= [ ]

[ ]

[ ]

1

1,..., KE

: Absatzhöchstmenge von Produkt 1,..., im betrachteten Planungszeitraum PE

Gesucht

: Produktionsmenge von Produkt 1,..., im Planungszeitraum PE

Maximiere unter Einhaltung de

j

j

n

j j

j

m

X j n

x j n

p x=

=

=

⋅∑

{ }

{ }

( )

,

1

r Nebenbedingungen (u.E.d.N) (s.t.)

1,..., :

1,..., : 0

Einheiten: "KE=Kapazitätseinheiten", "PE=Produkteinheiten", "GE=Geldeinheiten"

n

i j j i

j

j j

i m c x C

j n x X

=

∀ ∈ ⋅ ≤

∀ ∈ ≤ ≤

∑


Einsatz von Excel für das Beispiel

� Wir können das Problem auch in Excel lösen

� Dies wollen wir einmal exemplarisch durchführen

Microsoft

Excel-Arbeitsblatt


Anwendung 2 – Das Ernährungsproblem

� Andrea wundert sich, wieviel Geld sie für ihre tägliche Nahrung ausgibt

� Zudem möchte sie wissen, ob sie sich ausreichend gesund ernährt

� Daher analysiert sie die Speisen in ihrer Speisekammer und konsultiert Gesundheitsbücher

� Sie betrachtet die folgenden sechs Speisen

Nahrungsmittel Größe pro

Mahlzeit

Energie

(kcal)

Protein (g) Kalzium

(mg)

Preis

(€ Cents)

Haferflocken 28 g 110 4 2 3

Huhn 100 g 205 32 12 24

Ei 2 Einheiten 160 13 54 13

Vollmilch 237 ml 160 8 285 9

Kirschkuchen 170 g 420 4 22 20

Schweinefleisch

mit Bohnen

260 g 260 14 80 19


Weitere wichtige Informationen

� Andrea braucht am Tag mindestens � 2,000 kcal� 55 g Protein� 800 mg Kalzium� Eisen und Vitamine werden in Tablettenform zugeführt

(nicht zur Nachahmung empfohlen!)

� Damit wären also 10 Portionen Schweinefleisch mit Bohnen ausreichend� Die will Andrea aber natürlich nicht essen! � Also muss es weitere Einschränkungen geben

� Wir setzen somit Obergrenzen� Haferflocken: höchstens 4 Mahlzeiten am Tag� Huhn: höchstens 3 Mahlzeiten am Tag� Ei: höchstens 2 Mahlzeiten am Tag� Vollmilch: höchstens 8 Mahlzeiten am Tag� Kirschkuchen: höchstens 2 Mahlzeiten am Tag� Schweinefleisch mit Bohnen: höchstens 2 Mahlzeiten am Tag

7


Das LP des Ernährungsproblems

1 2 3 4 5 6

1 2 3 4 5 6

1 2 3 4 5 6

1 2 3 4 5 6

1 2

, , , , , Mahlzeiten der Speisen pro Tag

Minimiere 3 24 13 9 20 19

u.E.d.N.

0 4 0 3 0 2 0 8 0 2 0 2

110 205 160 160 420 260 2000

4 32 13

⋅ + ⋅ + ⋅ + ⋅ + ⋅ + ⋅

≤ ≤ ∧ ≤ ≤ ∧ ≤ ≤ ∧ ≤ ≤ ∧ ≤ ≤ ∧ ≤ ≤

⋅ + ⋅ + ⋅ + ⋅ + ⋅ + ⋅ ≥

⋅ + ⋅ + ⋅

x x x x x x

x x x x x x

x x x x x x

x x x x x x

x x 3 4 5 6

1 2 3 4 5 6

8 4 14 55

2 12 54 285 22 80 800

+ ⋅ + ⋅ + ⋅ ≥

⋅ + ⋅ + ⋅ + ⋅ + ⋅ + ⋅ ≥

x x x x

x x x x x x


…und im Allgemeinen

( )

( )

( )

,

Gegegeben

: Menge des Inhaltsstoffes in der Speise 1 1 .

: Täglicher Bedarf am Inhaltsstoff 1 .

: Kosten pro Mahlzeit für Speise 1 .

: Maximale Zahl an Mahlzeiten

= =

=

=

i j

i

j

j

a i j i ,...,m, j ,...,n

r i i ,...,m

c j j ,...,n

X ( )

( )

pro Tag von Speise 1 .

Gesucht

: Tägliche Anzahl an Mahlzeiten von Speise 1 .

Damit wird ein täglicher Ernährungsplan durch einen Vektor 0 definiert.

Zielfunktion: Minimiere

=

=

≥ ∈

j

n

j j ,...,n

x j j ,...,n

x , x IR

{ }

{ }

1

,

1

u.E.d.N

1,..., :

1,..., : 0

=

=

⋅

∀ ∈ ⋅ ≥

∀ ∈ ≤ ≤

∑

∑

n

j j

j

n

i j j i

j

j j

c x

i m a x r

j n x X


Konsequenzen

� Beide Anwendungen sind sehr unterschiedlich

� Aber sie resultieren in ähnliche mathematische Formulierungen (Lineare Programme, LP)

� Beide LPs besitzen

� …Vektoren kontinuierlicher Variablen

� …lineare Zielfunktionen

� …lineare Restriktionen

� …eine lineare Zielfunktion zur Minimierung oder Maximierung

� …Restriktionen verlangen die Einhaltung von unteren oder oberen Schranken


Spannende Frage

Vielleicht kann man eine allgemeine Form für alle LP‘s finden?

Und womöglich kann man die dann alle sogar mit einer Methode lösen?

Vielleicht kann man eine allgemeine Form für alle LP‘s finden?

Und womöglich kann man die dann alle sogar mit einer Methode lösen?

Genau das lernen wir jetzt!

Genau das lernen wir jetzt!

8


4.1.2 Definition von Linearen Programmen

� Im Folgenden lernen wir eine allgemeine Form kennen, die festlegt, was ein Lineares Programm ist

� Dies ist ein eindeutiges Schema für alle Linearen Programme

� In der Literatur finden sich insgesamt drei Grundformen von Linearen Programmen, die allgemein ausdrücken, was unter einem LP zu verstehen ist

� LP in allgemeiner Form

� LP in kanonischer Form

� LP in standardisierter Form

� Allerdings kann es vorkommen, dass in Lehrbüchern die Definitionen vertauscht sind, d.h., was hier kanonisch ist kann woanders standardisierte Form sein

� Dies ist aber wegen der Äquivalenz der Formen kein Problem


LP in allgemeiner Form

{ }1

Sei gegeben, mit , 1 , und .

Des weiteren sei eine Menge von Zeilenindizes, die Gleichheitsrestriktionen darstellen.

Zudem sei eine Menge von Zei

T

m n n m

i

T

m

a

A IR A ... a IR i ,...,m b IR

a

M

M

×

′

′∈ = ∧ ∈ ∈ ∈ ′

lenindizes, die Ungleichheitsrestriktionen ausdrücken.

Darüber hinaus sei eine Menge von Spaltenindizes, die zu positiv definierten Variablen

gehören, während die Spaltenindizes sind, die zu unbes

N

N

{ }

{ }

chränkten (=freie) Variablen

gehören. Zu beachten ist, dass und eine Partition der Menge 1 darstellen, d.h.

es gilt 1 und . Zudem bilden und eine Partition der

Menge 1

M M ,...,m

M M ,...,m M M N N

,..

∪ = ∩ = ∅

{ } { }( )

{ }( )

1 und .

Dann ist der zulässige Lösungsraum definiert durch

: 0 : : .

Für verfolgen wir die Maximierung der Funktion .

n T T

j i i i i

n T

.,n N N ,...,n N N

P

P x IR | j N x i M a x b i M a x b

c IR z x c x

∪ = ∩ = ∅

′ ′= ∈ ∀ ∈ ≥ ∧ ∀ ∈ ⋅ = ∧ ∀ ∈ ⋅ ≤

∈ = ⋅


LP in kanonischer Form

{ }

Seien und :

Dann ist die Menge der zulässigen Lösungen wie folgt definiert:

0 and

Lösungen, die zur Menge gehören werden als zulässig bezeichnet.

Zur Bewertung einer Lösung

×∈ ∈

= ∈ ≥ ⋅ ≤

m n m

n

A IR b IR

P x IR | x A x b

P

( )

dient der Vektor und die Zielfunktion

lautet Maximiere .

∈

= ⋅

n

T

x c IR

z x c x

� Deutlich einfacher ist die kanonische Form

� Allerdings sind hier alle Gleichheitsrestriktionen und negative Variablen ausgeschlossen


LP in standardisierter Form

{ }

Seien und gegeben:

Dann definiert sich die Menge der zulässigen Lösungen als:

0 and

Lösungen aus der Menge werden als zulässig bezeichnet.

Zur Bewertung einer Lösung x die

×∈ ∈

= ∈ ≥ ⋅ =

m n m

n

A IR b IR

P x IR | x A x b

P

( )

nt ein Vektor , wobei die Zielfunktion

lautet: .

Die standardisierte Form verfolgt entweder die Minimierung oder die Maximierung

der Funktion unter Berücksichtigung von 0 und .

∈

= ⋅

≥ ⋅ =

n

T

c IR

z x c x

z x A x b

� Ähnlich einfach ist ein LP in standardisierter Form

� Hier sind alle Ungleichheitsrestriktionen und negative Variablen ausgeschlossen

9


Zu unseren beiden Beispielen

� Offensichtlich sind das Ernährungsproblem (EP) und das Produktionsprogrammplanungsproblem (PPP) bereits in allgemeiner Form

� Das PPP erfüllt zudem die Anforderungen der kanonischen Form

� Wegen der Ungleichheitsrestriktionen sind beide Probleme allerdings nicht in standardisierter Form

� Allerdings gibt es auch viele Anwendungen in denen negative Variablenwerte sinnvoll sind (zur Abbildung der Möglichkeit von Eigen- oder Fremdfertigung)


Mächtigkeit der LP-Formulierungen

� LP Formulierungen sind als äquivalent anzusehen, wenn sie sich ineinander überführen lassen, d.h. mit der Formulierung A kann man alles abbilden, was man auch mit B abbilden kann und umgekehrt (gleiche Mächtigkeit in der Abbildung)

� Offensichtlich sind LPs in kanonischer Form und in standardisierter Form bereits auch in allgemeiner Form

� Damit ist die allgemeine Form mindestens so mächtig wie die beiden anderen

� Allerdings ist die standardisierte Form „schön handlich“ und durch Gleichungen algebraisch gut nutzbar

� Daher würden wir diese häufig vorziehen um ein allgemeines Lösungsverfahren zu entwickeln


Äquivalenz der LP-Formulierungen

� Um zu zeigen, dass die Formulierungen äquivalent und somit gleich mächtig sind müssen wir zeigen wie wir die besonderen Eigenschaften der allgemeinen Form in der kanonischen Form und in der standardisierten Form abbilden können

� Im Einzelnen müssen wir

� Ungleichheitsrestriktionen durch Gleichheitsrestriktionen und umgekehrt ausdrücken

� Unbeschränkte (freie) Variablen durch positive Variablen simulieren

� Maximierung und Minimierung als Zielfunktion ineinander überführen


Gleichheitsrestriktionen�Ungleichheitsrestriktionen

( ) ( ) ( )

1

1

1

Ersetze die Gleichheitsrestriktion

durch die zwei folgenden Ungleichheitsrestriktionen

und

1 1

n

i, j j i

j

n

i, j j i

j

n

i, j j i

j

a x b

a x b

a x b

=

=

=

⋅ =

⋅ ≤

− ⋅ ⋅ ≤ − ⋅

∑

∑

∑

10


Ungleichheitsrestriktionen�Gleichheitsrestriktionen

1

1

Ersetze die Ungleichheitsrestriktion

durch die Hinzunahme einer neuen positiven Schlupfvariable und erhalte

0

Wir nennen alle Variablen des ursprünglichen Problems

n

i, j j i

j

n

i, j j i i i

j

a x b

a x y b y

=

=

⋅ ≤

⋅ + = ∧ ≥

∑

∑

Strukturvariablen

um sie von den neuen Schlupfvariablen zu unterscheiden.


Zielfunktion – Max versus Min

( )

1

1

1

Ersetze die ursprüngliche Zielfunktion Minimiere

durch die äquivalente neue Zielfunktion Maximiere 1

Ersetze die ursprüngliche Zielfunktion Maximiere

durch die äquivalen

n

j j

j

n

j j

j

n

j j

j

c x

c x

c x

=

=

=

⋅

− ⋅ ⋅

⋅

∑

∑

∑

( )1

te neue Zielfunktion Minimiere 1n

j j

j

c x=

− ⋅ ⋅∑


Freie Variablen � Positive Variablen

Für jede freie Variable definiere zwei neue positive Variablen 0, 0

mit .

Diese Ersetzung führt im System zu einer Verdopplung der korrespondierenden -ten Spalte in und in .

j j j

j j j

T

x IR x x

x x x

j c A

+ −

+ −

∈ ≥ ≥

= −

( ) ( ) ( )

1

1 1

1 1 1

Dabei

wird die neue Spalte mit "-1" multipliziert:

...... ...

,..., ,..., ,..., , ,..., und ,..., ,...,

... ......

j

j n j j j n j n j

j

n n

n

xx x

xc c c x c c c c A x a a a x

x

x xx

+

−

⋅ → − ⋅ ⋅ = ⋅

( ) { } { }

1

1

...

,..., , ,..., ,mit: 1,..., : , 1,..., :

...

j m

j j n i i

j

n

x

xa a a a i n c IR i n a IR

x

x

+

−

→ − ⋅ ∀ ∈ ∈ ∀ ∈ ∈


Ergebnis der Umformungsschritte

� Wir haben gezeigt, dass wir (im schlimmsten Fall bei einer Verdoppelung der Variablenzahl) alle LP-Formen äquivalent ineinander überführen können

� Dies bedeutet, dass die folgenden Aussagen äquivalent sind

� Ein gegebenes Optimierungsproblem kann als LP in allgemeiner Form definiert werden

� Ein gegebenes Optimierungsproblem kann als LP in kanonischer Form definiert werden

� Ein gegebenes Optimierungsproblem kann als LP in standardisierter Form definiert werden

� Damit können wir uns bei jedem Problem, das als LP formulierbar ist,

aussuchen, in welcher Form es vorliegen soll

� Das wird im Folgenden meist die standardisierte Form sein

11


4.1.3 Der Simplex Algorithmus

� Im Folgenden wollen wir uns exemplarisch wieder der Produktionsprogrammplanung zuwenden und ein spezielles PPP systematisch optimal lösen

� In diesem Problem betrachten wir drei Produktarten (1,2 und 3) die auf drei Fertigungsstufen produziert werden

� Produkt 1

� Deckungsbeitrag pro Einheit: 5

� Produktionskoeffizienten auf den Stufen: 2, 4 und 3

� Produkt 2


� Produktionskoeffizienten auf den Stufen : 3, 1 und 4

� Produkt 3


� Produktionskoeffizienten auf den Stufen : 1, 2 und 2


Damit erhalten wir das LP in kanonischer Form

0,,

8243

11214

5132 s.t.

345Max

321

321

321

321

321

≥

≤⋅+⋅+⋅

≤⋅+⋅+⋅

≤⋅+⋅+⋅

=⋅+⋅+⋅

xxx

xxx

xxx

xxx

zxxx


…und transformieren in die standardisierte Form

Max

s.t.

, ,

z x x x

x x x

x x x

x x x

x x x

= ⋅ + ⋅ + ⋅

⋅ + ⋅ + ⋅ ≤

⋅ + ⋅ + ⋅ ≤

⋅ + ⋅ + ⋅ ≤

≥

1 2 3

1 2 3

1 2 3

1 2 3

1 2 3

5 4 3

2 3 1 5

4 1 2 11

3 4 2 8

0

Max

s.t.

, , , , ,

z x x x

x x x x

x x x x

x x x x

x x x x x x

= ⋅ + ⋅ + ⋅

⋅ + ⋅ + ⋅ + =

⋅ + ⋅ + ⋅ + =

⋅ + ⋅ + ⋅ + =

≥

1 2 3

1 2 3 4

1 2 3 5

1 2 3 6

1 2 3 4 5 6

5 4 3

2 3 1 5

4 1 2 11

3 4 2 8

0

� Die Variablen des ursprünglichen Programms werden als Strukturvariablen bezeichnet

� Im Gegensatz dazu nennen wir die neu eingeführten Variablen im LP rechts (mit Gleichheitsrestriktionen) Schlupfvariablen


Wir entwickeln eine erste Lösung

1 2 3

4 1 2 3

5 1 2 3

6 1 2 3 1 2 3 4 5 6

Max 5 4 3

s.t. 5 2 3 1

11 4 1 2

8 3 4 2 mit , , , , , 0

Dies ist ein mit der folgenden Interpretation:

Wir nennen die

z x x x

x x x x

x x x x

x x x x x x x x x x

n

= ⋅ + ⋅ + ⋅

= − ⋅ − ⋅ − ⋅

= − ⋅ − ⋅ − ⋅

= − ⋅ − ⋅ − ⋅ ≥

Dictionary

Variablen, die sich auf der rechten Seite

der Gleichungen befinden, als . Diese

Variablen erhalten den Wert Null.

Die anderen Variablen, die jeweils isoliert ausschließlich au

m

m

−

Nicht - Basisvariablen

4 5 6

f der

linken Seite der Gleichungen stehen, heißen . Sie bilden

die : 5 11 8 mit Zielfunktionswert

0. Wir bezeichnen in einem Dictionary die Komponenten der

Zielfunk

x x x

z

= ∧ = ∧ =

=

Basisvariablen

Basislösung

tion als .reduzierte Kosten

12


Der Begriff der Basislösung

� Jedes Dictionary definiert eine zulässige Basislösung� Dies ist sozusagen die Invariante des Simplex Verfahrens

� Damit springt der Simplex Algorithmus in jedem Verfahrensschritt von einer Basislösung zu einer anderen Basislösung

� Das schauen wir uns gleich an

� Eine Basislösung ist

� eine Lösung des LP, die alle Restriktionen der Matrix A erfüllt

� eine Lösung des LP, bei der höchstens m Variablen (die aktuellen Basisvariablen, wobei m die Anzahl der Zeilen der Matrix A ist) einen Wert ungleich Null besitzen (alle anderen Variablen sind gleich Null)

� Sind die Basisvariablen gewählt ist die Basislösung eindeutig

� Eine Basislösung heißt zulässige Basislösung falls zusätzlich alle Variablenwerte nicht-negativ sind

� Besitzt eine Basislösung weniger als m Variablen, die nicht den Wert Null haben, spricht man von einer entarteten Basislösung


Qualität der gefundenen Lösung

� Ist offensichtlich nicht gerade überzeugend (z=0)

� Wie kann man die Lösung vielleicht verbessern?� Der Zielfunktionswert ist natürlich nicht überraschend

� Nur Schlupfvariablen (keine Strukturvariable) sind in der Basis und damit ungleich Null

� Schlupfvariablen zeigen lediglich den Schlupf in den Restriktionen an. Also kann hierdurch kein Deckungsbeitrag entstehen

� Wir betrachten die Menge der Nicht-Basisvariablen

� Dazu schauen wir auf die Koeffizienten in der Zielfunktion

� Auf Grund der positiven Koeffizienten erhöht eine Erhöhung der Variablen x1,

x2 oder x3 den Zielfunktionswert z. Da x1 den größten positiven Koeffizienten

besitzt probieren wir diesen zuerst aus. Vorschriften zur Auswahl von Variablen

nennen wir Pivotstrategien. Die genutzte Strategie bezeichnet man als „Größte

Koeffizienten Regel“ (=„largest coefficient rule”)

� Um wieviel können wir x1 erhöhen?

zxxx =⋅+⋅+⋅ 321 345Max


Um wieviel kann man nun x1 erhöhen?

{ }

1 2 3

4 1 2 3 1 1

5 1 2 3 1 1

6 1 2 3 1 1

1

Max 5 4 3

5s.t. 5 2 3 1 0 5 22

11 11 4 1 2 0 11 4 04

8 8 3 4 2 0 8 3 03

5 8 511min , ,2 4 3 2

x x x z

x x x x x x

x x x x x x

x x x x x x

x

⋅ + ⋅ + ⋅ =

= − ⋅ − ⋅ − ⋅ ≥ ⇒ ≥ ⋅ ⇒ ≥

= − ⋅ − ⋅ − ⋅ ≥ ⇒ − ⋅ ≥ ⇒ ≥

= − ⋅ − ⋅ − ⋅ ≥ ⇒ − ⋅ ≥ ⇒ ≥

⇒ = =


Was ist nun zu tun?

!

Wie können wir die Struktur erhalten und gleichzeitig x1 auf die linke Seite, also in die

Basis, bringen?

Wie können wir die Struktur erhalten und gleichzeitig x1 auf die linke Seite, also in die

Basis, bringen?

Das geht nur für die erste Restriktion.

Und danach substituieren wir

einfach die Variable

13


Umformung des Dictionary

( )

( )( )

252

211

250,,,,,

23

21

21

21

251

21

21

23

25 s.t.

25

21

27

252Max

0,,,,,

242

12

12

32

538

212

12

12

32

5411

21

21

23

25 s.t.

342

12

12

32

55Max

651654321

4326

425

4321

432

654321

324326

324325

4321

32432

=⇒=∧=∧=⇒≥

⋅+⋅−⋅+=

⋅+⋅+=

⋅−⋅−⋅−=

=⋅−⋅+⋅−

≥

⋅−⋅−⋅−⋅−⋅−⋅−=

⋅−⋅−⋅−⋅−⋅−⋅−=

⋅−⋅−⋅−=

=⋅+⋅+⋅−⋅−⋅−⋅

zxxxxxxxxx

xxxx

xxx

xxxx

zxxx

xxxxxx

xxxxxx

xxxxxx

xxxx

zxxxxx


Analyse der neuen Lösung

� Die Koeffizienten zeigen uns, dass wir die Lösung noch weiter verbessern können

� Dies ist möglich für die Variable x3.

� Wiederum müssen wir schauen, wie weit wir diese Variable erhöhen können

� Dazu müssen wir Obergrenzen der einzelnen Restriktionen ableiten

� Hierzu betrachten wir wieder das aktuelle Dictionary

zxxx =⋅−⋅+⋅− 432 25

21

27

252Max


Bestimmung einer Obergrenze für x3

{ } 11,5min

102

32

12

12

1

0251

502

12

12

32

5 s.t.

25

21

27

252Max

3

34326

425

34321

432

==⇒

≤⇒≥⋅+⋅−⋅+=

≥⋅+⋅+=

≤⇒≥⋅−⋅−⋅−=

=⋅−⋅+⋅−

x

xxxxx

xxx

xxxxx

zxxx


Umformung des Dictionary

( )

( )

131120,,,,,

231

251

222 s.t.

331Max

23131112

251

21231

21

23

25 s.t.

25231

21

27

252Max

531654321

6423

425

6421

642

64234326

425

464221

46422

=⇒=∧=∧=⇒≥

⋅−⋅++=

⋅+⋅+=

+⋅−⋅−=

=−−⋅−

⋅−⋅++=⇒⋅+⋅−⋅+=⋅

⋅+⋅+=

⋅−⋅−⋅++⋅−⋅−=

=⋅−⋅−⋅++⋅+⋅−

zxxxxxxxxx

xxxx

xxx

xxxx

zxxx

xxxxxxxx

xxx

xxxxxx

zxxxxx

14


Und nun?

!

Da es keine Nicht-Basisvariablemehr gibt, die einen positiven

Koeffizienten in der Zielfunktion besitzt, haben wir eine optimale Lösung gefunden.

Da es keine Nicht-Basisvariablemehr gibt, die einen positiven

Koeffizienten in der Zielfunktion besitzt, haben wir eine optimale Lösung gefunden.

Genau! Betrachte dazu die Zielfunktion

zxxx =−−⋅− 642331


Struktur der Dictionaries

� Linke Seite der Gleichungen

� Nur diese m Variablen dürfen ungleich Null sein (eine für jede Restriktion)

� Jedes andere Vorkommen der Variablen ist durch den Wert der rechten Seite in allen Gleichungen und der Zielfunktion zu substituieren

� Wir bezeichnen diese Variablen als Basisvariablen

� Rechte Seite der Gleichungen� Diese Variablen sind gleich Null zu setzen

� Dies sind n-m Variablen

� Wir bezeichnen diese Variablen als Nicht-Basisvariablen

� ZielfunktionPositive (negative) Koeffizienten erhöhen (erniedrigen) den Zielfunktionswert wenn die zugehörige Variable in die Basis eingeführt wird

� In jedem Schritt erfolgt ein Austausch von einer Basisvariable gegen eine Nicht-Basisvariable. Es sind in jedem Schritt genau m Variablen in der Basis.

� Durch jeden dieser Schritte wird versucht, die aktuelle Lösung zu verbessern.

� Geometrisch bewegt sich die Lösungssuche auf dem Rand des Lösungsraums von Eckpunkt zu Eckpunkt


Der „Weg“ des Simplex Algorithmus’

Ein Eckpunkt

Zulässiger Lösungsraum

Iteration 1

Iteration 0

Iteration 2

xA

xB

Optimale Lösung

Zielfunktion


Der Primale Simplex Algorithmus (mit Dictionaries)

1. Transformiere das LP in die kanonische Form und bilde danach Gleichheitsrestriktionen.

2. Initialisiere das Dictionary mit einer ersten zulässigen Basislösung.

3. Gibt es nun strikt positive Koeffizienten in der Zielfunktion?

“JA” Iteration:

- „Größte Koeffizienten Regel“: Wähle die Variable xB mit dem größten positiven

Koeffizienten in der Zielfunktion.

- Bestimme die kleinste positive obere Schranke für xB in den Restriktionen

- Wenn es mindestens eine positive obere Schranke für xB gibt, setze xB auf die

minimale positive obere Schranke, die sich aus der Restriktion i ergibt;

terminiere andernfalls (keine positive obere Schranke) da der Lösungsraum

nicht beschränkt ist und sich die Lösung unendlich verbessern lässt (damit gibt

es keine optimale Lösung)

- Transformiere Gleichung i so, dass xB auf der linken Seite isoliert wird.

- Substituiere xB in allen anderen Gleichungen und in der Zielfunktion durch die

erhaltene rechte Seite der Gleichung i. Vereinfache das System. Gehe zu Schritt 3.

“NEIN” Terminiere. Eine optimale Basislösung wurde gefunden.

15


4.1.4 Schwierigkeiten bei der Berechnung

� Die präsentierte Lösungsberechnung lief sehr einfach

� Dabei blieben allerdings mögliche Probleme unerwähnt

� Aber es kann Probleme der folgenden Art geben

� Initialisierung

� Offensichtlich brauchen wir eine initiale Lösung

� Kann man diese Lösung immer generieren?

� Iteration

� Kann es Iterationen ohne Verbesserungen geben?

� Kann es beliebig lange Berechnungsphasen ohne Verbesserungen geben?

� Termination

� Endet die Berechnung immer?

� Oder sind auch zyklische Berechnungen möglich?


Initialisierung

� Zur Ausführung des Simplex Verfahrens muss immer eine zulässige Basislösung vorliegen

� Dazu muss zunächst eine erste Lösung bestimmt werden

� In jedem Schritt wird die aktuelle Lösung verändert, wobei darauf geachtet wird, dass die neue Lösung wieder zulässig ist

� Wir brauchen also für alle Fälle eine erste zulässige Lösung

� Dies zu ermöglichen, ist nicht immer so trivial wie in unserem kleinen Beispiel. Allerdings können wir eine erste Lösung durch einige Überlegungen für alle Fälle garantieren

� Zunächst kann jedes LP in kanonische Form gebracht werden

� Wenn der b-Vektor positiv ist, kann man die Schlupfvariablen auf die Werte des b-Vektors setzen und die Strukturvariablen mit Null definieren (siehe unser Beispiel)


Initialisierung

� Wenn b≥0, nimm die triviale Lösung: alle Strukturvariablen werden auf Null gesetzt und alle Schlupfvariablen werden auf die Werte des Vektors b gesetzt (Vektor der rechten Seite)

� Wenn es ein i gibt mit bi<0, wende die Zwei-Phasen Methode an

( ){ }{ }

{ }

0

0 0

1 0

1 0

1. Hilfs-LP: Maximiere

subject to 1 mit , 0

2. Initiale Lösung für das Hilfs-LP: ,..., ,

mit ... 0 min | 0 1,...,

Da es 1,..., gibt mit 0

m

Tini ini ini ini

n

ini ini ini

n i i

i

z x

A x x b x x

x x x x

x x x b b i m

i m b

= −

⋅ − ⋅ ≤ ≥

=

= = = ∧ = − < ∀ ∈

∈ <

*

, ist zulässig

3. Löse das Hilfs-LP und bestimme die optimale Lösung

4. Wenn >0, beende die Prozedur da das ursprüngliche LP nicht lösbar ist

5. Initiale zulässige Lösung zu dem ursprünglichen LP

inix

x

z

( )* * *

1: ,...,T

nx x x=


Zwei-Phasen Methode – Konsequenzen

4.1.4.1 Beobachtung: Da die Zielfunktion nach unten durch Null

beschränkt ist, ist das Hilfs-LP immer lösbar

4.1.4.2 Lemma: Die optimale Lösung für das Hilfs-LP liefert den

Zielfunktionswert Null genau dann wenn das ursprüngliche LP lösbar

ist

Beweis: “⇒”: Da z=0 gilt, folgt x0=0. Die optimale Lösung des Hilfs-LP

liefert eine zulässige Lösung zum Ursprungsproblem

“⇐”: Das ursprüngliche LP ist lösbar. Damit gibt es eine optimale

Lösung für das Hilfs-LP mit x0=0 und damit mit Zielfunktionswert z=0

16


Zwei-Phasen Methode – Konsequenzen

Betrachte die optimale Lösung des Hilfs-LP’s

� x0>0 ist Basisvariable:

Das ursprüngliche LP ist nicht lösbar da mindestens eine Restriktion verletzt ist

� x0 ist Nicht-Basisvariable oder x0=0 ist Basisvariable:

Lösche x0 und gehe zurück zu dem ursprünglichen LP und setze die ermittelte Lösung dort ein

Spezialfall:

x0=0 ist Basisvariable: Betrachte den Schritt in der Berechnung, bei dem die Zielfunktion das erste Mal Null wird. Dort wurde die Variable x0 auf Null reduziert. Damit war x0 in diesem Schritt ein Kandidat zur Entfernung aus der Basis. Dies sollte geschehen und der Schritt ist deshalb entsprechend zu modifizieren


Initialisierung – Beispiel I

1 2 3

1 2 3

1 2 3

1 2 3

1 2 3

0

1 2 3 0 4

1 2 3 0 5

1 2 3 0 6

Max

s.t. 2 2 4

2 3 5

2 1

, , 0

Max

s.t. 2 2 4

2 3 5 min

2 1

x x x z

x x x

x x x

x x x

x x x

x z

x x x x x

x x x x x

x x x x x

− + =

⋅ − + ⋅ ≤

⋅ − ⋅ + ≤ −

− + − ⋅ ≤ −

≥

− =

⋅ − + ⋅ − + =

⋅ − ⋅ + − + = − ↵

− + − ⋅ − + = −

0 1 2 3 4 5 6 , , , , , , 0x x x x x x x ≥


Initialisierung – Beispiel II

( )( )

( )

0,,,,,,

4343

325

92 s.t.

325Max

0,,,,,,

13252

325

432522 s.t.

325Max

6543210

65321

53210

5432

5321

6543210

65321321

53210

45321321

5321

≥

=+−⋅−⋅+⋅−

++⋅−⋅+=

=−++⋅

=−−⋅+⋅−−

≥

−=+++⋅−⋅+−⋅−+−

++⋅−⋅+=

=+++⋅−⋅+−⋅+−⋅

=++⋅−⋅+−

xxxxxxx

xxxxx

xxxxx

xxxx

zxxxx

xxxxxxx

xxxxxxxx

xxxxx

xxxxxxxx

zxxxx


Initialisierung – Beispiel III

1 2 3 5

4 2 3 5

0 1 2 3 5

6 1 2 3 5

0 1 2 3 4 5 6 2

1 2 3 5

4 2 3 5 4

Max 5 2 3

s.t. 9 2

5 2 3

4 3 4 3

, , , , , , 0 Führe ein

Max 5 2 3

s.t. 9 2 9

x x x x z

x x x x

x x x x x

x x x x x

x x x x x x x x

x x x x z

x x x x x

− − ⋅ + ⋅ − − =

= − ⋅ − +

= + ⋅ − ⋅ + +

= + ⋅ − ⋅ + ⋅ +

≥ ⇒

− − ⋅ + ⋅ − − =

= − ⋅ − + ⇒ = 2 2

0 1 2 3 5 0 2 2

6 1 2 3 5 6 2 2

0 1 2 3 4 5 6

92 02

5 5 2 3 5 3 03

4 3 4 3 4 4 0 1

, , , , , , 0

x x

x x x x x x x x

x x x x x x x x

x x x x x x x

− ⋅ ≥ ⇒ ≤

= + ⋅ − ⋅ + + ⇒ = − ⋅ ≥ ⇒ ≤

= + ⋅ − ⋅ + ⋅ + ⇒ = − ⋅ ≥ ⇒ ≤ ↵

≥

17


Initialisierung – Beispiel IV

( )( )

( )

1 1 3 5 6 3 5

4 1 3 5 6 3 5

0 1 1 3 5 6 3 5

2 1 3 5 6

0 1 2

3 3 1 1Max 5 2 3 14 4 4 4

3 3 1 1s.t. 9 2 1 04 4 4 4

3 3 1 1 5 2 3 14 4 4 4

3 3 1 1 14 4 4 4

, , ,

x x x x x x x z

x x x x x x x

x x x x x x x x

x x x x x

x x x x

− − ⋅ + ⋅ + ⋅ + ⋅ + ⋅ − ⋅ − − =

= − ⋅ + ⋅ + ⋅ + ⋅ − ⋅ − + ≥

= + ⋅ − ⋅ + ⋅ + ⋅ + ⋅ − ⋅ + +

= + ⋅ + ⋅ + ⋅ − ⋅

3 4 5 6

1 3 5 6

4 1 3 5 6

0 1 3 5 6

2 1 3 5 6

0 1 2 3 4 5 6 3

, , , 0

5 31 1Max 24 4 4 4

3 5 1 1s.t. 72 2 2 2

5 31 1 24 4 4 4

3 3 1 1 14 4 4 4

, , , , , , 0 Führe in die B

x x x

x x x x z

x x x x x

x x x x x

x x x x x

x x x x x x x x

≥

− + ⋅ + ⋅ − ⋅ − ⋅ =

= − ⋅ − ⋅ + ⋅ + ⋅

= − ⋅ − ⋅ + ⋅ + ⋅

= + ⋅ + ⋅ + ⋅ − ⋅

≥ ⇒ asis ein


Initialisierung – Beispiel V

1 3 5 6

4 1 3 5 6 3 3

0 1 3 5 6 3

2 1 3 5 6 3

0 1 2 3 4 5

5 31 1Max 24 4 4 4

3 5 51 1 14s.t. 7 0 72 2 2 2 2 5

5 3 81 1 2 04 4 4 4 5

3 3 1 1 4 1 04 4 4 4 3

, , , , ,

x x x x z

x x x x x x x

x x x x x x

x x x x x x

x x x x x x

− + ⋅ + ⋅ − ⋅ − ⋅ =

= − ⋅ − ⋅ + ⋅ + ⋅ ≥ ⇒ ⋅ ≤ ⇒ ≤

= − ⋅ − ⋅ + ⋅ + ⋅ ≥ ⇒ ≤ ↵

= + ⋅ + ⋅ + ⋅ − ⋅ ≥ ⇒ ≥ −

6

0

4 1 0 6

3 1 0 5 6

2 1 0 5 6

0 1 2 3 4 5 6 1 2 3

, 0

Max 0

s.t. 3 2

8 31 4 1 5 5 5 5 5

3 311 2 1 5 5 5 5 5

811 , , , , , , 0 0, , ist eine zulässige Lösung5 5

x

x z

x x x x

x x x x x

x x x x x

x x x x x x x x x x

≥

− =

= − + ⋅ −

= − ⋅ − ⋅ + ⋅ + ⋅

= + ⋅ − ⋅ + ⋅ + ⋅

≥ ⇒ = = =


Initialisierung – Beispiel VI

( )( )

1 2 3 1 1 5 6

1 5 6

Damit können wir die Berechnung mit dem ursprünglichen Problem fortfahren

und die ermittelte erste zulässige Lösung dort einsetzen

311 2 1Max Max 5 5 5 5

8 31 15 5 5 5

3Max 5

− + = − + ⋅ + ⋅ + ⋅

+ − ⋅ + ⋅ + ⋅

= −

x x x x x x x

x x x

1 5 6

4 1 6

3 1 5 6

2 1 5 6

1 2 3 4 5 6

1 1 25 5 5

s.t. 3

8 31 1 5 5 5 5

311 2 1 5 5 5 5

, , , , , 0

+ ⋅ − ⋅ + ⋅ =

= − −

= − ⋅ + ⋅ + ⋅

= + ⋅ + ⋅ + ⋅

≥

x x x z

x x x

x x x x

x x x x

x x x x x x


Terminierung

� In jeder Iteration des Simplex Verfahrens wird eine Variable aus der Basis entfernt und durch eine Nicht-Basisvariable ersetzt, die einen positiven Koeffizienten in der Zielfunktion aufweist

� Diese Wahl ist nicht immer eindeutig � Pivotstrategie� Nicht Basisvariablen

� Es bieten sich unter Umständen mehrere Nicht-Basisvariablen an, in die Basis aufgenommen zu werden

� Man könnte die größte Verbesserung des Zielfunktionswertes als Kriterium nehmen

� Gibt es keinen Kandidaten hat man eine optimale Lösung gefunden

� Basisvariablen� Die Wahl der die Basis verlassenden Variablen muss nicht eindeutig sein

� Gibt es keinen Kandidaten gibt es keine optimale Lösung, da die aktuelle Lösung beliebig verbessert werden kann

� Gibt es mehrere Restriktionen mit gleicher Schranke erhalten wir im nächsten Schritt eine entartete Basislösung

18


Entartete Basislösung – Beispiel I

1 2 3

4 3

5 1 2 3

6 1 2 3 1 2 3 5 6

3

1 2 3

Wir betrachten das folgende Dictionary

Max 2 8

s.t. 1 2

3 2 4 6

2 3 4 , mit , , , , 0

Wir nehmen in der Basis auf

Max 2 8

s.t.

⋅ − + ⋅ =

= − ⋅

= − ⋅ + ⋅ − ⋅

= + + ⋅ − ⋅ ≥

⋅ − + ⋅ =

x x x z

x x

x x x x

x x x x x x x x x

x

x x x z

4 3 3

5 1 2 3 3

6 1 2 3 3 1 2 3 5 6

1 1 2 02

1 3 2 4 6 02

1 2 3 4 0 , mit , , , , 02

= − ⋅ ≥ ⇒ ≤

= − ⋅ + ⋅ − ⋅ ≥ ⇒ ≤

= + + ⋅ − ⋅ ≥ ⇒ ≤ ≥

x x x

x x x x x

x x x x x x x x x x


Entartete Basislösung – Beispiel II

� Wir sehen, dass es zwei Basisvariablen gibt (x5, x6), die den Wert 0 besitzen

� Obwohl das erstmal nicht problematisch im engeren Sinne ist (Lösung ist zulässig) kann das schädliche Nebeneffekte haben

� Insbesondere kann auf diese Weise eine zyklische Berechnung entstehen

1 2 4

3 4

5 1 2

6 1 2 3 1 2 3 5 6

4

1 12 2

0 2

0 3 2 0

Max 4 2

s.t.

mit

x x x z

x x

x x x

x x x x , x ,x ,x ,x ,x

+ ⋅ − − ⋅ =

= − ⋅

= − ⋅ +

= + − ⋅ + ⋅ ≥


Terminierung versus zyklische Berechnungen

� Zyklische Berechnungen verhindern eine Terminierung des Verfahrens

� Dieses Problem tritt selten auf muss aber abgefangen werden

� Aber, wie kann es dazu kommen?

� Verbessert sich der Zielfunktionswert in jedem Simplexschritt kann es keine Zyklen geben, da die neue Lösung ständig echt besser wird

� Liegt dagegen aber eine degenerierte zulässige Basislösung vor, besteht durchaus die Gefahr, dass eine Basisvariable mit dem Wert Null gewählt wird, die Basis zu verlassen. In diesem Fall kann es passieren, dass sich der Zielfunktionswert nicht verändert beim Tausch der Lösung

� Auf diese Weise kann es zu einer Folge von Schritten kommen, bei der verschiedene Basen entstehen und die, nach einer Reihe von Variablenwechseln wieder eine vorherige Lösung erreicht

� Wechselt man nicht mehr die angewendete deterministische Pivotstrategie terminiert der Algorithmus nie


Pivotstrategie: Minimaler Index

� Diese Pivotstrategie wählt (bei Alternativen) immer die Variable, die den kleinsten Index besitzt

� Da alle Variablen einen eindeutigen Index besitzen ist diese Regel immer eindeutig

� Diese Regel wird bei der Pivotstrategie für jede Entscheidung verwendet, d.h., sowohl für Variablen, die neu in die Basis kommen können als auch für Variablen, die diese verlassen könnten

4.1.4.3 Theorem:

Das Simplex Verfahren terminiert immer wenn die PivotstrategieMinimaler Index verwendet wird

Beweis:

siehe die Bachelor Veranstaltung „Combinatorial Optimization“ im folgenden Wintersemester

19


Lineare Programmierung – Was haben wir gelernt?

� Wir kennen die allgemeinen Formen von Linearen Programmen sowie ihre Definition und Äquivalenz

� Mit dem uns bekannten Simplex Algorithmus finden wir immer eine optimale Lösung für alle Linearen Programme (!!)

� Insbesondere können wir mit speziellen Problemen umgehen

� Finden einer benötigten Startlösung mit Hilfe einer einfachen Starkonstellation oder durch Anwendung der Zwei-Phasen Methode

� Verhinderung von Zyklen in der Berechnung durch Einsatz einer Pivotstrategie

� Die Veranstaltung “Combinatorial Optimization” setzt dies fort

� Tiefes Verständnis der Zusammenhänge (Struktur eines LP)

� Dualität

� Anwendungen der kombinatorischen Optimierung

� Ganzzahlige Optimierung

� Anwendungen der Spieltheorie


4.2 Ein Beispiel zur stochastischen Optimierung

� Im Folgenden betrachten wir beispielhaft eine praktische Problemstellungen, bei der die Eingabeparameter nicht mehr bekannt sind, sondern stochastischer Natur sein können

� Dies trifft in der Praxis sehr häufig zu

� Wir betrachten dazu ein Bestellmengenproblem mit unsicherer Nachfrage

� Es wird eine stochastische Verteilung der Nachfrage unterstellt

� Es ist in einer Periode eine Bestellmenge festzulegen, die Einfluss auf die sich ergebenden Kosten hat

� Es ist eine optimale Bestellmenge zu finden, die zu minimalen erwarteten Kosten führt

� Wir beginnen hierzu mit der Betrachtung von Modellen, die nur eine Periode umfassen, d.h. es wird lediglich eine Periode betrachtet, für die eine optimale Bestellmenge zu ermitteln ist


4.2.1 Einperiodisches Bestandsmanagement

� Bei einem einperiodischen Modell wird lediglich ein Bestellvorgang betrachtet

� Hierzu ist eine optimale Bestellmenge zu ermitteln

� Dabei handelt es sich meist um Anwendungen mit sehr verderblichen Gütern, d.h., um Güter, die – falls nicht verkauft – in den Folgeperioden nicht mehr verwendbar sind

� Mögliche Beispiele sind hierfür

� Tageszeitungen

� Leicht verderbliche Lebensmittel

� Aktionswaren

� Extreme Modeartikel


Newsvendor Problem

� Als klassisches Modell dient in diesem Bereich das so genannte „Newsvendor or Newsboy Model“, d.h. das „Zeitungsverkäufermodell“

� Bei diesem Modell wird ein Zeitungsverkäufer betrachtet

� Dieser entscheidet an jedem Morgen, wie viele Zeitungen er bestellt

� Für jede Zeitung ist ein Betrag von c Euro Bestellkosten zu entrichten

� Dagegen erzielt der Verkäufer einen Erlös von r Euro pro verkaufter Zeitung

� Auch ist es möglich, eine nicht verkaufte Zeitung für v Euro zurückzugeben

� Offensichtlich gilt: r > c > v

20


Computer Journal at Mac‘s (vgl. Nahmias (2005))

� Wir betrachten ein einfaches Beispiel

� Mac, Besitzer eines Zeitungskiosks bestellt jeden Sonntag das wöchentlich erscheinende Magazin „The Computer Journal“

� Er bezahlt c=25 Cents für jedes Exemplar im Einkauf und veräußert es zu r=75 Cents

� Daneben können nicht veräußerte Exemplare für v=10 Cents zurückgegeben werden

� Mac möchte ein effizientes Bestandsmanagement installieren und erfasst hierzu die Häufigkeit der Nachfrage


Nachfrage der letzten 52 Wochen

� Mittelwert der Reihe ist 11,7307692

� Standardabweichung ist 4,74079246

0

5

10

15

20

25

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 2 21 2 2 2 25 2 27 2 2 3 31 3 3 3 35 3 37 3 3 4 41 4 4 4 45 4 47 4 4 50 51 52

Tag

Nachfrage


Resultierende Häufigkeiten

0

1

2

3

4

5

6

7

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

Nachfrage

Häufigkeit


Daten der diskreten Verteilung

Nachfrage Häufigkeit f F

0 1 0,019230769 0,019230769

1 0 0 0,019230769

2 0 0 0,019230769

3 0 0 0,019230769

4 3 0,057692308 0,076923077

5 1 0,019230769 0,096153846

6 2 0,038461538 0,134615385

7 2 0,038461538 0,173076923

8 4 0,076923077 0,25

9 6 0,115384615 0,365384615

10 2 0,038461538 0,403846154

11 5 0,096153846 0,5

21


Fortsetzung


12 4 0,076923077 0,576923077

13 1 0,019230769 0,596153846

14 5 0,096153846 0,692307692

15 5 0,096153846 0,788461538

16 1 0,019230769 0,807692308

17 3 0,057692308 0,865384615

18 3 0,057692308 0,923076923

19 3 0,057692308 0,980769231

20 0 0 0,980769231

21 0 0 0,980769231

22 1 0,019230769 1


Optimale Bestellmenge

� Mac möchte die Bestellmenge optimieren, um sein Bestandsmanagement zu verbessern, d.h. es sind die Kosten zu minimieren, deren Höhe von der Bestellmenge beeinflusst wird

� Zur Findung der optimalen Bestellmenge ist zu untersuchen, welche Kosten jeweils von Fehl- oder Überschussmengen verursacht werden

� Diese sind dann entsprechend zu quantifizieren und in ihrer Häufigkeit zu bewerten


Entwicklung einer Kostenfunktion

� Werden zu wenige Einheiten bestellt, d.h. es gibt Fehlmengen, treten die erzielbaren Erlöse als Opportunitätskosten auf.

Hier gibt es einen Unterbestand und wir setzen als Unterbestandskostensatz cu an (Unit Underage Cost)

� Im Fall zu großer Bestellmengen ist dagegen die Differenz aus Bestellkosten und Rückgabeerlös anzusetzen.

Hier gibt es einen Überbestand und wir setzen als Überbestandskostensatz co an (Unit Overage Cost)

� Damit ergibt sich der Erwartungswert der Kosten aus der Betrachtung aller möglichen Fälle, d.h. aller möglichen Nachfragen, in Abhängigkeit der gewählten Bestellmenge S

Es muss gelteno uc c v c r c r c v= − = − > >


Übergang zur stetigen Variante

� Im Folgenden wollen wir uns stetigen Nachfragefunktionen zuwenden

� Warum?

� Häufig lassen sich Gesetzmäßigkeiten in diskreten Verteilungen erkennen (siehe zum Beispiel der Tests auf Normalverteilung)

� Dies verbessert die Analysierbarkeit der Zusammenhänge

� Zudem können die Instrumente der Infinitesimalrechnung genutzt werden

� Zunächst wird nur eine beliebige stetige Verteilung herangezogen, um allgemeine Ergebnisse erzielen zu können

22


Eigenschaften der stetigen Variante

� Gegeben sei eine Zufallsvariable y, die für die Nachfrage steht� Wir unterstellen eine beliebige stetige Nachfrageverteilung� Deren Dichtefunktion f(y) gibt die Wahrscheinlichkeit dafür an,

dass genau y Güter (im diskreten Fall) nachgefragt werden � Deren Verteilungsfunktion F(y) gibt an, dass 0 bis einschließlich y

Güter nachgefragt werden� Falls f(y) bzw. F(y) nicht geben ist, sind Wertetabellen einsehbar� Zudem unterstellen wir, dass es keine negativen Nachfragen

geben kann, d.h. f(y)=0 für y<0� Beachte, dass dies keine triviale Annahme ist. Zum Beispiel lässt

die Normalverteilung bei geringen Mittelwerten und (relativ hierzu) größeren Varianzen durchaus positive Wahrscheinlichkeiten für negative Nachfragemengen zu

� Darüber hinaus werden aber keine weitere Annahmen an den genauen Verlauf der Nachfrageverteilung gestellt


Die stetige Kostenfunktion

� Wir betrachten somit im Folgenden die Kostenfunktion

� Vorgehen

� Wie können wir die optimale Bestellmenge bestimmen?

� Offensichtlich ist hierzu zunächst die Ableitung nach S zu ermitteln und dann Extrempunkte zu finden

( ) ( ) ( ) ( ) ( )0

S

o u

y y S

Z S c S y f y dy c y S f y dy

∞

= =

= ⋅ − ⋅ + ⋅ − ⋅∫ ∫


Leibnizregel

� Zur Lösung unseres Problems benötigen wir die so genannte Leibnizregel. Sie lautet allgemein

� Diese können wir nun einfach auf unser Problem anwenden. Für das erste Integral ergibt sich die Substitution

( )( )

( )

( )

( )

( )

( )

( )( )( )

( )( )( )

2

1

2

1

2 12 1

a S

y a S

a S

y a S

Z Sh y,S dy

S S

h y,S a S a Sdy h a S ,S h a S ,S

S S S

=

=

∂ ∂=

∂ ∂

∂ ∂ ∂= + ⋅ − ⋅

∂ ∂ ∂

∫

∫

( ) ( ) ( ) ( ) ( )yfySy,ShSSaSa ⋅−=== ,,0 21


Integral 1

� Damit erhalten wir

� Für das zweite Integral ergibt sich die Substitution

( ) ( )( )

( ) ( )

( )( )�

( ) ( )

( )

( ) ( )( ) ( )

2 1

2 1

0 01 0

0

0 0

= === =

= − ⋅= − ⋅

= =

∂ − ⋅ ∂ ∂ + ⋅ − ⋅

∂ ∂ ∂

∂ − ⋅= = =

∂

∫

∫ ∫

��

��

S

yS

S f yS S f y

S S

y y

S y f y a S a Sdy h a S ,S h a S ,S

S S S

S y f ydy f y dy F S

S

( ) ( ) ( ) ( ) ( )yfSyy,ShSaSSa ⋅−=∞== ,, 21

23


Integral 2


� Damit ergibt sich als erste Ableitung

( ) ( )( )�

( ) ( )

( )( )�

( ) ( )

( )

( ) ( )( ) ( )

2 1

2 1

0 10

lim

1

k

k

y S k S

S k f y S S f y

k

y S y S

y S f y a S a Sdy h a S ,S h a S ,S

S S S

y S f ydy f y dy F S

S

→∞

= = == =

= − ⋅ = − ⋅ =

∞

= =

∂ − ⋅ ∂ ∂ + ⋅ − ⋅ ∂ ∂ ∂

∂ − ⋅= = − = − +

∂

∫

∫ ∫

��

( ) ( )( )SFcSFc uo −⋅−⋅ 1


Und als zweite Ableitung

� ergibt sich somit

� Diese zweite Ableitung ist offensichtlich größer oder gleich Null für alle Werte von S und somit konvex

� Damit sind alle Nullstellen der ersten Ableitung Minima der Kostenfunktion

� Wir berechnen also die optimale Bestellmenge durch Nullsetzen der ersten Ableitung

( ) ( )( )( ) ( ) ( )SfcSfcS

SFcSFcuo

uo ⋅+⋅=∂

−⋅−⋅∂ 1


Berechnung der optimalen Bestellmenge

� Wir erhalten somit

� Man bezeichnet CR als das Critical ratio

� Es gilt für alle Nachfrageverteilungen

( ) ( )( )( ) ( )

( ) ( ) ( )

uo

u

uo

u

uo

uuuo

uuo

uo

cc

cCR

cc

cFS

cc

cSFcSFcc

SFccSFc

SFcSFc

+=

+=⇔

+=⇔=⋅+⇔

=⋅+−⋅⇔

=−⋅−⋅

− mit ,

0

01

1


CR – Beispielrechnung

� Sei die folgende Parameterkonstellation gegeben

� c=1€

� r=3€

� v=0,5€

� Damit gilt

8,05,2

2

5,02

2

€213

€5,05,01

==+

=⇒

=−=−=

=−=−=

CR

crc

vcc

u

o

24


Zurück zur diskreten Variante

� Da man davon ausgeht, dass die jeweilige diskrete Verteilung durch eine stetige angenähert werden kann, sind unsere Ergebnisse der stetigen Version auch verwendbar für den diskreten Fall

� Dies führt uns nun zurück zu unserem kleinen Eingangsbeispiel

Das Mac Beispiel


CR – Für das Mac Beispiel

� Hier war die folgende Parameterkonstellation gegeben

� c=25 Cents

� r=75 Cents

� v=10 Cents

� Damit gilt

76923,065

50

Cents 502575

Cents 151025

==⇒

=−=−=

=−=−=

CR

crc

vcc

u

o


Wie lässt sich dieses Ergebnis interpretieren?

� Wir wählen bei einer beliebigen Nachfrageverteilung die Bestellmenge, die in 80 Prozent aller Fälle keine Fehlmengen verursacht, d.h. es gilt

� Anders ausgedrückt: p(x≤S*)=F(S*)=0,8

� Für das Beispiel Mac

� CR=0,76923

� Wir suchen die Nachfrage bei der F ungefähr den Wert 0,76923 annimmt

� Dies ist wollen wir anhand der Tabelle ermitteln


Daten der diskreten Verteilung


0 1 0,019230769 0,019230769

1 0 0 0,019230769

2 0 0 0,019230769

3 0 0 0,019230769

4 3 0,057692308 0,076923077

5 1 0,019230769 0,096153846

6 2 0,038461538 0,134615385

7 2 0,038461538 0,173076923

8 4 0,076923077 0,25

9 6 0,115384615 0,365384615

10 2 0,038461538 0,403846154

11 5 0,096153846 0,5

25


Fortsetzung


12 4 0,076923077 0,576923077

13 1 0,019230769 0,596153846

14 5 0,096153846 0,692307692

15 5 0,096153846 0,788461538

16 1 0,019230769 0,807692308

17 3 0,057692308 0,865384615

18 3 0,057692308 0,923076923

19 3 0,057692308 0,980769231

20 0 0 0,980769231

21 0 0 0,980769231

22 1 0,019230769 1


Konsequenz

� Der gesuchte Wert CR wird offensichtlich zwischen 14 und 15 angenommen

� Wir wählen aufgrund der Nähe zu den Werten und nach einer genaueren Betrachtung 15 als optimale Bestellmenge


Unterstellung einer Normalverteilung

� Im Folgenden wollen wir eine Normalverteilung als Nachfragefunktion unterstellen

� Dazu benötigen wir zunächst einige allgemeine Informationen zur Normalverteilung

� Sie besitzt die Dichtefunktion

( ) ,

mit als Erwartungswert und als Standardabweichung

x µ

σf x e

σ π

µ σ

− − ⋅ = ⋅⋅ ⋅

21

21

2


Eigenschaften

Es gilt

und

( )t µ

σF e dt

σ π

µ

µ

− − ⋅

−∞

= ⋅ =⋅ ⋅∫

21

21 1

22

( )

( )

( )

x µx µ

σσf x e e

σ π σ π

f x

µ

µ

− + ⋅ − − − ⋅ − ⋅ = ⋅ = ⋅⋅ ⋅ ⋅ ⋅

= − + ⋅

22 211

221 1

2 2

2

26


Konsequenzen

� Damit entsprechen sich bei der Normalverteilung Median und Mittelwert

� Die Normalverteilung ist offensichtlich symmetrisch


Die zugehörige Verteilungsfunktion…

� ist leider nicht analytisch berechenbar

� Daher wird oft der Spezialfall mit μ=0 und σ=1 betrachtet

� Diese spezielle Verteilungsfunktion ist die so genannte Standardnormalverteilung N(0,1)

� Für diese Funktion sind spezielle Tabellierungen verfügbar

� Daher wäre es wünschenswert die allgemeine Normalverteilung hierauf zurückzuführen

� Auf diese Weise kann auf die spezielle Tabellierung der Standardnormalverteilung zurückgegriffen werden

� Wir wollen nun einige Eigenschaften dieser speziellen Verteilungsfunktion herleiten


Eigenschaften der Standardnormalverteilung

� Dichtefunktion

� Verteilungsfunktion

( ) ( )2

01

2

1

2

x

f x x eπ

ϕ

− = = ⋅

⋅

( ) ( )2

01

2

1

2

tx

F x Φ x e dtπ

−

−∞

= = ⋅⋅

∫


Transformation der Normalverteilung N(μ,σ)

� Es gilt die folgende z-Transformation

� Diese lässt sich leicht durch die folgende Beziehung zeigen. So gilt:

� Damit erhält man die Dichtefunktion als Ableitung

( )2

01

2

1

2

x µtz

σx µ

F x F e dtσ π

− = −

−∞

− = = ⋅

⋅ ∫

( )

101

2

01 01

2

1 1 1 1

2

− − ⋅

− ∂ − − ′= ⋅ = ⋅ = ⋅ ⋅ =

∂

x µ

σ

x µF

x µ x µσF f e f x

x σ σ σ σ σπ

27


Grundsätzliche Folgerungen

� Damit ist „die Brücke zur Standardnormalverteilung hergestellt“ und wir können nun formulieren

� Falls die Zufallsvariable x nach N(μ,σ) verteilt ist, gilt

� Damit gilt für Intervalle

( ) ( ) ( ) ( ) ( )( )

01 01 01 01

1 1

1 1

P a x b P x a P x b F a F b

a µ b µ b µ a µF F F F

σ σ σ σ

≤ ≤ = ≥ − ≥ = − − −

− − − − = − − + = −

( ) ( ) 011 1a µ

P x a F a Fσ

− ≥ = − = −


α – Quantil

� Für α (0≤α≤1) ist das α – Quantil der Wert z(α), bei dem gilt

� Daraus folgt unmittelbar

� Da aber auch die Verteilungsfunktion der Standardnormalverteilung nicht analytisch bestimmbar ist, kommt die folgende numerische Näherung der z-Transformation zur Anwendung

( )( ) ( )( )01F z α P x z α α= ≤ =

( ) ( )101z α F α−=

( ) ( ) , mit Quantil der StandardnormalverteilungS α µ z σα α∗ = + ⋅ −


Konsequenz

� Erinnern wir uns: Für das Critical Ratio CR gilt F(S*)=CR� Für die Standardisierung der Zufallsvariable S*

erhalten wir somit

Das Critical Ratio CR also ein CR – Quantil der Standardnormalverteilung

� Die optimale Bestellmenge wird über die Rücktransformation erhalten

( ) ( )( )*

* *01( )

x SF S P x S P F z CR CR

µ µ

σ σ

− −= ≤ = ≤ = =

( )S µ z CR σ∗ = + ⋅


Konsequenz

( )*

Sz CR

µ

σ

−=

z

( )01f z

( )01F z

( )( ) ( )( )

01 01

z CR

F z CR f z dz CR−∞

= ⋅ =∫

z

CR

28


Das Mac Beispiel

� In dem Mac Beispiel galt CR=0,8. Aus der numerischen Näherung der Standardnormalverteilung ergibt sich

� Seien die folgenden Daten gegeben

� Wir wählen somit für eine stochastisch unabhängige und normalverteilte Nachfrage eine Bestellmenge von 117 Stück

( ) ( )101 0,8 0,84z CR F −= ≈

( )

100 Stück, 20 Stück

100 0 84 20 117 Stück

µ σ

S µ z CR σ ,∗

= =

= + ⋅ ≈ + ⋅ =


Die Näherung der Standardnormalverteilung

z(α) α = F01(z(α))0,69 0,755

0,71 0,76

0,72 0,765

0,74 0,77

0,755 0,775

0,78 0,78

0,79 0,785

0,81 0,79

0,825 0,795

0,84 0,8

0,86 0,805

0,88 0,81


Erwartete Fehlmenge J(S)

� Man vereinbart als erwartete Fehlmenge bzgl. S

� Damit gilt

( ) ( ) ( )y S

J S y S f y dy

∞

=

= − ⋅∫

( ) ( ) ( ) ( ) ( )

( )

21

2

lim

1lim

2

k

k

y S y S

y µk

σ

k

y S

J S y S f y dy y S f y dy

y S e dyσ π

∗

∞

→∞

= =

− − ⋅

→∞

=

= − ⋅ = − ⋅

= − ⋅ ⋅⋅ ⋅

∫ ∫

∫


Erwartete normierte Fehlmenge L(z)

� Analog hierzu wird die erwartete normierte Fehlmenge für z vereinbart

� Zusammenhang zwischen J(S*) und L(z*)

( ) ( ) ( )y z

L z y z y dy

∞

=

= − ⋅ϕ∫

( ) ( ) ( )( )

( )

( ) ( )

y y µ

y z y µ z

y µ

σ

y µ z σ

L z y z e dy y µ z e dyπ π

y µz e dy J S

σ σπ

σ L z J S

∗ ∗

∗

∞ ∞− ⋅ − ⋅ − ∗ ∗ ∗

= = +

− ∞ − ⋅ ∗ ∗

= + ⋅

∗ ∗

= − ⋅ ⋅ = − − ⋅ ⋅⋅ ⋅

− = − ⋅ ⋅ = ⋅

⋅

⇒ ⋅ =

∫ ∫

∫

22

2

1 1

2 2

1

2

1 1

2 2

1 1

2

29


Eine weitere wichtige Eigenschaft von L(z)

� Nahmias (2005) zeigt die folgende wichtige Eigenschaft der erwarteten normierten Fehlmenge

� Diese Eigenschaft erlaubt uns eine kompakte Darstellung der erwarteten optimalen Kosten

( ) ( )

( ) ( ) ( ) ( )( )

− ⋅ − ⋅

=−∞

=−∞

= ⋅ − ⋅ − − ⋅ ⋅

⋅ ⋅

= − ⋅ − = − ⋅ −

∫

∫

zz y

y

z

y

L z e z y z e dyπ π

z z Φ y dy f z z F zϕ

2 21 1

2 2

01 01

1 11

2 2

1 1


Erwartete optimale Kosten

� Nun können wir für die erwarteten Kosten der optimalen Bestellmenge S* formulieren

( ) ( ) ( ) ( ) ( )

( ) ( ) ( ) ( ) ( ) ( )

( ) ( )

( ) ( ) ( ) ( )

0

0 0

0 0

S

o u

y y S

S S

o

y y y S y S y S y S

u

y S

o

y y y S y

Z S c S y f y dy c y S f y dy

c S f y dy y f y dy S f y dy y f y dy S f y dy y f y dy

c y S f y dy

c S f y dy y f y dy S f y dy y f y

∗

∗

∗ ∗

∗ ∗ ∗ ∗

∗

∗

∞∗ ∗ ∗

= =

∞ ∞ ∞ ∞∗ ∗ ∗

= = = = = =

∞∗

=

∞ ∞ ∞∗ ∗

= = =

= ⋅ − ⋅ + ⋅ − ⋅

= ⋅ ⋅ − ⋅ + ⋅ − ⋅ − ⋅ + ⋅

+ ⋅ − ⋅

= ⋅ ⋅ − ⋅ − ⋅ + ⋅

∫ ∫

∫ ∫ ∫ ∫ ∫ ∫

∫

∫ ∫ ∫ ( ) ( )

( ) ( ) ( ) ( )

( ) ( ) ( ) ( )

1

u

S y S

o u

y S y S y S

o u

y S y S

dy c y S f y dy

c S S f y dy y f y dy c y S f y dy

c S y S f y dy c y S f y dy

µ

µ

∗ ∗

∗ ∗ ∗

∗ ∗

∞ ∞∗

= =

∞ ∞ ∞∗ ∗ ∗

= = =

∞ ∞∗ ∗ ∗

= =

+ ⋅ − ⋅

= ⋅ ⋅ − − ⋅ + ⋅ + ⋅ − ⋅

= ⋅ − + − ⋅ + ⋅ − ⋅

∫ ∫

∫ ∫ ∫

∫ ∫


Erwartete optimale Kosten

( )�

( ) ( ) ( ) ( )

( ) ( ) ( )

( ) ( )

( ) ( )

( ) ( ) ( )u o

u o u o

o u

y S y Sz σ

o o u o o u

y S

J S σ L z

o o u

c c

c c c c

Z S c S µ y S f y dy c y S f y dy

c z σ c c y S f y dy c z σ c c σ L z

c z σ c c σ f z z F z

∗ ∗∗

∗ ∗

∞ ∞∗ ∗ ∗ ∗

= == ⋅

∞∗ ∗ ∗ ∗

=

= = ⋅

∗ ∗ ∗ ∗

= − =+ +

= ⋅ − + − ⋅ + ⋅ − ⋅

= ⋅ ⋅ + + ⋅ − ⋅ = ⋅ ⋅ + + ⋅ ⋅

= ⋅ ⋅ + + ⋅ ⋅ − ⋅ −

∫ ∫

∫��

��01 01

1

1

( ) ( ) ( )

( ) ( ) ( ) ( )

oo o u o u

u o

o o u o o u

cc z σ c c σ f z c c σ z

c c

c z σ c c σ f z c σ z c c σ f z

∗ ∗ ∗

∗ ∗ ∗ ∗

= ⋅ ⋅ + + ⋅ ⋅ − + ⋅ ⋅ ⋅+

= ⋅ ⋅ + + ⋅ ⋅ − ⋅ ⋅ = + ⋅ ⋅

01

01 01


Damit ergeben sich für Z(S*)

� Es gilt somit

� Damit ergibt sich als optimaler Gewinn

( ) ( ) ( ) ( ) ( ), ,

, ,

o uZ S c c σ f z f

∗ ∗= + ⋅ ⋅ = − + − ⋅ ⋅

= ⋅ ⋅ =

01 011 0 5 3 1 20 0 84

2 5 20 0 28 14

( ) ( ) ( ) ( )3 1 100 200 14 186uΠ S c µ Z S Z S∗ ∗ ∗= ⋅ − = − ⋅ − = − =

30


Konsequenzen

� Wir sehen unmittelbar, dass sowohl die Höhe des Erwartungswertes als auch die Höhe der Standardabweichung einen signifikanten Einfluss auf den erwarteten Gewinn haben

� Triviale Erkenntnis

� Je größer der Erwartungswert (also des erwarteten Absatzes) desto größer ist der erwartete Erlös und damit der erwartete Gewinn

� Je größer die Standardabweichung (also die Unsicherheit in der

Nachfrage) desto größer werden die erwarteten Kosten und mindert damit den erwarteten Gewinn. Zu beachten ist hierbei

� Es gibt Unsicherheit aufgrund einer unscharfen Nachfrageprognose (hier gibt es ein wichtiges Verbesserungspotential)

� Somit ist an einer verbesserten Prognose mit geringeren Abweichungen zu arbeiten


Folge: Idealer Extremfall

� Bei sicherer Nachfrageprognose ohne Abweichungen ergeben sich keinerlei erwartete Kosten mehr

� So wäre in diesem Fall die Bestellmenge an der nun sicheren erwarteten Nachfrageprognose auszurichten


Z(S*) bei Halbierung von σ

� Es gilt nun

� Erwartete Kosten

� Damit ergibt sich als optimaler erwarteter Gewinn

( ) ( ) ( ) ( ) ( )728,0105,2

84,01025,0 0101

=⋅⋅=

⋅⋅+=⋅⋅+= ∗∗fzfσccSZ uo

( ) ( ) ( ) 193720010013 =−=−⋅−= ∗∗SZSΠ

( ) 1091084,010084,0 ≈⋅+=⋅+== ∗∗ σµCRSS


Diskrete Variante

� Hier tritt die Nachfrage in vordefinierten Wahrscheinlichkeiten in diskreten Niveaus auf

� Wir gehen dabei davon aus, dass die Nachfrage für kleinere n Poisson verteilt ist

� Hierzu zunächst einige Informationen zur Poissonverteilung

31


Informationen zur Poissonverteilung

� Die Poissonverteilung ist eine diskrete Wahrscheinlichkeitsverteilung, d.h. es treten nur abzählbar viele Ausprägungen auf

� Sie ist abgeleitet aus einer Folge von Bernoulli Experimenten(2 mögliche Ausgänge)

� Die Dichtefunktion der Poissonverteilung ist definiert durch

� Die Ereignisrate λ ist zugleich Erwartungswert und Varianz der Verteilung

� Der Einsatz einer solchen Verteilung bietet sich immer dann an, wenn nur wenige Ausprägungen möglich sind

� Geht die Anzahl der möglichen Ausprägungen gegen Unendlich nähert sich die speziell parametrisierte Poissonverteilung der Standardnormalverteilung

( ) teEreignisra als mit , λλy

y ey!

λpyXp

−⋅===


Erwartungswert der Poissonverteilung

Es gilt für den Erwartungswert:

( )

( )

( )

0 0 0

1

1

1

1

1

1

1

∞ ∞ ∞− −

= = =

∞−

=

−∞−

=

−∞−

=

=

= ⋅ = ⋅ ⋅ = ⋅ ⋅

= ⋅ ⋅

= ⋅ ⋅ ⋅−

= ⋅ ⋅ =−

∑ ∑ ∑

∑

∑

∑λ

y yλ λ

y

y y y

yλ

y

yλ

y

yλ

y

e

λ λE X y p y e e y

y! y!

λe y

y!

λ λe y

y y !

λλ e λ

y !��


Varianz der Poissonverteilung

Es gilt für die Varianz

( ) ( ) ( )

( )( )

( )( )

( )( ) ( )( )

( )( )( ) ( )

( )λλλλλλe

!y

λλ

λλe!y

λ

yyyyλ

λλey!

λyyλλe

y!

λyy

λey!

λyyyλλe

y!

λye

y!

λλ

e!y

λλe

y!

λye

y!

λλλyy

pλλyypλyX

y

λy

y

λy

y

λy

y

λy

y

λy

y

λy

y

λy

y

λy

y

λy

y

λy

y

y

y

y

=−+=−+⋅−

⋅=

−+⋅−

⋅−⋅

⋅−⋅⋅=

−+⋅⋅−⋅=−+⋅⋅−⋅=

−⋅⋅+−⋅=+⋅−⋅⋅=⋅⋅+

⋅−

⋅⋅−⋅⋅=⋅⋅+⋅⋅−=

⋅+⋅⋅−=⋅−=

∑

∑

∑∑

∑∑∑

∑∑∑

∑∑

∞

=

−−

∞

=

−−

∞

=

−∞

=

−

∞

=

−∞

=

−∞

=

−

∞

=

−−∞

=

−∞

=

−

∞

=

∞

=

222

2

22

2

2

22

2

0

2

0

2

0

22

0

2

0

2

1

12

0

2

0

22

0

22

0

2

2

21

11

11

12

122

2Var


Erwartungswert der Kosten

� Damit können wir die folgende Formel ansetzen

� Bei der Ermittlung der optimalen Bestellmenge „stört“ die unendliche Summe

� Diese lässt sich allerdings durch einen einfachen Trick „entfernen“

� Wir definieren wie folgt

( ) ( ) ( )( ) ( ) ( )( )∑∑∞

=

∗−

=

∗∗

∗

∗

=⋅−⋅+=⋅−⋅=Sy

u

S

y

o yXpSycyXpyScSZ1

0

( ) ( )( )

( ) ( )( ) ( ) ( )( )∑∑

∑

−

=

∗∞

=

∗

∞

=

∗

∗

∗

=⋅−⋅−=⋅−⋅=

=⋅−⋅

1

00

S

y

u

y

u

Sy

u

yXpSycyXpSyc

yXpSyc

32


Direkte Vereinfachungen

� Und erhalten schließlich als vereinfachten Ausdruck

� Somit ergibt sich für die erwarteten Kosten

( )( ) ( )( ) ( ) ( )( )

( ) ( )( )∑

∑∑∑

−

=

∗∗

−

=

∗∞

=

∗∞

=

∗

∗

=⋅−⋅−⋅⋅−⋅=

=⋅−⋅−=⋅⋅−=⋅⋅=

1

0

1

000

1S

y

uuu

S

y

u

y

u

y

u

yXpSyccSc

yXpSycyXpcSyXpyc

λ

( ) ( ) ( )( ) ( ) ( ) ( )( )∑∑−

=

∗∗

=

∗∗

∗∗

=⋅−⋅−−⋅+=⋅−⋅=1

00

S

y

uu

S

y

o yXpSycScyXpyScSZ λ


Erwartungswert der Kosten

� Und damit erhalten wir

( )

( ) ( )( ) ( ) ( )( ) ( )

( ) ( )( ) ( ) ( )( )

( ) ( ) ( )( ) ( )∗

=

∗

∗

=

∗

=

∗

∗

=

∗

=

∗

∗

−λ⋅+=⋅−⋅+=

⋅−λ⋅+=⋅−⋅+=⋅−⋅=

−λ⋅+=⋅−⋅+=⋅−⋅=

∑

∑∑

∑∑

∗

∗∗

∗∗

ScyXpyScc

SccyXpyScyXpySc

ScyXpyScyXpySc

SZ

u

S

y

uo

uu

S

y

u

S

y

o

u

S

y

u

S

y

o

0

00

00


Poissonverteilung mit Mittelwert 3

Nachfrage Wahrscheinlichkeit Kumulierte Wahrscheinlichkeit

0 0,049787068 0,049787068

1 0,149361205 0,199148273

2 0,224041808 0,423190081

3 0,224041808 0,647231889

4 0,168031356 0,815263245

5 0,100818813 0,916082058

6 0,050409407 0,966491465

7 0,021604031 0,988095496

8 0,008101512 0,996197008

9 0,002700504 0,998897512

10 0,000810151 0,999707663

11 0,00022095 0,999928613

12 5,52376E-05 0,999983851

13 1,27471E-05 0,999996598

14 2,73153E-06 0,99999933

15 5,46306E-07 0,999999876

16 1,02432E-07 0,999999978

17 1,80763E-08 0,999999996

18 3,01272E-09 0,999999999

19 4,75692E-10 1

20 7,13538E-11 1

21 1,01934E-11 1

22 1,39001E-12 1


Beispiel von Folie 407 – Bestimmung von S*

� Wie man sofort sieht, ist S* auf 4 zu setzen (CR=2/2,5=0,8)

� Damit ergibt sich als erwarteter Gewinn

( ) ( ) ( ) ( )( ) ( )

( ) ( ) ( )( ) ( )

( )( ) 30,1298393275,1231935731,15,2

222404184,044808362,044808362,019914827,05,2

432425,04

0

0

≈=−⋅=

−+++⋅=

−⋅+=⋅−⋅+=

−⋅+=⋅−⋅+=

∑

∑

=

∗

=

∗∗

∗

y

u

S

y

uo

yXpy

ScyXpySccSZ λ

( ) ( ) ( ) ( )3 1 3 6 1,30 4,70uΠ S c µ Z S Z S∗ ∗ ∗= ⋅ − = − ⋅ − = − =

33


Servicegrade

� Bisher haben wir für Fehlmengen und Überbestände einfach Kosten angesetzt und diese schließlich minimiert

� Problem dabei ist allerdings

� dass diese Kosten nicht immer eindeutig ermittelbar sind

� So gibt es unter Umständen Kunden, die aufgrund von Fehlmengen dauerhaft oder zumindest längerfristig zur Konkurrenz wechseln

� Diese Auswirkungen zu ermitteln ist sehr schwierig

� Daher gibt es andere Ansätze, die eine bestimmte Qualität in Form von zu erreichenden Servicegraden vorgeben und ausgehend hiervon die Bestellmengen festlegen


α-Servicegrad

� Idee:

� Wir wollen mit der Vorgabe eines Wertes zwischen 0 und 1 für α bestimmen, dass die Nachfrage in αProzent vielen Fällen vollauf befriedigt werden kann

� Das heißt formal, dass wir das folgende Problem betrachten

( )

Minimiere S

unter Beachtung der Nebenbedingung

F S α≥


Beispielwerte

α z(α)0,895 1,25

0,9 1,29

0,905 1,31

0,91 1,34

0,915 1,37

0,92 1,41

0,925 1,44

0,93 1,48

0,935 1,51

0,94 1,56

0,945 1,6

0,95 1,64


α-Servicegrad – Die zugehörige Bestellmenge

� Wir können somit S* direkt ermitteln durch

� An unserem Beispiel (μ=100, σ=20) folgt für

� α=0,95: z=1,64 und damit S*=100+1,64.20=132,8. Also 133 Stück

� α=0,9: z=1,29 und damit S*=100+1,29.20=125,8. Also 126 Stück

� Die Funktion nimmt bei Annäherung an α=1 einen extrem ansteigenden Verlauf

( )αFS1−∗ =

34


β-Servicegrad

� Idee:

� Betrachte zu einer Bestellmenge S die erwartete Fehlmenge J(S)

� Sie enthält – wenn normiert – den Anteil der Nachfrage, der nicht befriedigt werden kann, d.h.

( ) ( ) ( )dyyfSySJSy

∫∞

=

⋅−=

( )( ) ( )

µ

dyyfSy

µ

SJ Sy

∫∞

=

⋅−

=


β-Servicegrad

� Das heißt – positiv formuliert – wir sind bei Bestellmenge S in der Lage, genau

Prozent der Nachfrage zu befriedigen

� Damit ergibt sich als Programm der Erfüllung eines β-Servicegrades

( )( ) ( )

µ

dyyfSy

µ

SJ Sy

∫∞

=

⋅−

−=− 11

( )1

Minimiere S

J Sunter Beachtung der Nebenbedingung

µ− ≥ β


β-Servicegrad – Die zugehörige Bestellmenge

� Wir betrachten wiederum unser Beispiel mit der Normalverteilung

� Unter Verwendung von J(S)=σ.L(z) gehen wir über zu der normierten Funktion L(z)

� Damit muss für S* gelten

� Beachte dass L(z) eine fallende Funktion ist

( ) ( ) ( )

( ) ( ) ( ) ( ) ( )∗∗∗

∗∗∗

≥⋅−

⇔⋅≥⋅−⇔⋅≥⋅−⇔

≥⋅−

⇔≥⋅

−⇔≥−

zLσ

µβzLσµβµβzLσµ

βµ

zLσµβ

µ

zLσβ

µ

SJ

11

11


Am Beispiel ergibt sich

� Wir unterstellen wieder die obigen Daten

� Durch Betrachtung von entsprechenden Tabellen erhalten wir

( ) ( )∗≥==⋅−

===

zLσ

µβ

,σ,µ,β

25,020

51

20100950

( )

1078,1062034,0100

34,025,01

≈=⋅+=⇒

≈=∗

−∗

S

Lz

35


4.2.2 Periodisches Bestandsmanagement

� Im Folgenden werden Modelle untersucht, die eine Betrachtung des Bestandsverlaufs über mehrere Periodenerlauben und somit längerfristige Effekte abbilden

� Dabei wird davon ausgegangen, dass Überbestände auch in den folgenden Perioden noch verwendet werden können und Fehlmengen Nachbestellungen in den folgenden Perioden auslösen

� Zudem soll es (zunächst) möglich sein, Bestellungen in Nullzeitzu erhalten, d.h. Lieferzeiten werden vernachlässigt

� Wir können also am Anfang einer Periode bestellen und erhalten in derselben Periode noch die entsprechende Lieferung

� Des weiteren gehen wir von einem Zielbestand S aus, der jeweils am Anfang einer jeden Periode auf dem Lager vorhanden sein soll


Variablen des Modells

� Wir vereinbaren als Parameter

� Alle diese Größen sind Zufallsvariablen

� Damit ergibt sich die Bestellmenge aus dem Lagerbestand, der zu Beginn einer Periode bekannt ist, durch die einfache Formel

� Negative Bestände repräsentieren Fehlmengen, die durch eine nachfolgende Bestellung auszugleichen sind

: Bestellmenge in Periode

: Lagerbestand am Anfang der Periode

: Nachfrage in Periode

t

t

t

X t

I t

Y t

t tX S I= −


Kostenfunktion

� Wir wollen wiederum die erwarteten Kosten pro Periode minimieren

� Dazu ist zunächst zu determinieren, welche Kostenbestandteile auftreten können und wie sich diese berechnen lassen

� Variable Bestellkosten c fallen je bestellter Einheit an

� Lagerhaltungskosten h fallen mit dem Lagerbestand an, der am Ende einer jeden Periode noch vorliegt. Diese werden durch den Lagerhaltungskostensatz h monetär bewertet

� Strafkosten p (Penalty Cost) fallen pro Einheit an, die als Fehlmenge auftritt (Kosten der Rückstellung einer Nachfrage,

Deckungsbeitrag)


Direkter Zusammenhang

� Wir bestellen in jeder Periode soviel, dass wir schließlich den Bestand S erreichen

� Das heißt also, es gilt

� Darüber hinaus gilt

� Man sieht

� Wir bestellen einfach in jeder Periode genau den Verbrauch der letzten Periode

� Wenn man einen positiven Endbestand erhält, dann fallen Lagerkosten an

� Wenn ein negativer Endbestand auftritt, dann fallen Fehlmengenkosten an

t tX S I= −

1 1 1 1 1 1 1

1

t t t t t t t t

t t

I I X Y I S I Y S Y

S I Y

− − − − − − −

−

= + − = + − − = −

⇔ − =

1t tX = Y −

36


Konsequenz

� Fehlmengen- und Lagerhaltungskosten treten also immer bei positiven oder negativen Beständen am Anfang einer Periode auf

� Da der Anfangsbestand einer Periode dem Endbestand der Vorperiode entspricht, müssen wir uns also zur Determinierung dieser Kosten lediglich den Bestand am Ende der einzelnen Perioden anschauen

� Damit ergibt sich für die Anfangsbestände

� Fehlmengen und Überbestände hängen somit lediglich von Yt

ab, d.h. wir müssen unterscheiden ob gilt

tt YSI −=+1

t tS Y oder S Y < >


Die erwarteten Gesamtkosten

� Da variable Bestellkosten entscheidungsirrelevant sind, können wir für die erwarteten Gesamtkosten einer Periode festhalten

� Dies ist offensichtlich die Zielfunktion des Newsvendor Problems, wenn man cu durch p und co durch h ersetzt

� Somit erhalten wir als optimales Bestellniveau

( ) { }( ) { }( )0,max0,max SYEpYSEhSZ tt −⋅+−⋅=

+= −∗

hp

pFS

1


Am Beispiel

� Wir betrachten als Beispiel wieder einen Händler

� Diesmal soll ein Elektronikteilhändler betrachtet werden, der sich auf spezielle Adapter für Hardwarebastler spezialisiert hat

� Wir betrachten die wöchentliche Nachfrage, wobei der Händler lediglich am Freitag bestellt und am Montagmorgen vor Geschäftseröffnung die entsprechende Lieferung erhält

� Da keine Verkäufe am Wochenende erfolgen, liegt hier die im Modell unterstellte Lieferung in Nullzeit vor

� Wir gehen wiederum von einer normalverteilten Nachfrage mit dem Erwartungswert μ=100 Stück/Woche und einer Standardabweichung von 50 Stück/Woche aus


Bestimmung des optimalen Bestandes S*

� Wir unterstellen die folgenden Kostensätze

� Lagerhaltungskosten h=0,5 €/Stück je Woche

� Fehlmengenkosten p=3 €/Stück je Woche

� Damit gilt für die optimale Bestellmenge

� Wir können z* direkt in der Tabelle der Standardnormalverteilung ablesen und erhalten

z*=1,07. Damit erhalten wir

* * 100 1,07 50 153,5 Stück pro WocheS zµ σ= + ⋅ = + ⋅ =

( )1 1 130,8571

3 0,5

pS F F F

p h

∗ − − − = = ≈ + +

37


Erwartete Kosten

� Wir können wiederum die Formel des Newsvendor Problems direkt einsetzen und erhalten somit als einfache Berechnung

� Setzt man einen Verkaufspreis von r = 10€ und Einkaufskosten von c = 4€ an, erhalten wir damit als erwarteten Gewinn

( ) ( ) ( ) ( ) ( )

( )

01 011,07

3 0,5 0,2251 50 39,3925 €/Woche

Z S p h f z p h fσ σ∗ ∗= + ⋅ ⋅ = + ⋅ ⋅

= + ⋅ ⋅ =

( ) ( ) ( )10 4 100 39,3925

560,6075 €/Woche

uS c Z Sµ∗ ∗Π = ⋅ − = − ⋅ −

=


Berücksichtigung der Lieferzeit

� In vielen Problemstellungen muss allerdings eine Lieferzeit durch das Anwendungssystem berücksichtigt werden

� Dies verändert die Problemstellung in der Weise, dass der Lagerbestand nicht sprunghaft, sondern schrittweise aufgefüllt wird

� Wir verfügen also nicht nur über den physischen Lagerbestand, sondern müssen noch zusätzlich offene, d.h. erfolgte aber noch nicht eingetroffene, Bestellungen berücksichtigen

� Dies wird zu einer „gewissen Verschiebung“ der Verteilung führen


Parameter und Modelldefinitionen

� Wir modifizieren unseren Modellentwurf nun wie folgt

� Neben dem Lagerbestand It zu einer Periode t treten somit periodenbezogene Parameter zu ausstehenden Bestellmengen Ot (Open Orders) und disponiblen Lagerbeständen IPt (Inventory Position)

� Der disponible Lagerbestand in Periode t IPt ergibt sich als Summe der in t noch ausstehenden Bestellmenge und dem dort vorliegenden Lagerbestand. Damit gilt

� Wir unterstellen zudem eine Lieferzeit von LT Perioden

t t tIP I O= +


Zusammenhang der Parameter

� Damit können wir uns nun verdeutlichen, wie sich Bestellungen in der Periode t auf den Lagerbestand in der Periode t+LT auswirken

� Konkret wird eine Bestellung in einer Periode wiederum so gebildet, dass der Lagerbestand zu Beginn der Periode durch die Bestellung auf den Zielbestand S aufgefüllt wird

� Die Bestellung in der Periode t (also Xt) selbst trifft dann im Laufe der Periode t+LT ein

� So gilt am Ende der Periode t+LT für den Lagerbestand

� Dabei lässt sich für den Lagerbestand am Ende der Periode t+LT-1 (d.h. am Anfang der Periode t+LT) festhalten

t LT t t LTI X Y+ ++ −

1 1... ...

t LT t t LT t t t LTI I X X Y Y+ − − + −= + + + − − −

38


Konsequenz

� Damit können wir direkt für den Lagerbestand am Anfang der Periode t+LT+1 folgern

� Was bedeutet dieses Ergebnis für die Suche nach einem optimalen Wert für S*?

1

1 1

1 1

1

... ...

... ...

...

t LT t LT t t LT

t t LT t t t LT t t LT

t t LT t t t t LT t LT

t t t t LT t LT

t LT

t

I I X Y

I X X Y Y X Y

I X X X Y Y Y

IP X Y Y Y

S Y

+ + + +

− − + − +

− − + − +

+ − +

+

=

= + −

= + + + − − − + −

= + + + + − − − −

= + − − − −

= − ∑ ττ


Interpretation des Ergebnisses

� Der Lagerbestand in Periode t wird also durch die Nachfrage in den Perioden t, t-1,…,t-LT bestimmt, die jeweils zu Fehlmengen oder Überständen führen können

� Damit sind wir an Informationen zur Verteilung der Summe der Nachfragen über diese Perioden interessiert

� Dies wird als Faltung bezeichnet

� Wir unterstellen wiederum stochastische Unabhängigkeit zwischen den einzelnen Perioden und definieren YLT+1 als die Faltung der LT+1 unabhängigen Nachfragen


Damit können wir schreiben

� für den Lagerbestand, der sich am Ende der Periode t+LT ergibt

� Allerdings vereinfacht sich diese Berechnung signifikant, wenn die Nachfrage jeweils normalverteilt ist

� So ist im Allgemeinen die Summe von k normalverteilten unabhängigen Zufallsvariablen mit Erwartungswert µ und Varianz σ2 wiederum normalverteilt mit Erwartungswert k.µ und Varianz k.σ2

� Dies wird an folgender Herleitung deutlich

1LT

t LTI S Y+

+ = −


Konsequenz

� Damit ergibt sich für die Verteilung der letzten LT+1 Perioden

� Erwartungswert (LT+1).µ und

� Varianz (LT+1).σ2

� Damit ergibt sich die Kostenfunktion

� Damit ergibt sich wiederum als optimale Lösung

( ) { }( ) { }( )1 1max ,0 max ,0LT LTZ S h E S Y p E Y S

+ += ⋅ − + ⋅ −

1

1LT

pS F

p h

∗ −

+

= +

39


Direkte Konsequenz

� Aufgrund der Eigenschaften der Normalverteilung gilt somit

� Wir unterstellen nun für unser kleines Beispiel eine Lieferzeit von LT=2 Wochen

� Die anderen Parameter behalten wir bei, d.h.

� Erwartungswert: μ=100 Stück/Woche

� Standardabweichung: σ=50 Stück/Woche

� Wir unterstellen die folgenden Kostensätze

� Lagerhaltungskosten h=0,5 €/Stück je Woche

� Fehlmengenkosten p=3 €/Stück je Woche


� μLT+1=3.100=300 Stück/Woche

� σLT+1=(3.502)1/2=86,60 Stück/Woche

1 1LT LTS zµ σ∗ ∗

+ += + ⋅


Ermittlung von S*

� Wir verwenden wieder die Gesetzmäßigkeit der Normalverteilung und erhalten wiederum direkt

� und somit für den optimalen Zielbestand

( )1 1 1

01, 1 01, 1 01, 1

30,8571 1,07

3 0,5LT LT LT

pz F F F

p h

∗ − − −

+ + +

= = ≈ ≈ + +

1 1300 1,07 86,80 392,662 Stück pro Woche

LT LTS zµ σ∗ ∗

+ += + ⋅ = + ⋅ =


Ermittlung der erwarteten Kosten

� Wir können wiederum die Formel des Newsvendor Problems direkt einsetzen und erhalten

� Setzt man wieder einen Verkaufspreis von r=10€ und Einkaufskosten von c=4€ an, erhalten wir damit als erwarteten Gewinn

( ) ( ) ( ) ( ) ( )

( )

01 1 01 11,07

3 0,5 0,2251 86,6 68,22781 €/Woche

LT LTZ S p h f z p h fσ σ∗ ∗

+ += + ⋅ ⋅ = + ⋅ ⋅

= + ⋅ ⋅ =

( ) ( ) ( )10 4 100 68,22781

531,77 €/Woche

uS c Z Sµ∗ ∗Π = ⋅ − = − ⋅ −

=


Sensitivitätsanalyse

� Wir sehen z.B. anhand der Formel für die Berechnung der Bestellkosten

� dass die Bestellkosten linear mit der Standardabweichung der Nachfrage steigen oder fallen

� oder dass die Bestellkosten linear mit (LT+1)1/2 steigen oder fallen

( ) ( ) ( ) ( ) ( )01 1 011

LTZ S p h f z p h f z LTσ σ∗ ∗ ∗

+= + ⋅ ⋅ = + ⋅ ⋅ ⋅ +

40


Praktische Konsequenz

� Wir können untersuchen, was es an Ersparnissen bringen würde, wenn wir durch eine bessere Abstimmung mit unserem Lieferanten die Lieferzeit auf eine Woche reduzieren würden

� Da z* offensichtlich unabhängig von LT ist, können wir einfach formulieren

( ) ( ) ( ) ( )( ) ( )

, 1 01 1 1 1

3 0,5 0,2251 50 3 2 39,3925 0,3178 12,52

LT LTZ S p h f z LT LTσ∗ ∗

−∆ = + ⋅ ⋅ ⋅ + − + −

= + ⋅ ⋅ ⋅ − = ⋅ ≈


Analyse der Bestandshöhe

� Wir analysieren in Abhängigkeit der Lieferzeit LT den Verlauf des

� Pipelinebestands (ps=„pipeline stock“)

� Sicherheitsbestands (ss=„safety stock“)

� Liegt eine Lieferzeit LT vor, entstehen durchschnittliche Pipelinebestände von

� D.h. in der Zeit der Beschaffung fallen diese Nachfragen durchschnittlich an und wir bestellen jeweils die Differenz zu S*, also durchschnittlich genau die erwartete Nachfragemenge

� Zudem ergibt sich ein gesamter Sicherheitsbestand ss von

LTps LT µ µ= ⋅ =

1 1 1LT LTss S z z LTµ σ σ∗ ∗ ∗+ += − = ⋅ = ⋅ + ⋅


Der Sicherheitsbestand

� dient zur Absicherung für Konstellationen in denen die Nachfrage die Summe der durchschnittlichen Erwartungswerte übersteigt

� erzeugen entsprechende Lagerkosten über den erwarteten Verbrauch

� Dies ist somit der Preis für die Unsicherheit in der Nachfrage

� Damit erlaubt eine bessere Kenntnis über die Nachfrage eine deutliche Reduktion der Kosten


α-Servicegrad

� Misst die Wahrscheinlichkeit, dass in einer Periode keine Rückstellung notwendig wird

� Man sucht damit aufgrund der oben hergeleiteten Zusammenhänge die kleinste Bestellmenge S* mit

� Damit wählen wir

( )1LTF S α∗

+ ≥

( )1

1LTS F α∗ −

+=

41


α-Servicegrad – Am Beispiel

� Wir betrachten nun wiederum ein einfaches Beispiel zur Illustration des Vorgehens

� Dazu sei bei unserem Hardware Shop ein α-Servicegrad von 95% angenommen

� Dann muss gelten

( )

( )

1

1 1 1

1

01, 1

1 1

0,95 , mit

0,95 1,65

300 1,65 86,6 442,89

LT LT LT

LT

LT LT

S F S z

z F

S z

µ σ

µ σ

∗ − ∗ ∗

+ + +

∗ −

+

∗ ∗

+ +

= ⇒ = + ⋅

= ≈

⇒ = + ⋅ = + ⋅ =


β-Servicegrad

� Der β-Servicegrad misst nun den Anteil der Nachfrage einer Periode der durchschnittlich zurückgestellt werden muss

� Damit zielt dieser Servicegrad auf die Berechnung der erwarteten Fehlmenge JLT+1(S) der Nachfrage in einer Periode

� Beim periodischen Bestandsmanagement lässt sich allerdings diese Berechnung nicht einfach isoliert für die einzelnen Perioden durchführen

� Warum?

( ) ( ) ( )1 1 LT LT

y S

J S y S f y dy

∞

+ +

=

= − ⋅∫


β-Servicegrad

� Während beim vorherigen α-Servicegrad eine Periode in der Weise isolierbar ist, dass nur gefragt wird, ob es keinerlei Fehlmengen (d.h. keine unbefriedigte Nachfrage) gibt, ist dies beim β-Servicegrad so einfach nicht mehr möglich

� Das Problem besteht hier nun darin, dass die genaue Wahrscheinlichkeit einer spezifischen Fehlmenge (d.h., y, mit y>S*) nicht periodengenau vorliegt

� Genauer gesagt, wir wissen nicht genau wann die Nachfrage y aufgetreten ist

� Somit kann es sein, dass wir in der betrachteten Periode eine unbefriedigte Nachfrage messen, die in Wahrheit in der Vorperiode aufgetreten ist und dort ebenfalls unbefriedigt geblieben ist


Wahrscheinlichkeit einer Fehlmenge

� Dies führt zu einer möglichen Überbewertung (d.h. Mehrfachzählung) von Fehlmengen

� Dies gilt natürlich nur für die von uns gewählte Definition des β-Servicegrades

� Für diese können wir aber die oben genannte Definition als Näherungswert ansetzen

� Dies erscheint vor allem dann sinnvoll, wenn der Wert für βnahe bei 1,0 liegen soll

� Hierbei ist zu beachten, dass diese höheren Werte für βmehrfache Fehlmengen deutlich unwahrscheinlicher werden lassen

� Daher werden wir für diese Fälle die oben genannte vereinfachte Formel als eine relativ genaue Näherung verwenden

42


Berechnung des β-Servicegrades

� Damit können wir allgemein den β-Servicegrad wie folgt herleiten

� Wir suchen die minimale Bestellmenge S*, für die gilt

� Betrachten wir hierzu unser kleines Beispiel

� Seien β=0,95 und µ=100 Stück/Woche

� Dann gilt

( ) ( )( ) ( ) ( )1 1

1 11 1

LT LT

LT LT

J S J SJ S J S

µβ β µ µ β β µ

µ µ

∗ ∗

+ + ∗ ∗

+ +

−− ≥ ⇔ ≥ ⇔ − ≥ ⋅ ⇔ − ⋅ ≥

( ) ( ) ( ) ( )

( ) ( )1 1 1

01 01

1 0,05 100 5

5 86,6 0,057737 1,19

Bei minimal gewähltem gilt somit 300 86,6 1,19 403,054

LT LT LTJ S J S L z

J z J z z

S S

β µ σ∗ ∗+ + +

∗ ∗ ∗

∗ ∗

− ⋅ ≥ ⇒ ⋅ = ≥ = ⋅

⇔ ≥ ⋅ ⇒ ≤ ⇒ ≈

≈ + ⋅ =


Damit erhalten wir

� Einen Pipelinebestand von

� und einen Sicherheitsbestand von

2 100 200LT µ⋅ = ⋅ =

1 1 403,054 300 103,054LT LTS zµ σ∗ ∗

+ +− = ⋅ = − =


4.2.3 Kontinuierliches Bestandsmanagement

� Bisher haben wir eine optimale Bestellmenge bestimmt, zu der – als Zielbestand – immer wieder aufzufüllen ist

� Wir wollen nun aber den Bestellpunkt und die Bestellmenge unabhängig voneinander optimieren, d.h. wir integrieren in das Modell eine höhere Flexibilität indem wir nicht länger den Bestellpunkt aus der verfolgten Bestellmenge als Zielbestand ableiten

� Dazu wird angenommen, dass immer maximal eine Bestellung offen sein kann


Die Kosten – Variable Bestellkosten

� Diese erwarteten Kosten entstehen ausschließlich abhängig vom Bedarf in einer Periode

� Wir können somit formulieren

� Dabei gilt

( ), = ⋅vBK x r c µ

Variable Bestellkosten je Produkteinheit

Erwartete Nachfrage im Planungszeitraum

c

µ

43


Die Kosten – Fixe Bestellkosten

� Diese Kosten entstehen aufgrund der Durchführung von Bestellungen


� Dabei gilt

( ), = ⋅fB

K x r kx

µ

Fixe Bestellkosten je Bestellvorgang

Erwartete Nachfrage im Planungszeitraum

k

µ


Die Kosten – Lagerkosten

� Diese Kosten entstehen aufgrund der vorhandenen Lagerbestände


� Dabei gilt

( )

: Maximaler Lagerbestand wenn Bestellung gerade eintrifft

: Minimaler Lagerbestand genau vor dem Eintreffen der Bestellung

2 2,

2 2

2

+ − ⋅

− ⋅

+ − ⋅ + − ⋅ ⋅ + − ⋅ ⋅ = ⋅ = ⋅

= ⋅ + − ⋅

LB

r x LT

r LT

r x LT r LT r x LTK x r h h

xh r LT

µ

µ

µ µ µ

µ

Lagerkostensatz

Lieferzeit in Perioden

h

LT


Achtung – Fehler in der Berechnung

� Leider erfolgt die Berechnung lediglich auf Basis der Erwartungswerte

� Damit gehen Fehlmengen als negative Bestände ein

� Dies ist offensichtlich nicht korrekt, da in diesen Situationen kein negativer Lagerbestand sondern kein Lagerbestandvorliegt

� Damit unterschätzen wir insgesamt den Lagerbestand

� Da dieser Fehler aber bei höheren Servicegraden sehr gering ist, können wir mit dieser Approximation arbeiten

� Es gibt allerdings auch exakte Ansätze zu dieser Problemstellung (vgl. Zipkin (2000))


Die Kosten – Fehlmengenkosten

� Diese Kosten entstehen aufgrund von Fehlmengen

� Bei jeder möglichen Bestellung ergeben sich erwartete Fehlmengenkosten von

� Da es µ/x viele Bestellvorgänge gibt, gilt

� Dabei gilt

( ) ( ) ( ), ,= ⋅ ⋅ = ⋅ ⋅FM PFM LTK x r p K x r p J rx x

µ µ

Kosten pro Einheit Fehlmenge

Lieferzeit in Perioden

p

LT

( ) ( ) ( ) ( ),

∞

=

= − ⋅ =∫PFM LT LT

y r

K x r y r f y J r

44


Ermittlung der optimalen Lösung

� Wir betrachten die Gesamtkostenfunktion

� und bilden die partiellen Ableitungen

( ) ( ),2

= ⋅ + ⋅ + + − ⋅ ⋅ + ⋅ ⋅

G LT

xK x r c k r LT h J r p

x x

µ µµ µ

( )( )

2 2

,

2

∂= − ⋅ + − ⋅ ⋅

∂G

LT

K x r hk J r p

x x x

µ µ

( ) ( )( ) ( )

( )( )( ) ( )( )

Anwendung der Leibniz Regel (siehe 2.Integral beim Newsvendor Problem)

,

1 1

∞

=

∂ − ⋅∂ ∂⋅ ⋅

= + ⋅ = + ⋅∂ ∂ ∂

⋅ ⋅= + ⋅ − − = + ⋅ − +

∫

��

y rG LT

LT LT

y r f y dyK x r J rp p

h hr x r x r

p ph F r h F r

x x

µ µ

µ µ


Auflösen nach x und r

� Optimale Wahl von x

� Optimale Wahl von r

( )( )

( ) ( )

( )( ) ( )( )

2 2

2 2

2

,0 0

2

02 2

2 2

∂= ⇔ − ⋅ + − ⋅ ⋅ =

∂

⇔ − ⋅ + ⋅ − ⋅ ⋅ = ⇔ ⋅ = ⋅ ⋅ + ⋅

⋅ ⋅ ⋅ + ⋅ ⋅ ⋅ +⇔ = ⇔ =

G

LT

LT LT

LT LT

K x r hk J r p

x x x

h hk x J r p x J r p k

J r p k J r p kx x

h h

µ µ

µ µ µ µ

µ µ

( )( )( ) ( )

( ) ( ) 1

,1 0 0

1 1−

∂ ⋅ ⋅ ⋅= + ⋅ − + = ⇔ − + ⋅ =

∂

⋅ ⋅ ⋅ ⋅⇔ ⋅ = − ⇔ = − ⇔ = −

⋅ ⋅

G

LT LT

LT LT LT

K x r p p ph F r h F r

r x x x

p p h x h xF r h F r r F

x x p p

µ µ µ

µ µ

µ µ


Ein Problem bleibt allerdings…

� beide Berechnungsformeln hängen voneinander in der Weise ab, dass x zur Bestimmung von r benötigtwird und umgekehrt dass r zur Bestimmung von x benötigt wird

� Daher müssen wir ein iteratives Vorgehen anwenden, das sich schrittweise der optimalen Konstellation annähert

� Dazu wird der folgende Algorithmus angewendet


Iterativer Lösungsansatz

1. Anfangslösung

Wir bestimmen eine Anfangslösung für die Bestellmenge x0 mit Hilfe der klassischen Bestellmengenformel. Auf dieser Basis wird mit Hilfe der Berechnungsformel für r ein Anfangswert für den Bestellwert ermittelt

2. Aktualisierung der Bestellmenge x

Wir aktualisieren die Bestellmenge mit der Berechnungsformel für x auf der Basis der aktuellen Werte für x und r

3. Aktualisierung des Bestellpunktes r

Wir aktualisieren den Bestellpunkt mit der Berechnungsformel für r auf der Basis der aktuellen Werte für x und r

4. Frage der Terminierung

Fällt die Veränderungsrate für x und r unter einen vorgegebenen Schwellwert, wird die Berechnung gestoppt. Andernfalls werden die Schritte 2 bis 4 wiederholt

45


Annahme einer Normalverteilung

� Die Berechnungsformeln können wiederum etwas vereinfacht werden, wenn eine normalverteilte Nachfrage vorliegt

� In diesem Fall können wir die Formeln

� aufgrund der Beziehung

� formulieren als

( )( )2 ⋅ ⋅ ⋅ +=

LTJ r p k

xh

µ 1 1− ⋅= −

⋅ LT

h xr F

pµ

( ) ( ) , mit −

= ⋅ = LTLT LT

LT

rJ r L z z

µσ

σ

( )( )2 ⋅ ⋅ ⋅ ⋅ +=

LTL z p k

xh

µ σ 1

01, mit 1− ⋅

= + ⋅ = − ⋅

LT LT

h xr z z F

pµ σ

µ


Beispiel (vgl. Thonemann (2010) S.238ff)

� Wir betrachten folgende Konstellation, die sich beim Bestandsmanagement für Anschlusskabel für Toaster ergibt

� Wir gehen von einer normalverteilten Nachfrage aus mit den folgenden Daten

� Wir unterstellen eine 365 Tage Produktion

� Die fixen Bestellkosten betragen k=50€ pro Bestellung

� Die variablen Bestellkosten betragen c=0,9€ pro Stück

� Der Lagerhaltungskostensatz beträgt h=0,2€ pro Stück und Jahr

Erwartungswert der Nachfrage: 36500 Stück pro Jahr

Standardabweichung der Nachfrage: =1720 Stück pro Jahr

=µ

σ


Fehlmengenkosten

� Falls es nicht gelingt die erforderliche Menge an Anschlusskabeln bereitzustellen, wird der eigentliche Produktionsprozess am Band erheblich gestört

� So werden die Toaster in diesem Fall ohne Anschlusskabel gefertigt und – nach erfolgter Lieferung – in einem Offline Schritt neben dem Band montiert

� Dazu sind spezielle Verschraubungen der hinteren Abdeckung wieder zu lösen und das Kabel in die Schutzvorhängung einzuführen

� Aufgrund von Lagerung, zusätzlichen Arbeitsschritten und Effizienzverlusten entstehen so Mehrkosten von p=3€ je Stück

� Da die Fertigung der Kabel in Tschechien erfolgt, ergeben sich Lieferzeiten von LT=9 Tagen


Beispiel – Vorbereitung

� Zunächst berechnen wir den Erwartungswert und die Standardabweichung der Nachfrage über die Lieferzeit

� Offensichtlich ist die ursprüngliche Verteilung eine Faltung der einzelnen Perioden von jeweils 9 Tagen

� Damit gilt

365 9 936.500 900 Stück

9 365 365

365 9 91720 270 Stück

9 365 365

LT LT

LT LT LT

= ⋅ ⇔ = ⋅ = ⋅ =

= ⋅ ⇔ = ⋅ ⇔ = ⋅ =

µ µ µ µ

σ σ σ σ σ

46


Beispiel – Initialisierung

� Wir bestimmen die erste Bestellmenge mit Hilfe der klassischen Herleitungsformel

� Wir bestimmen den Bestellpunkt

� Damit ergibt sich der aktuelle Bestellpunkt

0

36500x 2 k 2 50 4272 Stück

h 0,2

µ= ⋅ ⋅ = ⋅ ⋅ =

( )1 1 1

01 01 01

0,2 42721 1 0,9922 2,42

36500 3

− − − ⋅ ⋅ = − = − = ≈

⋅ ⋅

h xz F F F

pµ

900 2,42 270 1553 Stück= + ⋅ = + ⋅ =LT LT

r zµ σ


Aktualisierung der Bestellmenge

� Wir benötigen zunächst den Wert für L(z)

� und berechnen für die Bestellmenge

( )( ) ( )2 2 36500 0,0026 270 3 50

0,2

4361 Stück

⋅ ⋅ ⋅ ⋅ + ⋅ ⋅ ⋅ ⋅ += =

=

LTL z p kx

h

µ σ

( ) ( )2,42 0,0026= =L z L


Aktualisierung des Bestellpunktes

� Wir berechnen zunächst

� Damit erhalten wir den neuen Bestellpunkt

� Veränderungen sind signifikant!

� Daher: Keine Terminierung!

( )1 1 1

01 01 01

0,2 43611 1 0,9920 2,41

36500 3

− − − ⋅ ⋅ = − = − = ≈

⋅ ⋅

h xz F F F

pµ

900 2,41 270 1551 Stück= + ⋅ = + ⋅ =LT LT

r zµ σ


Aktualisierung der Bestellmenge

� Wir benötigen zunächst den Wert für L(z)

� und berechnen für die neue Bestellmenge

( )( ) ( )2 2 36500 0,0026 270 3 50

0,2

4361 Stück

⋅ ⋅ ⋅ ⋅ + ⋅ ⋅ ⋅ ⋅ += =

=

LTL z p kx

h

µ σ

( ) ( )2,41 0,0026= =L z L

47


Aktualisierung des Bestellpunktes

� Wir berechnen zunächst

� Damit erhalten wir den neuen Bestellpunkt

� Keine Veränderungen erzielt

� Daher: Terminierung!

( )1 1 1

01 01 01

0,2 43611 1 0,9920 2,41

36500 3

− − − ⋅ ⋅ − = − = ≈

⋅ ⋅

h xF F F

pµ

900 2,41 270 1551 Stück= + ⋅ = + ⋅ =LT LT

r zµ σ


Ergebnis

� Aufgrund der gewählten Genauigkeit erhalten wir die optimale Lösung

� Damit erhalten wir als erwartete variable Bestellkosten,

� als erwartete fixe Bestellkosten

� als erwartete Lagerkosten

� und als erwartete Fehlmengenkosten

4361 1551 Stück= ∧ =x r

( ), 0,9 €/Stück 36500 Stück/Jahr = 32850= ⋅ = ⋅vB

K x r c µ

( )36500

, 50 418,484361

= ⋅ = ⋅ =fB

K x r kx

µ

( )4361

, 0,2 1551 900 566,32 2

= ⋅ + − ⋅ = ⋅ + − =

LB

xK x r h r LT µ

( ) ( ) ( )36500 36500

, 3 2,41 270 3 0,0026 270 17,624361 4361

= ⋅ ⋅ ⋅ = ⋅ ⋅ ⋅ = ⋅ ⋅ ⋅ =FM LTK x r p L z Lx

µσ


Gesamtkosten

� Damit erhalten wir erwartete Gesamtkosten in Höhe von

( ), 32850 418,48 566,3 17,62 33852,4= + + + =G

K x r


Sicherheitsbestand und -kosten

� Wir haben den Sicherheitsbestand

� Und damit die Sicherheitsbestandskosten

1551 Stück 900 Stück=651 Stück= − = −LTss r µ

0,2 651 130,2 €/Jahr⋅ = ⋅ =h ss

48


Pipelinebestand und -kosten

� Wir haben den Pipelinebestand

� Und damit die Pipelinebestandskosten

900 Stück= =LTps µ

0,2 900 180 €/Jahr⋅ = ⋅ = ⋅ =LTh ps h µ


α-Servicegrad

� In α Prozent aller Fälle darf kein Fehlbestand auftreten

� Damit wird ein Qualitätskriterium an Stelle der Fehlmengenkosten eingeführt

� Wir minimieren also die Gesamtkosten unter Beachtung des Qualitätskriteriums

� Hierdurch entsteht das folgende Modell

( )

( )

,2

unter der Nebenbedingung

= ⋅ + ⋅ + + − ⋅ ⋅

≥

G

LT

xK x r c k r LT h

x

F r

µµ µ

α


α-Servicegrad – Lösung des Modells

� Betrachten wir nun die neue Zielfunktion

� Wir sehen, dass die einzelnen Teile unabhängig voneinander behandelt werden können

� So gibt es keinen Teil, der von beiden Variablen gleichzeitig abhängt

� Damit kann leicht eine optimale Lösung ermittelt werden

( )

TeilTeil I

Teil IIkonstant, d.h. unabhängig von und Kostenfunktion des klassischen

Bestellmengenproblems

,2 2

2

= ⋅ + ⋅ + + − ⋅ ⋅ = ⋅ + ⋅ + ⋅ + ⋅ − ⋅ ⋅

= ⋅ − ⋅ ⋅ + ⋅ + ⋅ + ⋅��

��

G

x r

x xK x r c k r LT h c k h r h LT h

x x

xc LT h k h r h

x

µ µµ µ µ µ

µµ µ �

IIIKosten abhängig von

dem gewähltenBestellpunkt


Analyse der Bestandteile

� Teil I

� Ist unabhängig von der Bestellmenge x und vom Bestellpunkt r

� Damit kann dieser Teil ignoriert werden

� Teil II

� Entspricht der Zielfunktion des klassischen Bestellmengenmodells

� Da Teil III unabhängig von x ist, kann Teil II isoliert gelöst werden

� Daher setzen wir für x

� Teil III

� Steigt mit größeren Werten für den Bestellpunkt r

� Somit ist r zu minimieren. Hierdurch gilt

2 kx

h

⋅ ⋅µ=

( ) ( )1 1

01

− −= = + ⋅LT LT LT

r F Fα µ σ α

49


α-Servicegrad – Beispiel

� Wir betrachten wieder das Toaster Beispiel

� Wir fordern einen α-Servicegrad von 95 Prozent

� Damit ergeben sich

� als optimale Bestellmenge

� und als optimaler Bestellpunkt

2 2 50 365004272

0 2

kx

h ,

⋅ ⋅µ ⋅ ⋅= = =

( ) ( )1 1

010,95 900 270 0,95 900 270 1,64 1343 Stück− −= = + ⋅ ≈ + ⋅ =

LTr F F


Kosten im Beispiel

� Damit erhalten wir die Gesamtkosten

( ),2

36500 42720,9 36500 50 1343 900 0,2

4272 2

33793 €/Jahr

= ⋅ + ⋅ + + − ⋅ ⋅

= ⋅ + ⋅ + + − ⋅

=

G

xK x r c k r LT h

x

µµ µ


β-Servicegrad

� Ein Fehlbestand tritt in höchstens β Prozent aller Fälle in einem Bestellzyklus auf� Hierbei ist zu beachten, dass

� ein Bestellzyklus die Zeitspanne zwischen dem Auslösen zweier Bestellungen definiert

� JLT(r) die erwartete Fehlmenge berechnet, die in einem Bestellzyklus beim Bestellpunkt r auftritt und

� x die erwartete Verbrauchsmenge in einem Bestellzyklus definiert� Damit wird wiederum ein Qualitätskriterium an Stelle der Fehlmengenkosten

eingeführt� Wir minimieren wiederum die Gesamtkosten für diese Konstellation� Hierdurch entsteht das folgende Modell

( )

( )

,2

unter der Nebenbedingung 1

= ⋅ + ⋅ + + − ⋅ ⋅

− ≥

G

LT

xK x r c k r LT h

x

J r

x

µµ µ

β


β-Servicegrad – Lösung des Modells

� Die Lösung dieses Modells ist wesentlich komplexer als im Falle der Vorgabe eines α-Servicegrades

� So hängt leider die Erfüllung der Qualitätsbedingung simultan von beiden Variablen (x und r) ab

� Da die Lösung dieses Modells etwas komplexer ist, wollen wir der Einfachheit halber lediglich eine heuristische Lösung entwickeln

� Das Vorgehen der Heuristik ist sehr einfach gehalten

� So wird zunächst die optimale Bestellmenge mit Hilfe der

klassischen Bestellmengenformel bestimmt

� Anschließend wird r in der Weise determiniert, dass gerade der

geforderte β-Servicegrad erreicht wird

2 kx

h

⋅ ⋅µ=

50


β-Servicegrad – Lösung des Modells

� Dies geschieht durch die folgende Berechnungsformel

( ) ( )( ) ( ) ( )( )

( )

1

1

1 1 1 1

1

−

−

− = ⇔ − = ⇔ − ⋅ = ⇔ − ⋅ =

− ⋅⇔ =

LT LT

LT LT

LT

J r J rx J r J x r

x x

xL r

β β β β

β

σ


β-Servicegrad – Beispiel

� Wir betrachten wieder das Toaster Beispiel

� Wir fordern einen β-Servicegrad von 99 Prozent

� Damit ergeben sich

� als optimale Bestellmenge

� und als optimaler Bestellpunkt

2 2 50 365004272

0 2

kx

h ,

⋅ ⋅µ ⋅ ⋅= = =

( ) ( )( )1 1 11 1 0,99 42720,158 0,64

270

− − − − ⋅ − ⋅ = = = ≈

LT

xr L L L

β

σ


β-Servicegrad – Beispiel

� Und erhalten somit

� Damit ergeben sich die Gesamtkosten

900 0,64 270 1073 Stück∗= + ⋅ = + ⋅ =

LT LTr zµ σ

( ),2

36500 42720,9 36500 50 1073 900 0,2

4272 2

33739 €/Jahr

= ⋅ + ⋅ + + − ⋅ ⋅

= ⋅ + ⋅ + + − ⋅

=

G

xK x r c k r LT h

x

µµ µ