Teil VIII: Optimierung im Rn in:

Michael Merz

Übungsbuch zur Mathematik für Wirtschaftswissenschaftler, page 364 - 419

450 Klausur- und Übungsaufgaben mit ausführlichen Lösungen

1. Edition 2013, ISBN print: 978-3-8006-4720-0, ISBN online: 978-3-8006-4721-7, https://doi.org/10.15358/9783800647217_364

Bibliographic information
Teil VIII: Optimierung im Rn 24. Nichtlineare Optimierung im Rn * Aufgabe 24.1 (MC-Aufgaben zur Optimierung im Rn ohne Nebenbedingungen) Kreuzen Sie an, welche der Aussagen a) bis e) wahr und welche falsch sind: a) Ist x0 eine Extremalstelle einer partiell differenzierbaren Funktion f : D ⊆ Rn −→ R im Inneren des Definitionsbereiches D, dann gilt grad f (x0) = 0. b) Die stationären Stellen einer partiell differenzierbaren Funktion f : D ⊆ Rn −→ R stimmen mit den Extremalstellen von f überein. c) Ist f : D ⊆ Rn −→ R eine partiell differenzierbare Funktion auf einer offenen Menge D, dann ist grad f (x0) = 0 eine hinreichende Bedingung für eine Extremalstelle von f an der Stelle x0. d) Ist f : D ⊆ Rn −→ R eine partiell differenzierbare Funktion auf einer offenenMenge D, dann sind durch die stationären Stellen von f bereits alle Kandidaten für lokale und globale Extremalstellen gegeben. e) Ist x0 ∈ D eine stationäre Stelle einer partiell differenzierbaren Funktion f : D ⊆ Rn −→ R, die keine Extremalstelle ist, dann wird x0 als Sattel- oder Terrassenpunkt bezeichnet. a) b) c) d) e) Wahr Falsch Lehrbuch: Abschnitt 24.2 Lösung: Zu a): Wahre Aussage (vgl. Satz 24.1 im Lehrbuch). Zu b): Falsche Aussage. Die stationären Stellen einer partiell differenzierbaren Funktion f : D ⊆ Rn −→ R sind lediglich die Kandidaten für lokale und globale Extrema, die im Inneren des DefinitionsbereichesD liegen. Das heißt, eine stationäre Stelle von f muss keine Extremalstelle von f sein. Ferner können die Stellen, die auf dem Rand ∂D des DefinitionsbereichesD liegen, Extremalstellen von f sein, obwohl sie keine stationären Stellen von f sind (vgl. Seite 709 im Lehrbuch). Zu c): Falsche Aussage. Bei grad f (x0) = 0 handelt es sich um eine notwendige, aber keine hinreichende Bedingung für eine Extremalstelle von f an der Stelle x0 (vgl. Satz 24.1 und Beispiel 24.2b) im Lehrbuch). Zu d): Wahre Aussage (vgl. Seite 709 im Lehrbuch). Zu e): Wahre Aussage (vgl. Seite 709 im Lehrbuch). ** Aufgabe 24.2 (MC-Aufgaben zur Optimierung im Rn ohne Nebenbedingungen) Kreuzen Sie an, welche der Aussagen a) bis e) wahr und welche falsch sind: a) Für eine stationäre Stelle x0 ∈ D einer zweimal stetig partiell differenzierbaren Funktion f : D ⊆ Rn −→ R ermöglicht die Hesse-Matrix Hf (x0) eine eindeutige Aussage darüber, ob x0 eine Extremalstelle von f ist oder nicht. b) Ist x0 ∈ D eine stationäre Stelle einer zweimal stetig partiell differenzierbaren Funktion f : D ⊆ Rn −→ R und ist die Hesse-Matrix Hf (x0) positiv semidefinit, dann ist x0 keine lokale Maximalstelle von f . 355 Kapitel 24 Teil VIII: Optimierung im Rn c) Ist x0 ∈ D eine stationäre Stelle einer zweimal stetig partiell differenzierbaren Funktion f : D ⊆ Rn −→ R und ist die Hesse-Matrix Hf (x0) negativ semidefinit, dann ist x0 eine lokale Maximalstelle oder ein Sattelpunkt von f . d) Ist x0 ∈ D eine stationäre Stelle einer stetig partiell differenzierbaren und konvexen Funktion f : D ⊆ Rn −→ R, dann ist x0 eine globale Minimalstelle von f . e) Eine Funktion f : D ⊆ Rn −→ R kann nicht mehrere globale Minimal- und Maximalstellen besitzen. a) b) c) d) e) Wahr Falsch Lehrbuch: Abschnitt 24.2 Lösung: Zu a): Falsche Aussage. Die Hesse-Matrix Hf (x0) liefert nur dann eine eindeutige Aussage über die Extremaleigenschaften von x0, wenn Hf (x0) positiv definit, negativ definit oder indefinit ist (vgl. Satz 24.3a)–c) imLehrbuch). Falls dieHesse-MatrixHf (x0)nur positiv oder negativ semidefinit ist, dann istmit Hilfe von Hf (x0) keine eindeutige Aussage über die Extremaleigenschaften von x0 möglich (vgl. Satz 24.3d) und e) im Lehrbuch). Zu b): Wahre Aussage. Bei einer lokalen Maximalstelle x0 von f ist die Hesse-Matrix Hf (x0) negativ semidefinit (vgl. Satz 24.3e) im Lehrbuch). Zu c): Wahre Aussage. Die Stelle x0 kann keine lokale Minimalstelle von f sein, da bei einer lokalen Minimalstelle die Hesse-Matrix Hf (x0) positiv semidefinit ist (vgl. Satz 24.3d) im Lehrbuch). Zu d): Wahre Aussage (vgl. Satz 24.5 im Lehrbuch). Zu e): Falsche Aussage. Eine Funktion f : D ⊆ Rn −→ R kann durchaus mehrere globale Minimal- und Maximalstellen aufweisen. Diese globalenMinimal- undMaximalstellen führen dann jedoch alle zum gleichen globalen Minimum bzw. Maximum. * Aufgabe 24.3 (Optimierung im Rn ohne Nebenbedingungen) Es sei f : D ⊆ R2 −→ R, (x, y) *→ f (x, y) eine zweimal stetig partiell differenzierbare Funktion auf einer offenen Menge D mit (x0, y0) ∈ D und grad f (x0, y0) = (0, 0)T . Welche Folgerung ergibt sich jeweils bei den folgenden Bedingungen? a) ∂ 2f (x0,y0) ∂x2 < 0, ∂ 2f (x0,y0) ∂y2 < 0 und ∂ 2f (x0,y0) ∂x2 · ∂2f (x0,y0) ∂y2 > ( ∂2f (x0,y0) ∂y∂x )2 b) ∂ 2f (x0,y0) ∂x2 > 0, ∂ 2f (x0,y0) ∂y2 > 0 und ∂ 2f (x0,y0) ∂x2 · ∂2f (x0,y0) ∂y2 = ( ∂2f (x0,y0) ∂y∂x )2 c) ∂ 2f (x0,y0) ∂x2 > 0, ∂ 2f (x0,y0) ∂y2 < 0 und ∂ 2f (x0,y0) ∂x2 · ∂2f (x0,y0) ∂y2 > ( ∂2f (x0,y0) ∂y∂x )2 d) ∂ 2f (x0,y0) ∂x2 < 0, ∂ 2f (x0,y0) ∂y2 > 0 und ∂ 2f (x0,y0) ∂x2 · ∂2f (x0,y0) ∂y2 < ( ∂2f (x0,y0) ∂y∂x )2 e) ∂ 2f (x0,y0) ∂x2 > 0, ∂ 2f (x0,y0) ∂y2 > 0 und ∂ 2f (x0,y0) ∂x2 · ∂2f (x0,y0) ∂y2 > ( ∂2f (x0,y0) ∂y∂x )2 Lehrbuch: Abschnitt 24.2 Lösung: Für die Determinante der Hesse-Matrix von f gilt allgemein det ( Hf (x, y) ) = ∂2f (x, y) ∂x2 · ∂ 2f (x, y) ∂y2 − ( ∂2f (x, y) ∂y∂x )2 . Zu a): Unter diesen Bedingungen gilt ∂ 2f (x0,y0) ∂x2 < 0 und det ( Hf (x, y) ) > 0. Bei der Stelle (x0, y0) handelt es sich somit um eine lokale Maximalstelle von f (vgl. Folgerung 24.10b) im Lehrbuch). 356 Kapitel 24Nichtlineare Optimierung im Rn Zu b): Unter diesen Bedingungen gilt det ( Hf (x, y) ) = 0. Es ist daher keine Aussage möglich, ob es sich bei (x0, y0) um die Stelle eines Sattelpunktes oder um eine lokale Extremalstelle von f handelt (vgl. Seite 718 im Lehrbuch). Zu c) und e): Unter diesen Bedingungen gilt ∂ 2f (x0,y0) ∂x2 > 0 und det ( Hf (x, y) ) > 0. Bei der Stelle (x0, y0) handelt es sich somit um eine lokale Minimalstelle von f (vgl. Folgerung 24.10a) im Lehrbuch). Zu d): Unter diesen Bedingungen gilt det ( Hf (x, y) ) < 0. Bei der Stelle (x0, y0) handelt es sich daher um die Stelle eines Sattelpunktes von f (vgl. Folgerung 24.10e) im Lehrbuch). * Aufgabe 24.4 (Anwendung der Optimierung im Rn ohne Nebenbedingungen) Betrachtet wird ein Unternehmen, das zwei verschiedene Produkte A und B herstellt. Dabei wird angenommen, dass die Gesamtkosten K zur Herstellung von x Einheiten von Produkt A sowie y Einheiten von Produkt B durch eine Funktion mit der Zuordnungsvorschrift K(x, y) = x2 − 2xy + 2y2 − 10x + 15 beschrieben werden und die gesamte Produktion zu Preisen von 8 Euro für Produkt A und 6 Euro für Produkt B abgesetzt werden kann. a) Stellen Sie die Erlösfunktion E(x, y) und die Gewinnfunktion G(x, y) des Unternehmens auf. b) Bestimmen Sie die gewinnmaximierenden Produktionsmengen x und y sowie den maximalen Gewinn. Lehrbuch: Abschnitt 24.2 Lösung: Zu a): Die Erlösfunktion E(x, y) und die Gewinnfunktion G(x, y) lauten E(x, y) = 8x + 6y bzw. G(x, y) = E(x, y)−K(x, y) = 8x + 6y − ( x2 − 2xy + 2y2 − 10x + 15 ) = −x2 − 2y2 + 2xy + 18x + 6y − 15. Zu b): Für den Gradienten und die Hesse-Matrix von G an der Stelle (x, y) gilt gradG(x, y) = ( ∂G(x, y) ∂x , ∂G(x, y) ∂y )T = (−2x + 2y + 18,−4y + 2x + 6)T und HG(x, y) = ∂ 2G(x,y) ∂x2 ∂2G(x,y) ∂x∂y ∂2G(x,y) ∂y∂x ∂2G(x,y) ∂y2 = (−2 2 2 −4 ) . Die stationären Stellen von f erhält man als Lösungen des folgenden linearen Gleichungssystems: −2x + 2y = −18 2x − 4y = −6 Durch elementare Zeilenumformungen folgt daraus, dass (21, 12) die einzige stationäre Stelle von G ist. Für die Determinante von HG(x, y) gilt ferner det (HG(x, y)) = 8− 4 = 4 > 0 für alle (x, y) (vgl. (8.42) imLehrbuch). Zusammenmit ∂ 2G(x,y) ∂x2 = −2 < 0 für alle (x, y) impliziert dies, dass (21, 12) eine globale Maximalstelle von G ist (vgl. Folgerung 24.10d) im Lehrbuch). Der maximale Gewinn beträgt somit f (21, 12) = 210. 357 Kapitel 24 Teil VIII: Optimierung im Rn ** Aufgabe 24.5 (Anwendung der Optimierung im Rn ohne Nebenbedingungen) Eine Ackerfläche wird mit Getreide bestellt. Zuvor werden x Mengeneinheiten vom Kunstdünger der Sorte 1 und y Mengeneinheiten vom Kunstdünger der Sorte 2 ausgestreut. Aus langjähriger Erfahrung weiß der Landwirt, dass der Ertrag in Abhängigkeit von der Düngung bei normalen Wetterbedingungen im relevanten Bereich näherungsweise durch eine Funktion mit der Zuordnungsvorschrift f (x, y) = −x2 − 2y2 + xy + 7x + 14y + 100 beschrieben wird. a) Bestimmen Sie x und y derart, dass der Landwirt einen maximalen Ertrag erzielt. Berechnen Sie den maximalen Ertrag und erläutern Sie, ob es sich dabei um das globale Maximum von f handelt. b) Ermitteln Sie mit Hilfe des totalen Differentials, wie sich der Ertrag näherungsweise ändert, wenn der Landwirt den Düngereinsatz von (x, y) = (6, 6) auf (6, 5) verändert. Vergleichen Sie diesen Näherungswert mit dem exakten Wert. Lehrbuch: Abschnitte 22.3 und 24.2 Lösung: Zu a): Für den Gradienten und die Hesse-Matrix von f an der Stelle (x, y) gilt grad f (x, y) = ( ∂f (x, y) ∂x , ∂f (x, y) ∂y )T = (−2x + y + 7,−4y + x + 14)T und Hf (x, y) = ∂ 2f (x,y) ∂x2 ∂2f (x,y) ∂x∂y ∂2f (x,y) ∂y∂x ∂2f (x,y) ∂y2 = (−2 1 1 −4 ) . Die stationären Stellen von f erhält man als Lösungen des folgenden linearen Gleichungssystems: −2x + y = −7 x − 4y = −14 Daraus folgt durch elementare Zeilenumformungen, dass (6, 5) die einzige stationäre Stelle von f ist. Für die Determinante von Hf (x, y) gilt ferner det ( Hf (x, y) ) = 8− 1 = 7 > 0 für alle (x, y) (vgl. (8.42) im Lehrbuch). Zusammen mit ∂ 2f (x,y) ∂x2 = −2 < 0 für alle (x, y) impliziert dies, dass (6, 5) eine globale Maximalstelle von f ist (vgl. Folgerung 24.10d) im Lehrbuch). Der maximale Ertrag beträgt somit f (6, 5) = 156. Zu b): Bei einer Veränderung des Düngereinsatzes von (x, y) = (6, 6) auf (6, 5) gilt dx = 0 und dy = −1. Das totale Differential an der Stelle (6, 6) ist daher gegeben durch df = ∂f (6, 6) ∂x dx + ∂f (6, 6) ∂y dy = 1 · 0+ (−4)(−1) = 4 (vgl. (22.20) im Lehrbuch). Der exakte Wert der Veränderung beträgt dagegen f (6, 5)− f (6, 6) = 156− 154 = 2. ** Aufgabe 24.6 (Optimierung im Rn ohne Nebenbedingungen) Betrachtet wird die reellwertige Funktion f : R3 −→ R, (x, y, z) *→ 2x2ey + 2y2 + 2z2. a) Ermitteln Sie die stationären Stellen von f . b) Bestimmen Sie die lokalen Extremalstellen und Sattelpunkte von f . Geben Sie an, ob es sich bei den lokalen Extremalstellen um globale Extremalstellen handelt. 358 Kapitel 24Nichtlineare Optimierung im Rn Lehrbuch: Abschnitt 24.2 Lösung: Zu a): Für den Gradienten von f an der Stelle (x, y, z) ∈ R3 gilt grad f (x, y, z) = ( ∂f (x, y, z) ∂x , ∂f (x, y, z) ∂y , ∂f (x, y, z) ∂z )T = ( 4xey, 2x2ey + 4y, 4z )T . Durch Lösen des (nichtlinearen) Gleichungssystems 4xey = 0 (24.1) 2x2ey + 4y = 0 (24.2) 4z = 0 (24.3) erhält man die stationären Stellen von f . Die Gleichung (24.1) besitzt offensichtlich die Lösung x = 0 und die dritte Gleichung (24.3) die Lösung z = 0. Wird x = 0 in die Gleichung (24.2) eingesetzt, erhält man y = 0. Das heißt, die Funktion f besitzt nur die stationäre Stelle (0, 0, 0). Zu b): Die Hesse-Matrix von f an der Stelle (x, y, z) ∈ R3 ist gegeben durch Hf (x, y, z) = ∂2f (x,y,z) ∂x2 ∂2f (x,y,z) ∂x∂y ∂2f (x,y,z) ∂x∂z ∂2f (x,y,z) ∂y∂x ∂2f (x,y,z) ∂y2 ∂2f (x,y,z) ∂y∂z ∂2f (x,y,z) ∂z∂x ∂2f (x,y,z) ∂z∂y ∂2f (x,y,z) ∂z2 = 4ey 4xey 04xey 2x2ey + 4 0 0 0 4 . Für die Hesse-Matrix speziell an der stationären Stelle (0, 0, 0) (vgl. Aufgabenteil a)) erhält man somit Hf (0, 0, 0) = 4 0 00 4 0 0 0 4 . Da die Diagonalmatrix Hf (0, 0, 0) ausschließlich positive Hauptdiagonaleinträge besitzt, ist sie positiv definit (vgl. Satz 10.32a) im Lehrbuch). Folglich handelt es sich bei der stationären Stelle (0, 0, 0) um eine lokale Minimalstelle von f (vgl. Satz 24.3a) im Lehrbuch). Wegen f (x, y, z) = 2x2ey + 2y2 + 2z2 ≥ 0 = f (0, 0, 0) für alle (x, y, z) ∈ R3 ist (0, 0, 0) sogar eine globale Minimalstelle von f . Ferner gilt, dass der Definitionsbereich von f keine Randstellen umfasst und die Funktion f partiell differenzierbar ist. Folglich muss eine Extremalstelle von f eine stationäre Stelle sein (vgl. Satz 24.1 im Lehrbuch). Da jedoch die Funktion f neben (0, 0, 0) keine weiteren stationären Stellen aufweist, impliziert dies, dass f keine anderen Extremalstellen oder Stellen mit Sattelpunkten besitzt. ** Aufgabe 24.7 (Anwendung der Optimierung im Rn ohne Nebenbedingungen) Ein Produzent bietet zwei Güter an. Zwischen den Absatzmengen x und y sowie den Güterpreisen p1 und p2 bestehen die Beziehungen x(p1, p2) = 50− p1 − 1 2 p2 und y(p1, p2) = 60− 1 2 p1 − 3 2 p2. Die Produktionskosten für die beiden Güter sind gegeben durch c1(x) = 60+ 1 2 x und c2(y) = 60+ 1 2 y. a) Bestimmen Sie den Gewinn des Produzenten G(p1, p2) als Funktion der beiden Preise. b) Ermitteln Sie die Preise p1 und p2, für welche der Gewinn maximal ist und geben Sie den maximalen Gewinn an. c) Der Produzent setzt den Preis des zweiten Gutes bei p2 = 10 fest. Bestimmen Sie den Preis des ersten Gutes, so dass der Gewinn maximal ist. 359 Kapitel 24 Teil VIII: Optimierung im Rn Lehrbuch: Abschnitt 24.2 Lösung: Zu a): Der Gewinn des Produzenten G(p1, p2) in Abhängigkeit von den beiden Güterpreisen p1 und p2 ist gegeben durch die Differenz von Erlösfunktion E(p1, p2) und Kostenfunktion K(p1, p2): G(p1, p2) = E(p1, p2)−K(p1, p2) = p1 · x(p1, p2)+ p2 · y(p1, p2)− c1(x)− c2(y) = p1 · x(p1, p2)+ p2 · y(p1, p2)− ( 60+ 1 2 x(p1, p2) ) − ( 60+ 1 2 y(p1, p2) ) = x(p1, p2) ( p1 − 12 ) + y(p1, p2) ( p2 − 12 ) − 120 = ( 50− p1 − 12p2 )( p1 − 12 ) + ( 60− 1 2 p1 − 32p2 )( p2 − 12 ) − 120 = −p21 − 3 2 p22 − p1p2 + 50,75p1 + 61p2 − 175 Zu b): Für den Gradienten und die Hesse-Matrix von G an der Stelle (p1, p2) gilt gradG(p1, p2) = ( ∂G(p1, p2) ∂p1 , ∂G(p1, p2) ∂p2 )T = (−2p1 − p2 + 50,75;−3p2 − p1 + 61)T und HG(x, y) = ∂ 2G(p1,p2) ∂p21 ∂2G(p1,p2) ∂p1∂p2 ∂2G(p1,p2) ∂p2∂p1 ∂2G(p1,p2) ∂p22 = (−2 −1−1 −3 ) . Die stationären Stellen von G sind gegeben als Lösungen des folgenden linearen Gleichungssystems: −2p1 − p2 = −50,75 −p1 − 3p2 = −61 Durch elementare Zeilenumformungen erhält man, dass (18,25; 14,25) die einzige stationäre Stelle vonG ist. Für die Determinante von HG(x, y) folgt det (HG(p1, p2)) = 6− 1 = 5 > 0 für alle (p1, p2) (vgl. (8.42) imLehrbuch). Zusammenmit ∂2G(p1,p2) ∂p21 = −2 < 0 für alle (x, y) impliziert dies, dass (18,25; 14,25) eine globaleMaximalstelle vonG ist (vgl. Folgerung 24.10d) im Lehrbuch). Der maximale Gewinn beträgt folglich G(18,25; 14,25) = 722,7188. Zu c): Wird der Preis des zweiten Gutes bei p2 = 10 festgesetzt, dann vereinfacht sich die Gewinnfunktion zu G(p1, 10) = −p21 − 150− 10p1 + 50,75p1 + 610− 175 = −p21 + 40,75p1 + 285. Für die erste und zweite Ableitung von G erhält man G′(p1, 10) = −2p1 + 40,75 bzw. G′′(p1, 10) = −2. Folglich gilt G′(p1, 10) = 0 genau dann, wenn p1 = 20,375 ist. Das heißt, p1 = 20,375 ist die einzige stationäre Stelle von G(p1, 10). Wegen G ′′(p1, 10) = −2 < 0 für alle p1, handelt es sich bei p1 = 20,375 um die globale Maximalstelle von G(p1, 10) (vgl. Folgerung 18.8b) im Lehrbuch). ** Aufgabe 24.8 (Optimierung im Rn ohne Nebenbedingungen) Betrachtet wird die reellwertige Funktion f : R3 −→ R, (x, y, z) *→ −4x2 − 2y2 − 1 2 z2 + 4xy + yz+ 100z. a) Ermitteln Sie die stationären Stellen von f . b) Untersuchen Sie f mit Hilfe der Hesse-Matrix auf Konvexität bzw. Konkavität. c) Bestimmen Sie die Extremalstellen und Sattelpunkte von f . Geben Sie an, ob es sich dabei um globale Extremalstellen handelt. 360 Kapitel 24Nichtlineare Optimierung im Rn Lehrbuch: Abschnitt 24.2 Lösung: Zu a): Für den Gradienten von f an der Stelle (x, y, z) ∈ R3 gilt grad f (x, y, z)= ( ∂f (x, y, z) ∂x , ∂f (x, y, z) ∂y , ∂f (x, y, z) ∂z )T =(−8x + 4y,−4y + 4x + z,−z+ y + 100)T . Durch Lösen des linearen Gleichungssystems −8x+4y = 0 (24.4) 4x−4y+z = 0 (24.5) y−z = −100 (24.6) erhält man die stationären Stellen von f . Die Gleichung (24.4) liefert x = 12 y. Wird dies in (24.5) eingesetzt, erhält man für (24.5)–(24.6): −2y+z = 0 (24.7) y−z = −100 (24.8) Addition dieser beiden Gleichungen und anschließendeMultiplikation mit−1 liefert weiter y = 100 und damit schließlich x = 50 und z = 200. Das heißt, die Funktion f besitzt nur die stationäre Stelle (50, 100, 200). Zu b): Die Hesse-Matrix von f an der Stelle (x, y, z) ∈ R3 ist gegeben durch Hf (x, y, z) = ∂2f (x,y,z) ∂x2 ∂2f (x,y,z) ∂x∂y ∂2f (x,y,z) ∂x∂z ∂2f (x,y,z) ∂y∂x ∂2f (x,y,z) ∂y2 ∂2f (x,y,z) ∂y∂z ∂2f (x,y,z) ∂z∂x ∂2f (x,y,z) ∂z∂y ∂2f (x,y,z) ∂z2 = −8 4 04 −4 1 0 1 −1 . Für die Hauptminoren der Hesse-Matrix gilt (vgl. Definition 10.37 sowie (8.42) und (8.44) im Lehrbuch): det(H1) = −8 < 0 det(H2) = det ( −8 4 4 −4 ) = −8 · (−4)− 4 · 4 = 16 > 0 det(H3) = det −8 4 04 −4 1 0 1 −1 = −8 · (−4) · (−1)− 1 · 1 · (−8)− (−1) · 4 · 4 = −8 < 0 Die Hesse-Matrix ist somit für alle (x, y, z) ∈ R3 negativ definit (vgl. Satz 10.38b) im Lehrbuch). Daraus folgt, dass die Funktion f streng konkav ist (vgl. Satz 22.45d) im Lehrbuch). Zu c): Als stationäre Stelle einer streng konkaven Funktion ist (50, 100, 200) eine globale Maximalstelle von f (vgl. Satz 24.5b) im Lehrbuch). Ferner gilt, dass der Definitionsbereich von f keine Randstellen umfasst und die Funktion f partiell differenzierbar ist. Folglich muss eine Extremalstelle von f eine stationäre Stelle sein (vgl. Satz 24.1 im Lehrbuch). Da jedoch die Funktion f neben (50, 100, 200) keine weiteren stationären Stellen aufweist, impliziert dies, dass f keine anderen Extremalstellen oder Stellen mit Sattelpunkten besitzt. ** Aufgabe 24.9 (Optimierung im Rn ohne Nebenbedingungen) Betrachtet wird die reellwertige Funktion f : R2 −→ R, (x, y) *→ (y − x2)e−2y. a) Ermitteln Sie die stationären Stellen von f . b) Bestimmen Sie die lokalen Extremalstellen und Sattelpunkte von f . Geben Sie an, ob es sich bei den lokalen Extremalstellen um globale Extremalstellen handelt. Lehrbuch: Abschnitt 24.2 361 Kapitel 24 Teil VIII: Optimierung im Rn Lösung: Zu a): Mit der Produkt- und Kettenregel (vgl. Satz 16.6c) und (16.15) im Lehrbuch) erhält man für die beiden partiellen Ableitungen erster Ordnung ∂f (x, y) ∂x = −2xe−2y und ∂f (x, y) ∂y = e−2y − 2(y − x2)e−2y = (2x2 − 2y + 1)e−2y . Für den Gradienten von f an der Stelle (x, y) ∈ R2 gilt somit grad f (x, y) = ( ∂f (x, y) ∂x , ∂f (x, y) ∂y )T = ( −2xe−2y , (2x2 − 2y + 1)e−2y )T . Durch Lösen des (nichtlinearen) Gleichungssystems −2xe−2y = 0 (24.9) (2x2 − 2y + 1)e−2y = 0 (24.10) erhält man die stationären Stellen von f . Wegen e−2y > 0 für alle y ∈ R besitzt die Gleichung (24.9) nur die Lösung x = 0. Aus der Gleichung (24.10) folgt, dass 2x2 − 2y + 1 = 0 gelten muss. Zusammen mit x = 0 impliziert dies −2y + 1 = 0 bzw. y = 12 . Die Funktion f besitzt folglich nur die stationäre Stelle ( 0, 12 ) . Zu b): Die Hesse-Matrix von f an der Stelle (x, y) ∈ R2 ist gegeben durch Hf (x, y) = ∂2f (x,y)∂x2 ∂2f (x,y)∂x∂y ∂2f (x,y) ∂y∂x ∂2f (x,y) ∂y2 = (−2e−2y 4xe−2y 4xe−2y −2e−2y − 2(2x2 − 2y + 1)e−2y ) . Daraus folgt für die Hesse-Matrix speziell an der stationären Stelle ( 0, 12 ) (vgl. Aufgabenteil a)): Hf ( 0, 1 2 ) = ( −2e−1 0 0 −2e−1 ) Das heißt, bei derHesse-MatrixHf ( 0, 12 ) handelt es sich umeineDiagonalmatrixmit ausschließlich negativen Hauptdiagonaleinträgen. Die Hesse-Matrix ist folglich negativ definit (vgl. Satz 10.32b) im Lehrbuch) und die Stelle ( 0, 12 ) somit eine lokale Maximalstelle (vgl. Satz 24.3b) im Lehrbuch). Ferner gilt, dass der Definitionsbereich von f keine Randstellen umfasst und die Funktion f partiell differenzierbar ist. Folglich muss eine Extremalstelle von f eine stationäre Stelle sein (vgl. Satz 24.1 im Lehrbuch). Da jedoch die Funktion f neben ( 0, 12 ) keine weiteren stationären Stellen aufweist, impliziert dies, dass f keine anderen Extremalstellen oder Stellen mit Sattelpunkten besitzt. Daraus folgt insbesondere, dass die lokale Maximalstelle ( 0, 12 ) sogar eine globale Maximalstelle von f ist. ** Aufgabe 24.10 (Optimierung im Rn ohne Nebenbedingungen) Betrachtet wird die reellwertige Funktion f : R2 −→ R, (x, y) *→ x4 + 2x2y2 − 2x2 − y2. a) Ermitteln Sie die stationären Stellen von f . b) Bestimmen Sie die lokalen Extremalstellen und Sattelpunkte von f . Geben Sie an, ob es sich bei den lokalen Extremalstellen um globale Extremalstellen handelt. Lehrbuch: Abschnitt 24.2 Lösung: Zu a): Für den Gradienten von f an der Stelle (x, y) ∈ R2 gilt grad f (x, y) = ( ∂f (x, y) ∂x , ∂f (x, y) ∂y )T = ( 4x3 + 4xy2 − 4x, 4x2y − 2y )T . Durch Lösen des (nichtlinearen) Gleichungssystems 4x(x2 + y2 − 1) = 0 (24.11) 2y(2x2 − 1) = 0 (24.12) 362 Kapitel 24Nichtlineare Optimierung im Rn erhält man die stationären Stellen von f . Die Gleichung (24.12) besitzt offensichtlich die drei Lösungen y = 0, x = − √ 2 2 und x = √ 2 2 . Lösung y = 0: Wird y = 0 in die Gleichung (24.11) eingesetzt, erhält man die Gleichung 4x(x2 − 1) = 0. Diese Gleichung besitzt die Lösungen x = 0, x = −1 und x = 1. Lösung x = − √ 2 2 : Einsetzen von x = − √ 2 2 in die Gleichung (24.11) liefert die Gleichung −2√2 ( y2 − 1 2 ) = 0, welche die Lösungen y = − √ 2 2 und y = √ 2 2 besitzt. Lösung x = √ 2 2 : Einsetzen von x = √ 2 2 in die Gleichung (24.11) liefert die Gleichung 2 √ 2 ( y2 − 1 2 ) = 0, welche ebenfalls die Lösungen y = − √ 2 2 und y = √ 2 2 besitzt. Die Funktion f besitzt folglich die sieben stationären Stellen: (x1, y1) (x2, y2) (x3, y3) (x4, y4) (x5, y5) (x6, y6) (x7, y7) (0, 0) (−1, 0) (1, 0) ( − √ 2 2 ,− √ 2 2 ) ( − √ 2 2 , √ 2 2 ) (√ 2 2 ,− √ 2 2 ) (√ 2 2 , √ 2 2 ) Zu b): Die Hesse-Matrix von f an der Stelle (x, y) ∈ R2 ist gegeben durch Hf (x, y) = ∂ 2f (x,y) ∂x2 ∂2f (x,y) ∂x∂y ∂2f (x,y) ∂y∂x ∂2f (x,y) ∂y2 = (12x2 + 4y2 − 4 8xy 8xy 4x2 − 2 ) . Für die Hesse-Matrizen speziell an den sieben stationären Stellen (x1, y1), . . . , (x7, y7) (vgl. Aufgabenteil a)) erhält man daraus: Hf (x1, y1) = ( −4 0 0 −2 ) Hf (x2, y2) = Hf (x3, y3) = ( 8 0 0 2 ) Hf (x4, y4) = Hf (x7, y7) = ( 4 4 4 0 ) Hf (x5, y5) = Hf (x6, y6) = ( 4 −4 −4 0 ) Die Berechnung der Determinante der Hesse-Matrix Hf (x, y) (vgl. (8.42) im Lehrbuch) und der zweiten partiellen Ableitung ∂ 2f (x,y) ∂x2 für die sieben stationären Stellen von f führt zu der folgenden Tabelle: (x1, y1) (x2, y2) (x3, y3) (x4, y4) (x5, y5) (x6, y6) (x7, y7) det(Hf (xi , yi)) 8 16 16 −16 −16 −16 −16 ∂2f (xi , yi) ∂x2 −4 8 8 4 4 4 4 363 Kapitel 24 Teil VIII: Optimierung im Rn Folglich handelt es sich bei (x1, y1) um eine lokale Maximalstelle und bei (x2, y2) und (x3, y3) um lokale Minimalstellen von f . An den Stellen (x4, y4), (x5, y5), (x6, y6) und (x7, y7) besitzt f Sattelpunkte (vgl. Folgerung 24.10a), b) und e) im Lehrbuch). Wegen lim x→±∞ f (x, y) = ∞ ist jedoch (x1, y1) keine globale Maximalstelle von f . Dagegen handelt es sich bei (x2, y2) und (x3, y3) sogar um globale Minimalstellen von f . ** Aufgabe 24.11 (Optimierung im Rn ohne Nebenbedingungen) Betrachtet wird die reellwertige Funktion f : R2 −→ R, (x, y) *→ (1− x2)y. a) Ermitteln Sie die stationären Stellen von f . b) Bestimmen Sie die Extremalstellen und Sattelpunkte von f ohne Zuhilfenahme der Hesse-Matrix. c) Überprüfen Sie das Ergebnis aus Aufgabenteil a) mit Hilfe der Hesse-Matrix. Lehrbuch: Abschnitt 24.2 Lösung: Zu a): Für den Gradienten von f an der Stelle (x, y) ∈ R2 gilt grad f (x, y) = ( ∂f (x, y) ∂x , ∂f (x, y) ∂y )T = ( −2xy, 1− x2 )T . Durch Lösen des (nichtlinearen) Gleichungssystems −2xy = 0 (24.13) 1− x2 = 0 (24.14) erhält man die stationären Stellen von f . Aus der Gleichung (24.14) folgt unmittelbar x = −1 oder x = 1.Werden diese beidenWerte in die Gleichung (24.13) eingesetzt, erhält man weiter y = 0. Das heißt, die Funktion f besitzt die beiden stationären Stellen (−1, 0) und (1, 0). Zu b): Für die Bestimmung der Extremalstellen und Sattelpunkte von f ohne Zuhilfenahme der Hesse-Matrix werden die Funktionswerte von f in einer unmittelbaren Umgebung der beiden stationären Stellen (−1, 0) und (1, 0) untersucht. An den stationären Stellen besitzt f den Funktionswert f (−1, 0) = f (1, 0) = 0. Ferner gilt: f (x, y) > 0 für 0 < |x| < 1 und y > 0 < 0 für 0 < |x| < 1 und y < 0 < 0 für |x| > 1 und y > 0 > 0 für |x| > 1 und y < 0 Das heißt, in der Umgebung beider stationärer Stellen (−1, 0) und (1, 0) gibt es Stellen mit größeren Funktionswerten (für 0 < |x| < 1 und y > 0 oder |x| > 1 und y < 0) und Stellen mit kleineren Funktionswerten (für 0 < |x| < 1 und y < 0 oder |x| > 1 und y > 0). Bei den beiden stationären Stellen kann es sich somit um keine Extremalstellen von f handeln, sondern um Stellen mit einem Sattelpunkt. Zu c): Die Hesse-Matrix von f an der Stelle (x, y) ∈ R2 ist gegeben durch Hf (x, y) = ∂ 2f (x,y) ∂x2 ∂2f (x,y) ∂x∂y ∂2f (x,y) ∂y∂x ∂2f (x,y) ∂y2 = (−2y −2x−2x 0 ) . 364 Kapitel 24Nichtlineare Optimierung im Rn Daraus folgt für die Hesse-Matrizen speziell an den beiden stationären Stellen (−1, 0) und (1, 0) (vgl. Aufgabenteil a)): Hf (−1, 0) = ( 0 2 2 0 ) Hf (1, 0) = ( 0 −2 −2 0 ) Die Berechnung der Determinante der beiden Hesse-Matrizen Hf (−1, 0) und Hf (1, 0) (vgl. (8.42) im Lehrbuch) liefert die Werte det ( Hf (−1, 0) ) = 0− 4 = −4 < 0 und det (Hf (1, 0)) = 0− 4 = −4 < 0. Daraus folgt, dass die beiden stationären Stellen von f keine Extremalstellen, sondern Stellenmit Sattelpunkten sind (vgl. Folgerung 24.10e) im Lehrbuch). *** Aufgabe 24.12 (Optimierung im Rn ohne Nebenbedingungen) Betrachtet wird die reellwertige Funktion f : R2 −→ R, (x, y) *→ −8x3 − 12x2 + 3xy2 + y3 + 3y2. a) Ermitteln Sie die stationären Stellen von f . b) Bestimmen Sie die lokalen Extremalstellen und Sattelpunkte von f . Geben Sie an, ob es sich bei den lokalen Extremalstellen um globale Extremalstellen handelt. Lehrbuch: Abschnitt 24.2 Lösung: Zu a): Für den Gradienten von f an der Stelle (x, y) ∈ R2 gilt grad f (x, y) = ( ∂f (x, y) ∂x , ∂f (x, y) ∂y )T = ( −24x2 − 24x + 3y2, 6xy + 3y2 + 6y )T . Durch Lösen des (nichtlinearen) Gleichungssystems −24x2 − 24x + 3y2 = 0 (24.15) 3y(2x + y + 2) = 0 (24.16) erhält man die stationären Stellen von f . Die Gleichung (24.16) besitzt offensichtlich die beiden Lösungen y = 0 und y = −2x − 2. Lösung y = 0: Wird y = 0 in die Gleichung (24.15) eingesetzt, erhält man die Gleichung −24x(x + 1) = 0. Diese Gleichung besitzt die Lösungen x = 0 und x = −1. Lösung y = −2x − 2: Einsetzen von y = −2x − 2 in die Gleichung (24.15) liefert −24x2 − 24x + 3(−2x − 2)2 = 0 ⇐⇒ −12x2 + 12 = 0 ⇐⇒ −12(x2 − 1) = 0 und damit die Lösungen x = −1 und x = 1. Die Funktion f besitzt damit die folgenden drei stationären Stellen: (x1, y1) (x2, y2) (x3, y3) (0, 0) (−1, 0) (1,−4) Zu b): Die Hesse-Matrix von f an der Stelle (x, y) ∈ R2 ist gegeben durch Hf (x, y) = ∂ 2f (x,y) ∂x2 ∂2f (x,y) ∂x∂y ∂2f (x,y) ∂y∂x ∂2f (x,y) ∂y2 = (−48x − 24 6y 6y 6x + 6y + 6 ) . 365 Kapitel 24 Teil VIII: Optimierung im Rn Daraus folgt für die Hesse-Matrizen speziell an den drei stationären Stellen (x1, y1), (x2, y2) und (x3, y3) (vgl. Aufgabenteil a)): Hf (x1, y1) = ( −24 0 0 6 ) Hf (x2, y2) = ( 24 0 0 0 ) Hf (x3, y3) = ( −72 −24 −24 −12 ) Die Berechnung der Determinante der Hesse-Matrix Hf (x, y) (vgl. (8.42) im Lehrbuch) und der zweiten partiellen Ableitung ∂ 2f (x,y) ∂x2 für die drei stationären Stellen von f führt zu der folgenden Tabelle: (x1, y1) (x2, y2) (x3, y3) det(Hf (xi , yi)) −144 0 288 ∂2f (xi , yi) ∂x2 −24 24 −72 Folglich ist (x1, y1) ein Sattelpunkt und (x3, y3) eine lokale Maximalstelle von f (vgl. Folgerung 24.10 b) und e) im Lehrbuch). Wegen det(Hf (x2, y2)) = 0 kann mit Hilfe der Determinante von Hf (x2, y2) keine Entscheidung darüber getroffen werden, ob es sich bei (x2, y2) um eine Extremalstelle oder einen Sattelpunkt von f handelt (vgl. Seite 718 im Lehrbuch). Für eine solche Entscheidung werden im Folgenden die Funktionswerte von f an der Stelle (x2, y2) = (−1, 0) entlang einer Geraden parallel zur x-Achse und einer Geraden parallel zur y-Achse näher untersucht. Aus ∂f (−1, 0) ∂x = 0 und ∂ 2f (−1, 0) ∂x2 = 24 > 0 folgt dann, dassf entlangeinerGeradenparallel zurx-Achse anderStelle (−1, 0)ein lokalesMinimumaufweist (vgl. Folgerung 18.8a) im Lehrbuch). Wegen ∂f (−1, 0) ∂y = 0 und ∂ 2f (−1, 0) ∂y2 = 0 kann jedoch auf diese Weise keine Aussage darüber getroffen werden, ob die Funktion f auch entlang einer Geraden parallel zur y-Achse an der Stelle (−1, 0) ein lokales Minimum besitzt (vgl. Seite 519 im Lehrbuch). Aus diesem Grund wird die Funktion g(t) := f (−1, t) = 8− 12− 3t2 + t3 + 3t2 = t3 − 4 betrachtet. Diese Funktion gibt die Funktionswerte von f entlang einer Geraden parallel zur y-Achse durch die Stelle (−1, 0) an. Wegen g(−a) < g(0) < g(a) für alle a > 0, kann jedoch die Funktion g bei t = 0 keine Extremalstelle besitzen. Folglich muss die Stelle (−1, 0) ein Sattelpunkt der Funktion f sein. Aus lim x→−∞ f (x, y) = ∞ folgt ferner, dass es sich bei (x3, y3) um keine globale, sondern lediglich um eine lokale Maximalstelle von f handelt. * Aufgabe 24.13 (MC-Aufgaben zur Optimierung im Rn mit Gleichheitsnebenbedingungen) Kreuzen Sie an, welche der Aussagen a) bis e) wahr und welche falsch sind: a) Bei einem Optimierungsproblem mit Gleichheitsnebenbedingungen sollte es immer mindestens so viele Nebenbedingungen wie Variablen geben. b) Das Minimum einer Funktion f unter Einbeziehung von Nebenbedingungen ist nicht kleiner als das Minimum von f ohne Berücksichtigung von Nebenbedingungen. 366 Kapitel 24Nichtlineare Optimierung im Rn c) Das Verfahren der Variablensubstitution kann bei Optimierungsproblemen mit Ungleichheitsnebenbedingungen angewendet werden. d) Das Verfahren der Variablensubstitution kann nur angewendet werden, wenn sich die Nebenbedingungen nach einer der Variablen auflösen lassen. e) Bei der Anwendung des Verfahrens der Variablensubstitution auf ein Optimierungsproblem mit nVariablen und k Gleichheitsnebenbedingungen resultiert ein neues Optimierungsproblem mit n− k Variablen ohne Nebenbedingungen. a) b) c) d) e) Wahr Falsch Lehrbuch: Abschnitt 24.3 Lösung: Zu a): Falsche Aussage. Bei einem Optimierungsproblem mit Gleichheitsnebenbedingungen muss es mehr Variablen als Nebenbedingungen geben. Auf diese Weise wird sichergestellt, dass es zur Optimierung noch Variablen gibt, die unabhängig voneinander variiert werden können (vgl. Seite 725 im Lehrbuch). Zu b): Wahre Aussage (vgl. Seite 725 im Lehrbuch). Zu c): Falsche Aussage. Beim Verfahren der Variablensubstitution müssen die Nebenbedingungen in Form von Gleichungen gegeben sein (vgl. Seite 725 im Lehrbuch). Zu d): Falsche Aussage. Für die Anwendbarkeit des Verfahrens der Variablensubstitution ist es erforderlich, dass die Gleichheitsnebenbedingungen nach verschiedenen Variablen aufgelöst werden können (vgl. Seite 725 im Lehrbuch). Zu e): Wahre Aussage. Bei dem resultierenden Optimierungsproblem sind die k Gleichheitsnebenbedingungen bereits in der zu optimierenden Funktion berücksichtigt (vgl. Seite 726 im Lehrbuch). ** Aufgabe 24.14 (MC-Aufgaben zur Optimierung im Rn mit Gleichheitsnebenbedingungen) Kreuzen Sie an, welche der Aussagen a) bis e) wahr und welche falsch sind: a) Bei der Anwendung der Lagrangeschen Multiplikatorenregel wird ein Optimierungsproblem in n Variablen mit k < n Gleichheitsnebenbedingungen in ein höherdimensionales Optimierungsproblem mit n + k Variablen ohne Nebenbedingungen überführt. b) Die Lagrangesche Multiplikatorenregel kann bei Optimierungsproblemen mit Ungleichheitsnebenbedingungen angewendet werden. c) Die Lagrangesche Multiplikatorenregel liefert eine notwendige Bedingung für lokale Extremalstellen unter k Gleichheitsnebenbedingungen. d) Der Gradient einer Lagrange-Funktion für ein Optimierungsproblem mit n Variablen und k Nebenbedingungen ist ein Spaltenvektor des Rn+k . e) Das −1-fache des Wertes des p-ten Lagrange-Multiplikators λp ist ein Maß für die Sensitivität des Funktionswertes bezüglich einer Veränderung der p-ten Beschränkung. a) b) c) d) e) Wahr Falsch Lehrbuch: Abschnitt 24.3 367 Kapitel 24 Teil VIII: Optimierung im Rn Lösung: Zu a): Wahre Aussage (vgl. Seite 728 im Lehrbuch). Zu b): Falsche Aussage. Die Lagrangesche Multiplikatorenregel kann wie das Verfahren der Variablensubstitution nur auf Optimierungsprobleme mit Gleichheitsnebenbedingungen angewendet werden (vgl. Satz 24.15 im Lehrbuch). Zu c): Falsche Aussage. Die Lagrangesche Multiplikatorenregel liefert nur dann eine notwendige Bedingung für lokale Extremalstellen unter kGleichheitsnebenbedingungen,wenn dieGradienten der kNebenbedingungsfunktionen linear unabhängig sind (vgl. Satz 24.15 im Lehrbuch). Zu d): Wahre Aussage (vgl. Seite 731 im Lehrbuch). Zu e): Wahre Aussage (vgl. Seite 739 im Lehrbuch). * Aufgabe 24.15 (Optimierung im Rn mit Gleichheitsnebenbedingungen) Betrachtet wird die reellwertige Funktion f : R2 −→ R, (x, y) *→ f (x, y) = 4x3 + xy − y + 2 unter der Nebenbedingung y − xy − 3x = 0. (24.17) a) Bestimmen Sie die Extremalstellen und Extremalwerte von f unter der Nebenbedingung (24.17) mit Hilfe des Verfahrens der Variablensubstitution. b) Begründen Sie kurz, ob es sich bei den im Aufgabenteil a) ermittelten Extremalstellen um globale Extremalstellen von f handelt. Lehrbuch: Abschnitt 24.3 Lösung: Zu a): Aufgrund der Struktur der Zuordnungsvorschrift von f bietet es sich an, die Gleichheitsnebenbedingung y − xy − 3x = 0 zu xy − y = −3x (24.18) umzuformen und in die Zuordnungsvorschrift von f einzusetzen. Es resultiert dann die Funktion ϕ : R −→ R mit der Zuordnungsvorschrift ϕ(x) := 4x3 − 3x + 2. Für die ersten beiden Ableitungen dieser reellwertigen Funktion ϕ in einer Variablen erhält man ϕ′(x) = 12x2 − 3 und ϕ′′(x) = 24x. Es gilt somit ϕ′(x) = 0 ⇐⇒ x2 = 1 4 ⇐⇒ x1,2 = ± 12 . Das heißt, die Funktion ϕ besitzt die beiden stationären Stellen x1 = − 12 und x2 = 12 . Wegen ϕ′′ ( − 12 ) = −12 < 0 und ϕ′′ ( 1 2 ) = 12 > 0 handelt es sich bei den stationären Stellen x1 = − 12 und x2 = 12 um eine lokale Maximal- bzw. Minimalstelle von ϕ (vgl. Folgerung 18.8a) im Lehrbuch). Aus (24.17) folgt ferner y(1−x) = 3x und damit dieGleichung y = 3x1−x . Einsetzen der beidenExtremalstellen x1 = − 12 und x2 = 12 in dieseGleichung liefert für die Variable y dieWerte y1 = −1 und y2 = 3. Die Funktion f besitzt somit unter der Gleichheitsnebenbedingung y−xy−3x = 0 die lokaleMaximalstelle ( − 12 ,−1 ) mit dem lokalenMaximalwertf ( − 12 ,−1 ) = 3 und die lokaleMinimalstelle ( 1 2 , 3 ) mit dem lokalenMinimalwert f ( 1 2 , 3 ) = 1. Zu b): Bei den beiden lokalen Extremalstellen ( − 12 ,−1 ) und ( 1 2 , 3 ) handelt es sich um keine globalen Extremalstellen von f unter der Gleichheitsnebenbedingung y − xy − 3x = 0. Denn wegen lim x→−∞ϕ(x) = −∞ und limx→∞ϕ(x) = ∞ ist die Funktion ϕ und damit auch die Funktion f unter der Nebenbedingung y−xy−3x = 0 nach unten und nach oben unbeschränkt. 368 Kapitel 24Nichtlineare Optimierung im Rn ** Aufgabe 24.16 (Anwendung der Optimierung im Rn mit Gleichheitsnebenbedingungen) Ein Anleger möchte sein Kapital so auf drei zur Auswahl stehende Anlageformen mit den erwarteten Renditen 9, 7 und 8 (in %) verteilen, dass das damit verbundene Investitionsrisiko minimiert wird. Das Risiko wird dabei durch die Funktion f : (0,∞)3 −→ R, (x, y, z) *→ f (x, y, z) = 2x2 + y2 + 3 2 z2 quantifiziert, wobei x, y und z die Anteile der drei Anlageformen im Portfolio sind. Der Anleger fordert dabei eine Rendite von genau 8,5 (in %). a) Geben Sie das Optimierungsproblem in mathematischer Form an und interpretieren Sie es. b) Lösen Sie das Optimierungsproblem mit Hilfe des Verfahrens der Variablensubstitution. c) Interpretieren Sie das Ergebnis aus Aufgabenteil b). Lehrbuch: Abschnitt 24.3 Lösung: Zu a): Es ist die globaleMinimalstelle der Funktionf unter den beidenGleichheitsnebenbedingungen x + y + z = 1 und 9x + 7y + 8z = 8,5 (24.19) zu bestimmen. Die erste Gleichheitsnebenbedingung drückt aus, dass der Anleger sein gesamtes Kapital auf die drei Anlageformen verteilt. Die zweite Gleichheitsnebenbedingung stellt sicher, dass die erwartete Gesamtrendite des Portfolios genau 8,5 (in %) beträgt. Zu b): Wird die erste Gleichheitsnebenbedingung in (24.19) nach x aufgelöst, resultiert x = 1− y − z. (24.20) Wird dieser Term in die zweite Gleichheitsnebenbedingung in (24.19) für die Variable x eingesetzt, folgt 9(1− y − z)+ 7y + 8z = 8,5 ⇐⇒ −2y − z = − 1 2 ⇐⇒ z = 1 2 − 2y. (24.21) Durch Einsetzen des Ausdruckes z = 12 − 2y in (24.20) für die Variable z, erhält man weiter x = 1− y − z = 1− y − ( 1 2 − 2y ) = 1 2 + y. Werden die beiden Ausdrücke x = 12 + y und z = 12 − 2y in die Zuordnungsvorschrift von f eingesetzt, resultiert schließlich die Funktion ϕ : (0,∞) −→ R, y *→ ϕ(y) : = f ( 1 2 + y, y, 1 2 − 2y ) = 2 ( 1 2 + y )2 + y2 + 3 2 ( 1 2 − 2y )2 = 9y2 − y + 7 8 . Für die ersten beiden Ableitungen dieser reellwertigen Funktion ϕ in einer Variablen erhält man ϕ′(y) = 18y − 1 und ϕ′′(y) = 18. Es gilt somit ϕ′(y) = 0 ⇐⇒ 18y − 1 = 0 ⇐⇒ y = 1 18 . Das heißt, die Funktion ϕ besitzt die stationäre Stelle y = 118 . Wegen ϕ′′ ( 1 18 ) = 18 > 0 für alle y ∈ (0,∞) handelt es sich bei der stationären Stellen y = 118 um eine globale Minimalstelle von ϕ (vgl. Folgerung 18.8b) im Lehrbuch). 369 Kapitel 24 Teil VIII: Optimierung im Rn Mit y = 118 und (24.21) erhält man für die Variable z den Wert z = 12 − 2 · 118 = 718 . Werden die Werte für y und z in (24.20) eingesetzt, resultiert für die Variable x der Wert x = 1 − y − z = 1 − 118 − 718 = 59 . Die Funktion f besitzt somit unter den beiden Gleichheitsnebenbedingungen (24.19) die globaleMinimalstelle( 5 9 , 1 18 , 7 18 ) . Zu c): Legt der Anleger x = 59 ≈ 55,6% in die erste Anlageform, y = 118 ≈ 5,6% in die zweite Anlageform und z = 718 ≈ 38,9% in die dritte Anlageform an, dann hält er ein Portfolio mit einer erwarteten Rendite von 8,5% und minimiert dabei das Investitionsrisiko, welches bei dieser Zusammensetzung des Portfolios f ( 5 9 , 1 18 , 7 18 ) = 2 ( 5 9 )2 + ( 1 18 )2 + 3 2 ( 7 18 )2 = 400+ 2+ 147 648 = 549 648 = 61 72 beträgt. ** Aufgabe 24.17 (Optimierung im Rn mit Nebenbedingungen) Untersuchen Sie, ob es sich bei ( 3,−2,− 12 ) , (3,−1, 0) und (3,− 32 ,− 12 ) um stationäre Stellen der Funktion f : R3 −→ R, (x, y, z) *→ f (x, y, z) = 4x2 + 2y2 + 4xz− 6z unter den beiden Nebenbedingungen x + y − z = 2 und x − y + z = 4 handelt. Lehrbuch: Abschnitt 24.3 Lösung: Die Funktion f ist unter den beiden Gleichheitsnebenbedingungen g1(x, y, z) := x + y − z− 2 = 0 und g2(x, y, z) := x − y + z− 4 = 0 (24.22) zu optimieren. Die stationären Stellen von f unter den beiden Gleichheitsnebenbedingungen (24.22) sind gegeben durch die stationären Stellen der Lagrange-Funktion L(λ1, λ2, x, y, z) : = f (x, y, z)+ λ1g1(x, y, z)+ λ2g2(x, y, z) = 4x2 + 2y2 + 4xz− 6z+ λ1(x + y − z− 2)+ λ2(x − y + z− 4) (vgl. (24.27) und Seite 731 im Lehrbuch). Für den Gradienten dieser Lagrange-Funktion gilt gradL(λ1,λ2,x,y,z) = ( ∂L(λ1,λ2,x,y,z) ∂x , ∂L(λ1,λ2,x,y,z) ∂y , ∂L(λ1,λ2,x,y,z) ∂z , ∂L(λ1,λ2,x,y,z) ∂λ1 , ∂L(λ1,λ2,x,y,z) ∂λ2 )T = (8x+4z+λ1+λ2,4y+λ1−λ2,4x−6−λ1+λ2,x+y−z−2,x−y+z−4)T . Folglich sind die drei Stellen ( 3,−2,− 12 ) , (3,−1, 0) und ( 3,− 32 ,− 12 ) genau dann stationäre Stellen von f unter den beiden Gleichheitsnebenbedingungen (24.22), wenn sie für geeignete Werte von λ1, λ2 dem linearen Gleichungssystem 8x + 4z+λ1 + λ2 = 0 4y +λ1 − λ2 = 0 4x −λ1 + λ2−6 = 0 (24.23) x+ y − z −2 = 0 x− y + z −4 = 0 370 Kapitel 24Nichtlineare Optimierung im Rn genügen. Durch Einsetzen der drei Stellen in das lineare Gleichungssystem (24.23) erhält man, dass die Stelle( 3,−2,− 12 ) nicht die letzte Gleichung von (24.23) erfüllt, und die Stelle (3,−1, 0) zwar den letzten beiden Gleichungen von (24.23) genügt, aber es keineWerte λ1, λ2 ∈ R gibt, so dass auch die ersten drei Gleichungen von (24.23) erfüllt sind. Dagegen genügt die Stelle ( 3,− 32 ,− 12 ) den letzten beiden Gleichungen von (24.23), undmit λ1 = −8 und λ2 = −14 existierenWerte, so dass auch die ersten drei Gleichungen erfüllt sind. Folglich ist nur ( 3,− 32 ,− 12 ) eine stationäre Stelle von f unter den beiden Gleichheitsnebenbedingungen (24.22). ** Aufgabe 24.18 (Optimierung im Rn mit Nebenbedingungen) Betrachtet wird die reellwertige Funktion f : R2 −→ R, (x, y) *→ f (x, y) = x2 + 2xy unter der Nebenbedingung y + 3 2 x − 6 = 0. (24.24) a) Ermitteln Sie die Extremalstellen und Extremalwerte von f unter der Nebenbedingung (24.24) mittels des Verfahrens der Variablensubstitution. b) Bestimmen Sie mit Hilfe der LagrangeschenMultiplikatorenregel Kandidaten für Extremalstellen von f unter der Nebenbedingung (24.24). Lehrbuch: Abschnitt 24.3 Lösung: Zu a): Auflösen der Gleichheitsnebenbedingung y + 32 x − 6 = 0 nach der Variablen y liefert y = 6− 3 2 x. (24.25) Wird dieser Term in die Zuordnungsvorschrift der Funktion f eingesetzt, resultiert die Funktion ϕ : R −→ R mit der Zuordnungsvorschrift ϕ(x) := f ( x, 6− 3 2 x ) = x2 + 2x ( 6− 3 2 x ) = −2x2 + 12x. Für die ersten beiden Ableitungen dieser reellwertigen Funktion ϕ in einer Variablen gilt ϕ′(x) = −4x + 12 und ϕ′′(x) = −4. Esgilt somitϕ′(x) = 0genaudann,wennx = 3.Dasheißt, dieFunktionϕ besitzt nur die stationäreStellex = 3, und wegen ϕ′′(x) < 0 für alle x ∈ R handelt es sich bei dieser stationären Stelle um eine globaleMaximalstelle von ϕ (vgl. Folgerung 18.8b) im Lehrbuch). Wird der Wert x = 3 in die Gleichung (24.25) eingesetzt, erhält man für die Variable y den Wert y = 32 . Die Funktion f besitzt somit unter der Gleichheitsnebenbedingung y+ 32 x−6 = 0 die globaleMaximalstelle ( 3, 32 ) und den globalenMaximalwertf ( 3, 32 ) = 32+2·3· 32 = 18. Zu b): Die Funktion f ist unter der Gleichheitsnebenbedingung g(x, y) := y + 3 2 x − 6 = 0 (24.26) zu optimieren. Das heißt, es gibt k = 1 Gleichheitsnebenbedingungen und die Lagrange-Funktion ist gegeben durch L(λ, x, y) : = f (x, y)+ λg(x, y) = x2 + 2xy + λ ( y + 3 2 x − 6 ) (24.27) (vgl. (24.27) im Lehrbuch). Für den Gradienten der Lagrange-Funktion L(λ, x, y) folgt somit gradL(λ, x, y) = ( ∂L(λ, x, y) ∂x , ∂L(λ, x, y) ∂y , ∂L(λ, x, y) ∂λ )T = ( 2x + 2y + 3 2 λ, 2x + λ, y + 3 2 x − 6 )T . 371 Kapitel 24 Teil VIII: Optimierung im Rn Durch Lösen des linearen Gleichungssystems 2x + 2y + 3 2 λ = 0 (24.28) 2x + λ = 0 (24.29) 3 2 x + y −6 = 0 (24.30) erhält man die stationären Stellen der Lagrange-FunktionL(λ, x, y). Aus der Gleichung (24.29) folgt x = − λ2 und durch Einsetzen in die beiden verbleibenden Gleichungen (24.28) und (24.30) resultiert damit 2y + λ 2 = 0 und − 3 4 λ+ y − 6 = 0. Die erste Gleichung liefert y = − 14λ, und in die zweite Gleichung eingesetzt, erhält man weiter − 3 4 λ− 1 4 λ− 6 = 0, also λ = −6. Für die beiden Variablen resultieren damit die Werte x = 3 und y = 32 . Das heißt, mit der Lagrangeschen Multiplikatorenregel erhält man als Kandidat für eine Extremalstellen von f unter der Gleichheitsnebenbedingung y + 32 x − 6 = 0 die Stelle ( 3, 32 ) . ** Aufgabe 24.19 (Optimierung im Rn mit Nebenbedingungen) Betrachtet wird eine reellwertige Funktion f : R2 −→ R, (x, y) *→ f (x, y) = x2 + 2y2 + 4y + 2000 unter der Nebenbedingung 2x + 2y = 79. (24.31) a) Bestimmen Sie mit Hilfe der LagrangeschenMultiplikatorenregel Kandidaten für Extremalstellen der Funktion f unter der Nebenbedingung (24.31). b) Weisen Sie nach, dass es sich bei den im Aufgabenteil a) ermittelten Kandidaten tatsächlich um globale Extremalstellen von f unter der Nebenbedingung (24.31) handelt und berechnen Sie die zugehörigen globalen Extremalwerte von f . Lehrbuch: Abschnitt 24.3 Lösung: Zu a): Die Funktion f ist unter der Gleichheitsnebenbedingung g(x, y) := 2x + 2y − 79 = 0 (24.32) zu optimieren. Das heißt, es gibt k = 1 Gleichheitsnebenbedingungen und die Lagrange-Funktion ist gegeben durch L(λ, x, y) : = f (x, y)+ λg(x, y) = x2 + 2y2 + 4y + 2000+ λ(2x + 2y − 79) (24.33) (vgl. (24.27) im Lehrbuch). Für den Gradienten der Lagrange-Funktion L(λ, x, y) gilt gradL(λ, x, y) = ( ∂L(λ, x, y) ∂x , ∂L(λ, x, y) ∂y , ∂L(λ, x, y) ∂λ )T = (2x + 2λ, 4y + 4+ 2λ, 2x + 2y − 79)T . Durch Lösen des linearen Gleichungssystems 2x +2λ = 0 (24.34) 4y+2λ+ 4 = 0 (24.35) 2x+2y − 79 = 0 (24.36) 372 Kapitel 24Nichtlineare Optimierung im Rn erhält man die stationären Stellen der Lagrange-Funktion L(λ, x, y). Aus den beiden Gleichungen (24.34) und (24.35) folgt x = −λ und y = − 1 2 λ− 1. (24.37) In Gleichung (24.36) eingesetzt folgt daraus weiter: 2x + 2y − 79 = 0 ⇐⇒ −2λ+ 2 ( − 1 2 λ− 1 ) − 79 = 0 ⇐⇒ −3λ− 81 = 0 ⇐⇒ λ = −27 Wird der Wert λ = −27 in die beiden Gleichungen in (24.37) eingesetzt, resultieren für die beiden Variablen die Werte x = 27 und y = 252 . Das heißt, die Lagrange-Funktion L(λ, x, y) besitzt nur die stationäre Stelle( −27, 27, 252 ) . Folglich handelt es sich bei der Stelle ( 27, 252 ) um einen Kandidaten für eine Extremalstelle der Funktion f unter der Nebenbedingung (24.32) (vgl. Satz 24.15 im Lehrbuch). Zu b): Für die Funktion L(−27, x, y) = x2 + 2y2 − 54x − 50y + 4133 erhält man die Hesse-Matrix HL(−27, x, y) = ∂ 2L(−27,x,y) ∂x2 ∂2L(−27,x,y) ∂x∂y ∂2L(−27,x,y) ∂y∂x ∂2L(−27,x,y) ∂y2 = (2 0 0 4 ) . Da es sich bei der Hesse-Matrix HL(−27, x, y) für alle (x, y) ∈ R2 um eine Diagonalmatrix mit ausschließlich positiven Hauptdiagonaleinträgen handelt, ist sie für alle (x, y) ∈ R2 positiv definit (vgl. Satz 10.32a) im Lehrbuch). Daraus folgt, dass die Funktion L(−27, x, y) streng konvex ist (vgl. Satz 22.45c) im Lehrbuch). Die Stelle ( 27, 252 ) ist daher die globale Minimalstelle von f unter der Gleichheitsnebenbedingung (24.32) (vgl. Satz 24.17a) im Lehrbuch), und das globale Minimum beträgt f ( 27, 25 2 ) = 272 + 2 ( 25 2 )2 + 4 · 25 2 + 2000 = 3091,5. ** Aufgabe 24.20 (Anwendung der Optimierung im Rn mit Nebenbedingungen) Betrachtet wird ein Haushalt mit der Nutzenfunktion U : (0,∞)2 −→ R, (x, y) *→ U(x, y) = −3x2 − 1 2 y2 + 12x + 7y + 16 unter der Budgetrestriktion 6x + 3y = 48. (24.38) a) Bestimmen Sie mit Hilfe der Lagrangeschen Multiplikatorenregel Kandidaten für Maximalstellen der Nutzenfunktion U unter der Nebenbedingung (24.38). b) Ermitteln Sie das nutzenmaximierende Güterbündel und den maximalen Nutzen des Haushaltes unter der Nebenbedingung (24.38). Lehrbuch: Abschnitt 24.3 Lösung: Zu a): Die Funktion U ist unter der Gleichheitsnebenbedingung g(x, y) := 6x + 3y − 48 = 0 (24.39) zu maximieren. Das heißt, es gibt k = 1 Gleichheitsnebenbedingungen und die Lagrange-Funktion ist gegeben durch L(λ, x, y) : = U(x, y)+ λg(x, y) = −3x2 − 1 2 y2 + 12x + 7y + 16+ λ(6x + 3y − 48) (24.40) 373 Kapitel 24 Teil VIII: Optimierung im Rn (vgl. (24.27) im Lehrbuch). Für den Gradienten der Lagrange-Funktion L(λ, x, y) folgt somit gradL(λ, x, y) = ( ∂L(λ, x, y) ∂x , ∂L(λ, x, y) ∂y , ∂L(λ, x, y) ∂λ )T = (−6x + 12+ 6λ,−y + 7+ 3λ, 6x + 3y − 48)T . Durch Lösen des linearen Gleichungssystems −6x + 6λ+12 = 0 (24.41) − y + 3λ+ 7 = 0 (24.42) 6x + 3y −48 = 0 (24.43) erhält man die stationären Stellen der Lagrange-Funktion L(λ, x, y). Aus den ersten beiden Gleichungen (24.41)–(24.42) folgt x = λ+ 2 und y = 3λ+ 7. (24.44) In Gleichung (24.43) eingesetzt folgt daraus weiter: 6x + 3y − 48 = 0 ⇐⇒ 6(λ+ 2)+ 3(3λ+ 7)− 48 = 0 ⇐⇒ 15λ− 15 = 0 ⇐⇒ λ = 1 Wird der Wert λ = 1 in die beiden Gleichungen in (24.44) eingesetzt, resultieren für die beiden Variablen die Werte x = 3 und y = 10.Das heißt, die Lagrange-FunktionL(λ, x, y) besitzt nur die stationäre Stelle (1, 3, 10). Folglich handelt es sich bei der Stelle (3, 10) um einen Kandidaten für eine Maximalstelle der Nutzenfunktion U unter der Nebenbedingung (24.39) (vgl. Satz 24.15 im Lehrbuch). Zu b): Für die Funktion L(1, x, y) = −3x2 − 1 2 y2 + 18x + 10y − 32 erhält man die Hesse-Matrix HL(1, x, y) = ∂ 2L(1,x,y) ∂x2 ∂2L(1,x,y) ∂x∂y ∂2L(1,x,y) ∂y∂x ∂2L(1,x,y) ∂y2 = (−6 0 0 −1 ) . Da es sich bei der Hesse-Matrix HL(1, x, y) für alle (x, y) ∈ (0,∞)2 um eine Diagonalmatrix mit ausschließlich negativenHauptdiagonaleinträgen handelt, ist sie für alle (x, y) ∈ (0,∞)2 negativ definit (vgl. Satz 10.32b) im Lehrbuch). Daraus folgt, dass die FunktionL(1, x, y) streng konkav ist (vgl. Satz 22.45d) im Lehrbuch). Die Stelle (3, 10) ist daher die globale Maximalstelle von U unter der Nebenbedingung (24.39) (vgl. Satz 24.17b) im Lehrbuch), und der maximale Nutzen beträgt U(3, 10) = −3 · 32 − 1 2 · 102 + 12 · 3+ 7 · 10+ 16 = 45. ** Aufgabe 24.21 (Anwendung der Optimierung im Rn mit Nebenbedingungen) Ein Unternehmen produziert drei Güter mit den Stückzahlen x1, x2 und x3. Die zugehörigen Preis-Absatz-Funktionen sind gegeben durch p1(x1) = 100− x1, p2(x2) = 50− x2, p3(x3) = 150− x3. Die Produktion ist betriebstechnisch restringiert durch die Nebenbedingung 2x1 + x2 + 3x3 = 70. (24.45) a) Bestimmen Sie die Zuordnungsvorschrift der Umsatzfunktion U : (0,∞)3 −→ R, (x1, x2, x3) *→ U(x1, x2, x3) des Unternehmens unter der Nebenbedingung (24.45). 374 Kapitel 24Nichtlineare Optimierung im Rn b) Ermitteln Sie mit Hilfe der Lagrangeschen Multiplikatorenregel die umsatzmaximierenden Produktionsmengen und den maximalen Umsatz unter der Nebenbedingung (24.45). c) Geben Sie eine ökonomische Interpretation für den resultierendenWert des Lagrange- Multiplikators an. Lehrbuch: Abschnitt 24.3 Lösung: Zu a): Die Zuordnungsvorschrift der Umsatzfunktion lautet U(x1, x2, x3) : = x1p1(x1)+ x2p2(x2)+ x3p3(x3) = 100x1 − x21 + 50x2 − x22 + 150x3 − x23 = −x21 − x22 − x23 + 100x1 + 50x2 + 150x3. Zu b): Die Funktion U ist unter der Gleichheitsnebenbedingung g(x1, x2, x3) := 2x1 + x2 + 3x3 − 70 = 0 (24.46) zu maximieren. Das heißt, es gibt k = 1 Gleichheitsnebenbedingungen und die Lagrange-Funktion ist gegeben durch L(λ, x1, x2, x3) : = U(x1, x2, x3)+ λg(x1, x2, x3) = −x21 − x22 − x23 + 100x1 + 50x2 + 150x3 + λ(2x1 + x2 + 3x3 − 70) (24.47) (vgl. (24.27) im Lehrbuch). Der Gradient der Lagrange-Funktion L(λ, x1, x2, x3) lautet somit gradL(λ, x1, x2, x3) = ( ∂L(λ, x1, x2, x3) ∂x1 , ∂L(λ, x1, x2, x3) ∂x2 , ∂L(λ, x1, x2, x3) ∂x3 , ∂L(λ, x1, x2, x3) ∂λ )T = (−2x1 + 100+ 2λ,−2x2 + 50+ λ,−2x3 + 150+ 3λ, 2x1 + x2 + 3x3 − 70)T . Durch Lösen des linearen Gleichungssystems −2x1 + 2λ+100 = 0 (24.48) − 2x2 + λ+ 50 = 0 (24.49) −2x3 + 3λ+150 = 0 (24.50) 2x1 + x2+3x3 − 70 = 0 (24.51) erhält man die stationären Stellen der Lagrange-Funktion L(λ, x1, x2, x3). Aus den ersten drei Gleichungen (24.48)–(24.50) folgt x1 = λ+ 50, x2 = 12λ+ 25 und x3 = 3 2 λ+ 75. (24.52) Werden die Terme in Gleichung (24.51) eingesetzt, dann folgt weiter: 2x1 + x2 + 3x3 − 70 = 0 ⇐⇒ 2(λ+ 50)+ 12λ+ 25+ 3 ( 3 2 λ+ 75 ) − 70 = 0 ⇐⇒ 7λ+ 280 = 0 ⇐⇒ λ = −40 Wird derWert λ = −40 in die drei Gleichungen in (24.52) eingesetzt, so erhält man für die Variablen dieWerte x1 = 10, x2 = 5 und x3 = 15. Das heißt, die Lagrange-Funktion L(λ, x1, x2, x3) besitzt nur die stationäre Stelle (−40, 10, 5, 15). Für die Funktion L(−40, x1, x2, x3) = −x21 − x22 − x23 + 20x1 + 10x2 + 30x3 + 2800 erhält man die Hesse-Matrix HL(−40,x1,x2,x3)= ∂2L(−40,x1,x2,x3) ∂x21 ∂2L(−40,x1,x2,x3) ∂x1∂x2 ∂2L(−40,x1,x2,x3) ∂x1∂x3 ∂2L(−40,x1,x2,x3) ∂x2∂x1 ∂2L(−40,x1,x2,x3) ∂x22 ∂2L(−40,x1,x2,x3) ∂x2∂x3 ∂2L(−40,x1,x2,x3) ∂x3∂x1 ∂2L(−40,x1,x2,x3) ∂x3∂x2 ∂2L(−40,x1,x2,x3) ∂x23 = −2 0 00 −2 0 0 0 −2 . 375 Kapitel 24 Teil VIII: Optimierung im Rn Da es sich bei der Hesse-Matrix HL(−40, x1, x2, x3) für alle (x1, x2, x3) ∈ (0,∞)3 um eine Diagonalmatrix mit ausschließlich negativen Hauptdiagonaleinträgen handelt, ist sie für alle (x1, x2, x3) ∈ (0,∞)3 negativ definit (vgl. Satz 10.32b) im Lehrbuch). Daraus folgt, dass die Funktion L(−40, x1, x2, x3) streng konkav ist (vgl. Satz 22.45d) im Lehrbuch). Die Stelle (10, 5, 15) ist daher die globale Maximalstelle von U unter der Gleichheitsnebenbedingung (24.46) (vgl. Satz 24.17b) im Lehrbuch), und der maximale Umsatz beträgt U(10, 5, 15) = −102 − 52 − 152 + 100 · 10+ 50 · 5+ 150 · 15 = 3150. Zu c): DerWert−λ = 40 ist der Schattenpreis einer Einheit der durch dieNebenbedingung 2x1+x2+3x3 = 70 restringierten Ressource. Er gibt an, wie sich dermaximale UmsatzU(10, 5, 15) = 3150 bei einer Veränderung derRestriktion c = 70 verhält. ZumBeispiel führt eineErhöhungvon c = 70 umeineMengeneinheit auf c = 71 dazu, dass der maximale Umsatz ungefähr um −λ = 40 Geldeinheiten steigt (vgl. Seite 739 im Lehrbuch). ** Aufgabe 24.22 (Optimierung im Rn mit Nebenbedingungen) Betrachtet wird die reellwertige Funktion f : R2 −→ R, (x, y) *→ f (x, y) = −x2 − y2 unter der Nebenbedingung x + y = 1. (24.53) a) Bestimmen Sie mit Hilfe der LagrangeschenMultiplikatorenregel Kandidaten für Extremalstellen der Funktion f unter der Nebenbedingung (24.53). Begründen Sie, ob es sich bei diesen Kandidaten bereits um alle möglichen Kandidaten für die Extremalstellen von f unter der Nebenbedingung (24.53) handelt. b) Erläutern Sie mit Hilfe der geränderten Hesse-Matrix der Lagrange-Funktion L, ob die in Aufgabenteil a) ermittelten Kandidaten tatsächlich Extremalstellen von f unter der Nebenbedingung (24.53) sind. c) Erläutern Sie, ob es sich bei den in Aufgabenteil b) ermittelten Extremalstellen von f um globale Extremalstellen handelt. Lehrbuch: Abschnitt 24.3 Lösung: Zu a): Die Funktion f ist unter der Gleichheitsnebenbedingung g(x, y) := x + y − 1 = 0 (24.54) zu optimieren. Das heißt, es gibt k = 1 Gleichheitsnebenbedingungen und die Lagrange-Funktion ist gegeben durch L(λ, x, y) := f (x, y)+ λg(x, y) = −x2 − y2 + λ(x + y − 1). (24.55) Der Gradient der Lagrange-Funktion L(λ, x, y) lautet daher gradL(λ, x, y) = ( ∂L(λ, x, y) ∂x , ∂L(λ, x, y) ∂y , ∂L(λ, x, y) ∂λ )T = (−2x + λ,−2y + λ, x + y − 1)T (vgl. (24.27) im Lehrbuch). Durch Lösen des linearen Gleichungssystems −2x +λ = 0 (24.56) − 2y+λ = 0 (24.57) x + y−1 = 0 (24.58) erhält man die stationären Stellen der Lagrange-Funktion L(λ, x, y). Aus den ersten beiden Gleichungen (24.56)–(24.57) folgt unmittelbar x = y = 12λ. In Gleichung (24.58) eingesetzt, folgt daraus weiter λ = 1 und damit insbesondere x = y = 12 . Das heißt, die Lagrange-Funktion L(λ, x, y) besitzt nur die stationäre Stelle( 1, 12 , 1 2 ) . 376 Kapitel 24Nichtlineare Optimierung im Rn Die Jacobi-Matrix an der Stelle (x, y) ∈ R2 lautet Jg(x, y) = grad g(x, y)T = ( ∂g(x, y) ∂x , ∂g(x, y) ∂y ) = (1, 1) (vgl. (24.29) im Lehrbuch). Der Rang der Jacobi-Matrix Jg(x, y), d.h. die Anzahl der linear unabhängigen Zeilenvektoren (Spaltenvektoren) von Jg(x, y) (vgl. Seite 195 imLehrbuch) beträgt somit 1 und ist damit gleich der Anzahl k der Gleichheitsnebenbedingungen für alle (x, y) ∈ R2. Folglich sind durch ( 1 2 , 1 2 ) bereits alle Kandidaten für lokale Extremalstellen von f unter der Gleichheitsnebenbedingung (24.54) gegeben (vgl. Satz 24.15 im Lehrbuch und Erläuterung auf Seite 731). Zu b): Die geränderte Hesse-Matrix der Lagrange-Funktion L lautet HL(λ, x, y) = 0 ∂g(x,y) ∂x ∂g(x,y) ∂y ∂g(x,y) ∂x ∂2L(λ,x,y) ∂x2 ∂2L(λ,x,y) ∂x∂y ∂g(x,y) ∂y ∂2L(λ,x,y) ∂y∂x ∂2L(λ,x,y) ∂y2 = 0 1 11 −2 0 1 0 −2 für alle (x, y) ∈ R2. Für die Determinante der geränderten Hesse-Matrix HL(λ, x, y) gilt somit det (HL(λ, x, y)) = 0+ 0+ 0− (−2)− 0− (−2) = 4 > 0 für alle (λ, x, y) ∈ R3. Bei der Stelle ( 1 2 , 1 2 ) handelt es sich somit um eine lokale Maximalstelle von f unter der Gleichheitsnebenbedingung (24.54) (vgl. Satz 24.18b) im Lehrbuch). Zu c): Die beiden Funktionen f und g sind stetig partiell differenzierbar und ihr DefinitionsbereichR2 umfasst keine Randstellen. Ferner ist der Rang der Jacobi-Matrix Jg(x, y) gleich der Anzahl k = 1 der Gleichheitsnebenbedingungen für alle (x, y) ∈ R2 (vgl. Aufgabenteil a)). Folglich muss eine Extremalstelle von f unter der Gleichheitsnebenbedingung (24.54) eine stationäre Stelle von L(λ, x, y) sein (vgl. Satz 24.15 im Lehrbuch). Da jedoch L(λ, x, y) neben ( 1, 12 , 1 2 ) keine weiteren stationären Stellen besitzt, impliziert dies, dass f unter der Nebenbedingung (24.54) keine anderen Extremalstellen oder Stellen mit Sattelpunkten aufweist. Daraus folgt insbesondere, dass die lokale Maximalstelle ( 1 2 , 1 2 ) sogar eine globale Maximalstelle von f unter der Nebenbedingung (24.54) ist. *** Aufgabe 24.23 (Anwendung der Optimierung im Rn mit Nebenbedingungen) Betrachtet wird ein Anleger, der ein Portfolio aus drei zur Auswahl stehenden Wertpapieren bildenmöchte. Dabeimöchte er dieWertpapieranteile x, y und z sowählen, dass die erwartete Rendite r beträgt und das mit dem Portfolio verbundene Investitionsrisiko minimiert wird. Die erwarteten Renditen der drei Wertpapiere betragen 110 , 2 10 und 3 10 , und das Risiko des Portfolios wird durch die reellwertige Funktion f : (0,∞)3 −→ R, (x, y, z) *→ f (x, y, z) = 1 20 x2 + 1 20 y2 + 1 20 z2 quantifiziert. a) Geben Sie das Optimierungsproblem in mathematischer Form an und interpretieren Sie es. b) Bestimmen Sie mit Hilfe der LagrangeschenMultiplikatorenregel Kandidaten für Extremalstellen von f unter den gegebenen Nebenbedingungen. Begründen Sie, ob es sich bei diesen Kandidaten bereits um alle möglichen Kandidaten für die Extremalstellen von f unter den gegebenen Nebenbedingungen handelt. c) Ermitteln Sie das risikominimale Portfolio und das globale Minimum der Risikofunktion f unter den gegebenen Nebenbedingungen in Abhängigkeit von der erwarteten Rendite r . 377 Kapitel 24 Teil VIII: Optimierung im Rn Lehrbuch: Abschnitt 24.3 Lösung: Zu a): Es ist die globaleMinimalstelle der Funktionf unter den beidenGleichheitsnebenbedingungen g1(x, y, z) := 110 x + 2 10 y + 3 10 z− r = 0 und g2(x, y, z) := x + y + z− 1 = 0 (24.59) zu bestimmen. Die erste Gleichheitsnebenbedingung stellt sicher, dass die erwartete Gesamtrendite des Portfolios r beträgt. Die zweite Gleichheitsnebenbedingung drückt aus, dass der Anleger sein gesamtes Kapital auf die drei Anlageformen verteilt. Zu b): Die Funktion f ist unter den beiden Gleichheitsnebenbedingungen (24.59) zu minimieren. Das heißt, es gibt k = 2 Gleichheitsnebenbedingungen, und die Lagrange-Funktion lautet somit L(λ1, λ2, x, y, z) : = f (x, y, z)+ λ1g1(x, y, z)+ λ2g2(x, y, z) = 1 20 x2 + 1 20 y2 + 1 20 z2 + λ1 ( 1 10 x + 2 10 y + 3 10 z− r ) + λ2(x + y + z− 1) (vgl. (24.27) im Lehrbuch). Der Gradient der Lagrange-Funktion ist folglich gegeben durch gradL(λ1, λ2, x, y, z) = ( ∂L(λ1, λ2, x, y, z) ∂x , ∂L(λ1, λ2, x, y, z) ∂y , ∂L(λ1, λ2, x, y, z) ∂z , ∂L(λ1, λ2, x, y, z) ∂λ1 , ∂L(λ1, λ2, x, y, z) ∂λ2 )T = ( 1 10 x + 1 10 λ1 + λ2, 110 y + 2 10 λ1 + λ2, 110 z+ 3 10 λ1 + λ2, 1 10 x + 2 10 y + 3 10 z− r, x + y + z− 1 )T . Durch Lösen des linearen Gleichungssystems 1 10 x + 1 10 λ1+λ2 = 0 (24.60) 1 10 y + 2 10 λ1+λ2 = 0 (24.61) 1 10 z+ 3 10 λ1+λ2 = 0 (24.62) 1 10 x+ 2 10 y+ 3 10 z − r= 0 (24.63) x+ y+ z − 1= 0 (24.64) erhält man die stationären Stellen der Lagrange-Funktion L(λ1, λ2, x, y, z). Für die ersten drei Gleichungen (24.60)–(24.62) erhält man nach kurzer Umformung: x = − λ1 − 10λ2 (24.65) y = −2λ1 − 10λ2 (24.66) z = −3λ1 − 10λ2 (24.67) Werden diese Ausdrücke für x, y und z in (24.63) und (24.64) eingesetzt, resultieren die beiden folgenden Gleichungen: −14λ1−60λ2 = 10r −6λ1−30λ2 = 1 Als Lösung dieses linearen Gleichungssystems erhält man nach kurzer Umformung λ1 = 1− 5r und λ2 = r − 730 . Durch Einsetzen dieser Ausdrücke für λ1 und λ2 in die drei Gleichungen (24.65)–(24.67) erhält man in Abhängigkeit von der erwarteten Rendite r die Anteile x = −5r + 4 3 , y = 1 3 und z = 5r − 2 3 . 378 Kapitel 24Nichtlineare Optimierung im Rn Für die Jacobi-Matrix an der Stelle (x, y, z) ∈ (0,∞)3 gilt Jg(x, y, z) = ( ∂g1(x,y,z) ∂x , ∂g1(x,y,z) ∂y , ∂g1(x,y,z) ∂z ∂g2(x,y,z) ∂x , ∂g2(x,y,z) ∂y , ∂g2(x,y,z) ∂z ) = ( 1 10 2 10 3 10 1 1 1 ) (vgl. (24.29) im Lehrbuch). Da die beiden Zeilen von Jg(x, y, z) offensichtlich linear unabhängig sind, besitzt die Jacobi-Matrix Jg(x, y, z) den Rang 2, d.h. die Anzahl der linear unabhängigen Zeilenvektoren (Spaltenvektoren) von Jg(x, y, z) beträgt 2 (vgl. Seite 195 im Lehrbuch). Das heißt, der Rang von Jg(x, y, z) ist gleich der Anzahl k der Gleichheitsnebenbedingungen für alle (x, y, z) ∈ (0,∞)3. Folglich sind durch( −5r + 4 3 , 1 3 , 5r − 2 3 ) (24.68) bereits alleKandidaten für lokaleExtremalstellen vonf unter den beidenGleichheitsnebenbedingungen (24.59) gegeben (vgl. Satz 24.15 im Lehrbuch und Erläuterung auf Seite 731). Zu c): Für die Funktion L ( 1− 5r, r − 7 30 , x, y, z ) = 1 20 x2 + 1 20 y2 + 1 20 z2 + (1− 5r) ( 1 10 x + 2 10 y + 3 10 z− r ) + ( r − 7 30 ) (x + y + z− 1) erhält man die Hesse-Matrix HL ( 1− 5r, r − 7 30 , x, y, z ) = 1 10 0 0 0 110 0 0 0 110 . AlsDiagonalmatrixmit nur positivenHauptdiagonaleinträgen ist dieHesse-MatrixHL ( 1− 5r, r − 730 , x, y, z ) für alle (x, y, z) ∈ (0,∞)3 positiv definit (vgl. Satz 10.32a) im Lehrbuch). Daraus folgt, dass die Funktion L ( 1− 5r, r − 730 , x, y, z ) streng konvex ist (vgl. Satz 22.45c) im Lehrbuch). Die Stelle (24.68) ist daher die globaleMinimalstelle vonf unter den beidenGleichheitsnebenbedingungen (24.59) (vgl. Satz 24.17a) imLehrbuch). Das heißt, bei (24.68) handelt es sich um das risikominimale Portfolio und das globale Minimum der Risikofunktion f unter den beiden Gleichheitsnebenbedingungen (24.59) in Abhängigkeit von der erwarteten Rendite r beträgt f ( −5r + 4 3 , 1 3 , 5r − 2 3 ) = 5 2 r2 − r + 7 60 . *** Aufgabe 24.24 (Optimierung im Rn mit Nebenbedingungen) Betrachtet wird die reellwertige Funktion f : (0,∞)3 −→ R, (x, y, z) *→ f (x, y, z) = x2y2z2 unter der Nebenbedingung 2x + 2y + 2z = 18. (24.69) a) Bestimmen Sie mit Hilfe der LagrangeschenMultiplikatorenregel Kandidaten für Extremalstellen der Funktion f unter der Nebenbedingung (24.69). Begründen Sie, ob es sich bei diesen Kandidaten bereits um alle möglichen Kandidaten für die Extremalstellen von f unter der Nebenbedingung (24.69) handelt. b) Erläutern Sie mit Hilfe der geränderten Hesse-Matrix der Lagrange-Funktion L, ob die in Aufgabenteil a) ermittelten Kandidaten tatsächlich Extremalstellen von f unter der Nebenbedingung (24.69) sind. 379 Kapitel 24 Teil VIII: Optimierung im Rn c) Erläutern Sie, ob es sich bei den in Aufgabenteil b) ermittelten Extremalstellen von f um globale Extremalstellen handelt. d) Geben Sie eine ökonomische Interpretation für den resultierendenWert des Lagrange- Multiplikators an. Lehrbuch: Abschnitt 24.3 Lösung: Zu a): Die Funktion f ist unter der Gleichheitsnebenbedingung g(x, y, z) := 2x + 2y + 2z− 18 = 0 (24.70) zu optimieren. Das heißt, es gibt k = 1 Gleichheitsnebenbedingungen, und die Lagrange-Funktion ist gegeben durch L(λ, x, y, z) : = f (x, y, z)+ λg(x, y, z) = x2y2z2 + λ(2x + 2y + 2z− 18) (24.71) (vgl. (24.27) im Lehrbuch). Der Gradient der Lagrange-Funktion L(λ, x, y, z) lautet somit gradL(λ, x, y, z) = ( ∂L(λ, x, y, z) ∂x , ∂L(λ, x, y, z) ∂y , ∂L(λ, x, y, z) ∂z , ∂L(λ, x, y, z) ∂λ )T = ( 2xy2z2 + 2λ, 2x2yz2 + 2λ, 2x2y2z+ 2λ, 2x + 2y + 2z− 18 )T . Durch Lösen des (nichtlinearen) Gleichungssystems 2xy2z2 + 2λ = 0 (24.72) 2x2yz2 + 2λ = 0 (24.73) 2x2y2z+ 2λ = 0 (24.74) 2x + 2y + 2z− 18 = 0 (24.75) erhält man die stationären Stellen der Lagrange-Funktion L(λ, x, y, z). Eine kurze Umformung liefert das zu (24.72)–(24.75) äquivalente (nichtlineare) Gleichungssystem: xy2z2 = −λ (24.76) x2yz2 = −λ (24.77) x2y2z = −λ (24.78) x + y + z = 9 (24.79) DurchGleichsetzen der beiden linken Seiten von (24.76) und (24.77) sowie von (24.77) und (24.78) folgt daraus weiter xyz(yz− xz) = 0 und xyz(xz− xy) = 0. Wegen x, y, z ∈ (0,∞) impliziert dies jedoch: xyz(yz− xz) = 0 ⇐⇒ yz− xz = 0 ⇐⇒ z(y − x) = 0 ⇐⇒ x = y xyz(xz− xy) = 0 ⇐⇒ xz− xy = 0 ⇐⇒ x(z− y) = 0 ⇐⇒ z = y Das heißt, es muss x = y = z gelten. In die Gleichung (24.79) eingesetzt liefert dies 3x = 9, also x = y = z = 3. Zusammen mit (24.76) erhält man daraus für den Lagrange-Multiplikator denWert λ = −243. Folglich besitzt die Lagrange-Funktion L(λ, x, y, z) nur die stationäre Stelle (−243, 3, 3, 3). Die Jacobi-Matrix an der Stelle (x, y, z) ∈ (0,∞)3 lautet Jg(x, y, z) = grad g(x, y, z)T = ( ∂g(x, y, z) ∂x , ∂g(x, y, z) ∂y , ∂g(x, y, z) ∂z ) = (2, 2, 2) (vgl. (24.29) im Lehrbuch). Der Rang der Jacobi-Matrix Jg(x, y, z), d.h. die Anzahl der linear unabhängigen Zeilenvektoren (Spaltenvektoren) von Jg(x, y, z) (vgl. Seite 195 im Lehrbuch), beträgt somit 1 und ist damit gleich der Anzahl k der Gleichheitsnebenbedingungen für alle (x, y, z) ∈ (0,∞)3. Folglich sind durch (3, 3, 3) 380 Kapitel 24Nichtlineare Optimierung im Rn bereits alle Kandidaten für lokale Extremalstellen von f unter der Gleichheitsnebenbedingung (24.70) gegeben (vgl. Satz 24.15 im Lehrbuch und Erläuterung auf Seite 731). Zu b): Die geränderte Hesse-Matrix der Lagrange-Funktion L lautet HL(λ, x, y, z) = 0 ∂g(x,y,z) ∂x ∂g(x,y,z) ∂y ∂g(x,y,z) ∂z ∂g(x,y,z) ∂x ∂2L(λ,x,y,z) ∂x2 ∂2L(λ,x,y,z) ∂x∂y ∂2L(λ,x,y,z) ∂x∂z ∂g(x,y,z) ∂y ∂2L(λ,x,y,z) ∂y∂x ∂2L(λ,x,y,z) ∂y2 ∂2L(λ,x,y,z) ∂y∂z ∂g(x,y,z) ∂z ∂2L(λ,x,y,z) ∂z∂x ∂2L(λ,x,y,z) ∂z∂y ∂2L(λ,x,y,z) ∂z2 = 0 2 2 2 2 2y2z2 4xyz2 4xy2z 2 4xyz2 2x2z2 4x2yz 2 4xy2z 4x2yz 2x2y2 für alle λ ∈ R und (x, y, z) ∈ (0,∞)3. Die geränderte Hesse-Matrix der Lagrange-Funktion L speziell an der Stelle (−243, 3, 3, 3) ist somit gegeben durch HL(−243, 3, 3, 3) = 0 2 2 2 2 2 · 34 4 · 34 4 · 34 2 4 · 34 2 · 34 4 · 34 2 4 · 34 4 · 34 2 · 34 . Um entscheiden zu können, ob es sich bei der Stelle (3, 3, 3) um eine lokale Minimal- oder Maximalstelle von f unter der Gleichheitsnebenbedingung (24.70) handelt, werden die beiden letzten Minoren der geränderten Hesse-Matrix HL(−243, 3, 3, 3) benötigt (vgl. Seite 734 im Lehrbuch). Für den vorletzten Hauptminor erhält man mit der Regel von Sarrus (vgl. (8.44) im Lehrbuch) det (H3(−243, 3, 3, 3)) = det 0 2 22 2 · 34 4 · 34 2 4 · 34 2 · 34 = 0+ 16 · 34 + 16 · 34 − 8 · 34 − 0− 8 · 34 = 16 · 34 > 0. Für den letzten Hauptminor erhält man durch Entwicklung nach der ersten Spalte (vgl. Satz 8.60 im Lehrbuch): det(H4(−243,3,3,3)) = det 0 2 2 2 2 2·34 4·34 4·34 2 4·34 2·34 4·34 2 4·34 4·34 2·34 = (−1)2 ·0·det 2·34 4·34 4·344·34 2·34 4·34 4·34 4·34 2·34 +(−1)3 ·2·det 2 2 24·34 2·34 4·34 4·34 4·34 2·34 +(−1)4 ·2·det 2 2 22·34 4·34 4·34 4·34 4·34 2·34 +(−1)5 ·2·det 2 2 22·34 4·34 4·34 4·34 2·34 4·34 Mit der Regel von Sarrus folgt daraus weiter det (H4(−243, 3, 3, 3)) = 0+ (−1)3 · 2 · 8 · (34)2 + (−1)4 · 2 · (−8) · (34)2 + (−1)5 · 2 · 8 · (34)2 = −48 · (34)2 < 0. Das heißt, der vorletzte Hauptminor ist positiv und der letzte Hauptminor ist negativ. Bei der Stelle (3, 3, 3) handelt es sich daher um eine lokale Maximalstelle von f unter der Gleichheitsnebenbedingung (24.70) (vgl. Satz 24.18b) im Lehrbuch). 381 Kapitel 24 Teil VIII: Optimierung im Rn Zu c): Die beiden Funktionen f und g sind stetig partiell differenzierbar und ihr Definitionsbereich (0,∞)3 umfasst keineRandstellen. Ferner ist derRangder Jacobi-MatrixJg(x, y, z)gleichderAnzahl k = 1derGleichheitsnebenbedingungen für alle (x, y, z) ∈ (0,∞)3 (vgl. Aufgabenteil a)). Folglich muss eine Extremalstelle von f unter derGleichheitsnebenbedingung (24.70) eine stationäre Stelle vonL(λ, x, y, z) sein (vgl. Satz 24.15 im Lehrbuch). Da jedoch L(λ, x, y, z) neben (−243, 3, 3, 3) keine weiteren stationären Stellen besitzt, impliziert dies, dass f unter der Nebenbedingung (24.70) keine anderen Extremalstellen oder Stellenmit Sattelpunkten besitzt. Daraus folgt insbesondere, dass die lokale Maximalstelle (3, 3, 3) sogar eine globale Maximalstelle von f unter der Nebenbedingung (24.70) ist. Zu d): Der Wert −λ = 243 ist der Schattenpreis einer Einheit der durch die Nebenbedingung 2x + 2y + 2z = 18 restringierten Ressource. Er gibt an, wie sich der maximale Funktionswert f (3, 3, 3) = 729 bei einer Veränderung der Restriktion c = 18 verhält. Zum Beispiel führt eine Erhöhung von c = 18 um eine Mengeneinheit auf c = 19 dazu, dass der maximale Funktionswert ungefähr um −λ = 243 Geldeinheiten steigt (vgl. Seite 739 im Lehrbuch). * Aufgabe 24.25 (Einhüllendensatz) Betrachtet wird die reellwertige Funktion f : R2 −→ R, (x, α) *→ f (x, α) = −(x − α2)2 + x, die neben der Variablen x auch noch von dem Parameter α abhängt, sowie ihre Maximalwertfunktion v(α) := max x∈R f (x, α). a) Bestimmen Sie die erste Ableitung von v mit Hilfe des Einhüllendensatzes. b) Geben Sie die Maximalwertfunktion v explizit an. Lehrbuch: Abschnitt 24.4 Lösung: Zu a): Für einen beliebigen aber festen Parameterwert α ∈ R erhält man für die erste und zweite Ableitung von f bezüglich der Variablen x f ′(x, α) = −2(x − α2)+ 1 und f ′′(x, α) = −2. Folglich gilt f ′(x, α) = 0 ⇐⇒ −2(x − α2)+ 1 = 0 ⇐⇒ x = 1 2 + α2. Das heißt, x∗(α) := 12 + α2 ist eine stationäre Stelle von f (x, α) und aus f ′′(x, α) < 0 für alle x ∈ R folgt, dass es sich bei x∗(α) um eine globale Maximalstelle von f in Abhängigkeit vom Parameter α handelt (vgl. Folgerung 18.8b) im Lehrbuch). Es gilt somit v(α) = f (x∗(α), α) und zusammen mit dem Einhüllendensatz (vgl. Satz 24.22 im Lehrbuch) liefert dies für die erste Ableitung der Maximalwertfunktion v: v′(α) = ∂f (x ∗(α), α) ∂α = −2 ( x∗(α)− α2 ) · (−2α) = 4α ( x∗(α)− α2 ) = 2α Zu b): Die Maximalwertfunktion v lautet explizit v : R −→ R, α *→ v(α) : = f (x∗(α), α) = − ( 1 2 + α2 − α2 )2 + 1 2 + α2 = − 1 4 + 1 2 + α2 = 1 4 + α2 (vgl. Seite 740 im Lehrbuch). 382 Kapitel 24Nichtlineare Optimierung im Rn ** Aufgabe 24.26 (Einhüllendensatz) Betrachtet wird die reellwertige Funktion f : R3 −→ R, (x, α1, α2) *→ f (x, α1, α2) = −5x2 + 10xα1 + 30xα2 + 12α1, die neben der Variablen x auch noch von den beiden Parametern α1 und α2 abhängt, sowie ihre Maximalwertfunktion v(α1, α2) := max x∈R f (x, α1, α2). a) Bestimmen Sie die beiden partiellen Ableitungen erster Ordnung von v mit Hilfe des Einhüllendensatzes. b) Geben Sie die Maximalwertfunktion v explizit an. c) Bestimmen Sie die beiden partiellen Ableitungen erster Ordnung von v ohne Zuhilfenahme des Einhüllendensatzes. Lehrbuch: Abschnitt 24.4 Lösung: Zu a): Für beliebige aber feste Parameterwerte α1, α2 ∈ R erhält man für die erste und zweite Ableitung von f bezüglich der Variablen x f ′(x, α1, α2) = −10x + 10α1 + 30α2 und f ′′(x, α1, α2) = −10. Folglich gilt f ′(x, α1, α2) = 0 ⇐⇒ −10x + 10α1 + 30α2 = 0 ⇐⇒ x = α1 + 3α2. Das heißt, x∗(α1, α2) := α1 + 3α2 ist eine stationäre Stelle von f (x, α1, α2) und aus f ′′(x, α1, α2) < 0 für alle x ∈ R folgt, dass es sich bei x∗(α1, α2) um eine globale Maximalstelle von f in Abhängigkeit von den beiden Parametern α1 und α2 handelt (vgl. Folgerung 18.8b) im Lehrbuch). Es gilt somit v(α1, α2) = f (x∗(α1, α2), α1, α2) und zusammen mit dem Einhüllendensatz (vgl. Satz 24.22 im Lehrbuch) liefert dies für die beiden partiellen Ableitungen erster Ordnung der Maximalwertfunktion v: ∂v(α1, α2) ∂α1 = ∂f (x ∗(α1, α2), α1, α2) ∂α1 = 10x∗(α1, α2)+ 12 = 10(α1 + 3α2)+ 12 ∂v(α1, α2) ∂α2 = ∂f (x ∗(α1, α2), α1, α2) ∂α2 = 30x∗(α1, α2) = 30(α1 + 3α2) Zu b): Die Maximalwertfunktion v lautet explizit v : R2−→R, (α1,α2) *→v(α1,α2) := f (x∗(α1, α2), α1, α2) = −5(α1 + 3α2)2 + 10(α1 + 3α2)α1 + 30(α1 + 3α2)α2 + 12α1 = −5(α21 + 6α1α2 + 9α22)+ 10α21 + 30α2α1 + 30α1α2 + 90α22 + 12α1 = 5α21 + 12α1 + 30α1α2 + 45α22 (vgl. Seite 740 im Lehrbuch). Zu c): Ausgehend von der expliziten Darstellung der Maximalwertfunktion v (vgl. Aufgabenteil b)) können die partiellenAbleitungen ersterOrdnungvonv ohneZuhilfenahmedesEinhüllendensatzes berechnetwerden.Man erhält dann: ∂v(α1, α2) α1 = 10α1 + 12+ 30α2 = 10(α1 + 3α2)+ 12 ∂v(α1, α2) α2 = 30α1 + 90α2 = 30(α1 + 3α2) 383 Kapitel 24 Teil VIII: Optimierung im Rn ** Aufgabe 24.27 (Einhüllendensatz) Betrachtet wird die reellwertige Funktion f : R3 −→ R, (x, y, α) *→ f (x, y, α) = −αx2 − 1 2 y2 + x(y + 1), die neben den Variablen x und y auch noch von dem Parameter α abhängt, sowie ihre Maximalwertfunktion v(α) := max (x,y)∈R2 f (x, y, α). a) Untersuchen Sie, unter welchen Voraussetzungen an den Parameter α ∈ R die Funktion f eine globale Maximalstelle besitzt. b) Bestimmen Sie die erste Ableitung von v mit Hilfe des Einhüllendensatzes. c) Ermitteln Sie, um wieviel sich der globale Maximalwert von f näherungsweise ver- ändert, wenn α ausgehend von 1 um eine Einheit erhöht wird. Lehrbuch: Abschnitt 24.4 Lösung: Zu a): Im Folgenden wird die Funktion f für einen beliebigen aber festen Parameterwert α ∈ R als Funktion von den beiden Variablen x und y betrachtet. Hierzu sei f̃α(x, y) := f (x, y, α) für alle (x, y) ∈ R2. Für den Gradienten von f̃α an der Stelle (x, y) ∈ R2 erhält man grad f̃α(x, y) = ( ∂f̃α(x, y) ∂x , ∂f̃α(x, y) ∂y )T = (−2αx + y + 1,−y + x)T . Durch Lösen des linearen Gleichungssystems −2αx + y+1 = 0 (24.80) x − y = 0 (24.81) erhält man die stationären Stellen von f in Abhängigkeit vom Parameter α. Aus der Gleichung (24.81) folgt unmittelbar x = y. Wird dies in die Gleichung (24.80) eingesetzt, erhält man weiter: −2αx + y + 1 = 0 ⇐⇒ x(1− 2α)+ 1 = 0 ⇐⇒ x = − 1 1− 2α Das heißt, es muss α = 12 gelten. In diesem Fall existiert die stationäre Stelle ( − 11−2α ,− 11−2α ) von f . Die Hesse-Matrix von f̃α an der Stelle (x, y) ∈ R2 lautet H f̃α (x, y) = ∂ 2f̃α(x,y) ∂x2 ∂2f̃α(x,y) ∂x∂y ∂2f̃α(x,y) ∂y∂x ∂2f̃α(x,y) ∂y2 = (−2α 1 1 −1 ) und besitzt die Determinante det ( H f̃α (x, y) ) = 2α − 1 (vgl. (8.42) im Lehrbuch). Es gilt somit ∂ 2f̃α(x,y) ∂x2 < 0 und det ( H f̃α (x, y) ) > 0 für alle (x, y) ∈ R2 genau dann, wenn α > 12 . Das heißt, für α > 1 2 besitzt die Funktion f eine globale Maximalstelle bei (x∗(α), y∗(α)) := ( − 1 1− 2α ,− 1 1− 2α ) (vgl. Folgerung 24.10d) im Lehrbuch). 384 Kapitel 24Nichtlineare Optimierung im Rn Zu b): Gemäß Aufgabenteil a) ist die Maximalwertfunktion von f für α > 12 definiert und gegeben durch v(α) = f (x∗(α), y∗(α), α) mit (x∗(α), y∗(α)) = (− 1 1− 2α ,− 1 1− 2α ) (vgl. Seite 740 im Lehrbuch). Mit dem Einhüllendensatz (vgl. Satz 24.22 im Lehrbuch) erhält man für die erste Ableitung der Maximalwertfunktion v: v′(α) = ∂f ( x∗(α), y∗(α), α ) ∂α = − (x∗(α))2 = −(− 1 1− 2α )2 = − 1 (1− 2α)2 (24.82) Zu c): Mit α = 1 und (24.82) erhält man v′(1) = − 1 (1−2·1)2 = −1. Das heißt, wird α ausgehend von 1 um eine Einheit erhöht, dann verringert sich der globale Maximalwert von f näherungsweise um 1. ** Aufgabe 24.28 (Einhüllendensatz) Betrachtet wird ein Unternehmen, das x > 0 Einheiten eines Produktes zu den Kosten K(x) = 12x2 − 2x herstellt und zum festen Stückpreis p > 0 vertreibt. a) Stellen Sie die Gewinnfunktion G(x, p) in Abhängigkeit von x und p auf und geben Sie den maximalen Gewinn v(p) = max x∈(0,∞) G(x, p) als Funktion vom Preis p an. Bestimmen Sie ferner die erste Ableitung der Maximalwertfunktion v(p). b) Der Stückpreis betrage nun p > 6 und die Kostenfunktion sei gegeben durch K(x) = x2 + 4x. Ferner wird für jede produzierte Einheit eine Steuer von 2 Geldeinheiten erhoben. Ermitteln Sie die Gewinnfunktion G(x, p) in Abhängigkeit von x und p und die erste Ableitung der zugehörigen Maximalwertfunktion v(p). Lehrbuch: Abschnitt 24.4 Lösung: Zu a): Die Gewinnfunktion in Abhängigkeit von x > 0 für einen beliebigen aber festen Preis p > 0 lautet G(x, p) = px −K(x) = px − ( 1 2 x2 − 2x ) = − 1 2 x2 + (p + 2)x. Für die erste und zweite Ableitung von G bezüglich der Variablen x gilt ∂G(x, p) ∂x = −x + p + 2 und ∂ 2G(x, p) ∂x2 = −1. Daraus folgt ∂G(x, p) ∂x = 0 ⇐⇒ −x + p + 2 = 0 ⇐⇒ x = p + 2. Das heißt, x∗(p) := p+ 2 ist eine stationäre Stelle vonG(x, p), und aus ∂2G(x,p) ∂x2 < 0 folgt, dass es sich bei x∗(p) um eine globale Maximalstelle von G in Abhängigkeit vom Preis p handelt (vgl. Folgerung 18.8b) im Lehrbuch). Es gilt somit v(p) = G(x∗(p), p) = − 1 2 x∗(p)2 + (p + 2)x∗(p) = 1 2 (p + 2)2 und für die erste Ableitung der Maximalwertfunktion v erhält man mit dem Einhüllendensatz (vgl. Satz 24.22 im Lehrbuch) v′(p) = ∂G(x ∗(p), p) ∂p = x∗(p) = p + 2. Zu b): Die Gewinnfunktion lautet nun G(x, p) = px −K(x)− 2x = px − ( x2 + 4x ) − 2x = −x2 + (p − 6)x 385 Kapitel 24 Teil VIII: Optimierung im Rn und für die erste und zweite Ableitung von G bezüglich der Variablen x gilt ∂G(x, p) ∂x = −2x + p − 6 und ∂ 2G(x, p) ∂x2 = −2. Daraus folgt ∂G(x, p) ∂x = 0 ⇐⇒ −2x + p − 6 = 0 ⇐⇒ x = 1 2 p − 3. Analog zu Aufgabenteil a) erhält man, dass die globale Maximalstelle vonG in Abhängigkeit vom Preis p jetzt durch x∗(p) := 12p − 3 und die erste Ableitung der Maximalwertfunktion durch v′(p) = ∂G(x ∗(p), p) ∂p = x∗(p) = 1 2 p − 3 gegeben ist. ** Aufgabe 24.29 (MC-Aufgaben zur Optimierung im Rn mit Ungleichheitsnebenbedingungen) Kreuzen Sie an, welche der Aussagen a) bis e) wahr und welche falsch sind: a) Ein Minimierungsproblem mit konvexer Zielfunktion f (x) und Ungleichheitsnebenbedingungen der Form g1(x) ≤ 0, . . . , gk(x) ≤ 0 ist ein konvexes Optimierungsproblem. b) Ein Maximierungsproblem mit konkaver Zielfunktion f (x) und Ungleichheitsnebenbedingungen der Form g1(x) ≤ 0, . . . , gk(x) ≤ 0 sowie konvexen Funktionen g1, . . . , gk kann in ein konvexes Optimierungsproblem überführt werden. c) Bei Optimierungsproblemen mit n Variablen und k Ungleichheitsnebenbedingungen muss n > k gelten. d) Für ein konvexes Optimierungsproblem sind die KKT-Bedingungen ein hinreichendes Kriterium für die Existenz einer globalen Minimalstelle. e) Für ein konvexes Optimierungsproblem sind die KKT-Bedingungen ein notwendiges Kriterium für die Existenz einer globalen Minimalstelle. a) b) c) d) e) Wahr Falsch Lehrbuch: Abschnitt 24.5 Lösung: Zu a): Falsche Aussage. Bei einem konvexen Optimierungsproblem mit zu minimierender konvexer Zielfunktion f müssen die Funktionen g1, . . . , gk zusätzlich konvex sein (vgl. Definition 24.27 im Lehrbuch). Zu b): Wahre Aussage (vgl. Seite 746 im Lehrbuch). Zu c): Falsche Aussage. Dies gilt nur für Optimierungsprobleme mit n Variablen und k Gleichheitsnebenbedingungen. Im Falle von Optimierungsproblemen mit nVariablen und k Ungleichheitsnebenbedingungen kann durchaus n ≤ k gelten (vgl. Seite 746 im Lehrbuch). Zu d): Wahre Aussage (vgl. Satz 24.29 im Lehrbuch). Zu e): Falsche Aussage. Für ein konvexes Optimierungsproblem sind die KKT-Bedingungen nicht nur ein hinreichendes Kriterium, sondern auch ein notwendiges Kriterium für die Existenz einer globalen Minimalstelle, wenn zusätzlich sogenannteQualifikationsbedingungen erfüllt sind (vgl. Satz 24.30 undBeispiel 24.32 imLehrbuch). 386 Kapitel 24Nichtlineare Optimierung im Rn *** Aufgabe 24.30 (Optimierung im Rn unter Ungleichheitsnebenbedingungen) Betrachtet wird das Minimierungsproblem min 3e−2y−x−2 − 3x − 2y − 6 (24.83) unter den beiden Nebenbedingungen: 2x + 2y + 2 ≤ 0 (24.84) x + 2y + 1 ≤ 0 (24.85) a) Untersuchen Sie, ob es sich bei diesem Minimierungsproblem (24.83)–(24.85) um ein konvexes Optimierungsproblem handelt. b) Erläutern Sie, ob die KKT-Bedingungen für dieses Minimierungsproblem ein notwendiges und hinreichendes Kriterium für die Existenz einer globalen Minimalstelle darstellen. c) Bestimmen Sie eine globale Minimalstelle dieses Optimierungsproblems. d) Erläutern Sie, ob die globale Minimalstelle eindeutig ist. Lehrbuch: Abschnitt 24.5 Lösung: Zu a): Es sei f (x, y) := 3e−2y−x−2 − 3x − 2y − 6, g1(x, y) := 2x + 2y + 2 und g2(x, y) := x + 2y + 1. Dann sind die Hesse-Matrizen von f , g1 und g2 gegeben durch: Hf (x, y) = ( 3e−2y−x−2 6e−2y−x−2 6e−2y−x−2 12e−2y−x−2 ) und Hg1 (x, y) = Hg2 (x, y) = ( 0 0 0 0 ) Diese drei Matrizen besitzen ausschließlich nichtnegative Hauptdiagonalelemente und es gilt det(Hf (x, y)) = det(Hg1 (x, y)) = det(Hg2 (x, y)) = 0. Die drei Hesse-Matrizen sind folglich positiv semi-definit (vgl. Folgerung 10.40c) im Lehrbuch) und die drei Funktionenf , g1 und g2 damit konvex (vgl. Satz 22.45 imLehrbuch). Das heißt, bei demMinimierungsproblem (24.83)–(24.85) handelt es sich um ein konvexes Optimierungsproblem (vgl. Definition 24.28 im Lehrbuch). Zu b): Bei demMinimierungsproblem (24.83)–(24.85) handelt es sich um ein konvexes Optimierungsproblem mit stetig partiell differenzierbarerZielfunktionf sowie stetig partiell differenzierbarenNebenbedingungsfunktionen g1 und g2 (vgl. Aufgabenteil a)). Folglich sind dieKKT-Bedingungen ein hinreichendesKriterium für die Existenz einer globalen Minimalstelle (vgl. Satz 24.29 im Lehrbuch). Da die Nebenbedingungsfunktionen g1 und g2 ferner affin-linear sind, stellen die KKT-Bedingungen auch ein notwendiges Kriterium für die Existenz einer globalen Minimalstelle dar (vgl. Satz 24.30 im Lehrbuch). Zu c): Die Lagrange-Funktion dieses Optimierungsproblems lautet L(λ1, λ2, x, y) = 3e−2y−x−2 − 3x − 2y − 6+ λ1(2x + 2y + 2)+ λ2(x + 2y + 1). Die beiden partiellen Ableitungen erster Ordnung von L bezüglich der Variablen x und y sind gegeben durch ∂L(λ1, λ2, x, y) ∂x = −3e−2y−x−2 − 3+ 2λ1 + λ2 und ∂L(λ1, λ2, x, y) ∂y = −6e−2y−x−2 − 2+ 2λ1 + 2λ2. Nullsetzen dieserAbleitungen liefert zusammenmit den komplementären Schlupfbedingungenλ1g1(x, y) = 0 und λ2g2(x, y) = 0 das (nichtlineare) Gleichungssystem: −3e−2y−x−2 − 3+ 2λ1 + λ2 = 0 (24.86) −6e−2y−x−2 − 2+ 2λ1 + 2λ2 = 0 (24.87) λ1(2x + 2y + 2) = 0 (24.88) λ2(x + 2y + 1) = 0 (24.89) 387 Kapitel 24 Teil VIII: Optimierung im Rn Je nachdem, welche der beiden Lagrange-Multiplikatoren λ1 und λ2 gleich und welche größer als Null vorausgesetzt werden, resultiert ein anderes gleichungsrestringiertes Optimierungsproblem. Das heißt, es sind insgesamt 22 = 4 verschiedene Fälle auf die Existenz einer globalen Minimalstelle zu untersuchen (vgl. Seite 749 im Lehrbuch). Fall 1: Es gelteλ1 = λ2 = 0.Aus (24.86) folgt dann−3e−2y−x−2=3,was einWiderspruch zu 3e−2y−x−2>0 ist. Fall 2: Es gelte λ1 > 0 und λ2 = 0. Mit λ2 = 0 erhält man für (24.86)–(24.87): −3e−2y−x−2 − 3+ 2λ1 = 0 (24.90) −6e−2y−x−2 − 2+ 2λ1 = 0 (24.91) Anschließende Subtraktion der zweiten Gleichung von der ersten Gleichung liefert 3e−2y−x−2 = 1.Wird dies in (24.90) eingesetzt, resultiert nach einer kurzenUmformung λ1 = 2. Einsetzen diesesWertes in (24.90) liefert weiter: 3e−2y−x−2 = 1 ⇐⇒ −2y − x − 2 = ln ( 1 3 ) ⇐⇒ −2y − x − 2 = − ln (3) ⇐⇒ x + 2y + 2 = ln (3) ⇐⇒ x + 2y + 1 = ln (3)− 1 > 0 Dies ist jedoch ein Widerspruch zu (24.85). Fall 3: Es gelte λ1 = 0 und λ2 > 0. Multiplikation der Gleichung (24.87) mit 12 und Subtraktion von der Gleichung (24.86) sowie anschließendes Einsetzen von λ1 = 0 liefert λ1 = 2 und damit den Widerspruch 0 = 2. Fall 4: Es gelte λ1, λ2 > 0. Dann erhält man aus (24.88)–(24.89) das lineare Gleichungssystem 2x + 2y + 2 = 0 x + 2y + 1 = 0, welches nach kurzer Rechnung zur Lösung x = −1 und y = 0 führt. Die KKT-Bedingungen liefern somit die globale Minimalstelle (−1, 0) und das globale Minimum f (−1, 0) = 3e−1− 3. Wegen λ1, λ2 > 0 sind an dieser Minimalstelle beide Nebenbedingungen (24.84)–(24.85) bindend, d.h. als Gleichungen erfüllt. Zu d): Da die KKT-Bedingungen für dieses Minimierungsproblem nicht nur ein hinreichendes Kriterium, sondern auch ein notwendiges Kriterium für die Existenz einer globalen Minimalstelle darstellen (vgl. Aufgabenteil b)), handelt es sich bei (−1, 0) um die einzige globale Minimalstelle des Optimierungsproblems. *** Aufgabe 24.31 (Optimierung im Rn unter Ungleichheitsnebenbedingungen) Betrachtet wird das Maximierungsproblem max ln(x)+ ln(y) (24.92) unter den beiden Nebenbedingungen: 10x+ 5y ≤ 350 (24.93) 1 10 x+1 5 y ≤ 8 (24.94) a) Untersuchen Sie, ob es sich bei diesem Maximierungsproblem (24.92)–(24.94) um ein konvexes Optimierungsproblem handelt. b) Bestimmen Sie die globalen Maximalstellen dieses Optimierungsproblems. c) Erläutern Sie, ob die in Aufgabenteil b) ermittelte Maximalstelle eindeutig ist. Lehrbuch: Abschnitt 24.5 388 Kapitel 24Nichtlineare Optimierung im Rn Lösung: Zu a): Das Maximierungsproblem (24.92) unter den Nebenbedingungen (24.93)–(24.94) ist äquivalent zum Minimierungsproblem min− ln(x)− ln(y) (24.95) unter den Nebenbedingungen (24.93)–(24.94) (vgl. Seite 746 im Lehrbuch). Im Folgenden sei f (x, y) := − ln(x)− ln(y), g1(x, y) := 10x + 5y − 350 und g2(x, y) := 110 x + 1 5 y − 8. Dann sind die Hesse-Matrizen von f , g1 und g2 gegeben durch: Hf (x, y) = ( 1 x2 0 0 1 y2 ) und Hg1 (x, y) = Hg2 (x, y) = ( 0 0 0 0 ) Die Diagonalmatrix Hf (x, y) besitzt ausschließlich positive Hauptdiagonalelemente und die beiden DiagonalmatrizenHg1 (x, y) = Hg2 (x, y)weisen nur nicht-negative Hauptdiagonalelemente auf. Folglich ist die Hesse- Matrix Hf (x, y) positiv-definit (vgl. Satz 10.32b) im Lehrbuch) und die beiden Hesse-Matrizen Hg1 (x, y) = Hg2 (x, y) sind positiv semi-definit (vgl. Satz 10.32c) imLehrbuch). Daraus folgt, dass die Zielfunktionf streng konvex ist und die beidenNebenbedingungsfunktionen g1 und g2 konvex sind (vgl. Satz 22.45a) und c) imLehrbuch). Das heißt, bei demMinimierungsproblem (24.95) unter den Nebenbedingungen (24.93)–(24.94) handelt es sich um ein konvexes Optimierungsproblem (vgl. Definition 24.28 im Lehrbuch). Zu b): Die Lagrange-Funktion des Minimierungsproblems (24.95) unter den Nebenbedingungen (24.93)– (24.94) lautet L(λ1, λ2, x, y) = − ln(x)− ln(y)+ λ1(10x + 5y − 350)+ λ2 ( 1 10 x + 1 5 y − 8 ) . Die beiden partiellen Ableitungen erster Ordnung von L bezüglich der Variablen x und y sind gegeben durch ∂L(λ1, λ2, x, y) ∂x = − 1 x + 10λ1 + λ210 und ∂L(λ1, λ2, x, y) ∂y = − 1 y + 5λ1 + λ25 . Nullsetzen dieserAbleitungen liefert zusammenmit den komplementären Schlupfbedingungenλ1g1(x, y) = 0 und λ2g2(x, y) = 0 das (nichtlineare) Gleichungssystem: − 1 x + 10λ1 + λ210 = 0 (24.96) − 1 y + 5λ1 + λ25 = 0 (24.97) λ1(10x + 5y − 350) = 0 (24.98) λ2 ( 1 10 x + 1 5 y − 8 ) = 0 (24.99) Je nachdem, welche der beiden Lagrange-Multiplikatoren λ1 und λ2 gleich und welche größer als Null vorausgesetzt werden, resultiert ein anderes gleichungsrestringiertes Optimierungsproblem. Das heißt, es sind insgesamt 22 = 4 verschiedene Fälle auf die Existenz einer globalen Minimalstelle zu untersuchen (vgl. Seite 749 im Lehrbuch). Fall 1: Es gelte λ1 = λ2 = 0. Aus (24.96) und (24.97) folgen dann die Widersprüche − 1x = 0 und − 1y = 0. Fall 2: Es gelte λ1 > 0 und λ2 = 0. Mit λ2 = 0 erhält man für (24.96)–(24.97): − 1 x + 10λ1 = 0 (24.100) − 1 y + 5λ1 = 0 (24.101) AnschließendeSubtraktion des zweifachender zweitenGleichungvonder erstenGleichung liefert− 1x+ 2y = 0, also y = 2x. Aus λ1 > 0 und (24.98) folgt ferner 10x + 5y − 350 = 0. Zusammen mit y = 2x folgt daraus 20x = 350, also x = 352 und y = 2x = 35. Das heißt, es gilt 110 x+ 15y = 35 4 > 8. Dies ist jedoch ein Widerspruch zu (24.94). 389 Kapitel 24 Teil VIII: Optimierung im Rn Fall 3: Es gelte λ1 = 0 und λ2 > 0. Mit λ1 = 0 erhält man für (24.96)–(24.97): − 1 x + λ2 10 = 0 (24.102) − 1 y + λ2 5 = 0 (24.103) Anschließende Subtraktion des 12 -fachen der zweitenGleichung von der erstenGleichung liefert− 1x + 12y = 0, also x = 2y. Aus λ2 > 0 und (24.99) folgt ferner 1 10 x + 1 5 y − 8 = 0. Zusammen mit x = 2y folgt daraus 25 y = 8, also y = 20 und x = 2y = 40. Das heißt, es gilt 10x + 5y = 500 > 350. Dies ist jedoch ein Widerspruch zu (24.93). Fall 4: Es gelte λ1, λ2 > 0. Dann erhält man aus (24.98)–(24.99) das lineare Gleichungssystem 10x + 5y − 350 = 0 1 10 x + 1 5 y − 8 = 0 welches nach kurzer Rechnung zur Lösung x = 20 und y = 30 führt. Da es sich bei dem Minimierungsproblem (24.95) unter den Nebenbedingungen (24.93)–(24.94) um ein konvexes Optimierungsproblem handelt (vgl. Aufgabenteil a)), die Funktionen f , g1 und g2 stetig partiell differenzierbar sind und ferner die Nebenbedingungsfunktionen g1 und g2 zusätzlich affin-linear sind, sind die KKT-Bedingungen ein notwendiges und hinreichendesKriterium für die Existenz einer globalenMinimalstelle (vgl. Satz 24.30 imLehrbuch). Die Stelle (20, 30) ist somit eine globale Minimalstelle des Minimierungsproblems (24.95) unter den Nebenbedingungen (24.93)–(24.94) und das globaleMinimumbeträgtf (20, 30) = − ln(20)−ln(30). Das ursprünglicheMaximierungsproblem (24.92) unter den Nebenbedingungen (24.93)–(24.94) besitzt folglich die globale Maximalstelle (20, 30) und das globale Maximum ist gegeben durch −f (20, 30) = ln(20) + ln(30). Wegen λ1, λ2 > 0 sind an dieser Maximalstelle beide Nebenbedingungen (24.93)–(24.94) bindend, d.h. als Gleichungen erfüllt. Zu c): Da die KKT-Bedingungen für dieses Optimierungsproblem nicht nur ein hinreichendes, sondern auch ein notwendiges Kriterium für die Existenz einer Optimalstelle darstellen (vgl. Aufgabenteil b)), handelt es sich bei (20, 30) um die einzige globale Maximalstelle des Optimierungsproblems. *** Aufgabe 24.32 (Optimierung im Rn unter Ungleichheitsnebenbedingungen) Betrachtet wird das Minimierungsproblem min(x − 2)2 + (y + 3)2 (24.104) unter den drei Nebenbedingungen: −x − 2y − 2 ≤ 0 (24.105) −x ≤ −2 (24.106) −y ≤ 3 (24.107) a) Untersuchen Sie, ob es sich bei diesem Minimierungsproblem (24.104)–(24.107) um ein konvexes Optimierungsproblem handelt. Erläutern Sie ferner kurz, ob die KKT- Bedingungen für dieses Minimierungsproblem ein notwendiges und hinreichendes Kriterium für die Existenz einer globalen Minimalstelle darstellen. b) Bestimmen Sie die globalen Minimalstellen dieses Optimierungsproblems. Lehrbuch: Abschnitt 24.5 390 Kapitel 24Nichtlineare Optimierung im Rn Lösung: Zu a): Es sei f (x, y) := (x − 2)2 + (y + 3)2, g1(x, y) := −x − 2y − 2, g2(x, y) := −x + 2 und g3(x, y) := −y − 3. Dann sind die Hesse-Matrizen von f , g1, g2 und g3 gegeben durch: Hf (x, y) = ( 2 0 0 2 ) und Hg1 (x, y) = Hg2 (x, y) = Hg3 (x, y) = ( 0 0 0 0 ) Die DiagonalmatrixHf (x, y) besitzt ausschließlich positive Hauptdiagonalelemente und die drei Diagonalmatrizen Hg1 (x, y) = Hg2 (x, y) = Hg3 (x, y) weisen nur nicht-negative Hauptdiagonalelemente auf. Folglich ist die Hesse-Matrix Hf (x, y) positiv-definit (vgl. Satz 10.32b) im Lehrbuch) und die drei Hesse-Matrizen Hg1 (x, y) = Hg2 (x, y) = Hg3 (x, y) sind positiv semi-definit (vgl. Satz 10.32c) im Lehrbuch). Daraus folgt, dass die Zielfunktion f streng konvex ist und die drei Nebenbedingungsfunktionen g1, g2 und g3 konvex sind (vgl. Satz 22.45a) und c) im Lehrbuch). Das heißt, bei dem Minimierungsproblem (24.104) unter den Nebenbedingungen (24.105)–(24.107) handelt es sich um ein konvexes Optimierungsproblem (vgl. Definition 24.28 im Lehrbuch). Bei dem Minimierungsproblem (24.104)–(24.107) handelt es sich um ein konvexes Optimierungsproblem mit stetig partiell differenzierbarer Zielfunktion f sowie stetig partiell differenzierbaren Nebenbedingungsfunktionen g1, g2 und g3. Folglich sind die KKT-Bedingungen ein hinreichendes Kriterium für die Existenz einer globalen Minimalstelle (vgl. Satz 24.29 im Lehrbuch). Da die drei Nebenbedingungsfunktionen g1, g2 und g3 ferner zusätzlich affin-linear sind, stellen die KKT-Bedingungen auch ein notwendiges Kriterium für die Existenz einer globalen Minimalstelle dar (vgl. Satz 24.30 im Lehrbuch). Zu b): Die Lagrange-Funktion des Minimierungsproblems (24.104) unter den Nebenbedingungen (24.105)– (24.107) lautet L(λ1, λ2, λ3, x, y) = (x − 2)2 + (y + 3)2 + λ1(−x − 2y − 2)+ λ2(−x + 2)+ λ3(−y − 3). Die beiden partiellen Ableitungen erster Ordnung von L bezüglich der Variablen x und y sind gegeben durch ∂L(λ1, λ2, λ3, x, y) ∂x = 2(x − 2)− λ1 − λ2 und ∂L(λ1, λ2, λ3, x, y) ∂y = 2(y + 3)− 2λ1 − λ3. Anschließendes Nullsetzen dieser Ableitungen führt zusammen mit den komplementären Schlupfbedingungen λ1g1(x, y) = 0, λ2g2(x, y) = 0 und λ3g3(x, y) = 0 zum linearen Gleichungssystem: 2x − λ1 − λ2 − 4 = 0 (24.108) 2y − 2λ1 − λ3 + 6 = 0 (24.109) λ1(−x − 2y − 2) = 0 (24.110) λ2(−x + 2) = 0 (24.111) λ3(−y − 3) = 0 (24.112) Je nachdem, welche der drei Lagrange-Multiplikatoren λ1, λ2 und λ3 gleich und welche größer als Null vorausgesetzt werden, resultiert ein anderes gleichungsrestringiertes Optimierungsproblem. Das heißt, es sind insgesamt 23 = 8 verschiedene Fälle auf die Existenz einer globalenMinimalstelle zu untersuchen (vgl. Seite 749 im Lehrbuch). Fall 1: Es gelte λ1 = λ2 = λ3 = 0. Aus (24.108)–(24.109) folgt dann x = 2 und y = −3. Die Lösung (2,−3) verletzt jedoch die Nebenbedingung (24.105) und ist damit keine globale Minimalstelle. Fall 2: Es gelte λ1 > 0 und λ2 = λ3 = 0. Für λ1 > 0 folgt aus (24.110) −x − 2y − 2 = 0. (24.113) Ferner erhält man mit λ2 = λ3 = 0 und (24.108)–(24.109) das lineare Gleichungssystem: 2x − λ1 − 4 = 0 2y − 2λ1 + 6 = 0 (24.114) WerdendiesebeidenGleichungennachx bzw.y aufgelöst unddie resultierendenTermeanschließend in (24.113) eingesetzt, erhält man − ( 1 2 λ1 + 2 ) − 2(λ1 − 3)− 2 = 0 391 Kapitel 24 Teil VIII: Optimierung im Rn bzw. nach einer kurzen Umformung− 52λ1+2 = 0, also λ1 = 45 . Durch Einsetzen diesesWertes in das lineare Gleichungssystem (24.114) resultieren für die beiden Variablen x und y die Werte x = 125 und y = − 115 . Bei( 12 5 ,− 115 ) handelt es sich somit um eine globaleMinimalstellemit demZielfunktionswertf ( 12 5 ,− 115 ) = 45 . Fall 3: Es gelte λ2 > 0 und λ1 = λ3 = 0. Aus λ1 = λ3 = 0 und (24.109) folgt y = −3, und λ2 > 0 impliziert zusammen mit (24.111) x = 2. Bei (2,−3) handelt es sich jedoch um keine globale Minimalstelle (vgl. Fall 1). Fall 4: Es gelte λ3 > 0 und λ1 = λ2 = 0. Aus λ1 = λ2 = 0 und (24.108) folgt x = 2, und λ3 > 0 impliziert zusammen mit (24.112) y = −3. Bei (2,−3) handelt es sich jedoch um keine globale Minimalstelle (vgl. Fall 1). Fall 5: Es gelte λ1, λ2 > 0 und λ3 = 0. Aus λ2 > 0 und (24.111) folgt x = 2. Wird x = 2 in (24.108) eingesetzt, erhält man −λ1 = λ2, was im Widerspruch zu λ1, λ2 > 0 steht. Fall 6: Es gelte λ1, λ3 > 0 und λ2 = 0. Aus λ3 > 0 und (24.112) folgt y = −3. Wird y = −3 in (24.109) eingesetzt, erhält man −2λ1 = λ3, was im Widerspruch zu λ1, λ3 > 0 steht. Fall 7 und Fall 8: Es gelte λ2, λ3 > 0 und λ1 = 0 oder λ1, λ2, λ3 > 0. In beiden Fällen folgt aus λ2, λ3 > 0 und (24.111)-(24.112) x = 2 und y = −3. Bei (2,−3) handelt es sich jedoch um keine globale Minimalstelle (vgl. Fall 1). Die KKT-Bedingungen liefern folglich die eindeutige globale Minimalstelle ( 12 5 ,− 115 ) und das globale Minimumbeträgt f ( 12 5 ,− 115 ) = 45 (vgl. Fall 2).Wegenλ1 > 0 undλ2 = λ3 = 0 ist an der globalenMinimalstelle( 12 5 ,− 115 ) nur die erste Nebenbedingung (24.105) bindend, während die beiden anderen Nebenbedingungen (24.106)–(24.107) nicht bindend, also als echte Ungleichungen erfüllt sind. 392 25. Lineare Optimierung * Aufgabe 25.1 (MC-Aufgaben zur Linearen Optimierung) Kreuzen Sie an, welche der Aussagen a) bis e) wahr und welche falsch sind: a) Unter linearen Optimierungsproblemen versteht man Optimierungsprobleme, bei denen sowohl die Zielfunktion als auch die Gleichungs- und Ungleichungsnebenbedingungen lineare Funktionen der Entscheidungsvariablen sind. b) Es liegt ein lineares Optimierungsproblem in Standardform vor, wenn es sich um ein Maximierungsproblem mit einer linearen Zielfunktion und linearen Gleichungs- und Ungleichungsnebenbedingungen mit Nichtnegativitätsbedingungen x1, . . . , xn ≥ 0 für die Entscheidungsvariablen handelt. c) Ein lineares Optimierungsproblem in Standardform besitzt mindestens eine optimale Lösung. d) Jede optimale Lösung eines Optimierungsproblems in Standardform lässt sich als Konvexkombination aus Eckpunkten des zulässigen Bereichs darstellen, die ebenfalls optimal sind. e) Bei der Suche nach einer optimalen Lösung eines linearen Optimierungsproblems in Standardform kannman sich auf die endlich vielen Eckpunkte des zulässigen Bereichs beschränken. a) b) c) d) e) Wahr Falsch Lehrbuch: Abschnitte 25.1, 25.3 und 25.4 Lösung: Zu a): Wahre Aussage (vgl. Seite 760 im Lehrbuch). Zu b): Falsche Aussage. Ein lineares Optimierungsproblem in Standardform ist ein Maximierungsproblem mit linearer Zielfunktion und linearen Ungleichungsnebenbedingungen der Form ≤ und Nichtnegativitätsbedingungen x1, . . . , xn ≥ 0 für die Entscheidungsvariablen (vgl. Definition 25.5 im Lehrbuch). Zu c): FalscheAussage. Ein linearesOptimierungsproblem in Standardformbesitzt keine optimale Lösung, falls der zulässige Bereich des Optimierungsproblems leer ist. Im Falle eines nach oben unbeschränkten zulässigen Bereichs ist es ebenfalls möglich, dass keine optimale Lösung existiert (vgl. Satz 25.10a) und Abbildung 25.3 im Lehrbuch). Zu d): Wahre Aussage (vgl. Satz 25.10b) im Lehrbuch). Zu e): Wahre Aussage (vgl. Seite 768 im Lehrbuch). ** Aufgabe 25.2 (Graphische Lösung von linearen Optimierungsproblemen) Ein Getränkeunternehmenmöchte aus den drei Getränken Likör 1, Likör 2 und Orangensaft eine neue Getränkemischung herstellen, wobei sich diese drei Getränke bezüglich ihres Alkoholgehalts und Preises wie folgt unterscheiden: Getränk Alkohol (in %) Kosten (€/Liter) Likör 1 20 12 Likör 2 10 18 Orangensaft 0 2 393 Kapitel 25 Teil VIII: Optimierung im Rn Das neue Mischgetränk soll dabei die folgenden Eigenschaften besitzen: • Mindestens einen Alkoholgehalt von 3% aufweisen • Mindestens zu 10% aus Likör 2 bestehen • Maximal zu 75% aus Orangensaft bestehen Die Variablen x1, x2 und x3 bezeichnen die Anteile der drei Getränke Likör 1, Likör 2 und Orangensaft. Das Unternehmen verfolgt dabei das Ziel der Kostenminimierung pro Liter. a) Formulieren Sie die Problemstellung als lineares Optimierungsproblem mit den drei Variablen x1, x2 und x3. b) Zeigen Sie, dass sich dieses lineare Optimierungsproblem in den beiden Variablen x2 und x3 ausdrücken und somit im R2 graphisch lösen lässt. c) Lösen Sie das lineare Optimierungsproblem graphisch. d) Untersuchen Sie, wie sich die optimale Lösung aus Aufgabenteil c) verändert, wenn das Mischgetränk einen Alkoholgehalt von genau 5% besitzen soll. Lehrbuch: Abschnitte 25.1 und 25.2 Lösung: Zu a): Als lineares Optimierungsproblem formuliert lautet die Problemstellung: Minimiere K(x1, x2, x3) := 12x1 + 18x2 + 2x3 (25.1) unter den Nebenbedingungen x1+ x2 + x3 = 1 (Mischungsbedingung) 20x1+10x2 ≥ 3 (Alkoholgehalt-Bedingung) (25.2) x2 ≥ 0,1 (Likör 2-Bedingung) x3 ≤ 0,75 (Orangensaft-Bedingung) und den Nichtnegativitätsbedingungen x1, x2, x3 ≥ 0. (25.3) Zu b): Aus (25.3) und der ersten Nebenbedingung von (25.2) folgt x1 = 1− x2 − x3 ≥ 0. In die Zielfunktion (25.1) und in die zweite Nebenbedingung von (25.2) eingesetzt, liefert dies K(x1, x2, x3) = 12x1 + 18x2 + 2x3 = 12(1− x2 − x3)+ 18x2 + 2x3 = 12+ 6x2 − 10x3 =: K̃(x2, x3) und 20x1 + 10x2 ≥ 3 ⇐⇒ 20(1− x2 − x3)+ 10x2 ≥ 3 ⇐⇒ 10x2 + 20x3 ≤ 17. Damit erhält man für das lineare Optimierungsproblem die äquivalente Darstellung: Minimiere K̃(x2, x3) = 12+ 6x2 − 10x3 (25.4) unter den Nebenbedingungen x2+ x3 ≤ 1 10x2+20x3 ≤ 17 (25.5) x2 ≥ 0,1 x3 ≤ 0,75 und den Nichtnegativitätsbedingungen x2, x3 ≥ 0. (25.6) Zu c): Aufgrund der Nichtnegativitätsbedingungen x2, x3 ≥ 0 liegt der zulässige Bereich Z im 1. Quadranten desR2. Erwird begrenzt durch dieGeradenx3 = 0,85− 12 x2,x2 = 0,1,x3 = 0,75undx3 = 1−x2, die sich aus den vier Nebenbedingungen (25.5) ergeben, wenn sie jeweils voll ausgeschöpft werden (vgl. Abbildung 25.1). 394 Kapitel 25Lineare Optimierung x 2 x 3 0 0,3 0,75 0,85 1 0 0,1 0,5 1 1,5 1,7 x 3 = 1 x 2 x 3 = 0,75 x 3 = 0,85 12 x2 x 2 = 0,1 x3 = 3 4 1 2 x2 x y K 0 = 1 0 K 0 = 5 ,1 K 0 = 5 ,6 Z Abb. 25.1: Graphische Lösung des linearen Optimierungsproblems (25.4)–(25.6) Für einen festenWertK0 ∈ R+ liegen alle (x2, x3) ∈ R2 mitK0 = 12+6x2−10x3 auf der Iso-Kosten-Gerade zu denKostenK0. Die Iso-Kosten-Geraden zu verschiedenenKostenK0 ∈ R+ sind parallel. In Abbildung 25.1 ist die Iso-Kosten-Gerade zu den Kosten K0 = 10 eingezeichnet. Zur Ermittlung der minimalen Kosten wird diese Iso-Kosten-Gerade parallel nach links oben bis zum Rand des zulässigen Bereichs Z verschoben. Auf diese Weise erhält man den Eckpunkt x∗ = (x∗2 , x∗3 ), für den die Zielfunktion K̃(x2, x3) = 12+ 6x2 − 10x3 unter allen zulässigen Lösungen (x2, x3) ∈ Z ihrMinimum annimmt.Wie ausAbbildung 25.1 ersichtlichwird, ist die optimale Lösung gegeben durch x∗ = (0,1; 0,75) und führt zu dem Kostenminimum K̃(0,1, 0,75) = 12+ 6 · 0,1− 10 · 0,75 = 5,1. Die optimale Mischung besteht folglich aus x1 = 1− 0,1− 0,75 = 0,15 Anteilen Likör 1, x2 = 0,1 Anteilen Likör 2 und x3 = 0,75 Anteilen Orangensaft. Zu d): Die zweite Nebenbedingung von (25.2) verändert sich dann zu 20x1 + 10x2 = 5. Durch Einsetzen von x1 = 1− x2 − x3 folgt daraus weiter 20x1 + 10x2 = 5 ⇐⇒ 20(1− x2 − x3)+ 10x2 = 5 ⇐⇒ 10x2 + 20x3 = 15. Folglich ist die zweite Nebenbedingung in (25.5) durch 10x2+20x3 = 15 zu ersetzen.Wie aus Abbildung 25.1 ersichtlich ist, ergibt sich dann die optimale Lösung zu y∗ = (0,1; 0,7). Das heißt, das Kostenminimum ist nun gegeben durch K(0,1, 0,7) = 12+ 6 · 0,1− 10 · 0,7 = 5,6 und die optimale Mischung besteht aus x1 = 1−0,1−0,7 = 0,2 Anteilen Likör 1, x2 = 0,1 Anteilen Likör 2 und x3 = 0,7 Anteilen Orangensaft. ** Aufgabe 25.3 (Graphische Lösung von linearen Optimierungsproblemen) Betrachtet wird ein Betrieb, der mit Hilfe von drei Produktionsfaktoren F1, F2 und F3 zwei verschiedene Produkte P1 und P2 produziert. Die folgende Tabelle gibt die Produktionskoeffizienten, den Bestand an Produktionsfaktoren sowie den Gewinn je produzierter Einheit an: 395 Kapitel 25 Teil VIII: Optimierung im Rn Produktions- Produkte Bestand faktoren P1 P2 F1 1 1 50 F2 10 40 800 F3 8 20 460 Gewinn 200 600 Die Variablen x1 ≥ 0 und x2 ≥ 0 bezeichnen die Produktionsmengen der beiden Produkte P1 und P2. Der Betrieb verfolgt als Ziel die Gewinnmaximierung, wobei bekannt ist, dass vom zweiten Produkt maximal 15 Einheiten abgesetzt werden können. a) Formulieren Sie die Problemstellung als lineares Optimierungsproblem in Standardform. b) Bestimmen Sie den zulässigen Bereich des linearen Optimierungsproblems. c) Lösen Sie das lineare Optimierungsproblem graphisch. Lehrbuch: Abschnitte 25.2 und 25.3 Lösung: Zu a): Das lineare Optimierungsproblem lautet in Standardform (vgl. Definition 25.5 im Lehrbuch): Maximiere z(x1, x2) := 200x1 + 600x2 (25.7) unter den Nebenbedingungen x1+ x2 ≤ 50 10x1+40x2 ≤ 800 (25.8) 8x1+20x2 ≤ 460 x2 ≤ 15 und den Nichtnegativitätsbedingungen x1, x2 ≥ 0. (25.9) Zu b): Der zulässige Bereich dieses linearen Optimierungsproblems ist gegeben durch Z := { x ∈ R2 : x1 + x2 ≤ 50, 10x1 + 40x2 ≤ 800, 8x1 + 20x2 ≤ 460, x2 ≤ 15, x1, x2 ≥ 0 } (vgl. Definition 25.7 im Lehrbuch). Zu c): Aufgrund der Nichtnegativitätsbedingungen x1, x2 ≥ 0 liegt der zulässige Bereich Z im 1. Quadranten des R2 und wird durch die x1-Achse und die x2-Achse begrenzt. Die anderen Begrenzungen vonZ sind durch die Geraden x1 + x2 = 50, 10x1 + 40x2 = 800, 8x1 + 20x2 = 460 und x2 = 15 festgelegt. Diese ergeben sich aus den vier Nebenbedingungen (25.8), wenn sie jeweils voll ausgeschöpft werden (vgl. Abbildung 25.2). Für einen festenWert z0 ∈ R+ liegen alle (x1, x2) ∈ R2 mit z0 = 200x1+600x2 auf der Iso-Gewinn-Geraden zum Gewinn z0. Die Iso-Gewinn-Geraden zu verschiedenen Gewinnen z0 ∈ R+ sind parallel. In Abbildung 25.2 ist die Iso-Gewinn-Gerade zumGewinn z0 = 6000 eingezeichnet. Zur Ermittlung desmaximalenGewinns wird diese Iso-Gewinn-Gerade parallel nach rechts oben bis zum Rand des zulässigen BereichsZ verschoben. Auf diese Weise erhält man den Eckpunkt x∗ = (x∗1 , x∗2 ), für den die Zielfunktion z(x1, x2) = 200x1+600x2 unter allen zulässigen Lösungen (x1, x2) ∈ Z ihr Maximum annimmt. Zur analytischen Berechnung dieser Lösung kann zum Beispiel die Gleichung 8x1 + 20x2 = 460 nach der Variablen x2 aufgelöst werden. Durch Gleichsetzen des dabei resultierenden Ausdrucks mit x2 = 15 erhält man dann 23− 2 5 x1 = 15 bzw. x1 = 20. Das heißt, die optimale Lösung ist x∗ = (20, 15) 396 Kapitel 25Lineare Optimierung x 1 x 2 0 10 20 30 40 50 0 10 20 30 40 50 60 x ∗ z0 = 6000 z0 = 13000 x 1 + x 2 = 50 10x 1 + 40 x 2 = 800 8x 1 + 20 x 2 = 460 x 2 = 15 Z Abb. 25.2: Graphische Lösung des linearen Optimierungsproblems (25.7)–(25.9) und führt zu dem Gewinnmaximum z(20, 15) = 200 · 20+ 600 · 15 = 13000. Das optimale Produktionsprogramm besteht folglich aus 20 Mengeneinheiten des Produkts P1 und 15 Mengeneinheiten des Produkts P2. ** Aufgabe 25.4 (Anwendung des Simplex-Algorithmus) Zur Herstellung von zwei Produkten P1 und P2 werden drei Maschinen M1,M2 und M3 benötigt. Die folgende Tabelle gibt die benötigten Fertigungszeiten (in Minuten) pro Mengeneinheit, die zur Verfügung stehenden Betriebszeiten sowie den Gewinn je produzierter Mengeneinheit an: Maschinen Produkte Betriebszeiten P1 P2 M1 2 1 120 M2 1 1 70 M3 1 3 150 Gewinn 10 15 Die Variablen x1, x2 ≥ 0 bezeichnen die Produktionsmengen der beiden Produkte P1 und P2. Der Betrieb verfolgt als Ziel die Gewinnmaximierung. a) Formulieren Sie die Problemstellung als lineares Optimierungsproblem in Standardform mit Schlupfvariablen. b) Bestimmen Sie mit Hilfe des Simplex-Algorithmus eine optimale Lösung. Geben Sie die bei den Austauschschritten jeweils resultierenden Basislösungen an. c) Lösen Sie das lineare Optimierungsproblem zur Kontrolle graphisch. 397 Kapitel 25 Teil VIII: Optimierung im Rn Lehrbuch: Abschnitte 25.2, 25.3 und 25.4 Lösung: Zu a): Das lineare Optimierungsproblem lautet in Standardform mit Schlupfvariablen (vgl. Definition 25.11 im Lehrbuch): Maximiere z(x1, x2) := 10x1 + 15x2 (25.10) unter den Nebenbedingungen 2x1+ x2 + x3 = 120 x1+ x2 +x4 = 70 (25.11) x1+3x2 + x5 = 150 und den Nichtnegativitätsbedingungen x1, x2, x3, x4, x5 ≥ 0. (25.12) Das heißt, zu den zwei Entscheidungsvariablen x1 und x2 sind die drei Schlupfvariablen x3, x4, x5 hinzugekommen. Zu b): Für die rechte Seite b des linearen Gleichungssystems (25.11) gilt b≥0. Der Ursprung (0, 0)∈R2 ist somit ein Eckpunkt des zulässigen BereichsZ des linearen Optimierungsproblems und (0,0,120,70,150)∈R5 eine erste zulässige Basislösung. Durch Austauschschritte im Simplex-Algorithmus (vgl. Seiten 774–776 im Lehrbuch) kann diese erste Basislösung sukzessiv verbessert werden. Die benötigten Austauschschritte bei der Durchführung des Simplex-Algorithmus bis zur Erreichung einer optimalen Lösung sind in den Simplex- Tableaus in Tabelle 25.1 dargestellt. Im ersten Austauschschritt wurde die Nichtbasisvariable x2 gegen die Basisvariable x5 (vgl. zweites Simplex- Tableau inTabelle 25.1) ausgetauscht,wodurch dieBasislösung (0, 50, 70, 20, 0) ∈ R5 resultiert.Anschließend wurde im zweiten Austauschschritt die Nichtbasisvariable x1 gegen die Basisvariable x4 (vgl. drittes Simplex- Tableau in Tabelle 25.1) ausgewechselt, was zur Basislösung (30, 40, 20, 0, 0) ∈ R5 führt. Da nach Durchführung des zweiten Austauschschritts alle Zielfunktionskoeffizienten cj kleiner oder gleich Null sind, ist diese dritte Basislösung bereits optimal (vgl. drittes Simplex-Tableau in Tabelle 25.1). Das heißt, x∗ = (30, 40) ist eine optimale Lösung des linearen Optimierungsproblems und der maximale Zielfunktionswert unter den Nebenbedingungen (25.11) und den Nichtnegativitätsbedingungen (25.12) beträgt z (30, 40) = 10 · 30+ 15 · 40 = 900. Das optimale Produktionsprogramm besteht folglich aus 30 Mengeneinheiten des Produkts P1 und 40 Mengeneinheiten des Produkts P2. Zu c): Aufgrund der Nichtnegativitätsbedingungen x1, x2 ≥ 0 liegt der zulässige Bereich Z im 1. Quadranten des R2 und wird durch die x1-Achse und die x2-Achse begrenzt. Die anderen Begrenzungen vonZ sind durch die Geraden 2x1 + x2 = 120, x1 + x2 = 70 und x1 + 3x2 = 150 festgelegt. Diese ergeben sich aus den drei Nebenbedingungen (25.11), wenn für die drei Schlupfvariablen x3, x4 und x5 jeweis der Wert Null eingesetzt wird (vgl. Abbildung 25.3). Für einen festen Wert z0 ∈ R+ liegen alle (x1, x2) ∈ R2 mit z0 = 10x1 + 15x2 auf der Iso-Gewinn-Geraden zum Gewinn z0. Die Iso-Gewinn-Geraden zu verschiedenen Gewinnen z0 ∈ R+ sind parallel. In Abbildung 25.3 ist die Iso-Gewinn-Gerade zum Gewinn z0 = 300 eingezeichnet. Zur Ermittlung des maximalen Gewinns wird diese Iso-Gewinn-Gerade parallel nach rechts oben bis zum Rand des zulässigen BereichsZ verschoben. Auf diese Weise erhält man den Eckpunkt x∗ = (x∗1 , x∗2 ), für den die Zielfunktion z(x1, x2) = 10x1 + 15x2 unter allen zulässigen Lösungen (x1, x2) ∈ Z ihr Maximum annimmt. Zur analytischen Berechnung dieser Lösung werden die beiden Gleichungen x1 + x2 = 70 und x1 + 3x2 = 150 jeweils nach der Variablen x2 aufgelöst. Durch Gleichsetzen der dabei resultierenden Ausdrücke erhält man dann 70− x1 = 50− 13 x1 bzw. x1 = 30. Damit folgt weiter x2 = 70 − 30 = 40. Das heißt, die optimale Lösung ist x∗ = (30, 40) und führt zu dem Gewinnmaximum z(30, 40) = 10 · 30+ 15 · 40 = 900. 398 Kapitel 25Lineare Optimierung NBV NBV BV BV BV −z x1 x2 x3 x4 x5 (0) 1 10 15 0 0 0 0 (1) 0 2 1 1 0 0 120 (2) 0 1 1 0 1 0 70 (3) 0 1 3 0 0 1 150 NBV BV BV BV NBV −z x1 x2 x3 x4 x5 (0′) 1 5 0 0 0 −5 −750 (0)− 15 · (3′) (1′) 0 53 0 1 0 − 13 70 (1)− (3′) (2′) 0 23 0 0 1 − 13 20 (2)− (3′) (3′) 0 13 1 0 0 1 3 50 1 3 · (3) BV BV BV NBV NBV −z x1 x2 x3 x4 x5 (0′′) 1 0 0 0 − 152 − 52 −900 (0′)− 5 · (2′′) (1′′) 0 0 0 1 − 52 12 20 (1′)− 53 · (2′′) (2′′) 0 1 0 0 32 − 12 30 32 · (2′) (3′′) 0 0 1 0 − 12 12 40 (3′)− 13 · (2′′) Tabelle 25.1: Simplex-Tableaus zu Aufgabe 25.4 x 1 x 2 0 30 60 90 120 0 30 60 90 120 150 2x 1 + x 2 = 120 x 1 + 3 x 2 = 150 x 1 + x 2 = 70 x ∗ z0 = 300 z0 = 900 Z Abb. 25.3: Graphische Lösung des linearen Optimierungsproblems (25.10)–(25.12) 399 Kapitel 25 Teil VIII: Optimierung im Rn ** Aufgabe 25.5 (Anwendung des Simplex-Algorithmus) Betrachtet wird ein Betrieb, der mit Hilfe von drei Produktionsfaktoren F1, F2 und F3 vier verschiedene Produkte P1, P2, P3 und P4 herstellt. Die folgende Tabelle gibt die Produktionskoeffizienten, den Bestand an Produktionsfaktoren sowie den Gewinn je produzierter Einheit an: Produktions- Produkte Bestand faktoren P1 P2 P3 P4 F1 1 3 0 1 4 F2 2 1 0 0 3 F3 0 1 4 1 3 Gewinn 2 4 1 1 Die Variablen x1, x2, x3, x4 ≥ 0 bezeichnen die Produktionsmengen der vier Produkte P1, P2, P3 und P4. Der Betrieb verfolgt als Ziel die Gewinnmaximierung. a) Formulieren Sie die Problemstellung als lineares Optimierungsproblem in Standardform. b) Formulieren Sie die Problemstellung als lineares Optimierungsproblem in Standardform mit Schlupfvariablen. c) Lösen Sie das lineare Optimierungsproblem mit Hilfe des Simplex-Algorithmus. d) Erläutern Sie, ob die in Aufgabenteil c) gefundene optimale Lösung eindeutig ist. e) Interpretieren Sie die Werte der drei Schlupfvariablen x5, x6 und x7 im Endtableau des Simplex-Algorithmus ökonomisch. Lehrbuch: Abschnitte 25.3 und 25.4 Lösung: Zu a): Das lineare Optimierungsproblem lautet in Standardform (vgl. Definition 25.5 im Lehrbuch): Maximiere z(x1, x2, x3, x4) := 2x1 + 4x2 + x3 + x4 (25.13) unter den Nebenbedingungen x1+3x2 +x4 ≤ 4 2x1+ x2 ≤ 3 (25.14) x2 + 4x3+x4 ≤ 3 und den Nichtnegativitätsbedingungen x1, x2, x3, x4 ≥ 0. (25.15) Zu b): Das lineare Optimierungsproblem lautet in Standardform mit Schlupfvariablen (vgl. Definition 25.11 im Lehrbuch): Maximiere z(x1, x2, x3, x4) = 2x1 + 4x2 + x3 + x4 (25.16) unter den Nebenbedingungen x1+3x2 +x4 + x5 = 4 2x1+ x2 +x6 = 3 (25.17) x2 + 4x3+x4 + x7= 3 und den Nichtnegativitätsbedingungen x1, x2, x3, x4, x5, x6, x7 ≥ 0. (25.18) Das heißt, zu den vier Entscheidungsvariablen x1, x2, x3, x4 sind die drei Schlupfvariablen x5, x6, x7 hinzugekommen. Zu c): Für die rechte Seiteb des linearenGleichungssystems (25.17) giltb≥0. DerUrsprung (0, 0, 0, 0)∈R4 ist somit einEckpunkt des zulässigenBereichsZ des linearenOptimierungsproblems und (0, 0, 0, 0, 4, 3, 3) ∈ R7 400 Kapitel 25Lineare Optimierung eine erste zulässige Basislösung. Durch Austauschschritte im Simplex-Algorithmus (vgl. Seiten 774–776 im Lehrbuch) kann diese erste Basislösung sukzessiv verbessert werden. Die benötigten Austauschschritte bei der Durchführung des Simplex-Algorithmus bis zur Erreichung einer optimalen Lösung sind in den Simplex- Tableaus inTabelle 25.2 dargestellt. ImerstenAustauschschrittwurdedieNichtbasisvariablex2 gegendieBasisvariable x5 (vgl. zweites Simplex-Tableau in Tabelle 25.2), im zweiten Austauschschritt die Nichtbasisvariable x3 gegen die Basisvariable x7 (vgl. drittes Simplex-Tableau in Tabelle 25.2) und im dritten Austauschschritt die Nichtbasisvariable x1 gegen die Basisvariable x6 (vgl. viertes Simplex-Tableau in Tabelle 25.2) ausgetauscht. Da nachDurchführung des drittenAustauschschrittes alle Zielfunktionskoeffizienten cj kleiner oder gleichNull sind, ist die zugehörige vierte Basislösung ( 1, 1, 12 , 0, 0, 0, 0 ) bereits optimal (vgl. viertes Simplex-Tableau). Das heißt, x∗ = ( 1, 1, 1 2 , 0 ) ist eine optimale Lösung des linearen Optimierungsproblems und der maximale Zielfunktionswert unter den Nebenbedingungen (25.14) und den Nichtnegativitätsbedingungen (25.15) beträgt z ( 1, 1, 1 2 , 0 ) = 2 · 1+ 4 · 1+ 1 2 + 0 = 13 2 . NBV NBV NBV NBV BV BV BV −z x1 x2 x3 x4 x5 x6 x7 (0) 1 2 4 1 1 0 0 0 0 (1) 0 1 3 0 1 1 0 0 4 (2) 0 2 1 0 0 0 1 0 3 (3) 0 0 1 4 1 0 0 1 3 NBV BV NBV NBV NBV BV BV −z x1 x2 x3 x4 x5 x6 x7 (0′) 1 23 0 1 − 13 − 43 0 0 − 163 (0)− 4 · (1′) (1′) 0 13 1 0 1 3 1 3 0 0 4 3 1 3 · (1) (2′) 0 53 0 0 − 13 − 13 1 0 53 (2)− (1′) (3′) 0 − 13 0 4 23 − 13 0 1 53 (3)− (1′) NBV BV BV NBV NBV BV NBV −z x1 x2 x3 x4 x5 x6 x7 (0′′) 1 34 0 0 − 12 − 54 0 − 14 − 234 (0′)− (3′′) (1′) 0 13 1 0 1 3 1 3 0 0 4 3 (2′) 0 53 0 0 − 13 − 13 1 0 53 (3′′) 0 − 112 0 1 16 − 112 0 14 512 14 · (3′) BV BV BV NBV NBV NBV NBV −z x1 x2 x3 x4 x5 x6 x7 (0′′′) 1 0 0 0 − 720 − 1110 − 920 − 14 − 132 (0′′)− 34 · (2′′) (1′′) 0 0 1 0 25 2 5 − 15 0 1 (1′)− 13 · (2′′) (2′′) 0 1 0 0 − 15 − 15 35 0 1 35 · (2′) (3′′′) 0 0 0 1 320 − 110 120 14 12 (3′′)+ 112 · (2′′) Tabelle 25.2: Simplex-Tableaus zu Aufgabe 25.5 Zu d): Die in Aufgabenteil c) bestimmte optimale Lösung x∗ = (1, 1, 12 , 0) ist eindeutig, da die zugehörigen Zielfunktionskoeffizienten cj aller Nichtbasisvariablen echt kleiner als Null sind (vgl. Seite 776 im Lehrbuch). Zu e): Die drei Schlupfvariablen x5, x6 und x7 haben im Endtableau des Simplex-Algorithmus als Nichtbasisvariablen denWert 0. Dies bedeutet, dass die drei ProduktionsfaktorenF1, F2 undF3 imRahmen des optimalen Produktionsplanes x∗ = (1, 1, 12 , 0) voll ausgeschöpft werden und somit Engpasskapazitäten bilden (vgl. Seite 771 im Lehrbuch). 401 Kapitel 25 Teil VIII: Optimierung im Rn ** Aufgabe 25.6 (Anwendung des Simplex-Algorithmus) Ein industrieller Betrieb fertigt mit Hilfe von drei Maschinen M1,M2 und M3 vier verschiedene Produkte P1, P2, P3 und P4. Die folgende Tabelle gibt die benötigten Fertigungszeiten (in Minuten) pro Mengeneinheit, die zur Verfügung stehenden Betriebszeiten sowie den Deckungsbeitrag je produzierter Mengeneinheit an: Produkte Betriebszeiten Maschinen P1 P2 P3 P4 M1 4 8 0 2 40 M2 2 2 10 2 60 M3 0 3 3 3 30 Deckungsbeitrag 4 2 6 2 Die Variablen x1, x2, x3, x4 ≥ 0 bezeichnen die Produktionsmengen der vier Produkte P1, P2, P3 und P4. Der Betrieb verfolgt als Ziel die Maximierung des Deckungsbeitrags. a) Formulieren Sie die Problemstellung als lineares Optimierungsproblem in Standardform mit Schlupfvariablen. b) Lösen Sie das lineare Optimierungsproblem mit Hilfe des Simplex-Algorithmus. c) Erläutern Sie, ob die in Aufgabenteil b) gefundene optimale Lösung eindeutig ist. d) Interpretieren Sie die Werte der Zielfunktionskoeffizienten im Endtableau des Simplex-Algorithmus ökonomisch. Lehrbuch: Abschnitte 25.3 und 25.4 Lösung: Zu a): Das lineare Optimierungsproblem lautet in Standardform mit Schlupfvariablen (vgl. Definition 25.11 im Lehrbuch): Maximiere z(x1, x2, x3, x4) := 4x1 + 2x2 + 6x3 + 2x4 (25.19) unter den Nebenbedingungen 4x1+8x2 +2x4 + x5 = 40 2x1+2x2 + 10x3+2x4 +x6 = 60 (25.20) 3x2 + 3x3+3x4 + x7 = 30 und den Nichtnegativitätsbedingungen x1, x2, x3, x4, x5, x6, x7 ≥ 0. (25.21) Das heißt, zu den vier Entscheidungsvariablen x1, x2, x3, x4 sind die drei Schlupfvariablen x5, x6, x7 hinzugekommen. Zu b): Für die rechte Seite b des linearen Gleichungssystems (25.20) gilt b ≥ 0. Der Ursprung (0, 0, 0, 0) ∈ R4 ist somit ein Eckpunkt des zulässigen Bereichs Z des linearen Optimierungsproblems und (0, 0, 0, 0, 40, 60, 30) ∈ R7 eine erste zulässige Basislösung. Durch Austauschschritte im Simplex- Algorithmus (vgl. Seiten 774–776 im Lehrbuch) kann diese erste Basislösung sukzessiv verbessert werden. Die benötigten Austauschschritte bei der Durchführung des Simplex-Algorithmus bis zur Erreichung einer optimalen Lösung sind in den Simplex-Tableaus in Tabelle 25.3 dargestellt. Im ersten Austauschschritt wurde die Nichtbasisvariable x3 gegen die Basisvariable x6 (vgl. zweites Simplex-Tableau in Tabelle 25.3) und im zweiten Austauschschritt die Nichtbasisvariable x1 gegen die Basisvariable x5 (vgl. drittes Simplex-Tableau in Tabelle 25.3) ausgetauscht. Da nach Durchführung des zweiten Austauschschrittes alle Zielfunktionskoeffizienten cj kleiner oder gleich Null sind, ist die zugehörige dritte Basislösung (10, 0, 4, 0, 0, 0, 18) bereits optimal (vgl. drittes Simplex-Tableau in Tabelle 25.3). Das heißt, x∗ = (10, 0, 4, 0) 402 Kapitel 25Lineare Optimierung NBV NBV NBV NBV BV BV BV −z x1 x2 x3 x4 x5 x6 x7 (0) 1 4 2 6 2 0 0 0 0 (1) 0 4 8 0 2 1 0 0 40 (2) 0 2 2 10 2 0 1 0 60 (3) 0 0 3 3 3 0 0 1 30 NBV NBV BV NBV BV NBV BV −z x1 x2 x3 x4 x5 x6 x7 (0′) 1 145 4 5 0 4 5 0 − 35 0 −36 (0)− 6 · (2′) (1) 0 4 8 0 2 1 0 0 40 (2′) 0 15 1 5 1 1 5 0 1 10 0 6 1 10 · (2) (3′) 0 − 35 125 0 125 0 − 310 1 12 (3)− 3 · (2′) BV NBV BV NBV NBV NBV BV −z x1 x2 x3 x4 x5 x6 x7 (0′′) 1 0 − 245 0 − 35 − 710 − 35 0 −64 (0′)− 145 · (1′) (1′) 0 1 2 0 12 1 4 0 0 10 1 4 · (1) (2′′) 0 0 − 15 1 110 − 120 110 0 4 (2′)− 15 · (1′) (3′′) 0 0 185 0 27 10 3 20 − 310 1 18 (3′)+ 35 · (1′) Tabelle 25.3: Simplex-Tableaus zu Aufgabe 25.6 ist eine optimale Lösung des linearen Optimierungsproblems und der maximale Zielfunktionswert unter den Nebenbedingungen (25.20) und den Nichtnegativitätsbedingungen (25.21) beträgt z (10, 0, 4, 0) = 4 · 10+ 2 · 0+ 6 · 4+ 2 · 0 = 64. Zu c): Die in Aufgabenteil b) bestimmte optimale Lösung x∗ = (10, 0, 4, 0) ist eindeutig, da die zugehörigen Zielfunktionskoeffizienten cj aller Nichtbasisvariablen echt kleiner als Null sind (vgl. Seite 776 im Lehrbuch). Zu d): Im Endtableau des Simplex-Algorithmus lautet die Zielfunktion z(x1, x2, x3, x4) = − 245 x2 − 3 5 x4 − 710 x5 − 3 5 x6 + 64 (vgl. letztes Simplex-Tableau in Tabelle 25.3). Daraus ist ersichtlich, dass sich der Deckungsbeitrag um 245 bzw. 3 5 Geldeinheiten verringert, wenn vom Produkt P2 bzw. P4 eine Mengeneinheit produziert wird, also für die zugehörigen Entscheidungsvariablen x2 = 1 bzw. x4 = 1 gilt. Ferner ist zu erkennen, dass sich der Deckungsbeitrag um 710 bzw. 3 5 reduziert, wenn die MaschineM1 bzw.M2 eine Zeiteinheit weniger eingesetzt wird, also für die zugehörigen Schlupfvariablen x5 = 1 bzw. x6 = 1 gilt. Das heißt, bei einer Erweiterung der Kapazitäten der MaschinenM1 undM2 um jeweils eine Zeiteinheit (d.h. x5 = −1 bzw. x6 = −1) würde der Betrieb einen zusätzlichen Deckungsbeitrag von 710 bzw. 3 5 erzielen. ** Aufgabe 25.7 (MC-Aufgaben zur Dualität von linearen Optimierungsproblemen) Kreuzen Sie an, welche der Aussagen a) bis e) wahr und welche falsch sind: a) Zu jedem linearen Optimierungsproblem ist ein duales Problem erklärt. b) Besitzt das primale Optimierungsproblem n Entscheidungsvariablen und m Nebenbedingungen vom Typ≤, dann weist das zugehörige duale Problemm Entscheidungsvariablen und n Nebenbedingungen vom Typ ≤ auf. 403 Kapitel 25 Teil VIII: Optimierung im Rn c) Ein primales Optimierungsproblem besitzt genau dann eine optimale Lösung, wenn für das zugehörige duale Problem keine optimale Lösung existiert. d) Existieren für das primale und das duale Problem zulässige Lösungen, dann existieren für beide Optimierungsprobleme optimale Lösungen. e) Mit Hilfe des Simplex-Algorithmus können ein primales Problem und das zugehörige duale Problem simultan gelöst werden. a) b) c) d) e) Wahr Falsch Lehrbuch: Abschnitt 25.7 Lösung: Zu a): Wahre Aussage (vgl. Seite 786 im Lehrbuch). Zu b): Falsche Aussage. Das duale Problem besitzt dannm Entscheidungsvariablen und n Nebenbedingungen vom Typ ≥ (vgl. Seite 786 im Lehrbuch). Zu c): Falsche Aussage. Ein lineares Optimierungsproblem besitzt genau dann eine optimale Lösung, wenn auch für das zugehörige duale Problem eine optimale Lösung existiert (vgl. Satz 25.27b) im Lehrbuch). Zu d): Wahre Aussage (vgl. Satz 25.27c) im Lehrbuch). Zu e): Wahre Aussage (vgl. Seite 789 im Lehrbuch). ** Aufgabe 25.8 (Duales Problem und Simplex-Algorithmus) Betrachtet wird das folgende lineare Minimierungsproblem: Minimiere zP (x1, x2, x3) := 40x1 + 40x2 + 20x3 (25.22) unter den Nebenbedingungen 4x1+ x2 ≥ 4 8x1+ x2 + 2x3 ≥ 2 (25.23) 5x2 + 2x3 ≥ 6 2x1+ x2 + 2x3 ≥ 2 und den Nichtnegativitätsbedingungen x1, x2, x3 ≥ 0. (25.24) a) Bestimmen Sie das zum linearen Minimierungsproblem (25.22)–(25.24) gehörende duale Problem. b) Lösen Sie das duale Problem mit Hilfe des Simplex-Algorithmus. c) Geben Sie die optimale Lösung des linearenMinimierungsproblems aus Aufgabenteil a) mit Hilfe des Ergebnisses aus Aufgabenteil b) an. Lehrbuch: Abschnitte 25.4 und 25.7 Lösung: Zu a): Das zum linearenMinimierungsproblem (25.22)–(25.24) gehörende duale Problem lautet (vgl. Seite 786 im Lehrbuch): Maximiere zD(y1, y2, y3, y4) := 4y1 + 2y2 + 6y3 + 2y4 (25.25) 404 Kapitel 25Lineare Optimierung unter den Nebenbedingungen 4y1+8y2 +2y4 ≤ 40 y1+ y2 + 5y3+ y4 ≤ 40 (25.26) 2y2 + 2y3+2y4 ≤ 20 und den Nichtnegativitätsbedingungen y1, y2, y3, y4 ≥ 0. (25.27) Zu b): Bei dem dualen Problem (25.25)–(25.27) handelt es sich um ein lineares Optimierungsproblem in Standardform (vgl. Definition 25.5 im Lehrbuch), welches mit Hilfe des Simplex-Algorithmus gelöst werden kann. Nach Einführung von Schlupfvariablen erhält man daraus (vgl. Definition 25.11 im Lehrbuch): Maximiere zD(y1, y2, y3, y4) = 4y1 + 2y2 + 6y3 + 2y4 (25.28) unter den Nebenbedingungen 4y1+8y2 +2y4 + y5 = 40 y1+ y2 + 5y3+ y4 +y6 = 40 (25.29) 2y2 + 2y3+2y4 + y7 = 20 und den Nichtnegativitätsbedingungen y1, y2, y3, y4, y5, y6, y7 ≥ 0. (25.30) Für die rechte Seite b des linearenGleichungssystems (25.29) gilt b≥0. Der Ursprung (0, 0, 0, 0)∈R4 ist somit ein Eckpunkt des zulässigen Bereichs Z des linearen Optimierungsproblems und (0, 0, 0, 0, 40, 40, 20) ∈ R7 eine erste zulässige Basislösung. Durch Austauschschritte im Simplex-Algorithmus (vgl. Seiten 774–776 im Lehrbuch) kann diese erste Basislösung sukzessiv verbessert werden. Die benötigten Austauschschritte bei der Durchführung des Simplex-Algorithmus bis zur Erreichung einer optimalen Lösung sind in den Simplex- Tableaus in Tabelle 25.4 dargestellt. Im ersten Austauschschritt wurde die Nichtbasisvariable y3 gegen die Basisvariable y6 (vgl. zweites Simplex-Tableau in Tabelle 25.4) und im zweiten Austauschschritt die Nichtbasisvariable y1 gegen die Basisvariable y5 (vgl. drittes Simplex-Tableau in Tabelle 25.4) ausgetauscht. Da nach Durchführung des zweiten Austauschschrittes alle Zielfunktionskoeffizienten cj kleiner oder gleich Null sind, ist die zugehörige dritte Basislösung (10, 0, 6, 0, 0, 0, 8) bereits optimal (vgl. drittes Simplex-Tableau in Tabelle 25.4). Das heißt, y∗ = (10, 0, 6, 0) ist eine optimale Lösung des linearen Maximierungsproblems (25.28)–(25.30) und der maximale Zielfunktionswert beträgt zD (10, 0, 6, 0) = 4 · 10+ 2 · 0+ 6 · 6+ 2 · 0 = 76. Zu c): Das lineareMinimierungsproblem (25.22)–(25.24) aus Aufgabenteil a) ist das zu dem linearenMaximierungsproblem (25.25)–(25.27) duale Problem. Seine optimale Lösung kann daher aus dem Simplex-Endtableau in Tabelle 25.4 abgelesen werden. Diese ist gegeben durch die mit −1 multiplizierten Einträge für die drei Schlupfvariablen y5, y6 und y7 in der Zielfunktionszeile des Simplex-Endtableaus. Das heißt, die optimale Lösung des linearen Minimierungsproblems (25.22)–(25.24) lautet x∗ = ( 7 10 , 6 5 , 0 ) und der minimale Zielfunktionswert beträgt zP ( 7 10 , 6 5 , 0 ) = 40 · 7 10 + 40 · 6 5 + 20 · 0 = 76 = zD (10, 0, 6, 0) . 405 Kapitel 25 Teil VIII: Optimierung im Rn NBV NBV NBV NBV BV BV BV −zD y1 y2 y3 y4 y5 y6 y7 (0) 1 4 2 6 2 0 0 0 0 (1) 0 4 8 0 2 1 0 0 40 (2) 0 1 1 5 1 0 1 0 40 (3) 0 0 2 2 2 0 0 1 20 NBV NBV BV NBV BV NBV BV −zD y1 y2 y3 y4 y5 y6 y7 (0′) 1 145 4 5 0 4 5 0 − 65 0 −48 (0)− 6 · (2′) (1) 0 4 8 0 2 1 0 0 40 (2′) 0 15 1 5 1 1 5 0 1 5 0 8 1 5 · (2) (3′) 0 − 25 85 0 85 0 − 25 1 4 (3)− 2 · (2′) BV NBV BV NBV NBV NBV BV −zD y1 y2 y3 y4 y5 y6 y7 (0′′) 1 0 − 245 0 − 35 − 710 − 65 0 −76 (0′)− 145 · (1′) (1′) 0 1 2 0 12 1 4 0 0 10 1 4 · (1) (2′′) 0 0 − 15 1 110 − 120 15 0 6 (2′)− 15 · (1′) (3′′) 0 0 125 0 9 5 1 10 − 25 1 8 (3′)+ 25 · (1′) Tabelle 25.4: Simplex-Tableaus zu Aufgabe 25.8 *** Aufgabe 25.9 (Duales Problem und Simplex-Algorithmus) Betrachtet wird ein Unternehmen, welches aus vier verschiedenen ErzenE1, E2, E3 und E4 eine Metalllegierung L herstellt. Die vier benötigten Erze werden zu den folgenden Preisen gehandelt: Erze E1 E2 E3 E4 Preis (€/ME) 15 12 16 10 Aus den vier Erzen werden zunächst drei Metalle (Zwischenprodukte) M1,M2 und M3 hergestellt, wobei die folgende Tabelle angibt, wieviel Mengeneinheiten sich vomMetall Mi (für i = 1, 2, 3) aus einer Einheit des Erzes Ej (j = 1, 2, 3, 4) gewinnen lassen: Erze E1 E2 E3 E4 M1 0,2 0,5 0,4 0,3 M2 0,2 0,1 0,2 0,1 M3 0,2 0,4 0,3 0,2 Von der Metalllegierung L sollen mindestens 10 Mengeneinheiten hergestellt werden. Hierzu werden mindestens 3,5 Mengeneinheiten von MetallM1, mindestens 2 Mengeneinheiten von MetallM2 und mindestens 4,5 Mengeneinheiten von MetallM3 benötigt. Die Variablen x1, x2, x3, x4 ≥ 0 bezeichnen die für die Herstellung der Metalllegierung L verbrauchtenMengeneinheiten der vier ErzeE1, E2, E3 undE4 und das Unternehmen verfolgt als Ziel die Minimierung der Herstellungskosten. a) Formulieren Sie die Problemstellung als lineares Optimierungsproblem mit den vier Variablen x1, x2, x3 und x4. 406 Kapitel 25Lineare Optimierung b) Bestimmen Sie das zum linearen Optimierungsproblem aus Aufgabenteil a) gehörende duale Problem. c) Lösen Sie das duale Problem aus Aufgabenteil b) mit Hilfe des Simplex-Algorithmus. d) Interpretieren Sie das zum linearen Optimierungsproblem aus Aufgabenteil a) gehörende duale Problem ökonomisch. e) Geben Sie die optimale Lösung des linearen Optimierungsproblems aus Aufgabenteil a) mit Hilfe des Ergebnisses aus Aufgabenteil c) an. Lehrbuch: Abschnitte 25.4 und 25.7 Lösung: Zu a): Als lineares Minimierungsproblem formuliert lautet die Problemstellung: Minimiere zP (x1, x2, x3, x4) := 15x1 + 12x2 + 16x3 + 10x4 (25.31) unter den Nebenbedingungen 0,2x1 + 0,5x2 + 0,4x3 + 0,3x4 ≥ 3,5 0,2x1 + 0,1x2 + 0,2x3 + 0,1x4 ≥ 2 (25.32) 0,2x1 + 0,4x2 + 0,3x3 + 0,2x4 ≥ 4,5 und den Nichtnegativitätsbedingungen x1, x2, x3, x4 ≥ 0. (25.33) Zu b): Das zum linearen Minimierungsproblem duale Problem lautet (vgl. Seite 786 im Lehrbuch): Maximiere zD(y1, y2, y3) := 3,5y1 + 2y2 + 4,5y3 (25.34) unter den Nebenbedingungen 0,2y1+0,2y2 + 0,2y3 ≤ 15 0,5y1+0,1y2 + 0,4y3 ≤ 12 (25.35) 0,4y1+0,2y2 + 0,3y3 ≤ 16 0,3y1+0,1y2 + 0,2y3 ≤ 10 und den Nichtnegativitätsbedingungen y1, y2, y3 ≥ 0. (25.36) Zu c): Bei dem dualen Problem (25.34)–(25.36) handelt es sich um ein lineares Optimierungsproblem in Standardform (vgl. Definition 25.5 im Lehrbuch), welches mit Hilfe des Simplex-Algorithmus gelöst werden kann. Nach Einführung von Schlupfvariablen erhält man daraus (vgl. Definition 25.11 im Lehrbuch): Maximiere zD(y1, y2, y3) = 3,5y1 + 2y2 + 4,5y3 (25.37) unter den Nebenbedingungen 0,2y1+0,2y2 + 0,2y3+y4 = 15 0,5y1+0,1y2 + 0,4y3 + y5 = 12 (25.38) 0,4y1+0,2y2 + 0,3y3 +y6 = 16 0,3y1+0,1y2 + 0,2y3 + y7 = 10 und den Nichtnegativitätsbedingungen y1, y2, y3, y4, y5, y6, y7 ≥ 0. (25.39) Für die rechte Seite b des linearen Gleichungssystems (25.38) gilt b ≥ 0. Der Ursprung (0, 0, 0) ∈ R3 ist somit ein Eckpunkt des zulässigen BereichsZ des linearen Optimierungsproblems und (0, 0, 0, 15, 12, 16, 10) ∈ R7 eine erste zulässige Basislösung. Durch Austauschschritte im Simplex-Algorithmus (vgl. Seiten 774–776 im Lehrbuch) kann diese erste Basislösung sukzessiv verbessert werden. Die benötigten Austauschschritte bei der Durchführung des Simplex-Algorithmus bis zur Erreichung einer optimalen Lösung sind in den Simplex- Tableaus in Tabelle 25.5 dargestellt. Im ersten Austauschschritt wurde die Nichtbasisvariable y3 gegen die Basisvariable y5 (vgl. zweites Simplex-Tableau in Tabelle 25.5) und im zweiten Austauschschritt die Nichtbasisvariable y2 gegen die Basisvariable y6 (vgl. drittes Simplex-Tableau in Tabelle 25.5) ausgetauscht. Da nach 407 Kapitel 25 Teil VIII: Optimierung im Rn Durchführung des zweiten Austauschschrittes alle Zielfunktionskoeffizienten cj kleiner oder gleich Null sind, ist die zugehörige dritte Basislösung ( 0, 56, 16, 610 , 0, 0, 6 5 ) bereits optimal (vgl. drittes Simplex-Tableau in Tabelle 25.5). Das heißt, y∗ = (0, 56, 16) ist eine optimale Lösung des linearen Maximierungsproblems (25.37)–(25.39) und der maximale Zielfunktionswert beträgt zD (0, 56, 16) = 3,5 · 0+ 2 · 56+ 4,5 · 16 = 184. NBV NBV NBV BV BV BV BV −zD y1 y2 y3 y4 y5 y6 y7 (0) 1 3,5 2 4,5 0 0 0 0 0 (1) 0 0,2 0,2 0,2 1 0 0 0 15 (2) 0 0,5 0,1 0,4 0 1 0 0 12 (3) 0 0,4 0,2 0,3 0 0 1 0 16 (4) 0 0,3 0,1 0,2 0 0 0 1 10 NBV NBV BV BV NBV BV BV −zD y1 y2 y3 y4 y5 y6 y7 (0′) 1 −2,125 0,875 0 0 −11,25 0 0 −135 (0)− 4,5 · (2′) (1′) 0 −0,05 0,15 0 1 −0,5 0 0 9 (1)− 0,2 · (2′) (2′) 0 1,25 0,25 1 0 2,5 0 0 30 52 · (2) (3′) 0 0,025 0,125 0 0 −0,75 1 0 7 (3)− 0,3 · (2′) (4′) 0 0,05 0,05 0 0 −0,5 0 1 4 (4)− 0,2 · (2′) NBV BV BV BV NBV NBV BV −zD y1 y2 y3 y4 y5 y6 y7 (0′′) 1 −2,3 0 0 0 −6 −7 0 −184 (0′)− 0,875 · (3′′) (1′′) 0 −0,08 0 0 1 0,4 −1,2 0 0,6 (1′)− 0,15 · (3′′) (2′′) 0 1,2 0 1 0 4 −2 0 16 (2′)− 0,25 · (3′′) (3′′) 0 0,2 1 0 0 −6 8 0 56 8 · (3′) (4′′) 0 0,04 0 0 0 −0,2 −0,4 1 1,2 (4′)− 0,05 · (3′′) Tabelle 25.5: Simplex-Tableaus zu Aufgabe 25.9 Zu d): Das duale Problem (25.34)–(25.36) kann als das lineare Optimierungsproblem eines Mitbewerbers interpretiert werden, welcher dem betrachteten Unternehmen 3,5 Mengeneinheiten von Metall M1 zum Preis y1 ≥ 0, 2 Mengeneinheiten von Metall M2 zum Preis y2 ≥ 0 und 4,5 Mengeneinheiten von Metall M3 zum Preis y3 ≥ 0 anbietet. Der Gesamtumsatz dieses Mitbewerbers beläuft sich somit auf 3,5y1 + 2y2 + 4,5y3 und erwird versuchen, diesen zumaximieren. Das betrachteteUnternehmenwird auf diesesAngebot jedoch nur eingehen, wenn die Nebenbedingungen (25.35) erfüllt sind. Das heißt, wenn der vom Mitbewerber verlangte Preis für die drei Metalle nicht höher ist als die Kosten, die dem betrachteten Unternehmen entstehen würden, wenn es die drei Metalle aus den vier Erzen E1, E2, E3 und E4 selbst produziert. Das heißt, der Mitbewerber hat das duale Problem (25.34)–(25.36) zu lösen (vgl. Seite 791 im Lehrbuch). Zu e): Das lineare Minimierungsproblem (25.31)–(25.33) aus Aufgabenteil a) ist das zu dem linearen Maximierungsproblem (25.34)–(25.36) duale Problem. Aus dem Simplex-Endtableau in Tabelle 25.5 kann daher die optimale Lösung abgelesen werden. Diese ist gegeben durch die mit −1 multiplizierten Einträge für die vier Schlupfvariablen y4, y5, y6 und y7 in der Zielfunktionszeile des Simplex-Endtableaus. Das heißt, die optimale Lösung des linearen Minimierungsproblems (25.31)–(25.33) lautet x∗ = (0, 6, 7, 0) und der minimale Zielfunktionswert beträgt zP (0, 6, 7, 0) = 15 · 0+ 12 · 6+ 16 · 7+ 10 · 0 = 184 = zD (0, 56, 16) . 408 Kapitel 25Lineare Optimierung ** Aufgabe 25.10 (Dualer Simplex-Algorithmus) Lösen Sie das lineare Minimierungsproblem: Minimiere z(x1, x2, x3, x4) = 15x1 + 12x2 + 16x3 + 10x4 (25.40) unter den Nebenbedingungen 0,2x1 + 0,5x2+0,4x3 + 0,3x4 ≥ 3,5 0,2x1 + 0,1x2+0,2x3 + 0,1x4 ≥ 2 (25.41) 0,2x1 + 0,4x2+0,3x3 + 0,2x4 ≥ 4,5 und den Nichtnegativitätsbedingungen x1, x2, x3, x4 ≥ 0 (25.42) mit Hilfe des dualen Simplex-Algorithmus. Lehrbuch: Abschnitt 25.8 Lösung: Zu a): Für die Anwendung des dualen Simplex-Algorithmus ist es erforderlich, dass das lineare Minimierungsproblem (25.40)–(25.42) zuvor in ein lineares Maximierungsproblem mit ausschließlich nicht positiven Zielfunktionskoeffizienten und Nebenbedingungen vom Typ≤ überführt wird. Dies wird durch Multiplikation der Zielfunktion und der Nebenbedingungen mit −1 erreicht (vgl. Seite 792 im Lehrbuch): Maximiere z̃(x1, x2, x3, x4) = −15x1 − 12x2 − 16x3 − 10x4 (25.43) unter den Nebenbedingungen −0,2x1 − 0,5x2−0,4x3 − 0,3x4 ≤ −3,5 −0,2x1 − 0,1x2−0,2x3 − 0,1x4 ≤ −2 (25.44) −0,2x1 − 0,4x2−0,3x3 − 0,2x4 ≤ −4,5 und den Nichtnegativitätsbedingungen x1, x2, x3, x4 ≥ 0. (25.45) Nach Einführung von Schlupfvariablen erhält man daraus (vgl. Definition 25.11 im Lehrbuch): Maximiere z̃(x1, x2, x3, x4) = −15x1 − 12x2 − 16x3 − 10x4 (25.46) unter den Nebenbedingungen −0,2x1 − 0,5x2−0,4x3 − 0,3x4+x5 = −3,5 −0,2x1 − 0,1x2−0,2x3 − 0,1x4 + x6 = −2 (25.47) −0,2x1 − 0,4x2−0,3x3 − 0,2x4 +x7 = −4,5 und den Nichtnegativitätsbedingungen x1, x2, x3, x4, x5, x6, x7 ≥ 0. (25.48) Für den Vektor c der Koeffizienten der Zielfunktion (25.46) gilt c < 0. Die Optimalitätsbedingung ist somit erfüllt, aber der Ursprung (0, 0, 0, 0) ∈ R4 ist wegen der Negativität der rechten Seite des linearen Gleichungssystems (25.47) kein Element des zulässigen Bereichs Z des linearen Optimierungsproblems und( 0, 0, 0, 0,− 72 ,−2,− 92 ) ∈ R7 folglich keine zulässige erste Basislösung. Durch Austauschschritte im dualen Simplex-Algorithmus (vgl. Seiten 792–793 imLehrbuch) kann diese erste (unzulässige) Basislösung unter Beibehaltung der Optimalitätsbedingung sukzessiv in eine zulässige Basislösung überführt werden. Die benötigten Austauschschritte bei der Durchführung des dualen Simplex-Algorithmus bis zur Erreichung einer zulässigen (und optimalen) Lösung sind in den Simplex-Tableaus in Tabelle 25.6 dargestellt. Im ersten Austauschschritt wurde die Nichtbasisvariable x2 gegen die Basisvariable x7 (vgl. zweites Simplex- Tableau in Tabelle 25.6) und im zweiten Austauschschritt die Nichtbasisvariable x3 gegen die Basisvariable x6 (vgl. drittes Simplex-Tableau in Tabelle 25.6) ausgetauscht. Da nach Durchführung des zweiten Austauschschrittes alle Zielfunktionskoeffizienten cj weiterhin kleiner oder gleich Null und die Werte auf der rechten 409 Kapitel 25 Teil VIII: Optimierung im Rn Seite nun positiv sind, ist die zugehörige dritte Basislösung ( 0, 6, 7, 0, 2310 , 0, 0 ) bereits optimal (vgl. drittes Simplex-Tableau in Tabelle 25.6). Das heißt, x∗ = (0, 6, 7, 0) (25.49) ist eine optimale Lösung des linearen Maximierungsproblems (25.43)–(25.45) und der maximale Zielfunktionswert beträgt z̃(0, 6, 7, 0) = −15 · 0− 12 · 6− 16 · 7− 10 · 0 = −184. Das heißt, das lineare Minimierungsproblem (25.40)–(25.42) besitzt ebenfalls die optimale Lösung (25.49), und der zugehörige Zielfunktionswert ist gegeben durch z(0, 6, 7, 0) = −z̃(0, 6, 7, 0) = 184. NBV NBV NBV NBV BV BV BV −z̃ x1 x2 x3 x4 x5 x6 x7 (0) 1 −15 −12 −16 −10 0 0 0 0 (1) 0 −0,2 −0,5 −0,4 −0,3 1 0 0 −3,5 (2) 0 −0,2 −0,1 −0,2 −0,1 0 1 0 −2 (3) 0 −0,2 −0,4 −0,3 −0,2 0 0 1 −4,5 NBV BV NBV NBV BV BV NBV −z̃ x1 x2 x3 x4 x5 x6 x7 (0′) 1 −9 0 −7 −4 0 0 −30 135 (0)+ 12 · (3′) (1′) 0 0,05 0 −0,025 −0,05 1 0 −1,25 2,125 (1)+ 0,5 · (3′) (2′) 0 −0,15 0 −0,125 −0,05 0 1 −0,25 −0,875 (2)+ 0,1 · (3′) (3′) 0 0,5 1 0,75 0,5 0 0 −2,5 11,25 −2,5 · (3) NBV BV BV NBV BV NBV NBV −z̃ x1 x2 x3 x4 x5 x6 x7 (0′′) 1 −0,6 0 0 −1,2 0 −56 −16 184 (0′)+ 7 · (2′′) (1′′) 0 0,08 0 0 −0,04 1 −0,2 −1,2 2,3 (1′)+ 0,025 · (2′′) (2′′) 0 1,2 0 1 0,4 0 −8 2 7 −8 · (2′) (3′′) 0 −0,4 1 0 0,2 0 6 −4 6 (3′)− 0,75 · (2′′) Tabelle 25.6: Simplex-Tableaus zu Aufgabe 25.10 410

Chapter Preview

References

Zusammenfassung

450 Aufgaben mit Lösungen zur Prüfungsvorbereitung

Vorteile

- 450 Aufgaben mit ausführlichen Lösungen und unterschiedlichen Schwierigkeitsgraden

- Abgestimmt auf das Lehrbuch "Mathematik für Wirtschaftswissenschaftler" (Merz/Wüthrich)

Zum Werk

Die Mathematikausbildung spielt eine zentrale Rolle im wirtschaftswissenschaftlichen Studium, da sie die methodischen Grundlagen für zahlreiche Vorlesungen liefert. So zentral die Rolle der Mathematik in der Ökonomie ist, so schwer tun sich allerdings die Studierenden mit mathematischen Methoden und Konzepten.

Dieses Übungsbuch hilft Studierenden, ihr erworbenes Wissen anzuwenden und zu testen. Über 400 Übungsaufgaben mit ausführlichen Lösungen unterstützen bei der optimalen Prüfungsvorbereitung. Zur besseren Orientierung wird jeder Aufgabe ein Schwierigkeitsgrad zugeordnet und ein Verweis auf den entsprechenden Abschnitt im zugrunde liegenden Lehrbuch "Mathematik für Wirtschaftswissenschaftler" von Merz/Wüthrich gegeben.

Autor

Prof. Dr. Michael Merz, Hamburg.

Zielgruppe

Studierende im Bachelor der Wirtschaftswissenschaften an Universitäten und Hochschulen.