Optimierungstheorie Übungsblatt 8

Universität Karlsruhe (TH)
Forschungsuniversität • gegründet 1825
| Institut für Angewandte und
| Numerische Mathematik
Prof. Dr. Christian Wieners, Dipl.-Math. techn. Martin Sauter
Optimierungstheorie
Übungsblatt 8
Sommersemester 2007
Aufgabe 33 (schriftlich)
(5 Punkte)
Das Skinspiel aus der Vorlesung wird durch folgende Tabelle bzw. Auszahlungsmatrix A
beschrieben:
P2 \ P1 ♦As ♠As ♠2
♦As
1
−1 −2
,
♠As −1
1
1
♦2
2
−1 −2
cT x mit
Stellen Sie die Auszahlungsmatrix auf und zeigen Sie, dass das Spiel ein Sattelpunktspiel ist. Bestimmen Sie für beide Revolverhelden eine reine, und gleichzeitig optimale,
Strategie.
20x1 + 60x2
x1
5x1
2x1
+ x2
+ 10x2
+ 10x2
unter x ≥ 0,
≤ 120 ,
≤ 700 ,
≤ 520 .
Lösen Sie das Optimierungsproblem mit dem revidierten Simplex-Verfahren. Benutzen
Sie dabei die Sherman-Morrison-Formel (Übungsblatt 6 - Aufgabe 27).
Hinweis: Den Algorithmus des revidierten Simplex-Verfahrens finden Sie auf den Folien
zu Kapitel 4 der Vorlesung.
x ∈ M 0 := {x ∈ Rn : Ax ≥ b, x ≥ 0}.
Vorankündigung:
Zeigen Sie:
0
0
0
(a) (P ) ist selbstdual, d.h. das duale Problem von (P ) ist äquivalent zu (P ).
(b) Falls M 0 6= ∅, so besitzt (P 0 ) eine optimale Lösung x∗ ∈ Rn und cT x∗ = 0.
(c) Geben Sie ein primal-duales Paar linearer Programme an, von denen keines eine
zulässige Lösung besitzt.
Aufgabe 35 (mündlich)
Kurz vor seinem Tod treffen sich Doc Holliday und Ike Clanton zu ihrem finalen Pistolenduell. Beide sind etwas in die Jahre gekommen und müssen abwägen, aus welcher
Entfernung (weit, mittel, kurz) sie das Feuer auf den Anderen eröffnen. Die Wahrscheinlichkeit aus den verschiedenen Entfernungen den Anderen tödlich zu treffen sind durch
folgende Tabelle gegeben:
Schütze
Doc Holliday
Ike Clanton
K
Schuss aus weiter Entfernung
Wenn der Gegner noch nicht geschossen hat, Schuss aus mittlerer Entfernung,
sonst aus kurzer Entfernung
Schuss aus kurzer Entfernung
Maximiere
Aufgabe 34 (schriftlich)
(4 Punkte)
Es sei A ∈ Rn×n schiefsymmetrisch, d.h. A = −AT . Weiter sei c ∈ Rn und b = −c.
Betrachten Sie das folgende Optimierungsproblem:
Minimiere
W
M
Aufgabe 36 (mündlich)
Betrachten Sie nochmals das Beispiel aus der Vorlesung:

1 −1 −2
1 .
A = −1 1
2 −1 −2

Verwenden Sie das Simplex-Verfahren, um zu zeigen Sie, dass das Spiel ein faires MatrixSpiel ist. Bestimmen Sie außerdem eine optimale Strategie für Spieler P1 .
(P 0 )
Beide haben sich die folgenden drei Strategien zurechtgelegt, um das Duell zu überleben:
weit
0.3
0.5
mittel
0.8
0.6
kurz
1.0
1.0
(z.B.: Die Wahrscheinlichkeit, dass
Doc Holliday seinen Gegner aus weiter Entfernung tödlich trifft, ist 0.3)
In der Woche vom 11.-15. Juni findet eine Vorlesungsbefragung via Internet statt. Näheres
dazu erfahren Sie auf dem nächsten Übungsblatt oder im Internet (s.u.).
Abgabe:
Die schriftlichen Übungsaufgaben sind bis spätestens Freitag, den 08. Juni 2007,
13.00 Uhr in den Einwurfschlitz Optimierungstheorie, neben der Treppe im 1. OG des
Mathematik-Gebäudes, einzuwerfen.
Die Besprechung der Aufgaben findet am Freitag, den 08. Juni 2007, 14.00-15.30 Uhr im
Engesser-Hörsaal (HS 93) statt. Dort wird auch das neue Übungsblatt ausgeteilt. Dieses
ist auch online verfügbar unter:
http://www.mathematik.uni-karlsruhe.de/ianm3/lehre/optim12007s/
Sprechstunden:
Prof. Dr. Christian Wieners: Mi. 10.00-12.00 Uhr
Dipl.-Math. techn. Martin Sauter: Do. 10.00-11.30 Uhr oder nach Vereinbarung
Vorrechnen:
Wenn Sie vorrechnen möchten, melden Sie sich bitte beim Übungsleiter (Email:
[email protected]).