Klausurrepetitorium ABWL „Planungs- und Entscheidungstechniken · Langrange-Multiplikatoren-Methode 1.1.2 Bestimmung von Extrema mit den KKT-Bedingungen 1.2. Quotientenprogramm

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


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


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


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


19.08.05 SIHK Hagen


Bestimmung der kritischen Punkte


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


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


19.08.05 SIHK Hagen


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


19.08.05 SIHK Hagen


Interpretation des Lagrange-Multiplikators: SchattenpreisDer Lagrange-Multiplikator gibt an, um wieviel sich der Zielfunktionswert ändert, wenn sich um eine Einheit ändert.Beispiel:


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


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

= −

≤≥


9


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


19.08.05 SIHK Hagen


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


19.08.05 SIHK Hagen


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


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 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


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 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


19.08.05 SIHK Hagen

Einschub: Zusammenhang mit (5.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


19.08.05 SIHK Hagen

Ermittlung einer zulässigen Basislösung I


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


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


17


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 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


19.08.05 SIHK Hagen


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


19.08.05 SIHK Hagen

Beginn 1.Phase (II) und (III) mit (-1) multipliziert


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


19.08.05 SIHK Hagen

Subtraktion von (II) und (III) von (I)


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


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


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


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


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


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


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


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. 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


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


19.08.05 SIHK Hagen


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


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

⎛ ⎞⎛ ⎞⎛ ⎞ ⎛ ⎞ ⎛ ⎞− + =⎜ ⎟⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟

⎝ ⎠⎝ ⎠ ⎝ ⎠ ⎝ ⎠⎝ ⎠+ + =

≥


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


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


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


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


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 =


32


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


33


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


34


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


35


19.08.05 SIHK Hagen

Idee des Verfahrens von Isbell und Marlow (1)

Lösungsraum


36


19.08.05 SIHK Hagen


z(x)

n(x)


Der Schnittpunkt der Geraden z(x)=0 und n(x)=0 bestimmt die Hilfszielfunktionen

37


19.08.05 SIHK Hagen


Nullösung ist zulässige Ausgangslösung; über optimale Lösung des Hilfsproblems lässt sich über Konstruktionsvorschrift weiteresHilfsproblem bestimmen

z(x)

n(x)


38


19.08.05 SIHK Hagen


Konstruktionsvorschrift bei Isbell/Marlow: x0=z(x)-q(x*)n(x)


z(x)

n(x)

x0

39


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


40


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


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


42


19.08.05 SIHK Hagen


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


19.08.05 SIHK Hagen


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


19.08.05 SIHK Hagen


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


19.08.05 SIHK Hagen


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


19.08.05 SIHK Hagen


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


19.08.05 SIHK Hagen


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


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


19.08.05 SIHK Hagen


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


19.08.05 SIHK Hagen

2. Ganzzahlige lineare OptimierungP4

LösungKeine110

0,33625125

u.d.N.97 max

:P4

≥≥≥

≤+≤+

+=

yx

yxyxyx

yxz

51


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


19.08.05 SIHK Hagen


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


19.08.05 SIHK Hagen


)0 ; 10();(70

:Lösung10010

0,33625125

u.d.N.97 max

:P5

==

≤≤≥≥

≤+≤+

+=

yxz

xyx

yxyxyx

yxz

54


19.08.05 SIHK Hagen


LösungKeine11010

0,33625125

u.d.N.97 max

:P6

≥≤≥≥

≤+≤+

+=

xyx

yxyxyx

yxz

55


19.08.05 SIHK Hagen


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


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


19.08.05 SIHK Hagen


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


19.08.05 SIHK Hagen


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


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


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


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


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?

Documents

Klausurrepetitorium ABWL „Planungs- und Entscheidungstechniken · Langrange-Multiplikatoren-Methode 1.1.2 Bestimmung von Extrema mit den KKT-Bedingungen 1.2. Quotientenprogramm