Operations Research Polyeder und Polytope · Polyeder es ist sogar möglich, dass sich ein Polyeder als Lösungmenge eines nichtlinearen Ungleichungssystems ergibt Beispiel sei P

Operations Research

Rainer Schrader

Zentrum für Angewandte Informatik Köln

11. Mai 2007

1 / 83

Polyeder und Polytope

2 / 83


Gliederung

• Polyeder

• Darstellung von Polyedern

• Optimierung linearer Funktionen

• Rezessionskegel und polyedrische Kegel

• Polytope

• Facetten und Basislösungen

• rationale Polyeder

3 / 83

Polyeder

• sei P ⊆ Rn

• P heißt Polyeder, wenn es sich als Durchschnitt von endlich vielenHalbräumen darstellen lässt

• d.h. es existieren eine Matrix A ∈ Rm×n und ein Vektor b ∈ Rm derart,dass

P = P(A, b)

• wie wir wissen, sind insbesondere folgende Mengen Polyeder:

• die leere Menge ∅ und der Rn

• lineare oder affine Teilräume des Rn

• die Matrix A und der Vektor b sind jedoch nicht eindeutig

• typischerweise gibt es unendlich viele verschiedene (endliche) lineareUngleichungssysteme mit demselben Lösungsraum P

4 / 83

Polyeder

• es ist sogar möglich, dass sich ein Polyeder als Lösungmenge einesnichtlinearen Ungleichungssystems ergibt

Beispiel

• sei P die Punktmenge im nichtnegativen Quadranten der euklidischenEbene

P = {(x1, x2) ∈ R2+ | x 2

1 + 2x 22 + 3x1x2 − 2x1 − 3x2 ≤ −1}

• P entspricht der Lösungsmenge des linearen Ungleichungssystems

x1 + x2 ≤ 1x1 + 2x2 ≥ 1

x1, x2 ≥ 0

• damit ist P ein Polyeder

5 / 83

Polyeder

Gliederung

• Polyeder




• Polytope



6 / 83

Darstellung von Polyedern

• seien S, T ⊆ Rn beliebige Teilmengen

• die Minkowski-Summe S + T ist definiert als

S + T = {s + t | s ∈ S, t ∈ T } , wobei S + ∅ = S. (1)

• seien V = {v1, . . . , vk} und W = {w1, . . . , w`} zwei endlicheTeilmengen des Rn mit W 6= 0

• sei P die Menge

P = conv V + cone W = {v + w | v ∈ conv V , w ∈ cone W }, (2)

• d.h. die Minkowski-Summe der endlich erzeugten konvexen Mengeconv V und des endlich erzeugten konvexen Kegels cone W

7 / 83


P = conv V + cone W = {v + w | v ∈ conv V , w ∈ cone W }, (2)

+ =

• P besteht also aus der Menge aller Linearkombinationen z vom Typ

z =kX

i=1

µi vi +X̀j=1

λj wj mit µi , λj ≥ 0,

kXi=1

µi = 1.

8 / 83


SeiP = conv V + cone W (2)

• wir wollen zeigen:

• P ist ein Polyeder und

• jedes Polyeder hat eine Darstellung vom Typ (2)

• in diesem Sinn sind Polyeder endlich erzeugt

• wir führen den Beweis in mehreren Schritten.

9 / 83


Lemma 1Die Menge P = conv V + cone W ist ein Polyeder.

Beweis:

• wir betrachten V und W als Matrizen mit Spaltenvektoren vi bzw. wj

• und das davon erzeugte Ungleichungssystem

z− V x −W y = 01T x = 1

x, y ≥ 0

• die Lösungen (x, y, z) bilden ein Polyeder P in Rk+m+n

• P ist die Projektion von P auf die z-Koordinaten,

• damit folgt die Behauptung aus dem Projektionslemma.

10 / 83


• der Beweis von Lemma 1 zeigt:

• für P kann im Prinzip mit dem FM-Eliminationsverfahren einUngleichungssystem Ax ≤ b berechnet werden, so dass P = P(A, b)

• sei nun P ein beliebiges Polyeder mit 0 ∈ P

• dann gibt es eine endliche Indexmenge I und Ungleichungen ai x ≤ bi

derart, dassP = {x ∈ Rn | aT

i x ≤ bi , i ∈ I}.

• wegen 0 ∈ P dürfen wir bi ∈ {0, 1} annehmen

• entsprechend zerfallen die Ungleichungen in die Typen A(0)x ≤ 0 undA(1)x ≤ 1.

11 / 83


Lemma 2Seien A und B Matrizen und P = {x | Ax ≤ 1, Bx ≤ 0}. Dann gilt für diePolare des Polyeders P :

Ppol = conv[AT , 0] + cone BT .

Beweis:

• Ppol besteht aus allen Vektoren c derart, dass die UngleichungcT x ≤ 1 von den Ungleichungen Ax ≤ 1 und Bx ≤ 0 impliziert ist

• nach dem Lemma von Farkas bedeutet dies:

Ppol = {c ∈ Rn | c = AT y + BT z, y, z ≥ 0, yT 1 ≤ 1}

= {c ∈ Rn | c = AT y + 0y0 + BT z, y, z ≥ 0, y0 ≥ 0, yT 1 + y0 = 1}

= conv[AT , 0] + cone BT .

12 / 83


Satz 3 (Dekompositionsatz von Weyl-Minkowski)

Eine Teilmenge P ⊆ Rn ist genau dann ein Polyeder, wenn es endlicheMengen V , W ⊆ Rn gibt mit der Eigenschaft

P = conv V + cone W .

Beweis:

• nach Lemma 1 ist die Bedingung hinreichend

• wir beweisen die Notwendigkeit

• wir nehmen oBdA P 6= ∅ an

• und unterscheiden die Fälle 0 ∈ P und 0 /∈ P

13 / 83

Darstellung von Polyedern0 ∈ P :

• dann kann P geschrieben werden als

P = {x | Ax ≤ 1, Bx ≤ 0}

• nach Lemma 2 ist Ppol = conv[AT , 0] + cone BT

• nach Lemma 1 ist dann Q = Ppol ein Polyeder

• da 0 ∈ P , gilt nach Satz 1.4 P = (Ppol )pol

• und somitP = (Ppol )pol = Qpol .

• wiederum aus Lemma 2 schließen wir:

• P kann als Minkowski-Summe einer endlich erzeugten konvexenMenge und eines endlich erzeugten konvexen Kegels ausgedrücktwerden.

14 / 83

Darstellung von Polyedern0 /∈ P :

• wähle ein beliebiges t ∈ P und betrachte die Translation(Minkowskisumme)

P = P + {−t}.

• wegen 0 ∈ P gibt es endliche Mengen V und W derart, dass

P = conv V + cone W

• für V = V + t und W = W folgt:

conv V + cone W = conv`V + t

´+ cone W

= conv V + t + cone W

= P + t= P

15 / 83


Nach dem Satz von Weyl-Minkowski erlaubt ein Polyeder P zwei zueinanderduale Sichtweisen:

Implizit: P ist Lösungsmenge eines endlichen linearen

Ungleichungssystems Ax ≤ b

Explizit: P ist die Menge aller Punkte, die von

endlichen Mengen V und W gemäß (2) erzeugt werden.

Wir werden gleich zeigen: zwischen den Darstellungen kann im Prinzip mitHilfe des FM-Verfahrens gewechselt werden.

16 / 83


Die Situation verallgemeinert damit die bei linearen oder affinen TeilräumenA ⊆ Rn bekannte:

• einerseits ist A Lösungsmenge eines linearen GleichungssystemsAx = b

• andererseits gibt es eine endliche Menge S = s1, . . . , sk derart, dassA die Menge aller affinen Linearkombinationen ist:

x = λ1s1 + . . . + λk sk mitkX

i=1

λi = 1

Die Umrechungen zwischen den Darstellungen sind

• im linearen/affinen Fall effizient möglich (z.B. mit dem Gauss-Verfahren)

• im allgemeinen Fall im Prinzip einfach möglich

Wir untersuchen dazu zuerst den Fall von Kegeln.

17 / 83

Darstellung von Polyedern• für P = {x | Ax ≤ 1, Bx ≤ 0} gilt nach Lemma 2:

Ppol = conv[AT , 0] + cone BT

• speziell für einen Kegel P(B, 0) folgt somit

P(B, 0)pol = cone BT

• nach Lemma 1.13 stimmen für Kegel Polare und dualer Kegel überein:

P(B, 0)◦ = cone BT

• cone BT ist die Projektion auf die z-Koordinaten des Systems

z− BT y = 0y ≥ 0

• berechne mit Fourier-Motzkin eine Matrix A mit der Eigenschaft

cone BT = P(A, 0).

18 / 83

Darstellung von Polyedern• berechne mit Fourier-Motzkin eine Matrix A mit der Eigenschaft

cone BT = P(A, 0).

• nach Satz 1.14 gilt für konvexe Kegel K = (K 0)0

• somit:

P(B, 0) = (P(B, 0)◦)◦ = (cone BT )◦L. 1.13

= P(A, 0)pol L. 2= cone AT .

• also bilden die Spaltenvektoren von AT (bzw. die Zeilenvektoren vonA) ein Erzeugendensystem für den Kegel P(B, 0).

• Problem: diese Berechnungsmethode eines Erzeugendensystemsüber das FM-Verfahren ist im allgemeinen nicht effizient.

19 / 83

Darstellung von Polyedern• das Vorgehen lässt sich auf allgemeine Polyeder verallgemeinern:

• zu P(A, b) wollen wir endliche Mengen V und W bestimmen mit

P(A, b) = conv V + cone W .

• wir betrachten dazu den polyedrischen Kegel

K =

»xt

–∈ Rn+1 | Ax − bt ≤ 0, t ≥ 0

ff.

• dann gilt:

x ∈ P(A, b) ⇐⇒»x1

–∈ K .

20 / 83

Darstellung von Polyedern• wie vorher bestimmen wir Vektoren h1, . . . , hk ∈ Rn mit der Eigenschaft

K =

»xt

–∈ Rn+1 | Ax − bt ≤ 0, t ≥ 0

ff= cone{h1, . . . , hk}

• wir können annehmen, dass die Erzeugenden folgende Form haben:

hi =

»h′iti

–mit ti = 1 oder ti = 0.

• im Fall ti > 0 können nämlich wir einfach den Vektor hi durch Divisionmit ti entsprechend normieren

• wir behaupten, dass die folgenden Mengen das Gewünschte leisten:

V = {h′i | ti = 1} und W = {h′j | tj = 0},

21 / 83


• denn wir haben für alle x ∈ P(A, b)»x1

–=

Xhi∈V

µi

»h′i1

–+

Xhj∈W

λj

»h′j0

–

für geeignete µi ≥ 0 und λj ≥ 0

• ein Blick auf die letzte Komponente zeigt zudem

1 =Xh′

i ∈V

µi .

• und somit

x =Xhi∈V

µi h′i +X

hj∈W

λj h′j ∈ conv V + cone W .

22 / 83


Gliederung

• Polyeder




• Polytope



23 / 83

Optimierung linearer Funktionen

• viele Anwendungsprobleme lassen sich als spezielle mathematischeOptimierungsprobleme modellieren

• dabei ist eine lineare Funktion f (x) = cT x über dem Schnitt von(endlich vielen) linearen Ungleichungen zu maximieren

Lineares Programmgegeben c ∈ Rn , A ∈ Rm×n und b ∈ Rm betrachte das Problem

maxx∈Rn

cT x (3)

s.d. Ax ≤ b

• diskussionswürdig ist die Verwendung von max anstelle von sup

• bevor wir darauf eingehen noch ein paar Bemerkungen

24 / 83


maxx∈Rn

cT x (3)

s.d. Ax ≤ b

• die Ungleichungen werden auch als Restriktionen bezeichnet

• die Matrix A als die Restriktionsmatrix

• der Vektor b als die rechte Seite

• und f (x) = cT x als die Zielfunktion

• wir werden lineare Programme auch in einer anderen Form betrachten:

• u.a. anstelle von max cx die Aufgabe min cx

• min cx ist jedoch äquivalent zu −max (−c)x

25 / 83

Optimierung linearer Funktionen• anstelle von

maxx∈Rn

cT x (3)

s.d. Ax ≤ b

• betrachten wir auch lineare Programme in der Form

max cT x (4)

s.d.Ax = b

x ≥ 0

• die Restriktionen lassen sich in die ursprüngliche Form bringen:

Ax = bx ≥ 0 ←→

Ax ≤ b−Ax ≤ −b−x ≤ 0

←→

24 A−A−I

35 x ≤

24 b−b−0

35

26 / 83

Optimierung linearer Funktionen• umgekehrt gilt

Ax ≤ b ←→ Ax + s = bs ≥ 0 ←→ Ax+ − Ax− + s = b

x+, x−, s ≥ 0

• die beiden Formen sind damit äquivalent

• die s-Variablen werden auch als Schlupfvariablen bezeichnet

• wir diskutieren jetzt die Verwendung des max anstelle von sup

27 / 83


• nach Weyl-Minkowski können wir den Lösungsraum P = P(A, b) alsP = conv V + cone W darstellen,

• dann ergibt sich sofort:

(0) ist P = ∅, so hat das lineare Optimierungsproblem keine Lösung

(1) gibt es ein w ∈ cone W mit cT w > 0, so sind dieZielfunktionswerte nach oben unbeschränkt („∞“)

(2) gilt cT w ≤ 0 für alle w ∈ cone W und ist V 6= ∅, dann ist

maxx∈P

cT x = maxv∈V

cT v <∞.

28 / 83


c c

c

29 / 83


Beweis von (2):

• unter den angenommenen Umständen gilt

maxx∈P

cT x = maxx∈conv V

cT x.

• sei V = {v1, . . . , vk} und v =Pk

i=1 µi vi ∈ conv V ein beliebigesElement

• wegen µi ≥ 0 undP

i µ = 1 folgt:

cT v =kX

i=1

µi cT vi ≤ ( maxj=1,...,k

cT vj ) ·kX

i=1

µi = maxvj∈V

cT vj

• und somitmaxx∈P

cT x = maxv∈V

cT v.

30 / 83


Theoretisch lässt sich somit das lineare Optimierungsproblem auf das folgendereduzieren:

(i) stelle fest, ob P(A, b) = ∅

(ii) andernfalls stelle fest, ob für ein w ∈ W die Ungleichung cT w > 0 gilt

(iii) andernfalls, löse das Problem maxv∈V cT v.

Bemerkung

• das Problem ist also entweder leer, unbeschränkt oder das Maximumwird angenommen

• damit ist die Verwendung von „ max “ motiviert

• (ii) gilt nicht ⇐⇒ c ∈ P(W T , 0) = W ◦ für alle w ∈ W

• die Frage ist, inwieweit dieser Ansatz praktikabel ist

31 / 83


Gliederung

• Polyeder




• Polytope



32 / 83

Rezessionskegel

• seien V und W endliche Mengen mit W 6= ∅

• sei P = conv V + cone W das erzeugte Polyeder

• der Rezessionskegel von P ist der konvexe Kegel

P0 = cone W

• sei jetzt P = (A, b) implizit gegeben

• über den Rezessionskegel haben wir bereits gesehen:

• mit seiner Hilfe kann die Unbeschränktheit eines linearenProgramms getestet werden

• er kann aufwendig mittels FM-Elimination berechnet werden

• es stellt sich daher die Frage, ob er einfacher berechnet werden kann

33 / 83

Rezessionskegel

Lemma 4Seien A ∈ Rm×n und b ∈ Rm so, dass P(A, b) = conv V + cone W undW 6= ∅. Dann gilt:

cone W = P(A, 0).

Beweis:

• sei p ein beliebiger Punkt in P(A, b)

• dann ist p = v + w mit v ∈ conv V und w ∈ cone W

• da v + λw ∈ P(A, b) für alle λ, folgt

limλ→∞

λ(Aw) = limλ→∞

A(λw) ≤ b− Av

• folglich Aw ≤ 0

• und somit cone W ⊆ P(A, 0)

34 / 83

Rezessionskegel

• und somit cone W ⊆ P(A, 0)

• weiter gilt für alle v ∈ conv V und z ∈ P(A, 0):

A(v + z) = Av + Az ≤ b + 0 = b

• d.h.P = conv V + cone W ⊆ conv V + P(A, 0) ⊆ P

• und somit P = conv V + cone W = conv V + P(A, 0)

• außerdem hatten wir für beliebige Koordinatenvektoren c festgestellt:

c ∈ (cone W )◦ ⇐⇒ (3) besitzt Optimallösung

⇐⇒ c ∈ P(A, 0)◦

• also folgt (cone W )◦ = P(A, 0)◦

• da für Kegel K = (K ◦)◦ gilt, folgt daraus cone W = P(A, 0).

35 / 83


Gliederung

• Polyeder




• Polytope



36 / 83

Polytope

• ein Polytop ist ein beschränktes Polyeder,

• d.h. es existiert ein R > 0 mit

‖x‖ ≤ R für alle x ∈ P .

• damit sind die Polytope genau die kompakten Polyeder

• dabei lassen wir P = ∅ als leeres Polytop zu

• nach Weyl-Minkowski ist eine Menge P ⊆ Rn genau dann ein Polytop,wenn eine endliche Menge V ⊆ Rn existiert mit

P = conv V .

Lemma 5P(A, b) ist genau dann ein Polytop, wenn P(A, 0) = {0} .

37 / 83


Gliederung

• Polyeder




• Polytope

• Lineare Optimierung und Polytope• Diskrete Optimierung und Polytope



38 / 83

Polytope

• wir betrachten lineare Zielfunktionen f (x) = cT x über einem Polytop

• wir wissen:P = conv V =⇒ max

x∈PcT x = max

v∈VcT v.

• diese Eigenschaft gilt aber auch umgekehrt.

Lemma 6Sei P ⊆ Rn ein Polytop und V ⊆ P eine endliche Teilmenge. Dann gilt:

P = conv V ⇐⇒ maxx∈P

cT x = maxv∈V

cT v für alle c ∈ Rn .

39 / 83

Polytope

Lemma 7Sei P ⊆ Rn ein Polytop und V ⊆ P eine endliche Teilmenge. Dann gilt:


cT x = maxv∈V


Beweis:

• es ist noch zu beweisen, dass die Eigenschaft hinreichend fürP = conv V ist

• angenommen, es gäbe ein y ∈ P r conv V ,

• nach dem Trennungslemma gibt es dann ein c mit der Eigenschaft

cT y > max{cT x | x ∈ conv V },

• was die Bedingung verletzen würde.

40 / 83

Polytope

Lemma 8Sei V ⊆ Rn endlich und v0 ∈ V so, dass v0 /∈ conv(V r {v0}). Dann istv0 Ecke von conv V .

Beweis:

• sei P = conv V und S = conv(V r {v0})

• da v0 /∈ S, existieren v1 ∈ S und c ∈ Rn so, dass

cT v > cT v1 ≥ cT x für alle x ∈ S

• sei z = cT v1

• dann ist z Optimalwert des Problems

maxx∈S

cT x = maxv∈V r{v0}

cT v

41 / 83

Polytope

• andererseits gilt

z < cT v0 ≤ maxx∈P

cT x = maxv∈V

cT v =: z∗ d.h. z∗ = cT v0.

• sei x ein beliebiger Punkt in P = conv V , d.h.

x =Xv∈V

λvv mit λv ≥ 0,Xv∈V

λv = 1

• ist cT x = z∗, so folgt

z∗ = cT x = λv0 cT v0 +Xv 6=v0

λv cT v ≤ λv0 z∗ + (1− λv0)z .

• wegen z < z∗ folgt daraus λv0 = 1 und deshalb x = v0

• also folgt P ∩ {x ∈ Rn | cT x = z∗} = {v0}

• d.h. v0 ist Ecke von P .

42 / 83

Polytope

Satz 9Jedes nichtleere Polytop P ist die konvexe Hülle seiner Ecken.

Beweis:

• sei V eine minimale Erzeugendenmenge mit P = conv V

• dann gilt v /∈ conv(V r {v}) für alle v ∈ V

• da ansonsten P = conv(V r {v}) – im Widerspruch zur Minimalitätvon V

• nach Lemma 8 besteht V dann nur aus Ecken von P .

Der obige Satz garantiert insbesondere, dass jedes nichtleere Polytop auchEcken hat.

Für Polyeder ist dies im Allgemeinen nicht richtig (z.B. bei linearen oder affinenRäumen)

43 / 83


Gliederung

• Polyeder




• Polytope

• Lineare Optimierung und Polytope• Diskrete Optimierung und Polytope



44 / 83

Polytope

Ein Grundproblem der diskreten Optimierung kann wie folgt formuliert werden:

• gegeben

• eine Grundmenge E• eine Gewichtsfunktion w : E → R auf der Grundmenge

• eine Familie F ⊆ 2E von Teilmengen der Grundmenge

• setze die Gewichtsfunktion auf Teilmengen fort mittels:

w (X ) =Xe∈X

w (e) für X ⊆ E

• gesucht ist eine Teilmenge in F mit maximalem Gewicht

maxF∈F

w (F ). (5)

45 / 83

Polytope• wir ordnen der Teilmengenfamilie F ⊆ 2E wie folgt ein Polytop zu:

• repräsentiere jedes F ∈ F durch seinen Inzidenzvektor χF ∈ RE ,wobei

χF (e) =

1, wenn e ∈ F0, wenn e /∈ F

• sei nunP(F) = conv{χF | F ∈ F} ⊆ RE

• nach Lemma 6 gilt für jede endliche Teilmenge V :


cT x = maxv∈V


• d.h. es macht keinen Unterschied, ob wir lineare Funktionen überV oder conv V optimieren

46 / 83

Polytope• damit wird das diskrete Optimierungsproblem:

maxF∈F

w (F ). (5)

• zu: maximiere die lineare Funktion mit den Koeffizientenwe = w (e) über dem Polytop P(F):

maxF∈F

w (F ) = maxF∈F

Xe∈E

weχF (e)

= maxx∈P(F)

Xe∈E

wexe

= maxx∈P(F)

wx

47 / 83

Polytope

Beispiel:

• sei E = {e1, e2, e3}

• sei F =˘∅, {e1}, {e2}, {e3}, {e1, e2}, {e2, e3}

¯• das Polytop P(F) sieht dann wie folgt aus:

0,0,0 1,0,0

0,1,0

0,0,1

0,1,1

1,1,0

48 / 83

Polytope• maximiere die lineare Funktion mit den Koeffizienten we = w (e) über

dem Polytop P(F):maxF∈F

w (F ) = maxx∈P(F)

wx

• wir haben damit das diskrete Optimierungsproblem auf ein linearesOptimierungsproblem zurückgeführt

• die Form entspricht jedoch noch nicht der von uns verlangten

max cT xAx ≤ b

• der Zulässigkeitsbereich ist nämlich nicht implizit über Ungleichungensondern explizit als konvexe Hülle von endlich vielen Punkten gegeben

49 / 83

Polytope• das Polytop ist explizit und nicht implizit gegeben als

Ax ≤ b

• in einem weiteren Schritt wird dann versucht, eine impliziteBeschreibung zu gewinnen

• zur Veranschaulichung dieses Ansatzes folgen zwei Beispiele

• beim ersten lässt sich eine implizite angeben

• beim zweiten ist eine solche nicht bekannt

50 / 83

Polytope

Beispiel 1: Matchings

• seien S und T zwei endliche Mengen mit |S| = |T |

• wir betrachten die Menge aller Paare

S × T = {(s, t) | s ∈ S, t ∈ T }

• eine Zuordnung (bzw. ein perfektes Matching) ist eine bijektiveAbbildung π : S → T

• wir stellen uns die Zuordnung als Menge von Paaren vor:

M = M(π) = {(s, π(s)) | s ∈ S} ⊆ S × T .

• M sei die Menge aller Zuordnungen

51 / 83

Polytope• sei w : S × T → R eine Gewichtsfunktion, die jedem Paar einen Wert

zuordnet

• das Zuordnungsproblem ist nun:

maxM∈M

X(s,t)∈M

w (s, t)

• im Spezialfall w : S × T → {0, 1} spricht man auch vomHeiratsproblem

• sei P(M) das Zuordnungspolytop

• es ist die konvexe Hülle aller Inzidenzvektoren von Zuordnungen

• damit ist das Zuordnungsproblem äquivalent zu

max wT xx ∈ P(M)

52 / 83

Polytopen = 3:

• die Inzidenzvektoren x haben Länge 9

• sie haben die Form

x = (x1,1, x1,2, x1,3, x2,1, x2,2, x2,3, x3,1, x3,2, x3,3)

• betrachte die ZuordnungS T

1

2

3

1

2

3

• ihr entspricht der Inzidenzvektor

x = (1, 0, 0, 0, 0, 1, 0, 1, 0)53 / 83

Polytopen = 3:

• P(M) ist in diesem Fall die konvexe Hülle der folgenden Vektoren:

(1, 0, 0, 0, 0, 1, 0, 1, 0)

(1, 0, 0, 0, 1, 0, 0, 0, 1)

(0, 1, 0, 1, 0, 0, 0, 0, 1)

(0, 1, 0, 0, 0, 1, 1, 0, 0)

(0, 0, 1, 1, 0, 0, 0, 1, 0)

(0, 0, 1, 0, 1, 0, 1, 0, 0)

54 / 83

Polytopedas Zuordnungsproblem ist äquivalent zu

max wT xx ∈ P(M)

• dies ist eine explizite Beschreibung

• wir suchen eine implizite Beschreibung,

• d.h. ein System linearer Ungleichungen dessen Lösungen x geradedie Punkte in P(M) sind.

Zur Erinnerung:

• P(M) ist die konvexe Hülle von Inzidenzvektoren von Zuordnungen

• ein Inzidenzvektor einer Zuordnung hat die Länge |S| · |T |

• wir bezeichnen seine Komponenten mit xst

• d.h. xst = 1, wenn s ∈ S dem Element t ∈ T zugeordnet wird55 / 83

Polytope• sei jetzt x ∈ P(M) ein beliebiger Vektor

• welche Ungleichungen muss x erfüllen?

• ist x der Inzidenzvektor eines perfekten Matchings, dann gilt sicherlich:

xs,t ≥ 0 für alle (s, t) ∈ S × T (M0)Xt∈T

xst = 1 für alle s ∈ S (M1)

Xs∈S

xst = 1 für alle t ∈ T (M2)

• diese Ungleichungen gelten natürlich auch für alleKonvexkombinationen von Zuordnungen

• und deshalb für alle x ∈ P(M)

56 / 83

Polytope• es stellt sich heraus, dass sie P(M) schon vollständig bestimmen:

Lemma 10P(M) = {x ∈ RS×T | x erfüllt (M0) - (M2)}.

Bemerkung

• wir beweisen das Lemma hier nicht

• es wird sich als Folgerung aus einem allgemeinerenOptimierungproblem ergeben

• es gibt |S|! viele Zuordnungen; alle sind Ecken von P(M)

• zur linearen Beschreibung von P(M) genügen aber schon2|S| Gleichungen und |S| Ungleichungen

57 / 83

PolytopeBeispiel 2: das Rundreiseproblem

• sei S eine endliche Menge und E = S × S

• eine Rundreise (oder TSP-Tour) ist eine Anordnung der Elementevon S,

τ = s0s1 . . . , sns0,

• in τ tritt außer s0 kein Element zweimal auf

• wieder stellen wir τ als Menge von Paaren dar:

T = T (τ) = {(s0, s1), . . . , (sn , s0)}

• sei d : S × S → R+ eine Distanzfunktion auf den Paaren

• wir definieren die Länge von T als

d (T ) =X

(s,t)∈T

d (s, t).

58 / 83

Polytope• sei T die Menge aller Rundreisen

• das Rundreiseproblem (TSP-Problem) ist

minT∈T

d (T ) ←→ maxT∈T

X(s,t)∈T

−d (s, t).

• auch hier kann man wieder das entsprechende RundreisepolyederP(T ) definieren

• die Struktur von P(T ) ist jedoch noch weitgehend ungeklärt ist

• es sind zwar sehr viele Klassen von gültigen Ungleichungen fürP(T ) bekannt

• eine vollständige Beschreibung von P(T ) ist eines der großengegenwärtigen offenen Probleme der Berechenbarkeitstheorie dertheoretischen Informatik

59 / 83

Polytope

Gliederung

• Polyeder




• Polytope



60 / 83

Facetten und Basislösungen

• sei P 6= ∅ ein nichtleeres Polyeder

• sei F ⊆ P eine Seitenfläche von P

• F heißt Facette von P , wenn gilt:

dim F = dim P − 1

Beispiel:

A

B

C

D

E

61 / 83

PolytopeBeispiel

x2 ≤ 1−9x2 ≤ −9

−4x1 +x3 ≤ −3−x3 ≤ −1

2x1 +x3 ≤ 9

x

x

x

1

2

3

62 / 83


x2 ≤ 1−9x2 ≤ −9

−4x1 +x3 ≤ −3−x3 ≤ −1

2x1 +x3 ≤ 9

• es ist:

• P ⊆ {x ∈ R3 | x2 = 1}

• dim P = 2

• dim P = n − rg„

0 1 00 −9 0

«• damit existiert eine Teilmatrix Ap von A so, dass

m = n − rg AP und AP x = bP für alle x ∈ P

63 / 83

Facetten und BasislösungenZur Erinnerung:

• sei P = P(A, b) ein Polyeder

• sei F = {x ∈ P | cT x = z} eine nichtleere Seitenfläche von P

• im 1. Kapitel haben wir gesehen, dass sich F darstellen lässt als:

F = {x | Ax ≤ b, AF x = bF }

• wobei gilt:

• cT x = z ist eine nichtnegative Linearkombination von ZeilenAF x = bF aus Ax ≤ b

• AF x = bF sind genau die Zeilen i , für die Ai x = bi für alle x ∈ F

64 / 83


• sei Apx ≤ bp das (möglicherweise leere) Teilsystem so, dass

AP x = bP für alle x ∈ P

• sei aff P die affine Hülle von P

• aff P ist der kleinste affine Raum, der P enthält

• dann gilt:

Lemma 11

aff P(A, b) = {x | Apx = bp}.

65 / 83

Facetten und BasislösungenLemma 11

aff P(A, b) = {x | Apx = bp}.

Beweis:

• es ist P ⊆ {x | Apx = bp}

• damit gilt auch aff P ⊆ {x | Apx = bp}

• sei umgekehrt H = {x | cT x = z} eine Hyperebene, die aff P enthält

• dann enthält H auch P

• damit ist H ∩ P die triviale Seitenfläche P

• dann ist cT x = z nichtnegative Linearkombination von Zeile inApx = bp

• damit folgt

x erfüllt Apx = bp ⇒ x erfüllt cT x = z

66 / 83

Facetten und Basislösungen• damit folgt

x erfüllt Apx = bp ⇒ x erfüllt cT x = z

• mit anderen Worten:

{x | Apx = bp} ⊆ {x | cT x = z} = H

• somit:{x | Apx = bp} ⊆

\P⊆H

H = aff P

Korollar 12

dim P(A, b) = n − rg Ap .

Beweis:

dim P = dim{x | Apx = bp} = dim ker Ap = n − rg Ap .

67 / 83


Satz 13Sei P = P(A, b) ein Polyeder. Dann ist jede echte Seitenfläche Durchschnittvon Facetten von P .

Beweis:

• sei m = dim P

• nach Lemma 11 existiert eine Teilmatrix Ap von A so, dass

m = n − rg AP und AP x = bP für alle x ∈ P .

• wir können oBdA annehmen, dass die Zeilen von Ap linear unabhängigsind

• analog existiert für die Seitenfläche F eine Teilmatrix AF , so dass

F = {x ∈ P | AF x = bF } und dim F = n − rg AF .

68 / 83


• wir können wieder annehmen, dass die Zeilen von AF linearunabhängig sind

• jedes x ∈ F erfüllt auch die Gleichung AP x = bP

• damit können wir weiter annehmen, dass AP eine Teilmatrix von AF ist

• dann hat das Teilsystem die Form:»AP

AF rP

–x =≤

»bP

bF rP

–

• sei nun aTi x ≤ bi eine beliebige Ungleichung in AF rP x ≤ bF rP

69 / 83


• angenommen, aTi x ≤ bi wird impliziert von

AP x = bP =

»AP

−AP

–x ≤

»bP

−bP

–

• nach dem Farkas-Lemma existiert dann Vektoren y, z so, dass

ai = yT AP − zT AP und yT bP − zT bP ≤ bi

• insbesondere lässt sich dann ai aus den Zeilen von AP kombinieren

• im Widerspruch zur linearen Unabhängigkeit der Zeilen von AF

• somit gilt:Fi = {x ∈ P | Apx = bP , aT

i x = bi} 6= P

70 / 83


• somit gilt:Fi = {x ∈ P | Apx = bP , aT

i x = bi} 6= P

• d.h. Fi ist echte Seitenfläche

• weiter ist

rg»AP

aTi

–= rg Ap + 1

• d.h. dim Fi = dim P − 1 und Fi ist Facette

• offenbar ist F gerade der Durchschnitt aller solcher Facetten Fi

• und damit Lösungsmenge der Gesamtheit der entsprechendenGleichungen.

71 / 83


• der Beweis des letzten Satzes zeigt insbesondere:

• die Gleichungen AP x = bP zusammen mit den Facettenungleichungenimplizieren jede andere Ungleichung aT x ≤ b in Ax ≤ b

• denn: sei aT x ≤ b eine weitere Ungleichung

• und seiz = max

x∈PaT x ≤ b.

• dann ist Fa = {x ∈ P | aT x = z} eine Seitenfläche und somitDurchschnitt von Facetten

• also implizieren die Facettenungleichungen aT x ≤ z ≤ b

• damit reicht das System AP x = bP zusammen mit denFacettenungleichungen aus, um P(A, b) eindeutig zu beschreiben.

72 / 83


• sei P = P(A, b) ein Polyeder

• wir haben gesehen, dass wir jedes Polyeder in die Form bringenkönnen:

P = {x ∈ Rn | Ax = b, x ≥ 0}

• zur Erinnerung: eine Ecke ist eine Seitenfläche F mit dim F = 0

• sei r = rg A und v ≥ 0

• dann ist v genau dann eine Ecke von P , wenn es eine IndexmengeN mit |N | = n − r gibt derart, dass v eindeutige Lösung desfolgenden Systems ist:

Ax = beT

j x = 0 (für alle j ∈ N).

73 / 83


• äquivalent dazu ist:

(i) vj = 0 für alle j ∈ N ;

(ii) die Teilmatrix AB der r Spalten A·j mit Index j /∈ N bildet eineSpalten-Basis von A (Basislösung)

(iii) ABBvB = b

• folglich:

Ecke von P ←→ nichtnegative Basislösung von Ax = b

• diese Beziehung ist im allgemeinen nicht 1-1

• es ist hilfreich, sich AB als die Matrix der ersten r Spalten vorzustellen

• dann ist v nichtnegative Lösung des Systems:

ABvB + AN vN = b mit vi = 0 für i ∈ N74 / 83

PolytopeBeispiel:

−2x2 +x3 ≤ 0−2x1 +x3 ≤ 02x1 +x3 ≤ 8

+2x2 +x3 ≤ 8−x1 ≤ 0−x2 ≤ 0−x3 ≤ 0

0,0,04,0,0

0,4,04,4,0

2,2,4

75 / 83

Polytope−2x2 +x3 ≤ 0

−2x1 +x3 ≤ 02x1 +x3 ≤ 8

+2x2 +x3 ≤ 8−x1 ≤ 0−x2 ≤ 0−x3 ≤ 0

Einfügen von Schlupvariablen (alle Variablen nichtnegativ):

−2x2 +x3 +s1 = 0−2x1 +x3 +s2 = 0+2x1 +x3 +s3 = 8

+2x2 +x3 +s4 = 8

x1, x2, x3, s1, s2, s3, s4 ≥ 0

76 / 83

Polytope−2x2 +x3 +s1 = 0

−2x1 +x3 +s2 = 0+2x1 +x3 +s3 = 8

+2x2 +x3 +s4 = 8

x1, x2, x3, s1, s2, s3, s4 ≥ 0

Umbenennen der Schlupfvariablen:

−2x2 +x3 +x4 = 0−2x1 +x3 +x5 = 0+2x1 +x3 +x6 = 8

+2x2 +x3 +x7 = 8

x1, x2, x3, x4, x5, x6, x7 ≥ 0

77 / 83

Polytope

führt zu folgender Matrix A mit rg A = 4:

A =

0BB@0 −2 1 1 0 0 0−2 0 1 0 1 0 0

2 0 1 0 0 1 00 2 1 0 0 0 1

1CCAeine mögliche Basislösung:

0BB@0 −2 1 1 0 0 0−2 0 1 0 1 0 0

2 0 1 0 0 1 00 2 1 0 0 0 1

1CCA ·0BBBBBBBB@

x1

x2

x3

x4

x5

x6

x7

1CCCCCCCCA=

0BB@0088

1CCA

mit Lösung x = (0, 0, 0, 0, 0, 8, 8) ⇔ Ecke (0, 0, 0)

0,0,04,0,0

0,4,04,4,0

2,2,4

78 / 83

Polytopeweitere Basislösungen:

0BB@0 -2 1 1 0 0 0

-2 0 1 0 1 0 02 0 1 0 0 1 00 2 1 0 0 0 1

1CCA ·0BBBBBBBB@

x1

x2

x3

x4

x5

x6

x7

1CCCCCCCCA=

0BB@0088

1CCA

mit Lösung x = (2, 2, 4, 0, 0, 0, 0) ⇔ Ecke (2, 2, 4)

0,0,04,0,0

0,4,04,4,0

2,2,4

0BB@0 -2 1 1 0 0 0

-2 0 1 0 1 0 02 0 1 0 0 1 00 2 1 0 0 0 1

1CCA ·0BBBBBBBB@

x1

x2

x3

x4

x5

x6

x7

1CCCCCCCCA=

0BB@0088

1CCA

mit Lösung x = (2, 2, 4, 0, 0, 0, 0) ⇔ Ecke (2, 2, 4)

0,0,04,0,0

0,4,04,4,0

2,2,4

79 / 83


Weiter ergibt sich:

Lemma 14P hat höchstens

`nr

´Ecken.

Beweis:

• es gibt`n

r

´Teilmengen von r Spalten von A

• nicht jede dieser Teilmenengen muss eine Spaltenbasis bilden

• nicht jede Spaltenbasis führt zu nichtnegativen Basislösungen.

80 / 83


Gliederung

• Polyeder




• Polytope



81 / 83

Rationale Polyeder• in konkreten Anwendungen muss man sich oft auf den Körper

Q beschränken

• ein Polyeder P ⊆ Rn heißt rational, wenn P mit rationalenParametern dargestellt werden kann

• wir wissen, dass dies auf zwei Arten möglich ist:

Implizit: P ist Lösungsmenge eines endlichen linearen

Ungleichungssystems Ax ≤ b mit A ∈ Qm,n , b ∈ Qm

Explizit: P ist die Menge aller Punkte, die von endlichen Mengen

V ⊆ Qn und W ⊆ Qn gemäß (2) erzeugt werden.

82 / 83

Rationale Polyeder• wir haben gesehen, dass die Umrechnungen „exlizit ↔ implizit“ mit

dem FM-Verfahren möglich sind

• das beruht nur auf den folgenden Operationen:

• Multipikation mit einem positiven Skalar;

• (Komponentenweise) Addition von Vektoren.

• diese Operationen führen nicht aus dem Skalarbereich Q heraus

• damit gilt:

sämtliche Kenngrössen rationaler Polyeder sind rational.

83 / 83

Documents

Operations Research Polyeder und Polytope · Polyeder es ist sogar möglich, dass sich ein Polyeder als Lösungmenge eines nichtlinearen Ungleichungssystems ergibt Beispiel sei P