Blatt 12 - TU Dortmund

Prof. Dr. Christoph Buchheim
M.Sc. Anna Ilyina
Sommersemester 2016
12. Übung
zur Vorlesung
Optimierung
Abgabe: Dienstag, 12. Juli bis 12 Uhr in den jeweiligen Briefkasten.
Besprechung: Montag, 18. Juli bzw. Dienstag, 19. Juli.
Bitte schreiben Sie die Nummer Ihrer Übungsgruppe auf Ihre Abgaben.
Aufgabe 1 (4 Punkte)
Betrachten Sie das lineare Optimierungsproblem
 
1

0
−1 1 −1 1
 
 , A := −2 −6 6 3
4
c := 
 
−2
−2 4
8 1
−7
min{c> x | Ax = b, x ≥ 0} mit
 
x1



x2 
2
4
 



0 , x := 
x3  , b := −18 .


2
x4
4
x5
Es sei B ⊆ {1, 2, 3, 4, 5} die Basis mit zugehöriger Basismatrix

1 1 −1
AB := −6 3 −2
4 1 −2
2
3
 10
3


und der Inversen A−1
B =
3
− 16
− 13
− 21

− 16

− 43  .
− 32
(a) Bestimmen Sie die zu B gehörigen Basis- und Nichtbasisvariablen und berechnen Sie den
zugehörigen Basisvektor x ∈ R5 . Ist dieser zulässig?
(b) Überprüfen Sie, ob das Simplex-Verfahren bei der Basis B aus (a) terminiert!
Aufgabe 2 (4 Punkte)
Lösen Sie mit dem Simplex-Algorithmus das folgende lineare Programm:
min
2x1 + x2 − 5x3
s.t. x1 + 2x2 − 4x3 + x4 + x5
=3
−2x1 + 3x2 − x3 − 5x4 + x6
=4
7x1 − 10x3 + 13x4 + x7
=0
≥0
x1 , ..., x7
Benutzen Sie dabei die Startbasis B = {5, 6, 7}.
1
Aufgabe 3 (4 Punkte)
Betrachten Sie das folgende LP mit Ganzzahligkeitsbedingungen.
min c> x
(IP )
s.t. Ax ≤ b
xi ∈ {0, 1},
i = 1, ..., n.
Solche Probleme sind im Allgemeinen sehr schwierig zu lösen. Oft geht man so vor, dass man
statt (IP) dessen so genannte LP-Relaxierung (R) betrachtet, wobei die Bedingung xi ∈ {0, 1}
durch 0 ≤ xi ≤ 1 ersetzt wird:
min c> x
(R)
s.t. Ax ≤ b
xi ∈ [0, 1] ,
i = 1, ..., n.
Untersuchen Sie den Zusammenhang zwischen (IP) und (R).
(a) Was sagt der Optimalwert von (R) über den Optimalwert von (IP) aus?
(b) Im Allgemeinen erfüllt die Optimallösung von (R) nicht die Bedingung xi ∈ {0, 1} für alle
i. Wenn dies zufällig doch der Fall ist, was kann man dann für (IP) folgern?
(c) Was folgt aus der Zulässigkeit bzw. Unzulässigkeit von (R) für (IP)?
Begründen Sie Ihre Aussagen.
Aufgabe 4 (4 Punkte)
Betrachten Sie eine Teilmenge U der Potenzmenge P({1, ..., n}) und das folgende lineare Programm:
min c> x
X
s.t.
xi ≤ 1 ∀S ∈ U
i∈S
x ≥ 0.
(a) Bringen Sie das Problem in Standardform.
(b) Zeigen Sie: Wenn S1 ∩ S2 = ∅ gilt für alle S1 , S2 ∈ U , so ist jede Basislösung ganzzahlig.
(c) Gilt die Aussage in (b) auch ohne die Disjunktheit?
Homepage: http://www.mathematik.tu-dortmund.de/lsv/teaching/opt16/index.html
2

Download Report