Ganzzahlige Optimierung
In diesem Kapitel betrachten wir lineare Programme mit ganzzahligen Nebenbedingungen.
- PDF / 492,507 Bytes
- 31 Pages / 439.37 x 666.142 pts Page_size
- 41 Downloads / 205 Views
In diesem Kapitel betrachten wir lineare Programme mit ganzzahligen Nebenbedingungen:
G ANZZAHLIGE O PTIMIERUNG Instanz:
Eine Matrix A ∈ Zm×n und Vektoren b ∈ Zm und c ∈ Zn .
Aufgabe:
Bestimme einen Vektor x ∈ Zn , so dass Ax ≤ b und cx maximal ist; entscheide, dass {x ∈ Zn : Ax ≤ b} = ∅; oder entscheide, dass sup{cx : x ∈ Zn , Ax ≤ b} = ∞.
Wir werden keine gemischt-ganzzahligen Programme betrachten, d. h. LPs mit ganzzahligen Nebenbedingungen f¨ur bloß eine echte Teilmenge der Variablen. Der gr¨oßte Teil der Theorie f¨ur lineare und ganzzahlige Programme l¨asst sich auf nat¨urliche Weise auf gemischt-ganzzahlige Programme erweitern.
PI P
Abbildung 5.1.
Nahezu alle kombinatorischen Optimierungsprobleme k¨onnen als ganzzahlige LPs formuliert werden. Die Menge der zul¨assigen L¨osungen ist dann die Menge {x : Ax ≤ b, x ∈ Zn } f¨ur eine bestimmte Matrix A und einen bestimmten Vektor b. Es ist P := {x ∈ Rn : Ax ≤ b} ein Polyeder und mit PI = {x : Ax ≤ b} I
110
5 Ganzzahlige Optimierung
bezeichnen wir die konvexe H¨ulle der ganzzahligen Vektoren in P. Wir nennen PI die ganzzahlige Hulle ¨ von P. Offensichtlich gilt PI ⊆ P. Ist P beschr¨ankt, so ist PI nach Satz 3.31 wieder ein Polytop (siehe Abb. 5.1). Der folgende Satz wurde von Meyer [1974] bewiesen: Satz 5.1. Die ganzzahlige H¨ulle PI eines jeden rationalen Polyeders P ist wieder ein rationales Polyeder. Beweis: Sei P = {x : Ax ≤ b}. Nach Satz 3.29 ist der rationale polyedrische Kegel C := {(x, ξ ) : x ∈ Rn , ξ ≥ 0, Ax − ξ b ≤ 0} endlich erzeugt. Wir k¨onnen annehmen, dass (x 1 , 1), . . . , (x k , 1), (y1 , 0), . . . , (yl , 0), mit x 1 , . . . , x k rational und y1 , . . . , yl ganzzahlig, C erzeugen (mittels Multiplikation einer endlichen Anzahl von erzeugenden Vektoren mit geeigneten positiven Skalaren). Betrachte das Polytop Q :=
k i=1
κi x i +
l
λi yi
: κi ≥ 0 (i = 1, . . . , k),
i=1 k
κi = 1,
i=1
! 0 ≤ λi ≤ 1 (i = 1, . . . , l) . Beachte, dass Q ⊆ P. Seien z 1 , . . . , z m die ganzzahligen Punkte in Q. Nach Satz 3.29 ist der von (y1 , 0), . . . , (yl , 0), (z 1 , 1), . . . , (z m , 1) erzeugte Kegel C polyedrisch, d. h. er kann durch {(x, ξ ) : M x + ξ b ≤ 0}, mit Matrix M und Vektor b rational, beschrieben werden. Wir behaupten, dass PI = {x : M x ≤ −b}. Um ⊆“ zu zeigen, sei x ∈ P ∩ Zn . Es ist (x, 1) ∈ C, d. h. x = ki=1 κi x i + ” l ur irgendwelche κ1 . . . , κk ≥ 0 mit ki=1 κi = 1 und λ1 . . . , λl ≥ 0. i=1 λi yi f¨ l Dann ist c := i=1 λi yi ganzzahlig, also ist auch x − c ganzzahlig. Ferner gilt x − c = ki=1 κi x i + li=1 (λi − λi )yi ∈ Q, also ist x − c = z i f¨ur irgendein i . Damit folgt (x, 1) = (c, 0) + (x − c, 1) ∈ C und somit ist M x + b ≤ 0. Um ⊇“ zu zeigen, sei x ein rationaler Vektor mit M x ≤ −b, d. h. (x, 1) ∈ ” C . Dann gibt es rationale Zahlen λ1 . . . , λl , μ1 , . . . , μm ≥ 0 mit m i=1 μi = 1, l m so dass x = i=1 λi yi + i=1 μi z j . O. B. d. A. k¨onnen wir annehmen, dass μ1 > 0. Sei δ ∈ N mit δλi ∈ N f¨ur i = 1, . . . , l, und sei δ ≥ μ11 . Dann ist (z 1 + li=1 δλi yi , 1) ∈ C und somit
Data Loading...
