0
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
Klausurrepetitorium ABWL„Planungs- und Entscheidungstechniken“
Südwestfälische Industrie- und Handelskammer
19. August 2005
Dr. Friedhelm Kulmann, Sandra Rudolph
1
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
Gliederung
1. Nichtlineare Optimierungsprobleme1.1. Quadratisches Programm
1.1.1 Exkurs: Bestimmung von Extrema mit Langrange-Multiplikatoren-Methode
1.1.2 Bestimmung von Extrema mit den KKT-Bedingungen
1.2. Quotientenprogramm
2. Lösung ganzzahliger linearer Optimierungsprobleme mit Branch & Bound
2
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
1. Nichtlineare Optimierungsprobleme
• Viele betriebswirtschaftlichen Fragestellungen führen zurOptimierung nichtlinearer Probleme (bspw. optimales Portfolio, optimales Werbeprogramm unterBerücksichtigung nichtlinearer Werberesponsefunktionen etc.)
• Besonderheit: Lineare Funktionen in den Nebenbedingungen• Versuch der Lösung dieser Probleme mit bekannten
Verfahren (Simplex-Verfahren)⇒ Transformation der nichtlinearen Zielfunktion in eine
lineare• Anwendung des Lösungsverfahrens auf das (Hilfs)problem• Ggfs. Übertragung der Lösung des Hilfsproblems auf das
Ausgangsproblem
3
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
1.1 Quadratisches Programm
Gegeben: Nichtlineares Optimierungsproblem mit Gleichungenals Restriktionen
Exkurs: Bestimmung der Extrema mit Hilfe der Lagrange-Methode (1)
1
1 1 1
1
max/min ( ,..., )u.d.N.
( ,..., ). . .. . .. . .( ,..., )
n
n
m n m
f x x
g x x b
g x x b
=
=
Lagrangefunktion von f unter Nebenbedingungen:
1 1
1 1 1 1 1 1
( ,..., , ,..., )( ,..., ) ( ( ,..., ) ) ... ( ( ,.., ) )
n m
n n m m n m
L x xf x x g x x b g x x b
λ λλ λ
=
+ − + + −
4
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
1.1 Quadratisches Programm
Bestimmung der kritischen Punkte
Exkurs: Bestimmung der Extrema mit Hilfe der Lagrange-Methode (2)
1 1 1
0 1,...,ii
gL f i mx x x
λ∂∂ ∂
= + = =∂ ∂ ∂
0 1,...,ii
n n n
gL f i mx x x
λ∂∂ ∂
= + = =∂ ∂ ∂
...
1 0 1,...,i n ii
L g (x ,...,x ) b i mλ∂
= − = =∂
5
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
1.1 Quadratisches ProgrammExkurs: Bestimmung der Extrema mit Hilfe der Lagrange-Methode (3)Gegeben: Zielfunktion und Gleichungen
in den Nebenbedingungen
Lagrangefunktion von f unter Nebenbedingung:
Partielle Ableitungen gleich Null setzen:
623),(u.d.N.
108),(
2121
2122
2121
=+=
−−+=
xxxxg
xxxxxxf
)623(108),,( 212122
2121 −++−−+= xxxxxxxxL λλ
(0)1 1
1
(0)2 2
2
1 2
32 8 3 0 42
2 10 2 0 5
3 2 6 0
L x xxL x xxL x x
λ λ
λ λ
λ
∂= − + = ⇒ = −
∂∂
= − + = ⇒ = −∂∂
= + − =∂
6
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
1.1 Quadratisches Programm
Beispiel (Fortführung)Exkurs: Bestimmung der Extrema mit Hilfe der Lagrange-Methode (4)
Einsetzen von und in die Restriktionen
Lösung:
Kritischer Punkt:
1332
06)5(2)234(3
=⇒
=−−+−
λ
λλ
TTxx ⎟
⎠⎞
⎜⎝⎛=
1332,
1333,
134),,( )0(
2)0(
1 λ
)0(1x (0)
2x
(0) (0)1 2
4 33( , ) ,13 13
TTx x ⎛ ⎞= ⎜ ⎟
⎝ ⎠
mit (0) (0)1 2
3601( , ) 21,3169
f x x = − = −
7
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
1.1 Quadratisches Programm
Interpretation des Lagrange-Multiplikators: SchattenpreisDer Lagrange-Multiplikator gibt an, um wieviel sich der Zielfunktionswert ändert, wenn sich um eine Einheit ändert.Beispiel:
Exkurs: Bestimmung der Extrema mit Hilfe der Lagrange-Methode (4)
iλib
2 21 2 1 2 1 2
1 2 1 2
( , ) 8 10u.d.N.
( , ) 3 2 5
f x x x x x x
g x x x x
= + − −
= + =
(0) (0)1 2
3601 32 3185( , ) 18,84169 13 169
f x x = − + = − = −
8
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
Bestimmung der Extrema mit Hilfe der Karush-Kuhn-Tucker-Bedingungen (1)Gegeben: Nichtlineares Optimierungsproblem mit
Ungleichungen als Restriktionen und nichtnegativenVariablen – 1-dimensionaler Fall
2min ( ) 8u.d.N.
30
f x x x
xx
= −
≤≥
1.1 Quadratisches Programm
9
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
Lagrangefunktion von f unter Nebenbedingung (u bezeichnetden Multiplikator):
Die Lagrangefunktion nimmt im Sattelpunkt ihr Minimum in x und ihr Maximum in u an
2( , ) 8 ( 3)L x u x x u x= − + −
1.1 Quadratisches ProgrammBestimmung der Extrema mit Hilfe der KKT-Bedingungen (2)
Anm.: Die Ausführungen gelten für reguläre Probleme, d.h. gewisse Regularitätsbedingungenmüssen erfüllt sein (s. Kurs 854)
10
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
1.1 Quadratisches ProgrammBestimmung der Extrema mit Hilfe der KKT-Bedingungen (3)
Lagrangefunktion nimmt im Sattelpunkt ihr Minimum in x und ihr Maximum in u an Da Nichtnegativitätsbedingung für x gegeben, ist partielle Ableitung >= bzw. <= Null
03
082082
≤−=∂∂
≤−+−⇔≥+−=∂∂
xxL
uxuxxL
11
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
1.1 Quadratisches ProgrammBestimmung der Extrema mit Hilfe der KKT-Bedingungen (4)
Gegeben: Nichtlineares Optimierungsproblem mit Ungleichungen als Restriktionen und nichtnegativenVariablen – 2-dim. Fall
2 21 2 1 2 1 2
1 2
1 2
min ( , ) 8 10u.d.N.3 2 6
, 0
f x x x x x x
x xx x
= + − −
+ ≤≥
12
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
Lagrangefunktion von f unter Nebenbedingung (u bezeichnetden Multiplikator):
Minimum der Langrangefunktion (unter Berücksichtigung der NNB) in x gegeben, wenn partielle Ableitungen nach xj >= Null und nach u <= Null
2 21 2 1 2 1 2 1 2( , , ) 8 10 (3 2 6)L x x u x x x x u x x= + − − + + −
1.1 Quadratisches ProgrammBestimmung der Extrema mit Hilfe der KKT-Bedingungen (5)
1 11
2 22
1 2
2 8 3 0 2 8 3 0
2 10 2 0 2 10 2 0
3 2 6 0
L x u x uxL x u x uxL x xu
∂= − + ≥ ⇔ − + − ≤
∂∂
= − + ≥ ⇔ − + − ≤∂∂
= + − ≤∂
13
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
Um die optimale Lösung zu bestimmen, führen wir Schlupfvariable vj
und s ein, um Ungleichungen in Gleichungen zu überführen
Bedingungen:
1.1 Quadratisches ProgrammBestimmung der Extrema mit Hilfe der KKT-Bedingungen (6)
1 1 1 11
2 2 2 22
1 2
2 8 3 0 2 3 8
2 10 2 0 2 2 10
3 2 6
L x u v x u vxL x u v x u vxx x s
∂= − + − + = ⇔ − − + = −
∂∂
= − + − + = ⇔ − − + = −∂
+ + =
14
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
Einschub: Zusammenhang mit (5.7)?
1.1 Quadratisches ProgrammBestimmung der Extrema mit Hilfe der KKT-Bedingungen (7)
1 00 1
H⎛ ⎞
=⎜ ⎟⎝ ⎠
32
TA⎛ ⎞
=⎜ ⎟⎝ ⎠
1 11
2 22
1 2
2 1 3 8
2 1 2 10
3 2 6
L x u vxL x u vxx x s
∂= − ⋅ ⋅ − + = −
∂∂
= − ⋅ ⋅ − + = −∂
+ + =
1 1
2 2
1 2
1 2 1 2
1 0 3 8i) -2
0 1 2 10ii) 3 2 6iii) , , , , 0
x vu
x vx x s
x x v v s
−⎛ ⎞ ⎛ ⎞⎛ ⎞ ⎛ ⎞ ⎛ ⎞− + =⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟−⎝ ⎠ ⎝ ⎠ ⎝ ⎠⎝ ⎠ ⎝ ⎠
+ + =≥
15
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
Ermittlung einer zulässigen Basislösung I
1.1 Quadratisches ProgrammBestimmung der Extrema mit Hilfe der KKT-Bedingungen (8)
1
0
0
s
-801-30-2
0
1
v2
0
0
v1
6023
-10-2-20
RHSux2x1
1
0
0
s
80-1302
0
-1
v2
0
0
v1
6023
10220
RHSux2x1
Keine vollständige Einheitsbasis, daher Einführung von Hilfsvariable zj
16
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
0
0
1
z1
0
1
0
z2
1
0
0
s
80-1302
0
-1
v2
0
0
v1
6023
10220
RHSux2x1
0
0
-1
z1
0
-1
0
z2
1
0
0
s
-801-30-2
0
1
v2
0
0
v1
6023
-10-2-20
RHSux2x1
Ermittlung einer zulässigen Basislösung II
1.1 Quadratisches ProgrammBestimmung der Extrema mit Hilfe der KKT-Bedingungen (9)
17
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
1 2
1 11 2
2 2
1 2
1 2 1 2
min u.d.N.
1 0 3 1 0 8i) -2
0 1 2 0 1 10ii) 3 2 6iii) , , , , 0
Z z z
x vu z z
x vx x s
x x v v s
= +
−⎛ ⎞ ⎛ ⎞⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞− + − − =⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟−⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠⎝ ⎠ ⎝ ⎠
+ + =≥
1.1 Quadratisches ProgrammBestimmung der Extrema mit Hilfe der KKT-Bedingungen (10)
1 11 2
2 2
1 2
1 2 1 2
1 0 3 1 0 8i) -2
0 1 2 0 1 10ii) 3 2 6iii) , , , , 0
x vu z z
x vx x s
x x v v s
−⎛ ⎞ ⎛ ⎞⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞− + − − =⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟−⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠⎝ ⎠ ⎝ ⎠
+ + =≥
Modifizierte KKT-Bedingungen nach Einführung der Hilfsvariable
Zu lösendes Hilfsproblem zur Bestimmung einer zulässigen Basislösung mittels 2-Phasen-Simplex
18
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
1.1 Quadratisches ProgrammBestimmung der Extrema mit Hilfe der KKT-Bedingungen (11)
u und s, v1 und x1 sowie v2 und x2 sind zueinander komplementäre Variable, daher dürfen sie nicht zusammen in die Basis. Aufgrund dessen vierte Bedingung:
1 1 2 2iv) 0, 0, 0v x v x s u⋅ = ⋅ = ⋅ =
1 2
1 11 2
2 2
1 2
1 2 1 2
min u.d.N.
1 0 3 1 0 8i) -2
0 1 2 0 1 10ii) 3 2 6iii) , , , , 0
Z z z
x vu z z
x vx x s
x x v v s
= +
−⎛ ⎞ ⎛ ⎞⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞− + − − =⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟−⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠⎝ ⎠ ⎝ ⎠
+ + =≥
19
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
Beginn 1.Phase (II) und (III) mit (-1) multipliziert
1.1 Quadratisches ProgrammBestimmung der Extrema mit Hilfe der KKT-Bedingungen (12)
011000000
1
0
0
s
0
0
-1
z1
-8001-30-2
0
1
v2
0
0
v1
60023
-10-1-2-20
z2 RHSux2x1
011000000
1
0
0
s
0
0
1
z1
800-1302
0
-1
v2
0
0
v1
60023
101220
z2 RHSux2x1
20
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
Subtraktion von (II) und (III) von (I)
1.1 Quadratisches ProgrammBestimmung der Extrema mit Hilfe der KKT-Bedingungen (13)
s
z2
z1
-1800011-5-2-2
1
0
0
s
0
0
1
z1
800-1302
0
-1
v2
0
0
v1
60023
101220
z2 RHSux2x1
1 1 2 2iv) 0, 0, 0v x v x s u⋅ = ⋅ = ⋅ =
Weil s in der Basis ist, darf u nicht aufgenommen werden, daher x1 oder x2
21
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
s
z2
z1
-1800011-5-2-2
1
0
0
s
0
0
1
z1
800-1302
0
-1
v2
0
0
v1
60023
101220
z2 RHSux2x1
1.1 Quadratisches ProgrammBestimmung der Extrema mit Hilfe der KKT-Bedingungen (14)
x2
z2
z1
-1800111-501
1/2
-1
0
s
0
0
1
z1
800-1302
0
-1
v2
0
0
v1
30013/2
4120-3
z2 RHSux2x1
22
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
x2
z2
z1
-1800111-501
½
-1
0
s
0
0
1
z1
800-1302
0
-1
v2
0
0
v1
30013/2
4120-3
z2 RHSux2x1
1.1 Quadratisches ProgrammBestimmung der Extrema mit Hilfe der KKT-Bedingungen (15)
x2
u
z1
-185/30-3/2-3/2100-13/2
½
-1/2
3/2
S
0
0
1
z1
8-3/23/2-10013/2
0
-1/2
v2
0
0
v1
30013/2
21/210-3/2
z2 RHSux2x1
23
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
x2
u
x1
011000000
2/13
-2/13
3/13
s
-3/13
3/13
2/13
z1
4/13-3/133/13-2/13001
-9/26
-2/13
v2
3/13
-3/13
v1
33/13-9/26010
32/132/13100
z2 RHSux2x1
1.1 Quadratisches ProgrammBestimmung der Extrema mit Hilfe der KKT-Bedingungen (16)
x2
u
z1
-185/30-3/2-3/2100-13/2
½
-1/2
3/2
S
0
0
1
z1
8-3/23/2-10013/2
0
-1/2
v2
0
0
v1
30013/2
21/210-3/2
z2 RHSux2x1
24
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
1.1 Quadratisches ProgrammBestimmung der Extrema mit Hilfe der KKT-Bedingungen (17)
x2
u
x1
011000000
2/13
-2/13
3/13
s
-3/13
3/13
2/13
z1
4/13-3/133/13-2/13001
-9/26
-2/13
v2
3/13
-3/13
v1
33/13-9/26010
32/132/13100
z2 RHSux2x1
1. Phase abgeschlossen, d.h. zulässige Basislösung gefunden:
1 24 33( , ) ,
13 13
TTx x ⎛ ⎞= ⎜ ⎟
⎝ ⎠mit 1 2
3601( , ) 21,3169
f x x = − = −
1 2 1 2
1 0 4 /13 3 8i) -2 32 /13
0 1 33/13 2 10ii) 3 4 /13 2 33/13 6iii) , , , , 0x x v v s
−⎛ ⎞⎛ ⎞ ⎛ ⎞ ⎛ ⎞− =⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟−⎝ ⎠⎝ ⎠ ⎝ ⎠ ⎝ ⎠
⋅ + ⋅ =≥
1 1 2 2iv) 0, 0, 0v x v x s u⋅ = ⋅ = ⋅ =
25
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
1.1 Quadratisches ProgrammBeispiel für Nulllösung als optimale Lösung (1)
Gegeben: Nichtlineares Optimierungsproblem mit Ungleichungen als Restriktionen und nichtnegativenVariablen
2 21 2 1 2 1 2
1 2
1 2
min ( , ) 8 10u.d.N.3 2 6
, 0
f x x x x x x
x xx x
= + + +
+ ≤≥
26
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
1.1 Quadratisches ProgrammBeispiel für Nulllösung als optimale Lösung (2)
Lagrangefunktion:2 2
1 2 1 2 1 2 1 2( , , ) 8 10 (3 2 6)L x x u x x x x u x x= + + + + + −
1 11
2 22
1 2
2 8 3 0 2 8 3 0
2 10 2 0 2 10 2 0
3 2 6 0
L x u x uxL x u x uxL x xu
∂= + + ≥ ⇔ − − − ≤
∂∂
= + + ≥ ⇔ − − − ≤∂∂
= + − ≤∂
Partielle Ableitungen:
27
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
1
2
1 2
1 2 1 2
1 0 0 3 8i) -2 0
0 1 0 2 10ii) 3 2 6iii) , , , , 0
vv
x x sx x v v s
⎛ ⎞⎛ ⎞⎛ ⎞ ⎛ ⎞ ⎛ ⎞− + =⎜ ⎟⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟
⎝ ⎠⎝ ⎠ ⎝ ⎠ ⎝ ⎠⎝ ⎠+ + =
≥
1.1 Quadratisches ProgrammBeispiel für Nulllösung als optimale Lösung (3)
Prüfung, ob für Nulllösung KKT-Bedingungen erfüllt sindWenn ja, dann ist Nulllösung optimale LösungWenn nein, dann gehe vor wie ab Folie 18 beschrieben
1 1 2 2iv) 0, 0, 0v x v x s u⋅ = ⋅ = ⋅ =
Anmerkung: u ist gleich Null, weil die Kapazitäten nicht berührt werden und daher der Schattenpreis Null ist
28
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
1.1 Quadratisches ProgrammAnmerkungen
Wie sehen die KKT-Bedingungen aus, wenn ein Maximierungs-problem vorliegt und kein Minimierungproblem? Warum?[Fragen nicht klausurrelevant!]
29
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
1.2 QuotientenprogrammProblemstellung
Betriebswirtschaftliche Entscheidungsprobleme stellen sich häufig als Maximierung einer Verhältnisgröße dar; Zähler und Nenner sinddabei lineare Funktionen der Entscheidungsvariablen
0
u.d.N.)()( max
0
0
≥≤
=++
=
xbAx
xnxz
dxdcxcq T
T
30
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
Beispiel1 2
1 2
1 2
1 2
2
1 2
20 15 ( )max 5 5 20 ( )
u.d.N.4 177 3 31
8, 0
x x z xqx x n x
x xx x
xx x
+= =
+ +
+ ≤+ ≤≤
≥
1 2
1 2
1 2 1
1 2 2
2 3
1 2 1 2 3
20 15 ( )max 5 5 20 ( )
u.d.N.4 177 3 31
8, , , , 0
x x z xqx x n x
x x sx x s
x sx x s s s
+= =
+ +
+ + =+ + =+ =
≥
Einführung der Schlupfvariablen
1.2 Quotientenprogramm
31
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
1. Zulässige Ausgangslösung x* suchen
Da Konstante im Nenner d0>0 ist, gilt für alle zulässigen Lösungenn(x) ≠ 0
Daher kann mit der Nullösung gestartet werden.
( ) ( )1 2 1 2 3, , , , 0,0,17,31,8x x s s s =
1.2 Quotientenprogramm
32
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
2. Hilfsprogramm aufstellen und lösenmax x0=z(x)-q(x*)n(x)
0 1 2 1 2
1 2 1
1 2 2
2 3
1 2 1 2 3
max 20 15 0 (5 5 20)u.d.N.4 177 3 31
8, , , , 0
x x x x x
x x sx x s
x sx x s s s
= + − ⋅ + +
+ + =+ + =+ =
≥
20 0 15 0( *) 05 0 5 0 20
q x ⋅ + ⋅= =
⋅ + ⋅ +
0
0
0
1
x0
0000-15-20
1700114
1
0
s3
0
1
s2
8010
31037
RHSs1x2x1
1.2 Quotientenprogramm
33
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
x0 ≠ 0 Setze x0:=x* und gehe wieder zu 2.
( ) ( )0 1 2 1 2 3
Lösung:, , , , , 140,1,8,5,0,0x x x s s s =
0 1 2 1 2
0 1 2
1 2 1
1 2 2
2 3
1 2 1 2 3
2820 15 (5 5 20)13
120 55 560max 13 13 13
u.d.N.4 177 3 31
8, , , , 0
x x x x x
x x x
x x sx x s
x sx x s s s
= + − ⋅ + +
= + −
+ + =+ + =+ =
≥
* 20 1 15 8 140 28( )5 1 5 12 20 65 13
q x ⋅ + ⋅= = =
⋅ + + ⋅ +
0
0
0
1
x0
-560/13000-55/13-120/13
1700114
1
0
s3
0
1
s2
8010
31037
RHSs1x2x1
1.2 Quotientenprogramm
34
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
( ) ( )0 1 2 1 2 3
Lösung:, , , , , 0,1,8,5,0,0x x x s s s =
x0 = 0 Optimale Lösung gefunden!
0
0
0
1
x0
- 560/13000-55/13-120/13
1700114
1
0
s3
0
1
s2
8010
31037
RHSs1x2x1
1.2 Quotientenprogramm
35
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
Idee des Verfahrens von Isbell und Marlow (1)
Lösungsraum
1.2 Quotientenprogramm
36
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
Idee des Verfahrens von Isbell und Marlow (2)
z(x)
n(x)
1.2 Quotientenprogramm
Der Schnittpunkt der Geraden z(x)=0 und n(x)=0 bestimmt die Hilfszielfunktionen
37
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
Idee des Verfahrens von Isbell und Marlow (3)
Nullösung ist zulässige Ausgangslösung; über optimale Lösung des Hilfsproblems lässt sich über Konstruktionsvorschrift weiteresHilfsproblem bestimmen
z(x)
n(x)
1.2 Quotientenprogramm
38
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
Idee des Verfahrens von Isbell und Marlow (4)
Konstruktionsvorschrift bei Isbell/Marlow: x0=z(x)-q(x*)n(x)
1.2 Quotientenprogramm
z(x)
n(x)
x0
39
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
Idee des Verfahrens von Isbell und Marlow (5)Optimale Lösung gefunden, wenn keine Verbesserung mehr möglich,d.h. Verfahren würde keine neue „Ecke“ des Polyeders aufsuchen
1.2 Quotientenprogramm
40
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
2. Ganzzahlige lineare Optimierung
• In der Praxis finden Methoden der linearen Optimierung breiteAnwendung
• Bei einigen Problemen ist die Ganzzahligkeitsforderungfür alle Strukturvariable (ILOP) oder für einige Variable (MILP)gegeben
• Verfahren der ganzzahligen Optimierung gehen von optimalerLösung des zugehörigen nicht-ganzzahligen Problems aus undermitteln dann sukzessiv die optimale Lösung des ganzzahligenProblems durch Einschränkung des Lösungsraums
• Entscheidungsbaumverfahren: Branch & Bound
41
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
B & B ist ein spezielles Enumerationsverfahren
⇒ Suche nach Optimallösung durch Aufspalten des Lösungs-raums des LPs ohne Ganzzahligkeitsforderung
⇒ Aufspaltung lässt sich als Verzweigung im Entscheidungsbaum darstellen
2. Ganzzahlige lineare Optimierung
42
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
2. Ganzzahlige lineare Optimierung
Beispiel:
max z=7 3u.d.N.5 2 51 (I)2 6 33 (II), 0 und ganzzahlig
x y
x yx y
x y
+
+ ≤+ ≤≥
Lösungsraum eines ILP
(I)
(II)
43
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
2. Ganzzahlige lineare Optimierung
max z=7 3u.d.N.5 2 51 (I)2 6 33 (II), 0
x y
x yx y
x y
+
+ ≤+ ≤≥
LP-Relaxation und Lösungsraum des zugehörigen LP
44
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
2. Ganzzahlige lineare Optimierung
max z=7 3u.d.N.5 2 51 (I)2 6 33 (II), 0
Lösung:( ; ) (9, 23;2, 42)
71,88
x y
x yx y
x y
x yz
+
+ ≤+ ≤≥
==
LP-Relaxation und Lösung des zugehörigen LP
45
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
2. Ganzzahlige lineare Optimierung
max z=7 3u.d.N.5 2 51 (I)2 6 33 (II), 0
Lösung:( ; ) (9, 23;2, 42)
71,88
x y
x yx y
x y
x yz
+
+ ≤+ ≤≥
==
Aufspaltung in Teilprobleme P1 und P2
P0
71,88( ; ) (9, 23 ; 2, 42)zx y=
=
P1 P2
9x ≤ 10x ≥
46
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
2. Ganzzahlige lineare Optimierung
P1:max z=7 3u.d.N.5 2 51 (I)2 6 33 (II)
9, 0
:70,5
( ; ) (9 ; 2,5)
x y
x yx y
xx yLösungzx y
+
+ ≤+ ≤≤≥
==
P1
47
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
2. Ganzzahlige lineare Optimierung
P2 :max z=7 3u.d.N.5 2 51 (I)2 6 33 (II)
10, 0
:71,5
( ; ) (10 ; 0,5)
x y
x yx y
xx yLösungzx y
+
+ ≤+ ≤≥≥
==
P2
48
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
2. Ganzzahlige lineare OptimierungAufspaltung von P2 in Teilprobleme P3 und P4, da zP2=71,5>zP1=70,5
P0
71,88( ; ) (9, 23 ; 2, 42)zx y=
=
P1 P2
9x ≤ 10x ≥70,5
( ; ) (9 ; 2,5)zx y=
=71,5
( ; ) (10 ; 0,5)zx y=
=
P4
1y ≥
P3
0y ≤
49
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
2. Ganzzahlige lineare Optimierung
P3 :max z=7 3u.d.N.5 2 512 6 33, 0
100
:71, 4
( ; ) (10, 2 ; 0)
x y
x yx y
x yxyLösungzx y
+
+ ≤+ ≤≥
≥≤
==
P3
50
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
2. Ganzzahlige lineare OptimierungP4
LösungKeine110
0,33625125
u.d.N.97 max
:P4
≥≥≥
≤+≤+
+=
yx
yxyxyx
yxz
51
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
2. Ganzzahlige lineare OptimierungAufspaltung in Teilprobleme P3 und P4
P0
71,88( ; ) (9, 23 ; 2, 42)zx y=
=
P1 P2
9x ≤ 10x ≥70,5
( ; ) (9 ; 2,5)zx y=
=71,5
( ; ) (10 ; 0,5)zx y=
=
P4
1y ≥
P3
0y ≤
71, 4( ; ) (10, 2 ; 0)zx y=
=
Keine Lösung
52
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
2. Ganzzahlige lineare OptimierungAufspaltung von P3 in Teilprobleme P5 und P6, da zP3=71,4>zP2=70,5
P0
71,88( ; ) (9, 23 ; 2, 42)zx y=
=
P1 P2
10x ≥70,5
( ; ) (9 ; 2,5)zx y=
=71,5
( ; ) (10 ; 0,5)zx y=
=
P4
1y ≥
P3
0y ≤
71, 4( ; ) (10, 2 ; 0)zx y=
=Keine Lösung
P6P5
9x ≤
10x ≤ 11x ≥
53
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
2. Ganzzahlige lineare OptimierungP5
)0 ; 10();(70
:Lösung10010
0,33625125
u.d.N.97 max
:P5
==
≤≤≥≥
≤+≤+
+=
yxz
xyx
yxyxyx
yxz
54
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
2. Ganzzahlige lineare OptimierungP6
LösungKeine11010
0,33625125
u.d.N.97 max
:P6
≥≤≥≥
≤+≤+
+=
xyx
yxyxyx
yxz
55
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
2. Ganzzahlige lineare OptimierungAufspaltung von P3 in Teilprobleme P5 und P6, da zP3=71,4>zP2=70,5
P0
71,88( ; ) (9, 23 ; 2, 42)zx y=
=
P2 P1
10x ≥70,5
( ; ) (9 ; 2,5)zx y=
=71,5
( ; ) (10 ; 0,5)zx y=
=
P4
1y ≥
P3
0y ≤
71, 4( ; ) (10, 2 ; 0)zx y=
=Keine Lösung
P6P5
9x ≤
10x ≤ 11x ≥
Keine Lösung
70( ; ) (10 ; 0)zx y=
=
56
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
2. Ganzzahlige lineare OptimierungAufspaltung von P2 in Teilprobleme P7 und P8, da zP2=70,5>zP5=70
P0
71,88( ; ) (9, 23 ; 2, 42)zx y=
=
P2 P1
10x ≥70,5
( ; ) (9 ; 2,5)zx y=
=71,5
( ; ) (10 ; 0,5)zx y=
=
P4
1y ≥
P3
0y ≤
71, 4( ; ) (10, 2 ; 0)zx y=
=Keine Lösung
P6P5
9x ≤
10x ≤ 11x ≥
Keine Lösung
70( ; ) (10 ; 0)zx y=
=
P8P7
2y ≤ 3y ≥
57
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
2. Ganzzahlige lineare OptimierungP7
P7 :max z=7 3u.d.N.5 2 512 6 33, 0
9269
( ; ) (9;2)
x y
x yx y
x yxyzx y
+
+ ≤+ ≤≥
≤≤=
=
58
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
2. Ganzzahlige lineare OptimierungP8
P8 :max z=7 3u.d.N.5 2 512 6 33, 0
9361,5
( ; ) (7,5 ; 3)
x y
x yx y
x yxyzx y
+
+ ≤+ ≤≥
≤≥=
=
59
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
2. Ganzzahlige lineare OptimierungAufspaltung von P2 in Teilprobleme P7 und P8
P0
71,88( ; ) (9, 23 ; 2, 42)zx y=
=
P2 P1
10x ≥70,5
( ; ) (9 ; 2,5)zx y=
=71,5
( ; ) (10 ; 0,5)zx y=
=
P4
1y ≥
P3
0y ≤
71, 4( ; ) (10, 2 ; 0)zx y=
=Keine Lösung
P6P5
9x ≤
10x ≤ 11x ≥
Keine Lösung
70( ; ) (10 ; 0)zx y=
=
P8P7
2y ≤ 3y ≥
69( ; ) (9 ; 2)zx y=
=61,5
( ; ) (7,5 ; 3)zx y=
=
60
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
2. Ganzzahlige lineare OptimierungOptimale Lösung als beste aller zulässigen Lösungen
P0
71,88( ; ) (9, 23 ; 2, 42)zx y=
=
P2 P1
10x ≥70,5
( ; ) (9 ; 2,5)zx y=
=71,5
( ; ) (10 ; 0,5)zx y=
=
P4
1y ≥
P3
0y ≤
71,4( ; ) (10,2 ; 0)zx y=
=Keine Lösung
P6P5
9x ≤
10x ≤ 11x ≥
Keine Lösung
70( ; ) (10 ; 0)zx y=
=
P8P7
2y ≤ 3y ≥
69( ; ) (9 ; 2)zx y=
=61,5
( ; ) (7,5 ; 3)zx y=
=
61
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
2. Ganzzahlige lineare OptimierungOptimale Lösung als beste aller zulässigen Lösungen
P0
71,88( ; ) (9, 23 ; 2, 42)zx y=
=
P2 P1
10x ≥70,5
( ; ) (9 ; 2,5)zx y=
=71,5
( ; ) (10 ; 0,5)zx y=
=
P4
1y ≥
P3
0y ≤
71, 4( ; ) (10, 2 ; 0)zx y=
=Keine Lösung
P6P5
9x ≤
10x ≤ 11x ≥
Keine Lösung
70( ; ) (10 ; 0)zx y=
=
P8P7
2y ≤ 3y ≥
69( ; ) (9 ; 2)zx y=
=61,5
( ; ) (7,5 ; 3)zx y=
=
62
Planungs- und Entscheidungs-techniken
19.08.05 SIHK Hagen
2. Ganzzahlige lineare OptimierungAnmerkungen
• Mit Hilfe der Auswahlregel wird bestimmt, in welcher Reihen-folge die Teilprobleme bearbeitet werden.
• Regel der größten Schranke: Bei einem Maximierungsproblemdas als nächstes behandeln, welches noch nicht untersucht wurde und die größte Schranke (ZFW) besitzt.
• LIFO-Regel: Das zuletzt behandelte Teilproblem wird solangeweiter untersucht, bis es ausgeschieden werden kann.
Vor- und Nachteile beider Regeln bzgl. Kriterien, die bei der computergestützten Optimierung relevant sind?