Klausurrepetitorium ABWL „Planungs- und Entscheidungstechniken ·...

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

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

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

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)

max/min ( ,..., )u.d.N.

( ,..., ). . .. . .. . .( ,..., )

g x x b

Lagrangefunktion von f unter Nebenbedingungen:

1 1 1 1 1 1

( ,..., , ,..., )( ,..., ) ( ( ,..., ) ) ... ( ( ,.., ) )

n n m m n m

L x xf x x g x x b g x x b

λ λλ λ

+ − + + −

19.08.05 SIHK Hagen

Bestimmung der kritischen Punkte

0 1,...,ii

gL f i mx x x

λ∂∂ ∂

= + = =∂ ∂ ∂

0 1,...,ii

gL f i mx x x

λ∂∂ ∂

= + = =∂ ∂ ∂

1 0 1,...,i n ii

L g (x ,...,x ) b i mλ∂

= − = =∂

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),(

−−+=

xxxxxxf

)623(108),,( 212122

2121 −++−−+= xxxxxxxxL λλ

(0)1 1

(0)2 2

32 8 3 0 42

2 10 2 0 5

3 2 6 0

L x xxL x xxL x x

∂= − + = ⇒ = −

∂∂

= − + = ⇒ = −∂∂

= + − =∂

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:

06)5(2)234(3

=−−+−

TTxx ⎟

⎠⎞

⎜⎝⎛=

134),,( )0(

)0(1x (0)

(0) (0)1 2

4 33( , ) ,13 13

TTx x ⎛ ⎞= ⎜ ⎟

⎝ ⎠

mit (0) (0)1 2

3601( , ) 21,3169

f x x = − = −

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:

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 = − + = − = −

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.

f x x x

≤≥

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)

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

082082

≤−=∂∂

≤−+−⇔≥+−=∂∂

uxuxxL

19.08.05 SIHK Hagen

Gegeben: Nichtlineares Optimierungsproblem mit Ungleichungen als Restriktionen und nichtnegativenVariablen – 2-dim. Fall

2 21 2 1 2 1 2

min ( , ) 8 10u.d.N.3 2 6

f x x x x x x

x xx x

= + − −

+ ≤≥

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= + − − + + −

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

∂= − + ≥ ⇔ − + − ≤

∂∂

= − + ≥ ⇔ − + − ≤∂∂

= + − ≤∂

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

2 8 3 0 2 3 8

2 10 2 0 2 2 10

L x u v x u vxL x u v x u vxx x s

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

∂∂

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

19.08.05 SIHK Hagen

Einschub: Zusammenhang mit (5.7)?

1 00 1

H⎛ ⎞

=⎜ ⎟⎝ ⎠

TA⎛ ⎞

=⎜ ⎟⎝ ⎠

2 1 3 8

2 1 2 10

L x u vxL x u vxx x s

∂= − ⋅ ⋅ − + = −

∂∂

= − ⋅ ⋅ − + = −∂

1 2 1 2

1 0 3 8i) -2

0 1 2 10ii) 3 2 6iii) , , , , 0

x vx x s

x x v v s

−⎛ ⎞ ⎛ ⎞⎛ ⎞ ⎛ ⎞ ⎛ ⎞− + =⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟−⎝ ⎠ ⎝ ⎠ ⎝ ⎠⎝ ⎠ ⎝ ⎠

+ + =≥

19.08.05 SIHK Hagen

Ermittlung einer zulässigen Basislösung I

-801-30-2

-10-2-20

RHSux2x1

80-1302

RHSux2x1

Keine vollständige Einheitsbasis, daher Einführung von Hilfsvariable zj

19.08.05 SIHK Hagen

80-1302

RHSux2x1

-801-30-2

-10-2-20

RHSux2x1

Ermittlung einer zulässigen Basislösung II

19.08.05 SIHK Hagen

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

x vu z z

x vx x s

x x v v s

−⎛ ⎞ ⎛ ⎞⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞− + − − =⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟−⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠⎝ ⎠ ⎝ ⎠

+ + =≥

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

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

x vu z z

x vx x s

x x v v s

−⎛ ⎞ ⎛ ⎞⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞− + − − =⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟−⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠⎝ ⎠ ⎝ ⎠

+ + =≥

19.08.05 SIHK Hagen

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

011000000

-8001-30-2

-10-1-2-20

z2 RHSux2x1

011000000

800-1302

101220

z2 RHSux2x1

19.08.05 SIHK Hagen

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

-1800011-5-2-2

800-1302

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

19.08.05 SIHK Hagen

-1800011-5-2-2

800-1302

101220

z2 RHSux2x1

-1800111-501

800-1302

30013/2

4120-3

z2 RHSux2x1

19.08.05 SIHK Hagen

-1800111-501

800-1302

30013/2

4120-3

z2 RHSux2x1

-185/30-3/2-3/2100-13/2

8-3/23/2-10013/2

30013/2

21/210-3/2

z2 RHSux2x1

19.08.05 SIHK Hagen

011000000

4/13-3/133/13-2/13001

33/13-9/26010

32/132/13100

z2 RHSux2x1

-185/30-3/2-3/2100-13/2

8-3/23/2-10013/2

30013/2

21/210-3/2

z2 RHSux2x1

19.08.05 SIHK Hagen

011000000

4/13-3/133/13-2/13001

33/13-9/26010

32/132/13100

z2 RHSux2x1

1. Phase abgeschlossen, d.h. zulässige Basislösung gefunden:

1 24 33( , ) ,

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

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

min ( , ) 8 10u.d.N.3 2 6

f x x x x x x

x xx x

= + + +

+ ≤≥

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= + + + + + −

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:

19.08.05 SIHK Hagen

1 2 1 2

1 0 0 3 8i) -2 0

0 1 0 2 10ii) 3 2 6iii) , , , , 0

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

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

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

u.d.N.)()( max

≥≤

dxdcxcq T

19.08.05 SIHK Hagen

Beispiel1 2

20 15 ( )max 5 5 20 ( )

u.d.N.4 177 3 31

x x z xqx x n x

x xx x

+ ≤+ ≤≤

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

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 =

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 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 ⋅ + ⋅= =

⋅ + ⋅ +

0000-15-20

1700114

RHSs1x2x1

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

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 sx x s

x sx x s s s

= + − ⋅ + +

= + −

+ + =+ + =+ =

* 20 1 15 8 140 28( )5 1 5 12 20 65 13

q x ⋅ + ⋅= = =

⋅ + + ⋅ +

-560/13000-55/13-120/13

1700114

RHSs1x2x1

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!

- 560/13000-55/13-120/13

1700114

RHSs1x2x1

19.08.05 SIHK Hagen

Idee des Verfahrens von Isbell und Marlow (1)

Lösungsraum

19.08.05 SIHK Hagen

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

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

19.08.05 SIHK Hagen

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

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

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

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

19.08.05 SIHK Hagen

Beispiel:

max z=7 3u.d.N.5 2 51 (I)2 6 33 (II), 0 und ganzzahlig

x yx y

+ ≤+ ≤≥

Lösungsraum eines ILP

19.08.05 SIHK Hagen

max z=7 3u.d.N.5 2 51 (I)2 6 33 (II), 0

x yx y

+ ≤+ ≤≥

LP-Relaxation und Lösungsraum des zugehörigen LP

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)

x yx y

+ ≤+ ≤≥

LP-Relaxation und Lösung des zugehörigen LP

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)

x yx y

+ ≤+ ≤≥

Aufspaltung in Teilprobleme P1 und P2

71,88( ; ) (9, 23 ; 2, 42)zx y=

9x ≤ 10x ≥

19.08.05 SIHK Hagen

P1:max z=7 3u.d.N.5 2 51 (I)2 6 33 (II)

( ; ) (9 ; 2,5)

x yx y

xx yLösungzx y

+ ≤+ ≤≤≥

19.08.05 SIHK Hagen

P2 :max z=7 3u.d.N.5 2 51 (I)2 6 33 (II)

( ; ) (10 ; 0,5)

x yx y

xx yLösungzx y

+ ≤+ ≤≥≥

19.08.05 SIHK Hagen

2. Ganzzahlige lineare OptimierungAufspaltung von P2 in Teilprobleme P3 und P4, da zP2=71,5>zP1=70,5

71,88( ; ) (9, 23 ; 2, 42)zx y=

9x ≤ 10x ≥70,5

( ; ) (9 ; 2,5)zx y=

( ; ) (10 ; 0,5)zx y=

1y ≥

0y ≤

19.08.05 SIHK Hagen

P3 :max z=7 3u.d.N.5 2 512 6 33, 0

:71, 4

( ; ) (10, 2 ; 0)

x yx y

x yxyLösungzx y

+ ≤+ ≤≥

≥≤

19.08.05 SIHK Hagen

2. Ganzzahlige lineare OptimierungP4

LösungKeine110

0,33625125

u.d.N.97 max

≥≥≥

≤+≤+

yxyxyx

19.08.05 SIHK Hagen

2. Ganzzahlige lineare OptimierungAufspaltung in Teilprobleme P3 und P4

71,88( ; ) (9, 23 ; 2, 42)zx y=

9x ≤ 10x ≥70,5

( ; ) (9 ; 2,5)zx y=

( ; ) (10 ; 0,5)zx y=

1y ≥

0y ≤

71, 4( ; ) (10, 2 ; 0)zx y=

Keine Lösung

19.08.05 SIHK Hagen

71,88( ; ) (9, 23 ; 2, 42)zx y=

10x ≥70,5

( ; ) (9 ; 2,5)zx y=

( ; ) (10 ; 0,5)zx y=

1y ≥

0y ≤

71, 4( ; ) (10, 2 ; 0)zx y=

=Keine Lösung

9x ≤

10x ≤ 11x ≥

19.08.05 SIHK Hagen

)0 ; 10();(70

:Lösung10010

0,33625125

u.d.N.97 max

≤≤≥≥

≤+≤+

yxyxyx

19.08.05 SIHK Hagen

LösungKeine11010

0,33625125

u.d.N.97 max

≥≤≥≥

≤+≤+

yxyxyx

19.08.05 SIHK Hagen

71,88( ; ) (9, 23 ; 2, 42)zx y=

10x ≥70,5

( ; ) (9 ; 2,5)zx y=

( ; ) (10 ; 0,5)zx y=

1y ≥

0y ≤

71, 4( ; ) (10, 2 ; 0)zx y=

=Keine Lösung

9x ≤

10x ≤ 11x ≥

Keine Lösung

70( ; ) (10 ; 0)zx y=

19.08.05 SIHK Hagen

2. Ganzzahlige lineare OptimierungAufspaltung von P2 in Teilprobleme P7 und P8, da zP2=70,5>zP5=70

71,88( ; ) (9, 23 ; 2, 42)zx y=

10x ≥70,5

( ; ) (9 ; 2,5)zx y=

( ; ) (10 ; 0,5)zx y=

1y ≥

0y ≤

71, 4( ; ) (10, 2 ; 0)zx y=

=Keine Lösung

9x ≤

10x ≤ 11x ≥

Keine Lösung

70( ; ) (10 ; 0)zx y=

2y ≤ 3y ≥

19.08.05 SIHK Hagen

P7 :max z=7 3u.d.N.5 2 512 6 33, 0

( ; ) (9;2)

x yx y

x yxyzx y

+ ≤+ ≤≥

≤≤=

19.08.05 SIHK Hagen

P8 :max z=7 3u.d.N.5 2 512 6 33, 0

9361,5

( ; ) (7,5 ; 3)

x yx y

x yxyzx y

+ ≤+ ≤≥

≤≥=

19.08.05 SIHK Hagen

2. Ganzzahlige lineare OptimierungAufspaltung von P2 in Teilprobleme P7 und P8

71,88( ; ) (9, 23 ; 2, 42)zx y=

10x ≥70,5

( ; ) (9 ; 2,5)zx y=

( ; ) (10 ; 0,5)zx y=

1y ≥

0y ≤

71, 4( ; ) (10, 2 ; 0)zx y=

=Keine Lösung

9x ≤

10x ≤ 11x ≥

Keine Lösung

70( ; ) (10 ; 0)zx y=

2y ≤ 3y ≥

69( ; ) (9 ; 2)zx y=

( ; ) (7,5 ; 3)zx y=

19.08.05 SIHK Hagen

2. Ganzzahlige lineare OptimierungOptimale Lösung als beste aller zulässigen Lösungen

71,88( ; ) (9, 23 ; 2, 42)zx y=

10x ≥70,5

( ; ) (9 ; 2,5)zx y=

( ; ) (10 ; 0,5)zx y=

1y ≥

0y ≤

71,4( ; ) (10,2 ; 0)zx y=

=Keine Lösung

9x ≤

10x ≤ 11x ≥

Keine Lösung

70( ; ) (10 ; 0)zx y=

2y ≤ 3y ≥

69( ; ) (9 ; 2)zx y=

( ; ) (7,5 ; 3)zx y=

19.08.05 SIHK Hagen

2. Ganzzahlige lineare OptimierungOptimale Lösung als beste aller zulässigen Lösungen

71,88( ; ) (9, 23 ; 2, 42)zx y=

10x ≥70,5

( ; ) (9 ; 2,5)zx y=

( ; ) (10 ; 0,5)zx y=

1y ≥

0y ≤

71, 4( ; ) (10, 2 ; 0)zx y=

=Keine Lösung

9x ≤

10x ≤ 11x ≥

Keine Lösung

70( ; ) (10 ; 0)zx y=

2y ≤ 3y ≥

69( ; ) (9 ; 2)zx y=

( ; ) (7,5 ; 3)zx y=

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?

Klausurrepetitorium ABWL „Planungs- und Entscheidungstechniken ·...

Documents

Leistungsportfolio der KKT Kratochwil GmbH · •Beratung, Planung und Ausführung, zugeschnitten auf individuelle Konzepte •Klimaanlagen in sämtlichen Bereichen, wie Heim, Gewerbe

Leistungsportfolio des Firmenverbundes KKT … · • fachgerechte Planung, zugeschnitten auf individuelle Konzepte ... wie z.B. ein Wildkühlanhänger für das Thüringer Ministerium

Bedienungsanleitung Wagner Alumedic mit Dondula · Dondola® apoya la columna vertebral óptimamente. Debido a la posibilidad de ajustar una inclinación extrema hacia adelante, usted

ANEXO III - Ed 09 2018 Conteúdo Programático …...DDD - Domain-Driven Design. Modelagem ágil: Programação extrema (eXtreme Programming Modelagem ágil: Programação extrema

Verteilte Systeme · 2019. 10. 22. · Verteilte Systeme Seite: 9 Weitere interessante Bücher und Paper (2) Chang E., Roberts R.:An improved algorithm for decentralized extrema-finding

GALLETTI - Kaltwassersysteme - KKT COOL · 2016. 3. 8. · Die Galletti - Gruppe kann heute auf über 1,5 Millionen verkaufte Geräte und 250.000 installierte Anlagen zurückblicken,

Das Datenaufnahmesystem fur das¨ Elektronenpaar ... · Symmetrie, dem Erwartungswert des Mesonenfeldes und der Hadronenmasse fehlt bis heute. Wahrend man also an den beiden Extrema

gabe der RiLSA liegen die Extrema bei m/s und 2,45 m/s. Setzt man die Richt linie von m/s als Grenze an, so halten 21 diesen Grenzwert ein oderliegen darun ter, 20 liegen darüber

Zürcher Fachhochschule Medienethik zwischen Publizistik und Ökonomie 1 Entscheidungstechniken: Analyserahmen von Barbara Thomass und Potter Pox 23. Oktober

2018 wird ein großes Jahr für die DONOTS: Die Band hat ... BOOKING KKT GMBH Humberto Pereira humberto@kkt.berlin MANAGEMENT DONOTS office@donots.com PRESSE DONOTS presse@donots.com

(1) Ronda Extrema Men - License Overall

Geomorphologische Systeme ExtremA 2018 · Geomorphologische Systeme xtrem & Risikoforschung ** * ** ExtremA 2018 Aktueller Wissensstand zu Extremereignissen . alpiner Naturgefahren

Institut für Technologie- und Prozessmanagement (ITOP) · Strategie, Technologie & Innovation, Prozesse tics ss t t Quantitative Entscheidungstechniken Das ITOP ist in der Wissenschaft

»Elastomertechnik ist im Kommen« - kkt-group.com · IntervIew »Elastomertechnik ist im Kommen« Im Gespräch mit Dr. Sven Vogt, geschäftsführender Gesellschafter der KKT Gruppe

ARTÍCULOS ORIGINALES intensivos intensive care unit · 2017-07-13 · Pupo Jiménez JM, et al. Morbilidad materna extrema según causas de admisión en cuidados intensivos. Vol.16,

Input: Entscheidungstechniken

160523 Programm KKT - Berliner Missionswerk · „Schmecket und sehet, ... Musikshow für die ganze Familie / Music for the whole family 14.45 UHR: „SYMPHONIC PERCUSSION BERLIN“

DEHA Kugelkopf Transportankersystem · Dieser Katalog entspricht der Einbau- und Verwen-dungsanleitung gemäß Richtlinie VDI/BV-BS 6205 DEHA KUGELKOPF-TRANSPORTANKERSYSTEM KKT 13

St ll t Stellenwert von Levosimendan in der Therapie kritisch ti kkt …dbknb.de/dbk/ai/weiterbildung/intensiv-stammtisch... · 2011-07-14 · Levosimendan in der Therapie kritisch

PVP 18,90 - PlanetadeLibros · 2020. 11. 12. · campesino que vive al borde de la pobreza extrema y una minoría de aristócratas tan sólo preocupados por defender sus privilegios