Embed Size (px)
Citation preview
LINEARE ALGEBRA II
Ao.Univ.-Prof. Mag. Dr. H. KautschitschInstitut fur MathematikUniversitat Klagenfurt
8. November 2006
ii
Inhaltsverzeichnis
Einleitung iii
IV Geometrie in Vektorraumen 1
14 Affine Geometrie 1
14.1 Affine Raume . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
14.2 Affine Eigenschaften von Geraden und Ebenen . . . . . . . . . . . . . . . . 10
14.3 Koordinatensysteme in affinen Raumen . . . . . . . . . . . . . . . . . . . . 17
14.3.1 Affine und kartesische Koordinatensysteme . . . . . . . . . . . . . . 18
14.3.2 Affine Koordinatentransformation . . . . . . . . . . . . . . . . . . . 24
14.4 Konvexe Mengen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
15 Metrische Geometrie 33
15.1 Abstands– und Winkelmessung . . . . . . . . . . . . . . . . . . . . . . . . . 33
15.2 Volumina von Simplices und Spaten . . . . . . . . . . . . . . . . . . . . . . 37
16 Lineare Optimierung 40
16.1 Geometrische Losung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
16.2 Geometrische Eigenschaften der zulassigen Menge Z . . . . . . . . . . . . . 48
16.3 Hauptsatz der linearen Optimierung . . . . . . . . . . . . . . . . . . . . . . 60
iii
Einleitung
Zunachst wird das Kapitel der linearen Gleichungssysteme durch die Determinantentheorie
abgeschlossen. Der Begriff der Determinante entstand ja ursprunglich bei LEIBNIZ aus
dem Bedurfnis, Losungen von Gleichungssystemen durch eine Formel darzustellen.
Anschließend wird gezeigt, wie man Vektorraumtheorie und die Ergebnisse aus der Theo-
rie der Gleichungssysteme zum Aufbau einer Geometrie, nicht nur im Anschauungsraum,
sondern auch in abstrakten Vektorraumen verwenden kann. Diese geometrischen Begriffs-
bildungen werden dann auf lineare Optimierungsproblemen angewendet.
Das fur die lineare Algebra wohl wichtigste Konzept, namlich die Linearitat, definiert als
Vertraglichkeit mit den Vektorraumoperationen, wird in allgemeinen, wie auch in Ska-
larproduktraumen behandelt und der Zusammenhang mit den Matrizen aufgezeigt. Die
Entwicklung der Eigenwerttheorie und eine Klassifikation von linearen Operatoren, wo-
bei insbesondere auf die geometrischen Auswirkungen im Anschauungsraum hingewiesen
wird, schließen dieses zentrale Kapitel ab.
Die beiden nachsten Kapitel sind dem Vereinfachen gewidmet. Zunachst wird dargelegt,
wie man durch Links– bzw. Rechtsmultiplikation mit geeigneten Matrizen eine gegebe-
ne Matrix auf eine moglichst ”einfache” Form transformieren kann. Als einfache For-
men werden die Diagonal–, Dreiecks- und Blockdiagonalmatrizen angesehen, insbesondere
die JORDAN’sche Blockdiagonalform. Statt eines Beweises der letzten Normalform wird
deren Erzeugung mittels unbestimmten Ansatzes bzw. verallgemeinerter Eigenvektoren
erlautert. Neben der Herleitung von Kriterien fur die Vereinfachung und den Spektraldar-
stellungen wird die Anwendung von Diagonalmatrizen fur das Losen von Differenzen– und
Differentialgleichungen und die Berechnung von Matrizenfunktionen demonstriert.
Nach den Matrizen werden quadratische Ausdrucke in n Variablen, sogenannten Quadri-
ken, vereinfacht. Dazu wird die Theorie der Bilinearformen bzw. der quadratischen Form
aufgebaut. Die Diskussion der Quadriken erfolgt sowohl in allgemeinen Vektorraumen,
als auch in Skalarproduktraumen. Abschließend wird noch gezeigt, wie die Geometrie der
Kegelschnitte vereinheitlich und auf eine entsprechende Geometrie der Quadriken verall-
gemeinert werden kann und damit gezeigt, wie auch quadratische Gebilde mittels linearer
Methoden beschrieben und analysiert werden konnen.
1
IV GEOMETRIE IN VEKTORRAUMENEs wird dargelegt, wie man die aus der Anschauung bekannten raumlichen Vorstellungen
auf abstrakte Raume verallgemeinern und rechnerisch behandeln kann. In der Linearen
Optimierung finden diese geometrischen Verallgemeinerungen eine nutzliche Anwendung.
14 Affine Geometrie
Bisher haben wir uns in Vektorraumen nur mit solchen Teilmengen beschaftigt, die fur
sich selbst wieder Vektorraume bildeten, also mit Teilraumen. Im Anschauungsraum, den
man als einen reellen Vektorraum auffassen kann, sind dies die unendlich ausgedehnten,
nicht gekrummten Punktmengen durch den Nullvektor 0.
Haufig benotigt man (und das nicht nur in der Geometrie) unendlich ausgedehnte, nicht
gekrummte Punktmengen, die nicht durch den Nullvektor 0 gehen:
Fur Optimierungsprobleme benotigt man daruber hinaus beschrankte, nicht gekrummte
Punktmengen, die mit je zwei Punkten auch deren gesamte “Verbindungsstrecke” ent-
halten.
2
Solche Punktmengen sind mit den geometrischen Grundbegriffen (Punkt, Gerade, Ebene,
Strecke) verbunden und wir werden sehen, daß sie ebenfalls durch lineare Gleichungen bzw.
Ungleichungen beschrieben werden konnen.
Wir wollen nun in beliebigen, nicht nur in reellen, Vektorraumen, Teilmengen unter-
suchen, die sich so wie die anschaulichen Geraden, Ebenen, Strecken usw. verhalten und
nachprufen, wann und wie diese abstrakten Geraden und Ebenen sich schneiden oder wann
sie parallel sind. Jenen Teil der Geometrie, der sich nur mit solchen Inzidenzbezie-
hungen beschaftigt, heißt affine Geometrie. In ihr wird von Abstandsuntersuchungen,
Messungen und von “senkrecht stehen auf” wird nicht gesprochen, dies geschieht in der
metrischen Geometrie. Anders als in einer Geometrievorlesung werden wir aber die
Grundbegriffe Punkt, Gerade, Ebene nicht axiomatisch, sondern mit Begriffen aus der
Vektorraumtheorie einfuhren. Die erzielten Ergebnisse stimmen mit denen der “Elemen-
targeometrie” uberein, aber nur im IR2 bzw. IR3 sehen die abstrakten Geraden und Ebenen
auch wie anschauliche Geraden und Ebenen aus. Dagegen sind die Ergebnisse in beliebigen,
abstrakten Vektorraumen oft nicht vorstellbar, aber trotzdem fur Anwendungen wichtig (→
CODIERUNG, APPROXIMATIONEN, LINEARE OPTIMIERUNGEN). Zum leichteren
Verstandnis sollte man sich aber immer die Verhaltnisse im Anschauungsraum (= 2– oder
3–dimensionaler reeller Vektorraum) vor Augen halten.
Zunachst wollen wir “nichtgekrummte” Punktmengen, die nicht durch 0 gehen, mit Hilfe
von Begriffen aus der Vektorraumtheorie beschreiben:
Man beobachtet: Die Ebene ε entsteht aus U durch Verschieben um ~p.
3
14.1 Affine Raume
Definition 14.1 Affiner Teilraum
V sei ein Vektorraum uber dem Korper K, U sei ein Teilraum von V und p ∈ V .
(i) Ein affiner Teilraum bzw. eine lineare Mannigfaltigkeit von V in Richtung
U ist die Teilmenge
A := {x ∈ V|x = p + u,u ∈ U} = p + U ⊆ V.
Auch so: Ein affiner Teilraum in Richtung U ist eine Nebenklasse von U (ein um p
“parallelverschobener” Teilraum U).
(ii) Die Dimension eines affinen Teilraumes ist die Dimension seiner Richtung:
dim(A) := dimU.
Bemerkung:
1. Die Differenz von 2 Punkten eines affinen Teilraumes A liegt stets in der Richtung
U , diese heißt daher auch Differenzenraum von A:
x1 − x2 = p + u1 − (p + u2) = u1 − u2 ∈ U
2. Ein affiner Teilraum ist wegen p ∈ A stets nichtleer. Jeder Teilraum ist ein affiner
Teilraum (mit p = 0), insbesondere kann jeder Vektorraum V als affiner Teilraum in
Richtung V aufgefaßt werden!.
Aber: Ein affiner Teilraum A ist nur dann ein Teilraum von V , wenn p ∈ U .
Beachte: im allgemeinen ist 0 6∈ A.
Beispiel: Sei A ∈ Km·n,~b ∈ Km und Rg(A) = r. Die Losungsmenge L = x0 + LH eines
losbaren, inhomogenen linearen Gleichungssystems A~x = ~b ist ein (n−r)−dimensionaler
affiner Teilraum im Kn mit der Losungsmenge des dazugehorigen homogenen Systems
A~x = ~0 als Richtung. Die Losungsmenge LH eines homogenen linearen Gleichungssys-
tems A~x = ~0 ist sogar ein (n− r)−dimensionaler Teilraum im Kn.
Die Darstellung von A = p + U ist unabhangig von der Wahl von p: Man kann fur p
jeden Vektor aus A nehmen und beschreibt damit dieselbe Punktmenge, denn es gilt:
4
Satz 14.1 Gleichheit von affinen Teilraumen
Zwei affine Teilraume A1 = p1 + U1 und A2 = p2 + U2 sind genau dann gleich, wenn sie
denselben Teilraum als Richtung besitzen und wenn die Differenz p1 − p2 in diesem liegt.
Formal:
A1 = A2 ⇔ U1 = U2 =: U und p1 − p2 ∈ U
(ohne Beweis)
Damit:
A = p + U = q + U ⇔ p− q ∈ U
Definition 14.2 Ein affiner Teilraum B = q + W heißt ein affiner Unterraum in
Richtung W des affinen Raumes A = p + U , wenn W ein Teilraum von U und q ∈ A ist.
B C A ⇔ W C U ∧ q ∈ A
Wir definieren nun die geometrischen Grundbegriffe Punkt, Gerade, Ebene in beliebigen
Vektorraumen als spezielle affine Teilraume A = p + U :
a) Sei U = {0} :, dann ist
A = p + {0} = {p}, d.h., A enthalt p als einziges Element und es ist dim(A) = 0;
Definition 14.3 Punkt
Ein Punkt P eines Vektorraumes V ist ein nulldimensionaler affiner Teilraum von V .
Kurzschreibweise: P = {p}
5
Ist P = {p} und Q = {q} dann ist P = Q ⇔ q − p ∈ U = {0} ⇔ q − p = 0 ⇔ q = p.
Vereinbarung: Ist P = {p}, dann kann man, um Klammern zu sparen, P mit p iden-
tifizieren: P := p. Der entsprechende Kleinbuchstabe bezeichnet also stets den Vektor,
durch den ein Punkt dargestellt wird.
Jeder Vektor p ∈ V ist also auch ein Punkt P = {p}. Nach der Identifizierung konnen
wir zu den Vektoren aus V auch Punkte aus V sagen, aber strenggenommen gilt nur:
P = {p} ⊂ V und nicht P = {p} ∈ V .
Ist P = {p} und Q = {q} ⇒ q − p ∈ U , d.h., fur je zwei Punkte P,Q ist der Differenzen-
vektor im Vektorraum U enthalten, also ein Vektor. Wir setzen:
PQ := q− p = Q−P (“Spitze–Schaft”–Regel)
b) Sei U =< a >:, dann ist
A = p+ < a >= {x ∈ V |x = p + λa, λ ∈ K} und es gilt dim(A) = 1.
Definition 14.4 Gerade
Eine Gerade g eines Vektorraumes V ist ein eindimensionaler affiner Teilraum von V .
Kurzschreibweise: g : x = p + λa, a heißt Richtungsvektor der Geraden g. (1)
Diese Gleichung heißt Punkt–Richtungsform der Geraden g durch P in Richtung <
a >. Der Parameter λ des Punktes X vergleicht die Lage des Punktes X mit jener des
Punktes P .
(1) heißt daher auch Parametergleichung der Geraden g.
Eine Gerade g wird also durch eine Vektorgleichung mit einem Parameter beschrieben.
Eine Gerade ist aber auch durch 2 verschiedene Punkte P,Q festgelegt: Die Richtung ist
dann durch < ~PQ >=< q − p > bestimmt. Die Parametergleichung von g lautet dann:
g : x = p + λ(q− p), Zweipunktform der Geraden g durch P und Q.
Sie stellt die Verbindungsgerade g(P,Q) der Punkte P und Q dar: g(P,Q) : x =
p + λ(q − p).
c) Sei U =< a,b > mit {a, b} l.u., dann ist
.A = p+ < a, b >= {x ∈ V |x = p + λa + µb, λ, µ ∈ K} und es ist dim(A) = 2.
6
Definition 14.5 Ebene
Eine Ebene ε eines Vektorraumes V ist ein zweidimensionaler affiner Teilraum von
V .
Kurzschreibweise: ε : x = p + λa + µb. (2)
(2) heißt Punkt–Richtungsform der Ebene ε durch P in Richtung < a, b >.
Eine Ebene ε wird also durch eine Vektorgleichung mit zwei Parametern beschrieben.
Eine Ebene ist aber auch festgelegt durch 3 Punkte P,Q,R, die nicht auf einer Geraden
liegen:
ε : x = p + λ(q− p) + µ(r− p): Dreipunktform der Ebene ε durch P,Q,R.
d) Verallgemeinerung: Sei dim(V ) = n und U =< v1, v2, . . . , vn−1 > mit {v1, v2, . . . , vn−1}
l.u., dann ist
A = {x ∈ V |x = p + λ1v1 + . . . + λn−1vn−1} = {x|x = p +∑n−1
i=1 λivi}.
Definition 14.6 Hyperebene
Eine Hyperebene H eines n−dimensionalen Vektorraumes V ist ein (n−1)−dimensionaler
affiner Teilraum von V .
Die Hyperebenen in einem 3–dimensionalen Vektorraum sind die Ebenen.
Die Hyperebene in einem 2–dimensionalen Vektorraum sind die Geraden.
Die Hyperebenen in einem 1–dimensionalen Vektorraum sind die Punkte.
e) Homogene Parameterdarstellung von affinen Teilraumen.
In den Beschreibungen g : x = p + λu, ε : x = p + λa + µb sieht es so aus, als ob p
ausgezeichnet ist, weil kein Parameter dabei steht. Dies ist jedoch nur scheinbar so:
g : x = p + λu = p− λp + λp + λu = (1− λ︸ ︷︷ ︸λ0
) p︸︷︷︸p0
+ λ︸︷︷︸λ1
(p + u︸ ︷︷ ︸p1
) =
= λ0p0 + λ1p1 mit p0 := p und p1 := p + u und λ0 + λ1 = 1− λ + λ = 1
Allgemein: A sei ein m−dimensionaler affiner Teilraum in Richtung U =< u1, . . . , um >.
Jedes x ∈ A kann als Linearkombination von m + 1 Punkten p0, p1, . . . , pm geschrieben
werden, wobei die Summe der Parameter 1 ist und die Differenzenvektoren ui :=
pi − p0(i = 1, . . . ,m) l.u. sind.
A : x = p +m∑i=1
λiui =m∑i=0
µipi mitm∑i=0
µi = 1 und {p1 − p0, . . . ,pm − p0} l.u.
7
Definition 14.7 Affine Hulle
Seien p0, p1, . . . , pm ∈ V .
(i) Eine Affinkombination der Punkte (Vektoren) p0, p1, . . . , pm ist eine Linearkom-
bination dieser Punkte, wobei die Summe der Parameter 1 ist.
x =m∑
i=0
λipi mitm∑
i=0
λi = 1.
(ii) Die affine Hulle < p0, . . . , pm >A der Punkte (Vektoren) {p0, . . . , pm} ist die Menge
aller Affinkombinationen von p0, . . . , pm.
< p0, . . . , pm >A:=
{x =
m∑i=0
λipi mitm∑
i=0
λi = 1
}.
Es gilt: Die affine Hulle von {p0, . . . , pm} ist der kleinste affine Teilraum, der
p0, . . . , pm enthalt.
(iii) (p0, . . . , pm) heißen Punkte in allgemeiner Lage ⇔
{p1 − p0, . . . , pm − p0} l.u. ⇔ dim(< p0, . . . , pm >A) = m.
Es gilt:
1 Punkt ist immer in allgemeiner Lage.
2 Punkte sind in allgemeiner Lage ⇔ sie sind verschieden.
3 Punkte sind in allgemeiner Lage ⇔ ihre Hulle ist eine Ebene. 3 Punkte sind nicht in
allgemeiner Lage ⇔ sie liegen auf einer Geraden.
4 Punkte sind in allgemeiner Lage ⇔ ihre Hulle ist ein 3–dimensionaler Raum. 4 Punkte
sind nicht in allgemeiner Lage ⇔ sie liegen in einer Ebene oder auf einer Geraden.
Damit gilt:
Jeder Punkt eines m−dimensionalen affinen Teilraumes A ist eine Affinkombi-
8
nation von m + 1 Punkten p0, . . . , pm in allgemeiner Lage.
A =
{x|x =
m∑i=0
λipi
}mit
m∑i=0
λi = 1
f) Parallelitat:
Im Anschauungsraum sind 2 Geraden parallel, wenn ihre Richtungsvektoren kollinear, also
l.a. sind. Eine Gerade ist parallel zu einer Ebene, wenn sie zu einer Geraden in der Ebene
parallel ist.
Definition 14.8 Parallelitat
(i) Die affinen Teilraume A1 = p1 + U1 und A2 = p2 + U2 heißen parallel, wenn eine
der Richtungen in der anderen enthalten ist (im besonderen konnen die Richtungen
gleich sein).
(ii) Die affinen Raume A1 und A2 heißen windschief, wenn sie nicht parallel sind und
ihr Durchschnitt leer ist.
A1 windschief zu A2 ⇔ A1 6 ‖A2 und A1 ∩A2 = ∅.
Beispiel: A = K3
A1 =
0BBB@2
1
0
1CCCA+ λ
0BBB@1
0
−1
1CCCA U1 =<
0BBB@1
0
−1
1CCCA >
A2 =
0BBB@−1
2
1
1CCCA+ µ
0BBB@2
−1
1
1CCCA+ ν
0BBB@3
−1
0
1CCCA U2 =<
0BBB@2
−1
1
1CCCA ,
0BBB@3
−1
0
1CCCA >
Es ist U1 ⊂ U2 (RowReduce) ⇒ A1‖A2
A3 =
0BBB@−1
2
1
1CCCA+ r
0BBB@2
−1
1
1CCCA U3 =<
0BBB@2
−1
1
1CCCA >
Es ist U1 6⊂ U3, U3 6⊂ U1 ⇒ A1 6 ‖A3.
Bemerkung: In hoher als 2-dimensionalen Vektorraumen ist die Parallelitat nicht transitiv:
A1‖A2 ∧A2‖A3 6⇒ A1‖A3
g) Abschlußeigenschaften von affinen Raumen
9
Definition 14.9 Verbindungsraum
Ai = pi + Ui seien affine Teilraume in Richtung Ui.
Der Verbindungsraum (die Summe) der affinen Raume Ai ist die Menge aller Punkte.
n∑i=1
Ai := A1 + . . . + An := p +n∑
i=1
Ui +n∑
i=1
< PPi >,Pi ∈ Ai, P ∈n⋃
i=1
Ai
Satz 14.2 Abschlußeigenschaften affiner Raume
(i) Der Durchschnitt von affinen Teilraumen ist entweder leer oder ein affiner Teilraum
mit der Richtung U1 ∩ U2.
A1 ∩A2 = p + (U1 ∩U2),p ∈ A1 ∩A2⋂n1 Ai = p +
⋂ni=1 Ui
(ii) Die Vereinigung von affinen Teilraumen ist im allgemeinen kein affiner Teilraum.
(iii) Die Summe (der Verbindungsraum) von affinen Teilraumen ist der kleinste
affine Teilraum, der die mengentheoretische Vereinigung der gegebenen Teilraume
enthalt.
Beispiel:
g = p+ < a >
h = q+ < b >seien 2 verschiedene Geraden in der Ebene (also {a, b} l.u.)
g + h = p+ < a > + < b >= p+ < a, b >= ε
Die eindimensionalen Teilraume < PP1 >,< PP2 > liefern keine neuen Beitrage.
Beispiel: g und h seien 2 verschiedene Geraden im Teilraum V 3 mit leerem Durchschnitt
(windschiefe Gerade): g = p + λa, h = q + µb.
g + h = p+ < a > + < b > + < ~PQ >=
= p+ < a, b, ~PQ >= Teilraum V 3.
Satz 14.3 Dimensionssatz fur affine Teilraume
dim(A1) + dim(A2) = dim(A1 + A2) + dim(A1 ∩A2), wenn A1 ∩A2 6= ∅
dim(A1) + dim(A2) = dim(A1 + A2) + dim(U1 ∩U2)− 1, wenn A1 ∩A2 = ∅
Folgt aus dem Dimensionssatz fur Teilraume (ohne Beweis).
10
14.2 Affine Eigenschaften von Geraden und Ebenen
“Affin” soll dabei bedeuten, daß wir uns nur auf Schnitt– und Parallelitatseigenschaften
konzentrieren, nicht jedoch z.B. auf Abstande. Wir werden zeigen, daß sich die Gera-
den oder Ebenen eines Vektorraumes V uber einem Korper K (bzw. die 1– oder 2–
dimensionalen linearen Mannigfaltigkeiten) tatsachlich wie die “anschaulichen” Geraden
oder Ebene verhalten. Aber nur in reellen Vektorraumen kann man sich eine Gerade so
vorstellen:
Im allgemeinen ist dies nicht der Fall: Eine Gerade g = p + U ist ein 1–dimensionaler
affiner Teilraum und geht daher durch Verschieben des 1–dimensionalen Vektorraumes
U hervor, U gleichmachtig mit K. In einem komplexen Vektorraum (K = IC) besteht
eine Gerade daher aus allen komplexen Zahlen, also aus allen Punkten der GAUSS’schen
Zahlenebene (!) und fur K = GF (2) besteht g nur aus 2 Punkten. Deshalb muß man sich
schon sorgfaltig uberlegen, daß affine Geraden sich auch tatsachlich so wie die Geraden
des Anschauungsraumes verhalten. Fur 3–dimensionale reelle Vektorraume erhalten
wir so die ublichen Aussagen der Elementargeometrie.
Satz 14.4 Punkte und Geraden
(i) Durch zwei verschiedene Punkte P und Q gibt es genau eine Gerade, namlich die
Verbindungsgerade
g(P,Q) : x = p + λ(q − p)
(ii) Durch einen Punkt Q, der nicht auf der Geraden g liegt, gibt es genau eine Gerade
h, die zu g parallel ist (EUKLIDISCHES AXIOM).
11
Beweis: (i) g(P,Q) : x = p+λ(q−p) enthalt fur λ = 0 den Punkt P und fur λ = 1 den Punkt
Q. Ist h : x = p+ < a > eine weitere Gerade, die P und Q enthalt, dann ist q− p ∈< a >,
wegen q − p 6= 0 ist < a >=< q − p >, also h : x = p+ < q − p >= p+ < a >= g
(iii) Sei g : x = p+λa und Q 6∈ g. h : x = q +λa enthalt Q (fur λ = 0) und ist parallel zu
g. Ist h1 : x = q + U eine weitere zu g parallele Gerade durch Q, dann ist U ⊆< a >
und damit wegen dim(U) = 1 = dim(< a >) : U =< a >, also ist h1 = h.
Bemerkung: Die durch die Vektorraumtheorie definierten Grundbegriffe Punkt, Gerade,
Ebene erfullen die Axiome einer EUKLIDISCHEN GEOMETRIE. Grund: Die Vektorrau-
maxiome entsprangen aus der anschaulichen (= euklidischen) Raumvorstellung.
Satz 14.5 Parallele Geraden
g und h seien zwei parallele Geraden einer Ebene mit dem gemeinsamen Richtungsvektor
a und P ∈ g,Q ∈ h. Dann gilt:
(i) g und h haben genau dann keinen gemeinsamen Punkt wenn {a, ~PQ} l.u.
(nicht kollinear) sind:
g ∩ h = ∅ ⇔ {a, ~PQ} l.u.
(ii) g und h fallen genau dann zusammen, wenn {a, ~PQ} l.a. (kollinear) sind
g = h ⇔ {a, ~PQ} l.a.
Da {a, ~PQ} entweder l.u. oder l.a. sein konnen gillt also:
Zwei parallele Geraden fallen entweder zusammen oder sie sind elementfremd.
Beweis:g : x = p + λa, h : x = q + µa
g ∩ h haben gemeinsame Punkte ⇔ ∃λµ,∈ K : p + λa = q + µa ⇔ q − p = (λ− µ)a
1. Fall: {a, q − p} l.u. ⇔6 ∃λ, µ ∈ K mit : (λ− µ)a = q − p ⇔6 ∃ gemeinsame Punkte.
12
2. Fall: {a, q − p} l.a. ⇔ q − p = la ⇔ q = p + la oder p = q − la. Damit gilt: Ist R ein Punkt von
g ⇒ r = p + λa ⇒ r = q − la + λa ⇒ r = q + (λ − l)a ⇒ R ist auch ein Punkt von h. Ist S ein
Punkt von h ⇒ s = q + µa ⇒ s = p + la + µa ⇒ s = p + (λ + µ)a ⇒ S ist auch ein Punkt von g,
insgesamt ist g mit h identisch (zusammenfallend).
Beispiel:
Sind die beiden Geraden g, h im K3 parallel, verschieden oder zusammenfallend?
g : ~x =
135
!+ λ
−25
−3
!
h = ~x =
−182
!+ µ
4
−106
!
4−10
6
!= −2
−25
−3
!⇒< a >=< b >⇒ g‖h
q − p =
−25
−3
!∈< a >⇒ {a, q − p}l.a. ⇒ g = h.
Satz 14.6 Nichtparallele Geraden
g und h seien 2 nichtparallele Geraden eines zumindest 3−dimensionalen affinen Teilraum
A mit den nichtkollinearen Richtungsvektoren a, b und P ∈ g,Q ∈ h.
Damit gilt:
(i) g und h windschief ⇔ {a, b, ~PQ} nicht komplanar:
g ∩ h = ∅ ⇔ {a,b, PQ} l.u.
(ii) g und h haben genau einen Schnittpunkt ⇔ {a, b, ~PQ} komplanar:
g ∩ h = {S} ⇔ {a,b, PQ} l.a.
Also: Zwei nichtparallele Geraden in einem zumindest 3–dimensionalen Raum
haben entweder genau einen Schnittpunkt oder sie sind windschief.
Zwei nichtparallele Geraden einer Ebene schneiden einander in genau einem
Punkt.
13
Beweis:g : x = p + λa, h : x = q + µb, {a, b} l.u.
g ∩ h = {S} ⇔ ∃λ, µ ∈ K : p + λa = q + µb ⇔ ∃λ, µ ∈ K : q − p = λa− µb (3)
1. Fall: {q − p, a, b} l.u. ⇔ (3) hat keine Losung (λ, µ) ⇔ g ∩ h = ∅.
2. Fall: {q − p, a, b} l.a. ⇒ q − p ist Lkbt. von a, b ⇒ (weil {a, b} l.u.)
∃ k, l ∈ K : q − p = ka + lb
(wegen {a, b} l.u. sind k und l eindeutig bestimmt) ⇔∃1 k, l ∈ K : p + ka = q − lb ⇔
∈ g ∈ h
g und h haben genau einen Punkt gemeinsam.
Folgerung: Zwei nichtparallele Geraden einer Ebene schneiden einander stets in genau
einem Punkt.
Beweis: {q − p, a, b} sind in einem 2–dimensionalen Raum stets l.a.
Flußdiagramm fur die Lage zweier Geraden g : p + λa und h : x = q + µb in einem
zumindest 3–dimensionalen affinen Raum:
14
Zusammenfassung:
Satz 14.7 Verhalten von Geraden
(i) Zwei Geraden in einem zumindest 3–dimensionalen affinen Raum sind entweder
parallel (auch zusammenfallend) oder sie schneiden einander in genau einem Punkt
oder sie sind windschief.
(ii) Zwei Geraden in einer Ebene sind entweder parallel (auch zusammenfallend) oder
sie schneiden einander in genau einem Punkt.
Ahnlich kann man fur Ebenen zeigen:
Satz 14.8 Parallele Ebenen
ε1, ε2 seien 2 parallele Ebenen mit Richtung U =< a, b >, P ∈ ε1, Q ∈ ε2 und
ε1 : p + λ1a + µ1b, ε2 : q + λ2a + µ2b.
(i) Haben zwei parallele Ebenen auch nur einen Punkt gemeinsam, so fallen sie zusam-
men
(ii) ε1 = ε2 ⇔ {a, b, ~PQ} l.a. (komplanar)
(iii) ε1 ∩ ε2 = ∅ ⇔ {a, b, ~PQ} l.u. (nicht komplanar)
Satz 14.9 Nicht parallele Ebenen
Zwei nicht parallele Ebenen eines 3–dimensionalen affinen Raumes schneiden einander
stets in genau einer Geraden.
Beweis:ε1 : x = p + ka + lb (k, l) ∈ K
ε2 : x = q + rc + sd (r, s) ∈ K
ε1]ε2 ⇒< a, b > 6=< c, d >
ε1 ∩ ε2 6= ∅ ⇔ ∃ Skalare k, l, r, s ∈ K mit:
p + ka + ld = q + rc + sd ⇔ q − p = ka + lb− rc− sd (4)
{q− p, a, b, c, d} sind l.a., 2 von ihnen lassen sich durch 3 l.u. Vektoren, etwa a, b, c (wegen der Nichtparal-
lelitat mussen in einem 3–dimensionalen Raum 3 der Vektoren a, b, c, d l.u. sein) eindeutig darstellen:
+
8>>><>>>:q − p = ra + sb + tc
d = ua + vb + wc
λd = λua + λvb + λwc
| · λ
15
q − p + λd = (r + λu)a + (s + λv)b + (t + λw)c
∀λ : q − (t + λw)c + λd| {z }∈ε2
= p + (r + λµ)a + (s + λv)b| {z }∈ε1
(5)
Formt man (5) um:
(q − tc) + λ(d− wc) = (p + ra + sb) + λ(ua + vb) =: g.
Man sieht, daß die gemeinsamen Punkte auf einer Geraden, der Schnittgeraden von ε1
und ε2 liegen.
Bemerkung: In einem 4–dimensionalen Vektorraum konnen {a, b, c, d} auch l.u. sein.
Dann schneiden die Ebenen einander in genau einem Punkt!
Zusammenfassung:
Satz 14.10 Verhalten von Ebenen in 3–dimensionalen Raumen
Zwei Ebenen eines 3−dimensionalen affinen Raumes sind entweder parallel (konnen auch
zusammenfallen) oder sie schneiden einander in einer Geraden.
Flußdiagramm fur die Lage zweier Ebenen ε1 und ε2 in einem 3–dimensionalen Vektor-
raum:
Analog erhalt man:
Satz 14.11 Gerade und Ebene
Eine Gerade eines 3–dimensionalen Vektorraum V ist entweder parallel zu einer Ebene
des Raumes (kann auch ganz in der Ebene liegen) oder die Gerade schneidet die Ebene in
genau einem Punkt.
16
Flußdiagramm uber die Lage einer Geraden und einer Ebene in einem 3–dimensionalen
Vektorraum:
Beispiel: V = K3
ε : x =
pz }| {0BBB@3
2
1
1CCCA+λ
az }| {0BBB@4
−1
6
1CCCA+µ
bz }| {0BBB@−3
−4
1
1CCCA
g : x =
qz }| {0BBB@1
3
1
1CCCA+r
cz }| {0BBB@1
−5
7
1CCCA1. Ist < c >⊆< a, b >⇔ {a, b, c} l.a.?
1 −5 7
4 −1 6
−3 −4 1
1 −5 7
0 19 −22
0 −19 22
1 −5 7
0 19 −22
0 0 0
⇒ l.a. ⇒ g‖ε
2. Ist g ganz in ε enthalten? ⇔ {q − p, a, b} l.a.?0BBB@−1
3
1
1CCCA−
0BBB@3
2
1
1CCCA =
0BBB@−4
1
0
1CCCA−4 1 0
4 −1 6
−3 −4 1
−4 1 0
0 0 6
0 19 −4
l.u. ⇒ g 6⊂ ε ⇒ g ∩ ε = ∅
17
Bemerkung: Abstrakte Geraden verhalten sich wie anschauliche Geraden.
Abstrakte Ebenen verhalten sich in 3–dimensionalen Raumen wie anschauliche Ebenen, in
hoher-dimensionalen Raumen treten unanschauliche Sachverhalte auf (z.B. zwei Ebenen
schneiden einander in einem Punkt!).
Beachte: Wir haben die Begriffe Punkt, Gerade und Ebene mit Hilfe der Vektorraumaxio-
me und den daraus abgeleiteten Begriffen definiert und durch Gleichungen beschrieben
(→ ANALYTISCHE GEOMETRIE).
In der SYNTHETISCHEN Geometrie sind Punkt, Gerade und Ebene undefinierte Grund-
begriffe, die gewisse Spielregeln (→ Euklidische Axiome) erfullen. Unsere definierten Punk-
te, Geraden und Ebenen erfullen dieselben Spielregeln, es sind dies aber Satze, die bewie-
sen werden mussen (im Gegensatz zu den Axiomen).
Analog kann man alle ublichen geometrischen Satze aus den Vektoraxiomen herleiten. Die
durch den Vektorraum definierten Punkte, Geraden und Ebenen verhalten sich so wie die
anschaulichen Punkte, Geraden und Ebenen.
Grund: Die Vektorraumaxiome wurden aus der Anschauung entnommen.
Vorteil der analytischen Methode: Man braucht von einer Menge von (auch abstrakten)
Objekten (wie z.B. Funktionen, n−Tupel, ...) nur die 9 Vektorraumaxiome uberprufen
und weiß dann, daß auch fur diese abstrakten Objekte die ublichen geometrischen Satze
gelten, also auch z.B. fur Geraden aus Funktionen, n−Tupeln usw. Daruber hinaus kann
das Herleiten bzw. der Umgang rechnerisch, durch Auflosen von Gleichungen erfolgen
(→ ANALYTISCHE GEOMETRIE), was wesentlich bequemer ist, als das axiomatische
Schließen (→ SYNTHETISCHE GEOMETRIE). Wir zeigen im folgenden, daß auch in ab-
strakten, endlich dimensionalen Vektorraumen Punktmengen durch Systeme von (meist
linearen) Gleichungen und Ungleichungen beschrieben werden konnen. (Bisher haben wir
nur im Vektorraum Kn der n−Tupel Teilraumen und affine Raume durch lineare Glei-
chungssysteme beschrieben.) Dazu werden, so wie in der anschaulichen Ebene bzw. im
anschaulichen Raum, Koordinatensysteme eingefuhrt.
14.3 Koordinatensysteme in affinen Raumen
Um affine Raume uber einem Korper K durch Gleichungen uber K beschreiben zu konnen,
muß man Punkten Korperelemente (Skalare) zuordnen konnen. Dies wird moglich durch
18
Einfuhrung von Koordinatensystemen. Sie entspricht der Einfuhrung von Basen in
Vektorraumen.
14.3.1 Affine und kartesische Koordinatensysteme
Beispiel: In der 2−dimensionalen Ebene ε werden 3 Punkte P0(p0), P1(p1), P2(p2) allge-
meiner Lage ausgezeichnet, d.h. p1 − p0, p2 − p0 sind l.u,, also eine Basis der Richtung U
der Ebene ε: U =< p1 − p0, p2 − p0 >.
~P0X = x − p0 heißt Ortsvektor des Punktes X bezuglich des Koordinatensystems
{P0, P1, P2}.
x− p0 = x1(p1 − p0) + x2(p2 − p0)
x = p0 + x1(p1 − p0) + x2(p2 − p0) ⇔ X(x1|x2)
Weil p1 − p0, p2 − p0 l.u., sind x1, x2 eindeutig bestimmt. Sie heißen die Koordinaten
[X] = (x1|x2) des Punktes X bezuglich {P0, P1, P2}. Die Koordinaten von X bezuglich
des Koordinatensystem {P0, P1, P2} sind die Koordinaten (Komponenten) des
Ortsvektors bezuglich der Basis { ~P0, P1, ~P0P2} von U .
KOORDINATEN eines Punktes = KOMPONENTEN seines Ortsvektors.
Ein Koordinatensystem in einem affinen Raum einfuhren heißt, Punkte auszeichnen.
Es gilt:~QX = ~P0X − ~P0Q ⇒ [ ~QX] = [ ~P0X]− [ ~P0Q] = [X]− [Q]
[ ~QX] = [X]− [Q] “Spitze–Schaft”–Regel
19
Allgemein:
Definition 14.10 Affine und kartesische Koordinatensysteme
A sei ein n−dimensionaler affiner Teilraum mit Richtung U in einem Vektorraum V uber
K. (Beachte, daß A auch ganz V sein kann, dann ist U = V ).
Ein Koordinatensystem von A ist ein geordnetes (n + 1)−Tupel
S := (P0, P1, . . . , Pn) von n + 1 Punkten aus A in allgemeiner Lage, d.h.
BS = ~{P0P1, ~P0P2, . . . , ~P0Pn} ist eine Basis der Richtung U .
P0 heißt Ursprung, P1, . . . , Pn heißen Einheitspunkte von S, die Geraden
ki : x = p0 + λ(pi − p0), i = 1, . . . , n
heißen die i−ten Koordinatenachsen des Koordinatensystems S.
BS heißt die zu S gehorige Basis von U .
Ist (V,<>) ein Skalarproduktraum, dann heißt S ein kartesisches Koordinatensystem
von A, wenn BS eine ON–Basis von V ist. Ist BS keine ON–Basis, dann heißt S ein
affines Koordinatensystem von A.
Jeder Punkt X(x) ∈ A laßt sich dann eindeutig in der Form
x = p0 +n∑
i=1
xi(pi − p0)
darstellen.
Der Vektor ~P0X = x − p0 heißt Ortsvektor von X bezuglich S, die Skalare x1, . . . , xn
heißen Koordinaten des Punktes X bezuglich des Koordinatensystems S.
Das n−Tupel (x1|x2| . . . |xn) heißt Koordinatenvektor von X.
X(x1|x2| . . . |xn) ⇔ ~P0X = (x1, x1, . . . , xn) ⇔ ~P0X := x = p0 +n∑
i=1
xi(pi − p0)
Satz 14.12 Koordinatenvektor und Ortsvektor
Der Koordinatenvektor eines Punktes bezuglich eines Koordinatensystems ist gleich dem
Komponentenvektor seines Ortsvektors bezuglich der zugehorigen Basis.
Weiters gilt: [QX]BS= [X]S − [Q]S.
Die Koordinaten eines Vektors bezuglich der zugehorigen Basis sind die Differenzen der
Koordinaten des Endpunktes und des Anfangspunktes des Vektors (“Spitze–Schaft”–
Regel).
20
Gegeben sei nun ein inhomogenes lineares Gleichungssystem A~x = ~b uber K von m Glei-
chungen in n Unbekannten vom Rang r also
A ∈ Kmn, Rg(A) = r.
Die Losungsmenge L ist gegeben durch
L = x0 + λ1 ~x1 + . . . + λn−r ~xn−r = x0+ < ~x1, . . . , ~xn−r >.
Wiederholung:
(i) Die Losungsmenge L eines linearen inhomogenen Gleichungssystems A~x = b von m
Gleichungen in n Unbekannten vom Rang r ist ein (n− r)−dimensionaler affiner
Unterraum des Kn (oder die leere Menge).
(ii) Die Losungsmenge eines homogenen linearen Gleichungssystems A~x = ~0 von m Glei-
chungen in n Unbekannten vom Rang r ist ein (n− r)−dimensionaler Teilraum
vom Kn.
Die Einfuhrung von Koordinatensystem in affinen Raumen ermoglicht es nun umgekehrt,
diese durch inhomogene LGS zu beschreiben (Gleichungsdarstellung, parameterfreie
Darstellung affiner Raume). Analog gestattete die Einfuhrung von Basen in Vek-
torraumen die Beschreibung von Teilraumen durch homogene LGS.
Satz 14.13 Gleichungsdarstellung von affinen Raumen
A sei ein n−dimensionaler affiner Raum uber dem Korper K mit einem Koordinatensys-
tem S.
B sei ein m−dimensionaler affiner Unterraum von A.
Dann gibt es ein i.a. inhomogenes lineares Gleichungssystem vom Rang n−m, dessen
Losungsmenge gerade die Koordinatenvektoren der Punkte von B bezuglich S sind.
Dieses den affinen Unterraum beschreibende Gleichungssystem ist nicht eindeutig be-
stimmt.
Beweisidee: B = p + U = {x|x = p + λ1u1 + . . . + λmum},m = dim(B). Dabei sei
{u1, . . . , um} eine Basis von U . Dann besitzt x− p ∈ U eine eindeutige Darstellung:
x− p = λ1u1 + . . . + λmum, λi ∈ K. (6)
21
Nun berechnet man die Koordinaten [X] von X, [p] von p bezuglich des Koordinatensys-tems S von A und die Komponenten [u1], . . . , [un] der Vektoren u1, . . . , un bezuglich derdazugehorigen Basis BS von U : Es sind [X], [p], [ui] ∈ Kn!(6) ist wegen der Linearitat der Komponentenbildung aquivalent zu:
[x− p]BS= λ1[u1] + . . . + λm[um]
↓[ ~PX]BS
= [X]S − [P ]S
also: λ1[u1] + . . . + λm[um] = [X]− [P ]. (7)
Das ist ein inhomogenes LGS mit n Gleichungen in den m Unbekannten λ1, . . . , λm
mit der Koeffizientenmatrix ([u1], . . . , [um]), die wegen der linearen Unabhangigkeit von
u1, . . . , um den Rang m hat. Also hat (7) eine eindeutige Losung λ1, . . . , λm (Rang = ]
Unbekannten). Setzt man diese in (7) ein, so erhalt man n−m ubrigbleibende Gleichungen
in
[x] = (x1, x2, . . . , xn) vom Rang n−m (weil dim(B) = m). Man erhalt diese bequem aus
(7) durch das Eliminationsverfahren (siehe folgendes Beispiel) bzw. mittels Z(A) = N(U)
und−→b = A−→p .
Da das Eliminationsverfahren nicht eindeutig bestimmt ist, sind auch die Gleichungen
nicht eindeutig bestimmt.
Zusammenfassung:
(i) Ein m–dimensionaler Teilraum eines n–dimensionalen Vektorraumes kann durch ein
homogenes Gleichungssystem in n Variablen vom Rang n–m beschrieben werden.
(ii) Ein m–dimensionaler affiner Raum eines n–dimensionalen Vektorraumes kann
durch ein inhomogenes lineares Gleichungssystem in n Variablen vom Rang n–
m beschrieben werden.
Beispiel: V = P2 = A P2 =< 1, x, x2 >, Standardbasis St, dim(P2) = 3
Sei p0 = 1 + x, p1 = x− x2, p2 = 3x + x2
a) p0, p1, p2 sind in allgemeiner Lage:
p1 − p0 = −1− x2, p2 − p0 = 1 + 2x + x2
[p1 − p0]St = (−1, 0,−1)
[p2 − po]St = (−1, 2, 1)
22
b) Ebene ε(p0, p1, p2) : durch p0, p1, p2
ε : f = 1 + x + λ(−1− x2) + µ(−1 + 2x + x2) = p + U
U =< −1− x2,−1 + 2x + x2 >
p = 1 + x
c) Koordinatensystem S = (0, 1, x, x2) von P2
1− 0 = 1
x− 0 = x
x2 − 0 = x2
l.u., [−1−x2]S =
−1
0
−1
=: ~u1, [−1+2x+x2]S =
−1
2
1
=: ~u2
[f ]S = [a0+a1x+a2x2]S =
a0
a1
a2
, ε =
f |[f ] =
1
1
0
+ λ
−1
0
−1
+ µ
−1
2
1
[1 + x]S =
1
1
0
= ~x0
Z(A) = N(U) U =< (−1, 0,−1), (−1, 2, 1) >
NullSpace[{{−1, 0,−1}, {−1, 2, 1}}]
Z(A) = (−1,−1, 1)
~b = A · ~x0 = (−1,−1, 1)
1
1
0
= −2
LGS: −a0 − a1 + a2 = 2
a0 + a1 − a2 = 2
ε = {f = a0 + a1x + a2x2|a0 + a1 − a2 = −2}
Die Ebene ε wird durch 1 = 3− 2 lineare Gleichungen in 3 = dim(P2) Unbekannten
beschrieben.
d) g(p,q)mit p = 3 + 2x + x2
q = 4 + x− 3x2
g =
f |[f ] =
3
2
1
+ r
1
−1
−4
g : f = 3 + 2x + x2 + λ(1− x− 4x2)
U = < (1,−1,−4) > ~x0 = (3, 2, 1)1
Z(A) = N(U) =< (4, 0, 1), (1, 1, 9) >
23
~b = A · x0 = (13, 5)
g :
4a0 + a2 = 13
ao + a1 = 5g = {f = a0 + a1x + a2x2|4a0 + a2 = 13,a0 + a1 = 5}
Die Gerade g wird durch 2 = 3 − 1 Gleichungen in 3 = dim(P2) Unbekannten
beschrieben.
e) Nun bestimmen wir den Durchschnitt von ε mit g
ε ∩ g : 1− x− 4x2 l.u. von −1− x2,−1 + 2x + x2
1 −1 −4
−1 0 −1
−1 2 1
RowReduce
1 0 0
0 1 0
0 0 1
⇒ l.u.dabei haben wir benutzt:
{vi} l.u. ⇒ {[vi]} l.u.
ε ∩ g = {f = a0 + a1x + a2x2
∣∣∣∣∣∣∣∣∣a0 + a1 − a2 = 2
4a0 + 1a2 = 13
a0 + a1 = 5
Weil P der Rang dieses LGS 3 ist, erhalt man eine eindeutige Losung.
LinearSolve [A,~b] ~b = (2, 13, 5)t(52 , 5
2 , 3)
ε ∩ g = {P} mit P = 52 + 5
2x + 3x2
P ∈ g : 3 + 2x + x2 + λ(1− x− 4x2) = 52 + 5
2 + 3x2
3 + λ = 52
λ = −12
Koeffizientenmatrix
52 + 5
2x + 3x2 = 3 + 2x + x2 − 12(1− x− 4x2)
oder mit Koordinaten in K3:52
52
3
=
3
2
1
+ λ
1
−1
−4
Analog sieht man, daß P ∈ ε.
24
14.3.2 Affine Koordinatentransformation
So wie man die Anderung der Koordinaten von Vektoren bei Wechsel der Basis durch
regulare Matrizen beschreiben kann, kann man auch die Anderung der Punktkoordinaten
bei Wechsel des Koordinatensystems durch ein Matrix–Vektor–Paar beschreiben.
A sei ein n−dimensionaler affiner Raum in einem Vektorraum uber dem Korper K. Ein
Wechsel des Koordinatensystems in A ruft auch einen Wechsel der Koordinaten eines
Punktes x ∈ A hervor.
S = (P0, P1, . . . , Pn): “altes” Koordinatensystem
S′ = (P ′0, P
′1, . . . , P
′n): “neues” Koordinatensystem
[x]S = (x1| . . . |xn): “alte” Koordinaten des Punktes X
[x]s,= (x′1| . . . |x′n): “neue” Koordinaten des Punktes X
Wie beim Basiswechsel drucken wir die neuen Punkte durch die alten aus:
P ′0 = P0 +
∑ni=1 ti ~P0Pi ⇔ p′0 = p0 +
∑ni=1 ti(pi − p0)
P ′j = P ′
0 +∑n
i=1 tij ~P0Pi ⇔ p′j = p0 +∑n
i=1 tij(pi − p0)
Ausfuhrlich:
p′1 − p′0 = t11(p1 − p0) + t21(p2 − p0) + . . . tn1(pn − p0)
p′2 − p′0 = t12(p1 − p0) + t22(p2 − p0) + . . . tn2(pn − p0)...
p′n − p′0 = t1n(p1 − p0) + t2n(p2 − p0) + . . . tnn(pn − p0)
T := (tij) =
t11 t12 . . . t1n
t21 t22 . . . t2n
...tn1 tn2 . . . tnn
(transponiert definiert!) ,~t = (t1, t2, . . . , tn)t
T ist regular, weil auch {p′1 − p′0, . . . , p′n − p′0} l.u. sind ((P ′
0, . . . , P′n) ist wieder ein
Koordinatensystem).
25
T ist sogar orthogonal (unitar), wenn ein kartesisches Koordinatensystem wieder auf
ein solches transformiert werden soll.
x = p′0 +∑n
j=1 x′j(p′j − p′0) =
= p0 +∑n
i=1 ti(pi − p0) +∑n
j=1 x′j∑n
i=1 tij(pi − p0) =
= p0 +∑n
i=1 ti(pi − p0) +∑n
i=1(∑n
j=1 tijx′j)(pi − po) =
= p0 +∑n
i=1(∑n
j=1 tijx′j + ti)(pi − p0) =
= p0 +∑n
i=1 xi(p′j − p′0)
Weil {p1 − p0, p2 − p0, . . . , pn − po} l.u. ist, folgt aus der eindeutigen Darstellbarkeit:
xi =n∑
j=1
tijx′j + ti fur i = 1, . . . , n
Also:[X]S = T [X]S′ + ~t bzw.
[X]alt = T [X]neu + ~t
Da T regular ist, existiert T−1 und wir erhalten:
[X]alt − t = T [X]neu
[X]neu = T [X]−1([X]alt − t) = T−1[X]alt − T−1t
Satz 14.14 Affine und kartesische Koordinatentransformationen
A sei ein n−dimensionaler affiner Raum eines Vektorraumes V , X ∈ A.
S := (P0, P1, . . . , Pn) sei ein Koordinatensystem in A.
T := (tij) ∈ Kn·n, t := (t1, z2, . . . , tn)t ∈ Kn.
P ′0 := P0 +
∑i=1 ti ~P0Pi
P ′j := P ′
0 +∑n
i=1 +tij ~P0Pi fur j = 1, . . . , n.
Dann gilt: S′ := (P ′0, P
′1, . . . , P
′n) ist genau dann ein Koordinatensystem in A, wenn T
regular ist. Die zugehorige Koordinatentransformation wird dann beschrieben durch:
[X]alt = T[X]neu + t bzw. [X]neu = T−1[X]alt −T−1t.
Ist S ein kartesisches Koordinatensystem, dann ist S′ genau dann wieder ein kartesisches
Koordinatensystem, wenn T eine orthogonale (unitare) Matrix ist. Fur die neuen Ko-
ordinaten gilt dann insbesondere:
[X]neu = Tt[X]alt −Ttt
26
T heißt Koordinatentransformationsmatrix von S → S′. Sie ist die Transponierte
jener Matrix, die angibt, wie sich die neuen Ortsvektoren von P ′1, . . . , P
′n durch die alten
ausdrucken lassen.
t heißt der Translationsvektor von S → S′. Er ist der Koordinatenvektor des neuen
Ursprungs bezuglich S.
Affine Koordinatenformationen konnen also durch eine regulare Matrix + Translations-
vektor beschrieben werden.
Erinnerung: Basiswechsel werden nur durch eine regulare Matrix allein beschrieben.
Affiner Koordinatenwechsel Komponentenwechsel
[X]alt = T [X]neu + t [x]alt = P [x]neu
14.4 Konvexe Mengen
In diesem Kapitel werden die aus der Anschauung bekannten Punktmengen Strecke, Drei-
eck, Pyramide, Halbstrahl u.a. auf abstrakte Vektorraume verallgemeinert. Sie sind keine
Teilraume oder affine Raume, werden aber speziell bei Optimierungsproblemen (→ Ope-
rations Research) benotigt. Zu ihrer Definition benotigt man allerdings angeordnete Ska-
larkorper.
Einige Beobachtungen;
Strecke PQ:
Gerade durch P,Q : x = p + µ(q − p) = (1− µ)p + µq = λ1p + λ2q mit λ1 + λ2 = 1
(λ1 = 1− µ, λ2 = µ)
λ1 = 1 ⇒ λ2 = 0 ⇒ x = p
λ1 = 0 ⇒ λ2 = 1 ⇒ x = q
Fur einen Punkt x ∈ PQ gilt: x = p+µ(q−p) mit 0 < µ < 1 ⇒ λ1 = 1−µ > 0, λ2 = µ > 0.
27
Also: X ∈ PQ ⇔ x = λ1p + λ2q mit λ1 + λ2 = 1, λ1, λ2 ≥ 0
Dreieck (PQR):
Ebene durch P,Q,R : x = p + µ(q − p) + ν(r − p)
= λ1p + λ2q + λ3r mit λ1 + λ2 + λ3 = 1
X1 ∈ QR ⇒ x1 = µ2q + µ3r mit µ2 + µ3 = 1, µ2, µ3 ≥ 0
X ∈ PX1 ⇒ x1 = ν1p + ν2x1 mit ν1 + ν2 = 1, ν1, ν2 ≥ 0
x = ν1p + ν2µ2q + ν2µ3r
x = λ1p + λ2q + λ3r mit λ1 + λ2 + λ3 = ν1 + ν2µ2 + ν2µ3 =
= ν1 + ν2(µ2 + µ3︸ ︷︷ ︸1
) = ν1 + ν2 = 1 und
λ1 = ν1 ≥ 0, λ2 = ν2µ2 ≥ 0, λ3 = ν2µ3 ≥ 0.
Also: X ∈ Dreieck (P,Q,R) ⇔ x = λ1p+λ2q+λ3r mit λ1+λ2+λ3 = 1 und λ1, λ2, λ3 ≥ 0.
P ist Ecke des Dreiecks 4⇔6 ∃X1, X2 ∈ 4 mit P ∈ X1X2.
X keine Ecke des Dreiecks 4⇔ ∃P,X1 ∈ 4 mit X ∈ PX1.
Definition 14.11 Konvexe und nicht beschrankte Mengen
V sei ein Vektorraum uber einem angeordneten Korper K.
T = {x1, x2, . . . , xr} ⊆ V,M ⊆ V .
(i) Eine Konvexkombination von x1,x2, . . . ,xr ist eine Linearkombination von x1, . . . , xr
der Form
λ1x1 + λ2x2 + . . . + λrxr mitr∑
i=1
λi = 1 und λi ≥ 0.
Sind alle λi > 0, dann spricht man von einer echten Konvexkombination.
(ii) Die konvexe Hulle H(T) von T ist die Menge aller Konvexkombinationen von T .
H(x1, . . . , xr) =
{x|x =
r∑i=1
λixi mit∑
λi = 1 und λi ≥ 0
}.
(iii) Eine Strecke PQ durch P und Q ist die konvexe Hulle von {P,Q}. P,Q heißen
Endpunkte der Strecke PQ.
PQ = {x|x = λ1p + λ2q mit λ1 + λ2 = 1, λ1, λ2 ≥ 0}
28
(iv) Eine Teilmenge M von V heißt konvex, wenn sie mit je zwei Punkten x1, x2 ∈ M
stets auch alle Punkte der Strecke x1x2 enthalt.
M konvex ⇔x1 ∈ M
x2 ∈ M
⇒ {x|x = λ1x2 + λ2x2, λ1 + λ2 = 1, λ1, λ2 ≥ 0} ⊆ M
(v) Ein Punkt x ∈ M heißt Ecke von M , wenn es keine verschiedenen Punkte x1, x2 ∈
M gibt, so daß x echte Konvexkombination von x1, x2 ist.
(vi) Ein Strahl durch p in Richtung a ist die Menge der Punkte {x|x = p + λa, λ ≥ 0}.
(vii) M heißt nicht–beschrankt, wenn M einen Strahl umfaßt.
Andernfalls heißt M beschrankt.
Beachte: Es gibt also 3 Arten von Hullen: lineare, affine, konvexe.
Satz 14.15 Einfache Eigenschaften von konvexen Mengen
(i) Die konvexe Hulle H(x1, x2, . . . , xr) ist stets konvex.
(ii) Der Durchschnitt von konvexen Mengen ist stets konvex.
(iii) Die Vereinigung von konvexen Mengen ist i.a. nicht konvex.
(iv) Jeder m−dimensionale affine Raum A ist eine nichtbeschrankte, konvexe Menge
ohne Ecken.
Beweis fur die Eckenfreiheit: Sei x ∈ A ⇒ x = p +Pm
i=1 λiui ⇒ x1 := p +P
(λi + k)ui ∈ A und
x2 := p +P
(λi − k)ui ∈ A. Es ist x1 6= x2 und x = 12x1 + 1
2x2.
(v) Ist T1 = {x1, . . . , xr} und T2 = {xr+1, . . . , xn}, dann ist H(T1 ∪ T2) = Menge aller
Konvexkombinationen je eines Punktes von H(T1) und H(T2). Damit kann man die
konvexe Hulle einer endlichen Menge T = {x1, . . . , xm} induktiv aufbauen: Man
geht aus von der konvexen Hulle von {x1, x2} = x1x2 aus. Dann bildet man die kon-
vexe Hulle von {x1, x2} ∪ {x3} = {x1, x2, x3} als Menge aller Konvexkombinationen
von Punkten aus x1x2 und x3 usw.
29
Definition 14.12 Spezielle konvexe Mengen im Kn
{~e1, . . . , ~en} sei die Standardbasis des Kn.
(i)
K+ :=
{x|x =
n∑i=1
λiei, λi ∈ K, λi ≥ 0
}heißt der Positivitatskegel im Kn.
Auch so:
K+ := {~x|~x ∈ Kn und ~x ≥ 0}.
1. Quadrant 1. Oktant
(ii) ~m = (m1, . . . ,mn) ∈ Kn, ε > 0
W (~m, ε) :={~x/ ‖xi −mi‖ ≤
ε
2, i = 1, . . . , n
}W heißt Wurfel mit Mittelpunkt ~m und Kantenlange ε.
Mittels der Dreiecksungleichung kann man zeigen, daß W eine konvexe Menge ist.
30
Definition 14.13 Spezielle Punkte
M sei eine konvexe Menge.
x ∈ M heißt innerer Punkt, wenn es einen Wurfel W (x, ε) gibt, der ganz in M enthalten
ist (der nur Punkte aus M enthalt).
x ∈ M heißt Randpunkt, wenn jeder Wurfel W (x, ε) sowohl Punkte von M als auch
Punkte von M c enthalt.
M heißt offen, wenn jeder Punkt von M ein innerer Punkt ist.
M heißt abgeschlossen, wenn M c offen ist.
offenes Intervall abgeschlossenes Intervall
offene Halbebene abgeschlossene Halbebene
offener Halbraum abgeschlossener Halbraum
~at · ~x > b oder ~at · ~x < b ~at · ~x > b oder ~at · ~x < b
Jede Hyperebene zerlegt den Raum in 2 Halbraumen.
Definition 14.14 Konvexe Mengen, die keine affinen Raume sind
(i) Die Menge der positiven Losungen eines inhomogenen linearen Gleichungssystems
ist eine konvexe Menge mit Ecken.
Sei A ∈ Kmn,~b ∈ Km. Dann ist Z := {x ∈ Kn|Ax = b und x ≥ 0} = L ∩ K+
konvex.
31
Z heißt zulassige Menge bezuglich des LGS A~x = ~b.
Z kann leer sein (wenn Rg(A) 6= Rg(A, b)).
Beweis der Konvexheit: Fur ~x1, ~x2 ∈ Z und λ1 ≥ 0, λ2 ≥ 0 mit λ1 + λ2 = 1 gilt:
A(λ1 ~x1+λ2x2) = λ1A ~x1+λ2A ~x2 = λ1~b+λ2
~b = (λ1+λ2)~b = 1~b = ~b und λ1 ~x1+λ2 ~x2 ≥
0.
Die Bestimmung der Ecken ist in hoherdimensionalen Raumen lastig (→ Operations
Research).
Fur die weiteren Beispiele sei {u1, u2, . . . , ur} l.u. in V, p ∈ V , beliebig.
(ii) K :={x|x = x0 +
∑ki=1 λiui, λi ≥ 0
}K heißt k− dimensionaler Kegel in V mit Spitze x0. (Der Kegel ist eine Verall-
gemeinerung des Winkelfeldes.)
K ist nichtbeschrankt, x0 ist die einzige Ecke.
Strahlen sind 1−dimensionale Kegel.
(iii) Sp := {x|x = x0 +∑r
i=1 λiui, 0 ≤ λi ≤ 1}
Sp heißt das von den Kantenvektoren u1, u2, . . . , uk von x0 aus aufgespannte k−dimen-
sionale Parallelepiped (k−Spat). (Verallgemeinerung des Parallelogramms).
Strecken sind 1–dimensionale, Parallelo-
gramme sind 2–dimensionale Parallelepipede.Die Ecken sind genau die Punkte
e = x0 +k∑
i=1
λiui mit λi ∈ {0,1}.
(iv) Si ={x|x = x0 +
∑ki=1 λiui, λi ≥ 0,
∑ki=1 λi = 1
}Si heißt der von den Vektoren u1, . . . , uk von x0 aus aufgespannte
k−dimensionale Simplex (k−Simplex). (Verallgemeinerung des Dreiecks).
32
Si ist als Teilmenge von SP beschrankt.
{x0, x0 + u1, . . . , x0 + uk} sind die Ecken von S.
S kann man in homogener Darstellung schreiben als
Si ={
x|x =∑k
i=0 µivi, µi ≥ 0,∑k
i=0 µi = 1}
mit µi = λi, i = 1, . . . , k; µ0 = 1−∑k
i=1 λi
vi = x0 + ui, i = 1, . . . , k; v0 = x0
Der k−dimensionale Simplex ist daher die konvexe Hulle seiner k+1 Ecken (in allgemeiner
Lage).
33
15 Metrische Geometrie
Neben der Untersuchung von Inzidenz– und Parallelitatseigenschaften werden in der Ele-
mentargeometrie auch viele Aussagen uber Abstande, Langen, Inhalte, Winkel und Or-
thogonalitat gemacht. Um diese Begriffe in die Sprache der linearen Algebra ubersetzen
und damit einer rechnerischen Behandlung zuganglich machen zu konnen, benotigt man
als zusatzliche Eigenschaften in Vektorraumen nur das Skalarprodukt. In diesem Kapitel
werden also generell Skalarproduktraume vorausgesetzt. Die Inhaltsmessung von einigen
konvexen Punktmengen wird mit Determinanten behandelt.
Nachdem wir bisher affine Raume generell als Teilmengen von Vektorraumen aufgefaßt
haben, ubernehmen wir die ubliche Abstands– und Winkelmessung von Skalarproduk-
traumen.
15.1 Abstands– und Winkelmessung
Definition 15.1 Abstand und Winkel
(V,<, >) sei ein Skalarproduktraum, A sei ein affiner Raum in V .
(i) Unter dem Abstand zweier Punkte X,Y ∈ A, symbolisch d(X, Y ), versteht man
die reelle Zahl
d(X,Y) := ‖y − x‖ =√
< y − x,y − x >.
In reellen Skalarproduktraumen ist daruber hinaus eine Winkelmessung moglich:
(ii) Sind X, Y, Z ∈ A mit X 6= Y 6= Z, dann versteht man unter dem Winkel <)(X,Y,Z)
mit dem Scheitel Y die reelle Zahl
<)(X,Y,Z) := arccos< x− y, z− y >
‖x− y‖‖z− y‖
Besonders nutzliche Gleichungsdarstellungen von Punktmengen erhalt man mittels karte-
sischer Koordinatensysteme (nach R. DESCARTES, 1596-1650).
Als Beispiel fur eine Gleichungsdarstellung untersuchen wir die Darstellung von Hyper-
ebenen.
A sei ein n−dimensionaler affiner Raum in Richtung U . H sei eine Hyperebene in Richtung
W =< e1, e2, . . . , en−1 > mit der ON–Basis B = (e1, e2, . . . , en−1):
H = {x|x = p + λ1e1 + . . . + λn−1en−1}
34
{e1, . . . , en−1} kann zu einer ON–Basis von U erganzt werden (Satz uber die orthogonale
Zerlegung):
U =< e1, e2, . . . , en−1, n0 >
n0 ist also ein normierter Vektor, der auf alle Vektoren aus W orthogonal steht. Dann gilt
fur jeden Punkt X ∈ H:
< x− p, n0 >=< λ1e1 + . . . + λnen, n0 >= λ1 < e1, n0 > + . . . + λn−1 < en−1, no >= 0
Damit ist n0 ⊥ x − p ∀x ∈ H und ebenso gilt: n ⊥ x − p ∀x ∈ H fur n := k · n0 mit
k ∈ K.
n heißt daher Normalvektor der Hyperebene H.
Jeder Punkt x ∈ H erfullt < x − p, n0 >= 0. Ist umgekehrt x ∈ A mit < x − p, n0 >=
0 ⇒ x− p = λ1e1 + . . . λn−1en−1 + λnn0 und < x− p, n0 >= 0 ergibt:
< λ1e1 + λn−1en−1 + λnn0, n0 >= 0 ⇒
λ1 < e1, n0︸ ︷︷ ︸0
> + . . . + λn−1 < en−1, n0︸ ︷︷ ︸0
> +λn < n0, n0︸ ︷︷ ︸1
>= 0 ⇒ λn = 0 ⇒ x − p =
λ1e1 + . . . + λn−1en−1 ⇒ x = p + λ1e1 + . . . + λn−1en−1 ⇒ x ∈ H.
Die Hyperebene H durch den Punkt P (p) in Richtung W ist also die Menge aller Punkte
X(x) mit
< x− p,n0 >= 0 ⇔< x,n0 >=< p,n0 >=: c
oder auch
< x− p, n >= 0 ⇔< x, n >=< p, n > .
wobei n ∈ W⊥.
Insbesondere gilt auch fur den Einheitsvektor n0 von n:
< x− p,n0 >= 0 ⇔< x,n0 >=< p,n0 >
Diese Darstellung von H heißt HESSEsche Normalvektorform von H. (O.L. HESSE,
1811–1874).
Ihre Bedeutung liegt, so wie im anschaulichen Raum V 2 bzw. V 3 (siehe Kapitel ??) darin,
daß man den Abstand eines Punktes von einer Hyperebene leicht berechnen kann.
35
Definition 15.2 Abstand eines Punktes von einer Punktmenge
A sei ein affiner Raum, M ⊂ A und Y (y) ∈ A.
Unter dem Abstand d(Y,M) des Punktes Y von der Menge M versteht man das Infimum
der Abstande d(Y, X) mit X(x) ∈ M .
d(Y, M) := inf{d(Y, X)|X ∈ M} = inf{‖x− y‖/X ∈ M}
Ist M ein affiner Teilraum, dann gibt es stets ein F (f) ∈ M mit minimalem ‖f − y‖.
F heißt der zu Y gehorige Fußpunkt.
Nach dem Satz uber die beste Approximation gilt fur eine Hyperebene H in Richtung W :
d(Y, H) = min{‖x− y‖/x ∈ H} =< y − p, no >.
Das heißt: Man erhalt den Abstand eines Punktes Y von einer Hyperebene H
durch P und dem Normalvektor n, wenn man in der Hesseschen Normalvektor-
form von H :< x−p,n0 >= 0 fur x den Punkt y einsetzt: d(Y,H) =< y−p,no >.
Die Gerade l durch Y mit dem Richtungsvektor n heißt Lot auf H durch Y. Der
Durchschnitt des Lotes mit der Hyperebene enthalt genau einen Punkt F , genannt der
Fußpunkt des Lotes: {F} = l ∩H.
Es gilt: d(Y,F) = |d(Y,H)|
Der Fußpunkt ist also jener eindeutig bestimmte Punkt, fur den der Abstand angenommen
wird.
Fur den Ortsvektor f von F gilt auch: f = y− < y − p,n0 > n0.
Vergleiche noch einmal Kapitel ??. Beachte, daß jetzt die Punkte auch Funktionen, Poly-
nome, Matrizen u.a. sein konnen!
Der Abstand d(P,Q) = ‖p − q‖ zwischen zwei Punkten P und Q kann wegen (N1) nur
positiv sein. Der Abstand d(Y, H) eines Punktes Y von einer Hyperebene H kann wegen
d(Y, H) =< y − p, n0 > aber auch negativ sein. Damit zerlegt die Hyperebene H den
affinen Raum A in 2 Halbraume:
A+ := {Y |d(Y, H) > 0} heißt positiver Halbraum von A bezuglich H
A− := {Y |d(Y, H) < 0} heißt negativer Halbraum von A bezuglich H
Nach Satz 14.13 kann eine Hyperebene als (n−1)−dimensionaler Unterraum des n−dimensiona-
len affinen Raumes A nach Einfuhrung eines Koordinatensystems durch eine inhomogene,
lineare Gleichung in n Variablen uber K dargestellt werden. (Koordinatenform der
36
HESSEschen Normalvektorform von H). Wahlt man insbesondere ein kartesisches
Koordinatensystem aus, kann man die Koeffizienten der n Variablen geometrisch schon
deuten:
S = (O,E1, . . . , En) sei ein kartesisches Koordinatensystem von A mit Richtung U .
X ∈ H und P ∈ H haben die kartesischen Koordinaten
[X]S = (x1, . . . , xn), [P ]S = (p1, . . . , pn) und der Normalvektor n0 von H habe die Koor-
dinaten
[n0]SU= (n1, n2, . . . , nn).
Bekanntlich laßt sich das Skalarprodukt bezuglich ON–Basen als Standardskalarprodukt
schreiben.
< x, y >= [y]∗[x]
Damit gilt fur die HESSEsche Normalvektorform:
0 =< x− p, n0 >= [n0]t · [x− p] = [n0]t · [x]t − [n0]t[p]︸ ︷︷ ︸=:c
Also: [n0]t · [x] = c ⇔ n1x1 + . . . + nnxn = c
Die Koeffizienten von x1, . . . ,xn in der Koordinatendarstellung der HESSE-
schen Normalvektorform einer Hyperebene H bezuglich eines kartesischen Ko-
ordinatensystems geben die Koordinaten des Normalvektors von H an.
Zusammenfassung:
Satz 15.1 HESSEsche Normalvektorform einer Hyperebene
(V,<>) sei ein Skalarproduktraum. H = p+W sei eine Hyperebene des n−dimensionalen
affinen Raumes A mit Richtung U ⊆ V , Y (y) ∈ A ein beliebiger Punkt.
(i) Ein Normalvektor n von H ist ein Element aus W⊥ =< n >.
(ii) H = {x ∈ A| < x− p, n >= 0}.
Bezeichnet n0 den Einheitsvektor von n, dann heißt
< x− p,n0 >= 0
die HESSEsche Normalvektorform von H.
(iii) d(Y,H) =< y − p,n0 > gibt den Abstand des Punktes Y von H an.
37
(iv) Bezuglich eines kartesischen Koordinatensystems S laßt sich H durch eine i.a. in-
homogene lineare Gleichung der Form
n1x1 + . . . + nnxn = c
darstellen, wobei (n1, n2, . . . , nn) die Koordinaten eines Normalvektors von H bezuglich
SU sind. Fur c gilt: c = [n]t[p].
(v) Die Hyperebene H teilt den affinen Raum in 2 Halbraume:
positiver Halbraum A+ = {X|d(X, H) > 0} = {(x1, . . . , xn)|n1x1 + . . . + nnxn >
c}.
negativer Halbraum A− = {X|d(X, H) < 0} = {(x1, . . . , xn)|n1x1 + . . .+nnxn <
c}.
Beispiel: Im (R4, <>St) ist die Hyperebene H gegeben durch
H = ~x =
0BBBBBB@1
0
2
1
1CCCCCCA+ λ1
0BBBBBB@1
0
0
1
1CCCCCCA+ λ2
0BBBBBB@0
1
1
0
1CCCCCCA+ λ3
0BBBBBB@1
−1
1
−1
1CCCCCCA ; Y =
0BBBBBB@1
2
−2
1
1CCCCCCA
Bezuglich des Standardkoordinatensystems erhalt man durch Elimination oder durch Be-
stimmung des Orthogonals (mittels NullSpace) die Koordinatengleichung:
H : x1 + x2 − x3 − x4 = −2
(1, 1,−1,−1)t ist ein Normalvektor von H.
HESSEsche Normalvektorform:
x1 + x2 − x3 − x4 + 2 = 0
d(Y, H) = 1+2+2−1+22 = 3
IR4,+ : x1 + x2 − x3 − x4 > −2
IR4,− : x1 + x2 − x3 − x4 < −2
15.2 Volumina von Simplices und Spaten
Soll eine Zahl den Inhalt µ einer Figur messen, so stellt man an diese Zahl folgende
“naturliche” Forderungen (Maßeigenschaften einer Figur):
38
1. Translationsinvarianz: Der Inhalt µ einer Figur soll sich nicht andern, wenn die
Figur verschoben wird:
Ist M ′ = M + v ⇒ µ(M ′) = µ(M)
2. Additivititat: Sind M1,M2 zwei disjunkte Mengen, so gilt:
µ(M1 ∪Ms) = µ(M1) + µ(M2)
3. Streckung: Ist X0 eine beliebige Ecke und ~X0Xi eine beliebige von X0 ausgehende
Kante von M und wird Xi ersetzt durch X1 = X0 + λ ~X0Xi, wahrend die anderen
Kanten erhalten bleiben, so gilt fur die so in einer Richtung gestreckte Punktmenge
Mλ : µ(Mλ) = µ(M).
4. Ausartung: Besitzt M statt k+1 nur k l.u. Punkte, so ist µ(M) = 0. (Der Inhalt ein
und derselben Figur andert sich, wenn man zu einer anderen Dimension des Inhalts
ubergeht.) So hat eine Strecke der Lange 3 den 1−dimensionalen Inhalt (= Lange)
3, jedoch den 2−dimensionalen Inhalt (= Flacheninhalt) 0.
5. Normierung: Fur das elementargeometrische Einheitsquadrat M0 gilt µ(M0) = 1
In der Analysis wird gezeigt, daß man durch das bestimmte Integral vielen Punktmengen
so eine Zahl als Maß zuordnen kann. Genauso, wie man aber im Rn(n > 3) nicht jeder
Punktemenge eine Zahl so zuordnen kann, daß a)–e) gilt, kann man auch in Vektorraumen
nicht jede Punktmenge “messen”, es gelingt dies nur fur k−Spate und k−Simplexe. Die
Translationsinvarianz erreicht man dadurch, daß man das Volumen des k−Spates durch
die k Kantenvektoren ~X0Xi definiert, denn:
Es gelte: Xi = X0 + ~X0Xi(i = 1, . . . , k).
Durch eine Translation v ergeben sich die Punkte X∗0 = X0 + v und X∗
i = Xi + v mit
X∗i = X∗
0 + ~X∗0X∗
i = X∗0 + ( ~X0X0)︸ ︷︷ ︸
−v
+ ~X0X∗i + ( ~XiX∗
i )︸ ︷︷ ︸v
= X∗0 + ~X0Xi also ist
~X0Xi = ~X∗0X∗
i
Wir werden also jedem Spat SP (X0, . . . , Xk) ein Element µ(Sp) ∈ K, genannt “Volumen”,
abhangig von den Kantenvektoren ui := ~X0Xi zuordnen:
SP (X0, . . . , Xk) → µ( ~u1, . . . , ~uk) ∈ K
39
1. durch c) erhalten wir aus der Forderung der Multilinearitat
2. durch die Forderung bzw. Festsetzung µ( ~u1, . . . , ~uk) = 0 fur ~v, . . . , ~vk l.a.
3. erhalten wir durch die Forderung V (~e1, . . . , ~ek) = 1 wobei ~e1, . . . , ~ek eine ON–Basis
des dem affinen Unterraum zugehorigen Vektorraumes U ist.
Diese Forderungen stimmen mit den Eigenschaften D1, D2, D3 einer Determinante uberein,
daher gilt nach Satz ??.
Satz 15.2 Volumsformel
B sei ein k−dimensionaler Unterraum eines affinen Raumes A.
X0, X1, . . . , Xk seien k+1 l.u. Punkte und {b1, b2, . . . , bk} eine Basis der Richtung von B.
˜X0Xi =: ui =∑k
j=1 uijbj. Die vij sind also die Komponenten der von einem Punkt x0
ausgehenden Kantenvektoren eines Spates. Dann gilt:
(i) Das Volumen V des k−Spates Sp(X0, X1, . . . , Xk) bezuglich der Basis {bi} ist gege-
ben durch die Determinanten der Koordinaten der Kantenvektoren:
V =
∣∣∣∣∣∣∣∣∣u11 . . . u1k
...
uk1 . . . ukk
∣∣∣∣∣∣∣∣∣(ii) Das Volumen µ des k−Simplex Si(X0, X1, . . . , Xk) bezuglich der Basis {bi} ist ge-
geben durch den k!−Teil der Determinante der Koordinaten der Kantenvektoren:
V =1k!
∣∣∣∣∣∣∣∣∣u11 . . . u1k
...
uk1 . . . ukk
∣∣∣∣∣∣∣∣∣Bemerkung: Der k−Spat kann in k! volumsgleiche k−Simplexe zerlegt werden: Das Par-
allelogramm (k = 2) in k! = 2! = 2 flachengleiche Teildreiecke, das Parallelogramm in
k! = 3! = 6 volumsgleiche Tetraeder.
40
16 Lineare Optimierung
Es werden die geometrischen Begriffsbildungen in abstrakten Vektorraumen (meistens ist
es der IRn, n auch sehr groß) auf Optimierungsfragen angewendet.
Bei einer Vielzahl wirtschaftlicher Entscheidungen steht das Optimieren bestimmter Großen
im Vordergrund.
Zu den Großen, bei denen ein Maximum angestrebt wird, gehoren: Gewinn, Umsatz, Fer-
tigungsmengen, Lebensdauer eines Produktes (mit Einschrankungen), Zahl der belieferten
Kunden.
Zu den Großen, bei denen ein Minimum angestrebt wird, gehoren: Kosten, Preis, Abfall-
menge, Transportwege, Energieverbrauch, Zahl der wartenden Kunden.
In dem folgenden Beispiel wird bewußt ein kleiner Ausschnitt aus der okonomischen Wirk-
lichkeit gewahlt. Auch bei zukunftigen Beispielen wird in dieser Einfuhrung zur Wahrung
der Ubersicht im Unterschied zur Praxis eine Reihe von Aspekten unberucksichtigt bleiben,
um die Beispiele “von Hand” berechenbar zu machen.
Man kann nun bestimmten okonomischen Vorgangen unter Vernachlassigung unwesent-
licher Sachverhalte ein vereinfachtes mathematisches System zuordnen. Ein solches in
der Linearen Optimierung angewandtes System von Gleichungen und Ungleichungen heißt
Modell, den Vorgang des Aufstellens der Gleichungen und Ungleichungen nennt man
Modellieren.
16.1 Geometrische Losung
Um den Sachverhalt in der Zeichenebene veranschaulichen zu konnen, erfolgt eine Be-
schrankung auf n = 2.
Beispiel: Maximumproblem im IR2 (aus KOHLER, Lineare Algebra)
In einem chemischen Betrieb werden aus drei Rohstoffen Ri(i = 1, 2, 3) zwei Fertigprodukte
Pk(k = 1, 2) hergestellt. In der Tabelle der Abbildung 1 sind fur beide Produkte die
Rohstoffanteile je Einheit der Fertigprodukte angebeben.
41
Rohstoffe/Fertigprodukte P1 (ME) P2 (ME)
R1 1,5 3,0
R2 2,5 2,0
R3 0 1Abbildung 1: Materialverbrauchsnormen fur die Produkte P1 und P2
Außerdem betragen die pro Zeiteinheit (ZE) verfugbaren Rohstoffmengen fur R1 210 ME,
fur R2 200 ME und fur R3 60 ME. Der Stuckgewinn betragt bei P1 3 DM und bei P2 4
DM.
Aufgabe
a) Bei welcher Stuckzahl von P1 bzw. P2 ist der Gewinn maximal?
b) Wie hoch ist der maximale Gewinn?
Losung: Fur gesuchte Großen werden Variable eingesetzt.
Die pro ZE hergestellten Stuckzahlen von P1 sei x1, die von P2 sei x2.
Die Tabelle in Abbildung 2 wird um die Spalte V der verfugbaren Rohstoffmenge und um
die Zeile G der Stuckgewinne erganzt zu Abbildung 2.
Verfugbare Mengen
Rohstoffe/Fertigprodukte P1 (ME) P2 (ME) V (ME)
R1 1,5 3,0 210
R2 2,5 2,0 200
R3 0 1 60
Gewinn G 3 4Abbildung 2: Erweiterung von Abb. 1 um die Kapazitatsbeschrankungen
Da fur 1 ME P1 1,5 ME des Rohstoffes R1 und fur 1 ME des Produktes P2 3 ME des
Rohstoffes R1 benotigt werden, sind fur x1 ME des Produktes P1 und x2 ME des Produktes
P2 1,5 x1 + 3x2 ME des Rohstoffes R1 erforderlich (das ist wieder die vereinfachende
Proportionalitatsannahme).
Da jedoch in der Zeiteinheit nur 210 ME des Rohstoffes R1 zur Verfugung stehen, gilt die
Relation
1, 5x + 3x2 ≤ 210 (8)
42
Entsprechend erhalt man fur die beiden ubrigen Rohstoffmengen
2, 5x1 + 2x2 ≤ 200
x2 ≤ 60(9)
Die Ungleichungen (8) und (9) nennt man einschrankende Bedingungen (Restrik-
tionen).
Außerdem durfen die Stuckzahlen nicht negativ sein:
x1 ≥ 0
x2 ≥ 0(10)
Die Ungleichung (10) stellt die sog. Nichtnegativitatsbedingung dar.
Da der Gewinn je ME des Produktes P1 3 DM, fur x1 ME des Produktes P1 somit 3x1
betragt und der Gewinn je ME des Produktes P2 4 DM, fur x2 ME des Produktes P2
somit 4x2 betragt (wieder die Proportionalitatsannahme), lautet die Funktionsgleichung
fur den Gesamtgewinn
G = 3x1 + 4x2 (11)
Die Gleichung (11) heißt Zielfunktion des Optimierungsproblems oder im hier vorliegen-
den Fall Gewinnfunktion. Zusammenfassend ergibt sich damit fur Beispiel (12) folgendes
mathematische Modell.
1. Restriktionen1, 5x1 + 3x2 ≤ 210
2, 5x1 + 2x2 ≤ 200
x2 ≤ 60
(12)
2. Zielfunktion
G = 3x1 + 4x2 → max (13)
3. Nichtnegativitatsbedingung
x1 ≥ 0
x2 ≥ 0(14)
Die Restriktionen (12) werden nun in einem zweidimensionalen Koordinatensystem darge-
stellt. Jede Ungleichung charakterisiert eine Halbebene. Die Schnittmenge der drei Halb-
ebenen ist zu ermitteln. Um die Halbebenen darzustellen, lost man die drei Ungleichun-
gen nach x2 auf und zeichnet die drei Berandungsgeraden, indem man die dazugehorigen
43
Abbildung 3
Gleichungen betrachtet. Anschließend kennzeichnet man die jeweiligen Halbebenen durch
Schraffur.
Da außerdem die Nichtnegativitatsbedingungen (14) gelten, kann die gesuchte Punkte-
menge, d.h. der Bereich, in dem die moglichen Kombinationen der Stuckzahlen x1 und
x2 liegen, nur im ersten Quadranten sein. Die Schnittmenge der durch die Ungleichungen
(12) und (14) dargestellten Punktmenge wird in Abbildung 3 geometrisch veranschau-
licht. Diejenige Punktmenge, die den Restriktionen und der Nichtnegativitatsbedingungen
genugt, wird als zulassiger Bereich bezeichnet. Denkbar als mogliche Stuckzahlen, die
die Restriktionen und die Nichtnegativitatsbedingung erfullen, waren z.B.
Q1(20, 30) und Q2(30, 40)
Geht man von dem Unternehmensziel der Gewinnmaximierung aus, dann sind somit die-
jenigen Stuckzahlen x1 und x2 zu bestimmen, fur die der Gewinn maximal wird.
Dazu betrachtet man zunachst alle Kombinationen der Stuckzahlen, bei denen der Gewinn
konstant ist. Bei konstantem G stellt Gleichung (13) eine Gerade un R2 dar.
44
Die Steigung dieser Geraden ermittelt man, indem man die Gleichung (13) nach x2 auflost.
x2 = −34x1 +
G
4(15)
Auf der Geraden mit der Gleichung (15) liegen alle Punkte, die als Mengenkombination
der Stuckzahlen x1 und x2 interpretiert, den gleichen Gewinn ergeben.
Mengenkombinationen bei gleichem Gewinn
Ist G = 40, so erhalt man auf (15) etwa folgende Kombinationen der Stuckzahlen:
x1 = 4, x2 = 7 bzw. x1 = 8, x2 = 4.
Die Gerade mit der Gleichung (15) heißt deshalb auch Isogewinngerade. Da alle Iso-
gewinngeraden die gleiche Steigung besitzen, verlaufen sie parallel zueinander. Der Or-
dinatenabschnitt der Geraden ist G4 . Der Gewinn wird somit um so hoher, je großer G
4
ist.
Die Isogewinngerade muß also moglichst weit vom Ursprung weg parallel verschoben wer-
den, jedoch so, daß sie mit dem schraffierten Bereich noch mindestens einen Punkt ge-
meinsam hat.
Fur G = 100(200, 300, 360) lauten die Isogewinngeraden
x2 = −34x1 + 25
x2 = −34x1 + 50
x2 = −34x1 + 75
x2 = −34x1 + 90
Diese Isogewinngeraden sind in Abbildung 4 eingezeichnet.
Die optimale Mengenkombination liegt im Punkt B(40, 50), d.h. bei Erzielung des maxi-
malen Gewinns mussen vom Produkt P1 40 Stuck und vom Produkt P2 50 Stuck herge-
stellt werden. Die genauen Werte fur die Stuckzahlen erhalt man durch Bestimmung des
Schnittpunktes der entsprechenden Geraden.
Den maximalen Gewinn ermittelt man, indem man die Stuckzahlen x1 = 40 ME und
x2 = 50 Me in Gleichung (13) einsetzt. Es ist Gmax = 3 [GE/ME]·40 ME +4 [GE/ME]·50
ME = 320 GE.
Da die Gerade mit G4 = 85 bzw. G = 340 keinen Punkt mit dem zulassigen Bereich
gemeinsam hat, scheiden die auf ihr liegenden Punkte fur die Mengenkombination aus.
45
Abbildung 4
Beispiel: Minimumproblem im R2
Fur ein Stuck Vieh seien folgende Mindestnahrungsrationen verbindlich:
3 Einheiten des Nahrstoffes A
6 Einheiten des Nahrstoffes B
2 Einheiten des Nahrstoffes C
Zur Verfugung stehen zwei Futtersorten S1 und S2. In 1 ME der Sorte S1 ist ME des
Nahrstoffes A und 1 ME des Nahrstoffes B enthalten. In 1 ME der Sorte S2 ist 0,5 ME
des Nahrstoffes A, 2 ME des Nahrstoffes B und 2 ME des Nahrstoffes C enthalten. Die
Kosten betragen fur die Sorte S1 2,5 GE/ME und fur die Sorte S2 3 GE/ME.
Aufgabe
(a) Wie muß das Futter gemischt werden, damit die angegebenen Nahrstoffe darin ent-
halten sind und die Gesamtkosten minimal werden?
b) Wie hoch sind die minimalen Kosten?
Losung
46
Die Angaben werden in der Tabelle der Abbildung 5 ubersichtlich dargestellt.
Nahrstoff/Futtersorte S1 S2 Mindestmengen in ME
A 1 0,5 3
B 1 2 6
C 0 2 2
Kosten 2,5 3Abbildung 5: Zusammensetzung der beiden Futtersorten
Es werden x1 ME der Sorten S1 mit x2 ME der Sorten S2 gemischt.
Aus der Abbildung 5 entnimmt man folgendes mathematisches Modell:
1. Restriktionenx1 + 0, 5 ≥ 3
x1 + 2x2 ≥ 6
2x2 ≥ 2
(16)
2. Zielfunktion
K = 2, 5x1 + 3x2 → min (17)
3. Nichtnegativitatsbedingung
x1 ≥ 0
x2 ≥ 0(18)
Die durch die Ungleichungen (16) und (18) dargestellten Halbebenen werden in einem
zweidimensionalen Koordinatensystem geometrisch veranschaulicht.
Die Schnittmenge der entsprechenden Halbebenen ist nicht beschrankt. Der Graph der
Zielfunktion stellt bei konstantem K eine Gerade dar, die Isokostengerade.
Alle Isokostengeraden besitzen die gleiche Steigung. Man erhalt die Steigung aller paralleler
Isokostengeraden, indem man Gleichung (17) nach x2 auflost.
x2 −2,53 x1 + K
3
= −56x1 + K
3
(19)
Die Steigung aller Isokostengeraden betragt m = −56 . In Abbildung 6 sind vier Isokosten-
geraden dargestellt.
(K = 3,K = 6,K = 11,K = 15)
47
Abbildung 6: Isokostengeraden
Eine optimale (minimale) Losung ergibt sich fur diejenigen Wertepaare (x1, x2) der Punk-
te, die auf einer Isokostengeraden liegen, deren Ordinatenabschnitt minimal ist. Die Iso-
kostengerade muß somit parallel verschoben werden, und zwar moglichst dicht an den
Ursprung heran, jedoch so, daß sie noch mindestens einen Punkt mit dem zulassigen Be-
reich gemeinsam hat. Der Punkt B(2,2) gibt das Optimum an. Auf der Isokostengeraden
mit K=3 bzw. K=6 liegt kein Punkt des zulassigen Bereiches.
Antwort auf
a) Von Sorte S1 und S2 sind je 2 ME zu mischen.
b) Minimale Kosten: K=2,5 [GE/ME]· 2ME+3[GE/ME]· 2ME=11GE
Man sieht schon an diesen beiden Beispielen, wie geometrische Grundbegriffe und Vorstel-
lungen benutzt werden (zulassige Bereiche, Halbebenen, beschrankt und nicht beschrankt,
Schnittmengen). Unsere Verallgemeinerungen gestatten es, dasselbe Verfahren auch in
hoher–dimensionalen Vektorraumen anzuwenden.
48
16.2 Geometrische Eigenschaften der zulassigen Menge Z
Restriktionen in Ungleichungsform konnen durch Einfuhrung von Schlupfvariablen auf
Gleichungsform gebracht werden. Man erhalt so i.a. m Gleichungen in n Unbekannten.
Durch Weglassen von uberflussigen (= l.a.) Gleichungen kann man erreichen, daß die
Koeffizientenmatrix dieses LGS vollen Zeilenrang hat.
Standardproblem der linearen Optimierung
K sei ein geordneter Korper. Gegeben seien eine (m× n)−Matrix A ∈ Km·n mit
Rg(A) = m, ein Vektor ~b ∈ Km mit ~b ≥ ~0. Mit dem Vektor ~lt = (l1, l2, . . . , ln) ∈ Kn werde
die lineare Funktion (Linearform) L : Kn → K mit
L(~x) := ~lt~x =n∑
i=1
lixi
gebildet. L(~x) heißt Zielfunktion.
Gesucht ist das Minimum Lmin der Zielfunktion L : Kn → K auf der zulassigen Menge
Z :={~x|A~x = ~b und ~x ≥ 0
}und jene Stellen ~x ∈ Z, an denen dieses Minimum angenommen wird, d.h., die Teilmenge
Mmin := {~x|~x ∈ Z und L(~x) = Lmin} ⊂ Z
der zulassigen Minimalpunkte von Z.
Das Problem ist losbar, wenn Mmin 6= 0.
Will man unter den gleichen Bedingungen das Maximum Lmax von L bestimmen, dann
ist dies gleichwertig mit der Bestimmung des Minimums von −L :
Lmax = (−L)min
~b ≥ 0 kann durch eventuelle Multiplikation mit (−1) stets erreicht werden.
Z ist eine konvexe Teilmenge des Kn. Ist Z 6= ∅, dann besitzt Z auch Ecken, aber es sind
hochstens endlich viele. Das soll die Hauptaussage der folgenden Uberlegungen sein. Dazu
49
schreiben wir das LGS A~x = ~b folgend um: ~x = (x1, x2, . . . , xn) ∈ Kn, A ∈ Km·n.
A~x = ~b ⇔ x1 ·
a11
a21
...
am1
︸ ︷︷ ︸
~s1
+ . . . + xn ·
a1n
a2n
...
amn
︸ ︷︷ ︸
~sn
=
b1
b2
...
bm
⇔ x1 · ~s1 + . . . + xn · ~sn = ~b
also A = (~s1, ~s2, . . . , ~sn).
Der i−te Spaltenvektor ~si von A heißt der zur i−ten Koordinate xi von x gehorige
Spaltenvektor.
Ein zulassiger Punkt ~x ∈ Z hat wegen ~x ≥ 0 keine negativen Koordinaten. Die Ecken in
Z kann man folgend charakterisieren:
Satz 16.1 Charakterisierung von Ecken
Ein Punkt ~x ∈ Z ist genau dann eine Ecke von Z, wenn die zu den positiven (> 0)
Koordinaten gehorigen Spaltenvektoren von A l.u. sind.
Beweis:
1. ⇒: Sei ~c eine Ecke von Z = {~x|A~x = ~b ∧ ~x ≥ 0}. Die Anzahl der positiven Koordi-
naten von ~c sei p.
1. Fall: p = 0, d.h., alle Koordinaten sind 0 ⇒ ~c = ~0 (also ~b = ~0). Die Menge der
zugehorigen Spaltenvektoren ist leer, eine leere Menge ist definitionsgemaß l.u.
2. Fall: p > 0. Durch Umnumerierung kann man erreichen, daß die ersten p Ko-
ordinaten von ~c positiv sind, die Spaltenvektoren von A werden gleichartig
umgeordnet:
~c = (c1, c2, . . . , cp, 0, . . . , 0), A = (~s1, . . . , ~sp, ~sp+1, . . . , ~sn)
~b = A~c = (~s1, . . . ~sp, . . . ~sn) · (c1, . . . , cp, 0, . . . , 0)t = c1 ~s1 + . . . + cp ~sp =∑p
i=1 ci~si
Angenommen, {~s1, . . . , ~sp} waren l.a. ⇒ ∃λ1, . . . , λp, nicht alle 0 mit∑pi=1 λi~si = ~0 ⇒
∑pi=1(ci ~sp + δλi)~si = ~b∀δ ∈ K, d.h. die Punkte ~x1 und ~x2 mit
50
geeignetem δ0 > 0 (so daß c1 − δ0λ1 > 9).
~x1 =
c1 + δ0λ1
...
cp + δ0λp
0...
0
> ~0 und ~x2 =
c1 − δ0λ1
...
cp − δ0λp
0...
0
> ~0
sind verschiedene Elemente von Z und ~c = 12 ~x1 + 1
2 ~x2, d.h., ~c ist keine Ecke im
Widerspruch zur Annahme.
Die zu positiven Koordinaten von Ecken gehorigen Spaltenvektoren mussen l.u.
sein.
2. ⇐: Sei ~x ∈ Z mit p positiven Koordinaten, o.B.d.A. sei ~x = (x1, x2, . . . , xp, 0, . . . , 0)
und {~s1, . . . , ~sp} l.u. Spaltenvektoren von A.
1. Fall: p = 0 ⇒ ~x = ~0. Ware ~x keine Ecke ⇒ ~x ist echte Konvexkombination von
zwei verschiedenen ~x1, ~x2 ∈ Z :
~x = λ1 ~x1 + λ2 ~x2 mit λ1, λ2 > 0, λ1 + λ2 = 1
Wegen ~x1 ≥ 0, ~x2 ≥ 0 folgt, daß ~x1 = ~0, ~x2 = ~0, Widerspruch.
2. Fall: p > 0. Ware ~x keine Ecke ⇒ ~x = λ1~a + λ2~c mit
λ1, λ2 > 0, λ1 + λ2 = 1,~a,~c ≥ 0 und ~a 6= ~c, also
x1
...
xp
0...
0
= λ1
≥ 0
a1
...
ap
ap+1
...
an
≥0
+λ2
≥ 0·
c1
...
cp
cp+1
...
cn
≥0
⇒ap+1 = . . . = an = 0 und
cp+1 = . . . = cn = 0
Wegen A · ~a = ~b und A · ~c = ~c gilt auch A · (~a− ~c) = ~0, also wegen
A = (~s1, . . . , ~sp, . . . , ~sn):
(a1 − c1) · ~s1 + . . . + (ap − cp) · ~sp + 0 · ~sp+1 + . . . + 0 · ~sn = ~0.
51
Nun sind ~s1, . . . , ~spl.u. ⇒ a1− c1 = 0, . . . , ap− cp = 0 ⇒ a1 = c1, . . . , ap = cp ⇒
~a = ~b (Widerspruch).
Daher ist ~x eine Ecke, wenn die zu positiven Koordinaten gehorigen Spalten-
vektoren l.u. sind.
Beim Standardproblem ist Rg(A) = m = dim < ~s1, . . . , ~sn >, d.h., m ist auch die Maxi-
malanzahl l.u. Spaltenvektoren von A. Daher gilt:
Bemerkung:
Unter den Voraussetzungen des Standardproblems (insbesondere Rg(A) = m und ~b ≥ 0)
hat jede Ecke der zulassigen Menge Z hochstens m positive Koordinaten. Damit kann
man definieren:
Definition 16.1 Entartete und nichtentartete Ecken
(i) Eine Ecke der zulassigen Menge Z heißt entartet, wenn sie weniger als m positive
Koordinaten besitzt.
(ii) Eine Ecke der zulassigen Menge Z heißt nicht entartet, wenn sie genau m positive
Koordinaten besitzt. Dabei ist m = Rg(A).
Beispiel 1:
A =
2 −1 1 0 0
1 −1 0 1 0
1 1 0 0 1
,~b =
2
2
5
P sei das Bild der zulassigen Menge von
2 −1
1 −1
1 1
1 1
·(
x1
x2
)≤
2
2
5
,
(x1
x2
)≥ ~0,
nicht aber die zulassige Menge Z von A~x = ~b, ~x ≥ 0. Diese ist eine Teilmenge vom K5,
wegen rg(A) = 3 und n−Rg(A) = 5− 3 = 2 ist Z aber in einer affinen Ebene ε vom K5
52
enthalten. Eine Parameterdarstellung von ε ist z.B. gegeben durch
ε : ~x =
72
32
−72
0
0
+ λ1
−1
−1
1
0
2
+ λ2
−1
1
3
2
0
λ1 = 1, λ2 = 1 liefert ~xt =
(32 , 3
2 , 12 , 2, 2
)∈ ZZ aber die zugehorigen Spaltenvektoren
{~s1, ~s2, ~s3, ~s4, ~s5} sind l.a., also ist ~x keine Ecke von Z.
λ1 = 3, λ2 = 5 liefert ~x = (−92 , . . .) 6∈ Z.
Wie kann man Z beschreiben? Z ist ja nur eine konvexe Teilmenge von ε !
Wie erhalt man die Ecken von Z?
Wegen Rg(A) = 3 und n = 2 hat man 2 freie Variable, wir nehmen dafur die Nicht–
Schlupf–Variablen. Jeder Punkt
(x1|x2) ∈ P (die Koordinaten sind also gerade die Nicht-Schlupfvariablen) liefert mit den
Parametern t1 := x1, t2 := x2 einen Punkt (x1, x2, . . . , x5)t ∈ Z, namlich
(∗)
x1 = t1
x2 = t2
x3 = 2− 2t1 + t2
x4 = 2− t1 + t2
x5 = 5− t1 − t2
⇔ Z : ~x =
0
0
2
2
5
+ t1
1
0
−2
−1
1
+ t2
0
1
1
1
−1
, (t1, t2) ∈ P
z.B.: Fur (t1, t2) = (1, 1) ∈ P erhalt man
~x = (1, 1, 1, 2, 3) ≥ 0 und A~x = ~b, also ~x ∈ Z.
Wegen Satz 16.2 ist aber ~x auch keine Ecke von Z.
Die Ecken von Z erhalt man, wenn man fur die Parameter (t1, t2) gerade die
Ecken des “Parameterpolygons” P wahlt.
Die Ecken von P erhalt man durch alle moglichen Schnitte der das Polynom P begren-
zenden Geraden (= Hyperebenen im K2):
53
Polygonecken: (0, 0), (1, 0), (73 , 8
3), (0, 5)
↓ ↓ ↓ ↓
Ecken von Z : ~p1 =
0
0
2
2
5
~p2 =
1
0
0
1
4
~p3 =
73
83
073
0
~p4 =
0
5
7
7
0
↓ ↓ ↓ ↓
Test auf Ecken: {s2, s4, s5}, {s1, s4, s5}, {s1, s2, s3}, {s2, s3, s4} l.u. ?
(RowReduce) ja ja ja ja
{~p1, ~p2, ~p3, ~p4} sind nichtentartete Ecken von Z (wegen Rg(A) = 3).
Die Darstellung (*) zeigt, daß Z eine 2−parametrige Punkteschar enthalt und beschrankt
ist. Wegen (t1, t2) ∈ P , einem beschrankten Viereck, enthalt Z namlich keinen Strahl.
zu Beispiel 2: 1 −2 1 0 0
−2 1 0 1 0
1 1 0 0 −1
,~b =
2
2
1
Polygonecken: (1, 0), (2, 0), (0, 1), (0, 2)
↓ ↓ ↓ ↓
~p1 =
1
0
1
4
0
~p2 =
2
0
0
6
1
~p3 =
0
1
4
1
0
~p4 =
0
2
6
0
1
↓ ↓ ↓ ↓
Test auf Ecken: {s1, s3, s4}, {s1, s4, s5}, {s2, s3, s4}, {s2, s3, s5} l.u.?
ja ja ja ja
⇒ {~p1, ~p2, ~p3, ~p4} sind nichtentartete Ecken von Z.
Beispiel 3:
A ∈ Km·n, Rg(A) = m ≥ 1, Z = {~x|A~x = ~0 und ~x ≥ 0}, Dann ist ~x = ~0 eine entartete Ecke
54
von Z. (~0 ist nicht Konvexkombination von nichtnegativen Zahlen, ~0 hat keine positiven
Koordinaten).
Um die Eckenanzahl in der zulassigen Mengen Z abschatzen zu konnen, benotigt man den
Begriff der “Basis einer Ecke ~p ∈ Z”.
Sei Rg(A) = m.
~p
nichtentartet: ∃ genau m positive Koordinaten ⇒ die zugehorigen Spaltenvektoren
bilden eine Basis vom Spaltenraum
= Km
entartet: ∃p < m positive Koordinaten ⇒ die p l.u. zugehorigen Spalten–
vektoren lassen sich (i.a. auf
mehrere Arten) zu einer Basis von
Km erganzen
Definition 16.2 Basis einer Ecke
~p sei eine Ecke der zulassigen Menge Z = {~x|A~x = ~b ≥ 0, ~x ≥ 0} mit Rg(A) = m.
Eine Basis B~p der Ecke ~p ist eine Menge von m l.u. Spaltenvektoren von A, welche die zu
positiven Koordinaten von ~p gehorigen Spaltenvektoren von A umfaßt. Die zu den Vektoren
einer Basis B~p gehorigen Unbekannten des LGS A~x = b heißen Basisvariable (BV) von
~x zur Basis B~b, die ubrigen Unbekannten heißen Nichtbasisvariable (NBV) von ~x.
Bemerkungen
1. Nach dem Basiserganzungssatz ist einer nichtentarteten Ecke eindeutig eine Basis
vom Km zugeordnet, einer entarteten Ecke dagegen mehrere.
2. Jede Basis einer Ecke ist auch eine Basis vom Km.
Es gilt nun der wichtige
Satz 16.2 Endlichkeit der Eckenanzahl
Die zulassige Menge Z = {~x ∈ Kn|A~x = ~b ≥ 0 und ~x ≥ 0} mit Rg(A) = m besitzt
mindestens eine und hochstens endlich viele Ecken.
Beweis fur die Existenz hochstens endlich vieler Ecken: Idee: Man zeigt, daß man jeder
l.u. Menge von m Spaltenvektoren von A hochstens eine (d.h. auch keine) Ecke zuordnen
kann.
55
Damit gilt dann: Anzahl der Ecken ≤(
nm
), weil man aus n Elementen auf
(nm
)Arten m
Elemente herausgreifen kann (es kommt auf die Reihenfolge nicht an).
Sei ~p ∈ Z eine Ecke ⇔ die zu positiven Koordinaten gehorigen Spaltenvektoren von A
sind l.u.
Sei { ~sk1 , ~sk2 , . . . , ~skm} eine Menge von m l.u. Spaltenvektoren von A. Dann hat das LGS
sk1 · ~sk1 + . . . + xkm · ~skm = ~b−n∑
i=m+1
xki· ~ski
(20)
in den m Unbekannten xk1 , . . . , xkm fur jede Wahl von xkm+1 , . . . , xkn , also auch fur
xkm+1 = . . . = xkn = 0
eine eindeutige Losung (Rg( ~sk1 , . . . , ~skm) = m = ] Unbekannten).
Sei xk1 = l1, . . . , xkm = lm.
Dann ist der Punkt ~p = (p1, p2, . . . , pn) mit
pki=
lkii = 1, . . . ,m
0 i = m + 1, . . . , n
eine Losung von A~x = ~b.
Sind alle lki≥ 0, dann ist ~p eine Ecke von Z (denn die zu lki
gehorigen Spaltenvektoren
~sk1 , . . . , ~skm sind nach Voraussetzung l.u.). Ist aber mindestens ein lki< 0, dann ist ~p 6∈ Z.
Der Vorgang:
(i) Wahle aus den n Spaltenvektoren von A m l.u. aus
(ii) Lose damit das LGS (20)
liefert also hochstens eine Ecke.
Durch diesen Vorgang werden aber auch alle Ecken von Z erfaßt (unter Umstanden hat
man nur zu viel gerechnet):
Sei ~p ∈ Z eine Ecke mit p ≤ m positiven Koordinaten xk1 , . . . , xkp (mehr als m kann es nach
Satz 16.2 nicht geben!). Dann sind die zugeordneten Spaltenvektoren von A: ~sk1 , . . . , ~skp
nach Satz 16.1. Nach dem Basiserganzungssatz kann man diese l.u. Menge von Vektoren
aus Km zu einer Basis von Km erganzen: Km =< ~sk1 , . . . , ~skp , . . . , ~skm >.
Geht man von dieser Basis aus, erhalt man mittels des obigen Vorganges gerade das
56
vorgegebene ~p (ganz egal, wie man zu einer Basis erganzt hat, denn wegen Rg(A) = m =
] Unbekannten ist (20) eindeutig losbar).
Der Beweis liefert auch die Methode, wie man alle Ecken von Z erhalt. Allerdings wachst(nm
)fur große n, m explosionsartig (= exponentiell) an.
Beispiel:
Berechne alle Ecken von Beispiel 1 (ohne Parameterpolygon P )
Rg(A) = 3, n = 5 ⇒ ∃ hochstens(
nm
)=
(53
)=
(53
)= 5·4
1·2 = 10 Moglichkeiten, um aus den
5 Spaltenvektoren eine Menge von 3 l.u. auszuwahlen.
(k1, k2, k3) l.u. NBV BV Ecke entartet
(1, 2, 3) ja x4 = 0, x5 = 0 (72 , 3
2 ,−72) nein
(1, 2, 4) ja x3 = 0, x5 = 0 (73 , 8
3 ,−73) (7
3 , 83 , 0, 7
3 , 0) nein
(1, 2, 5) ja (0,−2, 7) nein
(1, 3, 4) ja (5,−8,−3) nein
(1, 3, 5) ja (2,−2, 3) nein
(1, 4, 5) ja (1, 1, 4) (1, 0, 0, 1, 4) nein
(2, 3, 4) ja x1 = 0, x5 = 0 (5, 7, 7) (0, 5, 7, 7, 0) nein
(2, 3, 5) ja x1 = 0, x4 = 0 (−2, 0, 7) nein
(2, 4, 5) ja x1 = 0, x5 = 0 (−2, 0, 7) nein
(3, 4, 5) ja x1 = 0, x2 = 0 (2, 2, 5) (0, 0, 2, 2, 5) nein
Eingabe: s1, . . . , sn so, daß A = {s1, . . . , sn}, b;
Auswahl (k1, k2, k3)
aa = {sk1 , sk2 , sk3} ar = {sk4 , sk5}
RowReduce [aa]
Linear Solve [aa, b] gibt Werte der Basisvariablen.
Fur beschrankte zulassige Mengen Z gilt daruber hinaus:
Satz 16.3 Beschreibung zulassiger Mengen
Eine beschrankte zulassige Menge ist die konvexe Hulle ihrer (endlich vielen) Ecken.
Beweis:
Z besitzt mindestens eine und hochstens endlich viele Ecken. Da Z konvex ist, enthalt Z
57
jede Konvexkombination dieser Ecken. Wir mussen noch zeigen, daß durch Konvexkom-
binationen der Ecken auch jedes Element ~x ∈ Z erfaßt wird:
Sei Rg(A) = m = n : Wegen Z 6= ∅ hat A~x = ~b genau eine Losung ~x0 ≥ 0 ⇒ Z = { ~x0}
und ~x0 ist Konvexkombination von ~x0, namlich ~x0 = 1 · ~x0.
Sei Rg(A) = m < n :
Sei b = 0 : Dann ist die Losungsmenge LH von A~x = ~0 ein (n − m)−dimensionaler
Teilraum von Kn, d.h., mit einem ~x0 > ~0 liegen auch alle positiven Vielfache λ ~x0 ∈ LH ,
dann ware aber Z im Gegensatz zur Annahme unbeschrankt. Es kann in Z also kein
positives ~x0 > 0 geben ⇒ Z = {~0} und ~0 = 1 ·~0 ist Konvexkombination von ~0.
Sei b 6= 0 : Dann ist ~0 6∈ Z ⇒ jedes ~x ∈ Z hat mindestens eine positive Komponente. Sei
~x0 = (x1, . . . , xn)t ∈ Z mit p ≥ 1 positiven Komponenten, P sei die Menge jener Indices
i mit xi > 0, also P := {i|xi > 0} und S := {~si|i ∈ P} sei die Menge der dazugehorigen
Spaltenvektoren von A.
1. Fall: Sei S l.u. ⇒ nach 6.1 ist ~x0 eine Ecke und damit eine Konvexkombination der
Ecken von Z, namlich ~x0 = 1 · ~x0 +0 · ~x1 + . . .+0 · ~xm, wobei ~xi(i = 0, . . . ,m) Ecken
von Z sind.
2. Fall: Sei S l.a. ⇒ ∃λi ∈ K, nicht alle 0, mit∑i∈P
λi~si = ~0. (21)
Davon ist mindestens ein λi > 0, sonst multipliziert man (21) mit (−1). IP sei die Index-
menge der positiven λi, IN sei die Indexmenge der negativen λi, also
IN := {i|λi < 0} ⊂ P, IP := {i|λi > 0} ⊂ P
Es ist IP 6= ∅, aber auch IN 6= ∅:
Fur jedes t ∈ K sind namlich die Punkte
~y(t) := (y1, . . . , yn) mit yi =
xi + tλi fur i ∈ P
0 fur i 6∈ P(22)
Losungen von A~x = ~b (wegen (21)):
A~y(t) = A ~x0 + t ·∑i∈P
λi~si + t · 0 ·∑j 6∈P
λj ~sj = ~b + t ·~0 +~0 = ~b.
58
Waren nun alle λi ≥ 0 ⇒ alle ~y(t) ≥ 0 ⇒ alle ~y(t) ∈ Z ⇒ Z ist unbeschrankt im
Widerspruch zur Beschranktheit. Also gilt es in (21) mindestens ein negatives λi.
Es gilt nun folgender Hilfssatz.
Jeder Punkt ~x0 ∈ Z mit r ≥ 1 positiven Koordinaten ist Konvexkombination zweier
verschiedener Punkte von Z mit je hochstens r − 1 positiven Koordinaten.
Da jeder Punkt aus Z hochstens n positive Koordinaten hat, kommt man mit diesem
Hilfssatz nach endlich vielen Schritten auf folgende Situation:
~x0 mit n ≥ r ≥ 1 positiven Koordinaten ist Konvexkombination von Punkten ~yi ∈ Z mit
hochstens r−1 positiven Koordinaten, jedes ~yi ∈ Z ist wiederum Konvexkombination von
Punkten ~zi mit hochstens r−2 positiven Koordinaten usw. Letztlich ist ~x0 Konvexkombi-
nation von Punkten mit genau einer positiven Koordinate. Solche sind aber stets Ecken,
denn:
Hat ~x0 genau eine positive Koordinate xp ⇒ S = {~sp}. Da A eine Nullspalte enthalt, ist
{~sp} l.u. ⇒ ~x0 ist eine Ecke.
~x0 ist also letztlich Konvexkombination von Ecken von Z. Damit ist auch der 2. Fall
abgehandelt.
Beweis des Hilfssatzes:
Mit den Indizes aus IP und IN und den Koordinaten xi von ~x0 bilden wir die Skalare
t1 := −mini∈IP
xi
λi=:
−xp
λp< 0 und t2 := min
i∈IN
xi
|λi|=
xq
−λq> 0
Damit gilt fur alle i ∈ IP und t ≥ t1 : xi + tλi ≥ 0 und fur alle i ∈ IN und t ≤ t2 :
xi + tλi ≥ 0. Fur t mit t1 ≤ t ≤ t2 gilt damit fur alle i ∈ P : xi + tλi ≥ 0, also ~y(t) ∈ Z.
Fur t = t1 = −xp
λpgilt fur die p−te Koordinate von ~y(t1) nach (22):
yp = xp + t1λp = xp−xp
λp· λp = 0
Fur t = t2 = xq
−λqgilt fur die q−te Koordinate von ~y(t2):
yq = xq + t2λq = xq −xq
λpλp = 0.
Die Punkte ~y(t1) ∈ Z und ~y(t2) ∈ Z sind also verschieden und haben hochstens r − 1
positive Koordinaten, denn yp = 0 bzw. yq = 0.
59
Jedes t mit t1 ≤ t ≤ t2 kann man nur schreiben als t = l1t1 + l2t2 mit l1, l2,≥ 0 und
l1 + l2 = 1. Damit ist
~y(t) = l1~y(t1) + l2~y(t2)∀t : t1 ≤ t ≤ t2
Weil t1 < 0 und t2 > 0 gilt dies insbesondere fur t = 0:
~y(0) = (x1, . . . , xn) = ~x0
Also ist ~x0 Konvexkombination von 2 Punkten ~y1(t1), ~y2(t2) ∈ Z mit hochstens r − 1
positiven Koordinaten.
Zusammenfassung:
Sei A ∈ Km·n,~b ∈ Km,~b ≥ 0 und Rg(A) = m.
Die zulassige Menge Z = {~x|A~x = ~b und ~x ≥ 0}.
(i) kann beschrankt oder nicht beschrankt sein
(ii) ist stets konvex
(iii) hat mindestens eine und hochstens endlich viele Ecken
(iv) ist die konvexe Hulle ihrer Ecken, falls sie beschrankt ist.
60
16.3 Hauptsatz der linearen Optimierung
Um einen anschaulichen Uberblick uber Losungsmoglichkeiten von linearen Optimierungs-
aufgaben zu erhalten, geben wir in den beiden nachsten Beispielen die Restriktionen in 2
Variablen wieder in Ungleichungsform an.
Beispiel:
Gegeben sei das in Beispiel 1 in Standardform behandelte lineare Ungleichungssystem
2x1 −x2 ≤ 2
x1 −x2 ≤ 2
x1 +x2 ≤ 5
x1 ≥ 0
x2 ≥ 0
undc := L1(~x) := −x1 + x2
c := L2(~x) := 2x1 + x2
Gesucht ist jeweils das Minimum von L1 und L2 auf der zulassigen Menge Z und jene
Stellen, in denen dieser Minimalwert angenommen wird.
Losung: Das Bild von Z ist in Beispiel 1 durch die Menge P gegeben. Um den Minimalwert
von L1 geometrisch zu erhalten, gehen wir nach dem in 6.1 Gesagten folgend vor:
(i) Setze L1(~x) gleich einer Konstanten c. Dies ergibt die Geradenschar
−x1 + x2 − c = 0.
(ii) Ermittle aus dieser Geradenschar jene Gerade, die bei kleinstmoglichem c mit Z
mindestens einen Punkt gemeinsam hat.
Dies kann dadurch erfolgen, daß man eine Gerade aus der Schar, am zweckmaßigsten
die mit c = 0, so parallel verschiebt, daß der Abschnitt auf der x2−Achse moglichst
klein wird.
Man erhalt L1 min = −1 in genau einem Punkt ~xmin = (1/0) (siehe Abb. 1) L2 min = −2,
angenommen in allen Punkten der Verbindungsstrecke von (1/0) zu (73 |
83) (siehe Abb.
2).
61
Abb. 1 Abb. 2
Beispiel 4:
Gegeben sei das in Beispiel 2 in Standardform behandelte lineare Ungleichungssystem:
x1 −2x2 ≤ 2
−2x1 +x2 ≤ 2
x1 +x2 ≥ 1
x1 ≥ 0
x2 ≥ 0
Die zulassige Menge Z ist unbeschrankt.
Bestimme die Minima und die zulassigen Minimalpunkte fur die folgenden Zielfunktionen:
a) L1(~x) := −x1 + x2 b) L2(~x) := −x1 + 4x2
c) L3(~x) := −x1 + x2 d) L4(~x) := −x1 + 2x2
Aus den folgenden Abb. 3 – Abb. 6 entnimmt man folgendes Losungsverhalten:
Abb. 3 Abb. 4
62
Abb. 5 Abb. 6
Abbildung 7
63
a) Abb. 3: Es existiert kein zulassiger Minimalpunkt und damit kein Minimum von L1
auf Z.
b) Abb. 4: Es gibt genau einen Minimalpunkt (2/0), mit L2 min = L2(2/0) = −2.
c) Abb. 5: Es gibt unendlich viele zulassige Minimalpunkte, namlich die Punkte auf
der Verbindungsstrecke der Ecken P1(1|0) und P2(0|1) und
L2 min = L3(1, 0) = . . . = L3(0|1) = 1.
d) Abb. 6: Es gibt unendlich viele zulassige Minimalpunkte, die alle auf dem von der
Ecke P (2|0) ausgehenden Strahl in Richtung ~u = (2, 1) liegen.
L4 min = L2(2|0) = . . . = −2.
Zusammenfassung der Beobachtungen:
(i) Ein lineares Optimierungsproblem kann unlosbar sein. Dies ist trivialerweise der
Fall, wenn die zulassige Menge leer ist. Aber auch bei nichtleerer zulassiger Men-
ge muß kein zulassiger Minimalpunkt existieren. Dies kann jedoch nur bei unbe-
schrankter zulassiger Menge auftreten (Abb. 3).
(ii) Falls ein Minimum der Zielfunktion existiert, kann es dazu genau einen (Abb. 1,
Abb. 4) aber auch unendlich viele zulassige Minimalpunkte geben. Immer wird
jedoch das Minimum auch in einer Ecke angenommen (minimale Ecke). Die Ver-
bindungsstrecke von zwei zulassigen Minimalpunkten enthalt ebenfalls nur zulassige
Minimalpunkte.
In den beiden folgenden Satzen werden diese Beobachtungen allgemein abgesichert.
Satz 16.4 Konvexkombination
Jede Konvexkombination endlich vieler zulassiger Minimalpunkte ist wieder ein zulassiger
Minimalpunkt.
H( ~x1, . . . , ~xr) ⊂ Mmin fur ~x1, . . . , ~xr ∈ Mmin.
Beweis: ~xi zulassiger Minimalpunkt ⇒ A~xi = ~b, ~xi ≥ 0 und
L(~xi) = m := min~x∈Z L(~x).
64
Sei ~x Konvexkombination von ~x1, . . . , ~xr ⇒
~x =r∑
i=1
λi ~xi mit λi ≥ 0 undr∑
i=1
λi = 1.
(i) A~x = A(∑
i λi ~xi) =∑
i λiA~xi =∑
i(λi~b) = (
∑·λi)~b = 1~b = ~b
(ii) ~x =∑
λi ~xi ≥ 0
(iii) L(~x) = L(∑
i λi ~xi) =∑
i λiL(~xi) =∑
i λic = c(∑
i λi) = c · 1 = c
(i)–(iii) zeigen, daß ~x wieder ein zulassiger Minimalpunkt ist.
Die vorhergehenden Bilder zeigen, daß das Minimum stets auch in einem Eckpunkt der
zulassigen Menge angenommen wird. Dies gilt tatsachlich auch allgemein:
Satz 16.5 Hauptsatz der linearen Optimierung.
Falls das lineare Optimierungsproblem losbar ist, wird das Minimum stets auch in min-
destens einer Ecke der zulassigen Menge angenommen.
Kurz: Es existiert eine minimale Ecke.
Voraussetzung: A ∈ Kmin, Rg(A) = m,~0 ≤ ~b ∈ Km,~l ∈ Kn
Z = {~x|A~x = b ∧ ~x ≥ 0}, L(~x) := ~lt · ~x
m := min~x∈Z L(~x),Mmin := {~x|~x ∈ Z ∧ L(~x) = m}.
Behauptung: Ist Mmin 6= ∅, dann enthalt Mmin mindestens eine Ecke von Z.
Beweis: Aus Mmin 6= ∅ ⇒ ∃ ~x0 ∈ Z : L( ~x0) = m.
Angenommen, dieses ~x0 := (x1, . . . , xn) besitze p ≥ 0 positive Koordinaten. P sei die
Indexmenge der positiven Koordinaten: P := {i|x0i > 0}. S sei die Menge der zu diesen
positiven Koordinaten gehorigen Spaltenvektoren von A : S : {~xi|i ∈ P}.
Ist p = 0, dann ist ~x0 = ~0 und daher eine Ecke:
~0 kann nicht echte Konvexkombination zweier verschiedener, nichtnegativer Punkte ~x1, ~x2
sein: Aus ~0 = λ1 ~x1 + λ2 ~x2 mit λ1, λ2 > 0 und λ1 + λ2 = 1 folgt ~x1 = ~x2 = ~0.
Ist p > 0, dann unterscheiden wir 2 Falle:
1. Fall: S l.u. ⇒ ~x0 ist nach Satz 16.1 eine Ecke.
65
2. Fall: S la. ⇒ ∃ eine nichttriviale Linearkombination der Spaltenvektoren
~si(i ∈ P ), die den Nullvektor ergibt:∑i∈P
ki~si = ~0 (23)
Mindestens einer der Skalare ki ist positiv, sonst multipliziert man (23) einfach mit (−1).
IP sei die Indexmenge der positiven, IN die Indexmenge der negativen Skalare in (23).
∅ 6= IP := {i|ki > 0} ⊂ P, IN := {j|kj < 0} ⊂ P
Vom zulassigen Minimalpunkt ~x0 = (x01, . . . , x
0n) mit p positiven Koordinaten ausgehend,
konstruieren wir uns einen weiteren zulassigen Minimalpunkt, aber mit hochstens p − 1
positiven Koordinaten:
Fur jedes δ ∈ K konstruieren wir mit ~x0 die Punkte ~x1(δ) und ~x2(δ) mit folgenden
Koordinaten:
~x1(δ) :=
x0i − δki i ∈ P
0 i 6∈ Pund ~x2(δ) :=
x0i + δki i ∈ P
0 i 6∈ P(24)
(i) x1(δ), x2(δ) erfullen das LGS Ax = b (weil auch A ~x0 = ~b)
A ~x1(δ) =∑
i∈P (x0i − δki) · ~si =
∑i∈P x0
i ~si − δ ·∑
i∈P ki~si =∑
i∈P x0i ~si − δ · ~0 = ~b,
wegen
~b =∑n
i=1 x0i ~si =
∑i∈P x0
i ~si +∑
i6∈P x0i ~si =
∑i∈P x0
i ~si +∑
0 · ~si =∑
i∈P x0i · ~si.
Analog ist A ~x2(δ) = ~b.
(ii) x1(δ0) ≥ 0 und x2(δ0) ≥ 0 fur bestimmte δ0
Wir bilden alle Quotienten x0i
ki> 0(i ∈ IP ) und
x0j
−kj> 0(j ∈ IN ).
Unter diesen endlich vielen Quotienten gibt es jeweils einen kleinsten, es sei dies der
mit dem Index i = r und j = s, also
x0r
kr:= min
i∈IP
x0i
kiund
x0s
−ks:= min
j∈IN
x0j
−kj.
Dann gilt fur alle 0 < δ ≤ xrkr
: x0i −δki ≥ 0 ∀i ∈ IP , denn man zieht von x0
i maximal
ab: x0i − xr
kr· ki ≥ x0
i −x0
iki
ki = 0.
Ebenso gilt fur alle 0 < δ ≤ xs−ks
: x0i +δki ≥ 0 ∀i ∈ IN , denn man gibt was Negatives
hinzu.
66
Somit sind alle Koordinaten von ~x1(δ ≤ xrkr
) ≥ 0, denn:
ist i ∈ IP ⊂ P , dann ist nach oben x0i − δki ≥ 0
ist i ∈ IN ⊂ P , dann ist ki < 0, also x0i − δki erst recht positiv (weil ja x0
i ≥ 0).
ist i 6∈ P , dann ist nach Definition (24) die Koordinate 0.
Analoges gilt fur ~x2(δ ≤ x0s
−ks). Wahlt man δ0 als die kleinere der beiden Zahlen{
x0r
kr, x0
s−ks
}, also 0 < δ0 := min
{x0
rkr
, x0s
−ks
}, dann gilt ~xn(δ0) ≥ 0 und ~x2(δ0) ≥ 0.
(iii) L(x1(δ0)) = L(x0) = Lmin und L(x2(δ0)) = L(x0) = Lmin
L(~x) =∑n
i=1 lixi ⇒ (wenn man die Summanden mit li = 0 weglaßt):
L( ~x1(δ0)) =∑
i∈P li(x0i − δ0ki) =
∑i∈P lix
0i − δ0
∑i∈P liki =
=∑n
i=1 lix0i − δ0
∑i∈P liki = L( ~xo)− δ0
∑i∈P liki
L( ~x2(δ0)) =∑
i∈P li(x0i + δ0ki) = L( ~x0) + δ0
∑i∈P liki.
Weil nun Lmin = L( ~x0) ≤ L(~x)∀~x ∈ Z ist, also auch fur ~x = ~x1(δ0) bzw. ~x = ~x2(δ0)),
erhalt man: L( ~x0) ≤ L( ~x1(δ0)) = L( ~x0)−δ0∑
i∈P liki, also∑
i∈P liki ≤ 0 und analog
L( ~x0) ≤ L( ~x2(δ0)) = L ~x0) + δ0∑
i∈P liki, also∑
i∈P liki ≥ 0.
Also muß∑
i∈P liki = 0 sein, also L( ~x1(δ0)) = L(x00) = Lmin und L( ~x2(δ0)) = Lmin
und damit sind mit (i) und (ii) ~x1(δ0) und ~x2(δ0) zulassige Minimalpunkte.
Sie haben aber weniger positive Koordinaten als ~x0, denn:
Ist δ0 = xrkr⇒ die r−te Koordinate von ~x1(δ0)) = x0
r − xrkr· kr = 0.
Ist δ0 = xs−ks
⇒ die s−te Koordinate von ~x2(δ0) = x0s
+xs−ks
· ks = 0.
Von einem zulassigen Minimalpunkt ~x0 ausgehend erhalt man so auf alle Falle einen
weiteren zulassigen Minimalpunkt ~x1, aber mit weniger positiven Koordinaten. Die Menge
S1 der zu den positiven Koordinaten von ~x1 gehorigen Spaltenvektoren von A wird daher
eine echte Teilmenge von S sein: S1 ⊂ S. Ist S1 l.u., dann ist ~x1 eine Ecke. Ist S1 l.a., dann
wendet man dasselbe Verfahren wie oben auf ~x1 an usw. Spatestens nach p Schritten ist
Sp die leere Menge, also l.u., und man hat eine Ecke erhalten, w.z.z.w.
Wann gibt es uberhaupt zulassige Minimalpunkte? Ist die zulassige Menge Z unbeschrankt,
muß es solche nicht geben (siehe Abb. 3). Bei beschrankten, zulassigen Mengen kann dies
jedoch nicht passieren (wir mussen allerdings K = IR voraussetzen).
67
Satz 16.6 Existenz zulassiger Minimalpunkte
Sei A ∈ IRm·n, Rg(A) = m,~0 ≤ ~b ∈ IRm,~l ∈ IRn, L(~x) := ~lt~x.
Z := {~x ∈ Kn|A~x = ~b und ~x ≥ 0} sei nichtleer und beschrankt.
Dann existiert mindestens ein ~x0 ∈ Z mit L( ~x0) = min~x∈Z L(~x).
Eine lineare Optimierungsaufgabe mit nichtleerer und beschrankter zulassiger
Menge ist losbar.
Beweis: Der Satz ist eine direkte Folgerung aus dem Satz das Maximum und Minimum
aus der mehrdimensionalen Analysis (nach WEIERSTRASS):
Die Teilmenge D ⊆ IRn sei nicht leer, abgeschlossen und beschrankt. Die Abbildung f :
IRn → IR sei stetig. Dann besitzt f auf D ein globales Maximum und ein globales Minimum.
Bei uns ist D = Z. Weil in Z in allen Ungleichungen das Gleichheitszeichen ≤ auftritt, ist
Z abgeschlossen (d.h. IRn\Z ist offen).
Lineare Abbildungen sind stets stetig, also insbesondere auch L(~x) = ~lt~x.
Um die lineare Optimierungsaufgabe zu losen, konnte man daher folgend vorgehen:
1. Entscheide, ob das Problem losbar ist.
Berechne dazu die zulassige Menge Z.
Ist Z 6= ∅ und beschrankt ⇒ Problem losbar.
Ist Z unbeschrankt, kann das Problem auch unlosbar sein (siehe SIMPLEXVER-
FAHREN → Operations Research).
2. Berechne alle Ecken ~x1, . . . , ~xr von Z.
Berechne L( ~xk) fur alle k = 1, . . . , r.
Dann ist nach c) Lmin = L(~x) = mink∈Ir L( ~xk).
Dieses Vorgehen ist praktisch unbrauchbar, denn n und m sind oft > 100.
Das von G.B. DANTZIG 1947 entwickelte SIMPLEXVERFAHREN gestattet es, nach
endlich vielen Schritten entweder die Nichtlosbarkeit des Problems erkennen bzw. eine
minimale Ecke finden zu konnen.
![1LJKW 5XQ NP NP 6HSWHPEHU 6HLWH $ O W H U V N O D V V … · /lq]hu 6sdundvvhq &lw\ 1ljkw 5xq np np 6hswhpehu $ o w h u v n o d v v h q s o d w ] l h u x q j &20387(' 7,0(6 67$57](https://img.pdfslide.org/doc/110x75/5e197772b720bf6b71683331/1ljkw-5xq-np-np-6hswhpehu-6hlwh-o-w-h-u-v-n-o-d-v-v-lqhu-6sdundvvhq-lw.jpg)
![q Einladung - kinderklinik-datteln.de · R R S H U D W LR Q I U 7 U DQ VS D UH Q ] XQ G 4 XD OLW W LP * H V X Q G K H L W V Z H V H Q e Dienstag, 19. Februar 2019 Seminar 10.30 -](https://img.pdfslide.org/doc/110x75/5d617bf188c993d6258b470b/q-einladung-kinderklinik-r-r-s-h-u-d-w-lr-q-i-u-7-u-dq-vs-d-uh-q-xq-g-4.jpg)
![D FK V WH LQ 3 R V W3 d un p | j olfk n h lwh q j le w h v lp 6 fk d q ]h q j h ol q g h g h v q r ug lvfk h q = h q wux p v lq g h u 2 uwvfk d iw 5 d p vd x vr z lh 3 d un s od](https://img.pdfslide.org/doc/110x75/5e5202f7788a0e0e9d190d4e/-d-fk-v-wh-lq-3-r-v-w-3-d-un-p-j-olfk-n-h-lwh-q-j-le-w-h-v-lp-6-fk-d-q-h-q-j.jpg)
![uantensprung - qs-wob.de+Fl… · ... =QdbYh QeV]Ub[cQ] CYU XQd TYU UXU]Q\YWU 2UdbYURcgYbdY ... * GQc XQd CYU Q\c 2UdbYURcgYbdY^ e ... YSX V b TYU 1ecRY\Te^W Q…](https://img.pdfslide.org/doc/110x75/5aea8ebb7f8b9a90318bc79f/uantensprung-qs-wobde-fl-qdbyh-qevubcq-cyu-xqd-tyu-uxuqywu-2udbyurcgybdy.jpg)
![PE Programm WS2018 daniela - Universität Mozarteum · ' lh 7hloq hk p hu lq q hq huk d owhq q d fk $ e vfk ox vv g hv % d vlvp r g x ov hlq = z lvfk h q ]h uwlÀ n d w x q g q d](https://img.pdfslide.org/doc/110x75/5f0e51a17e708231d43ea9ed/pe-programm-ws2018-daniela-universitt-mozarteum-lh-7hloq-hk-p-hu-lq-q-hq-huk.jpg)
![%HWWHQDXHU :HLKHU 6FKLHVVHQ · PDF file5dqjlhuwh 9huhlqh 5dqj9huhlq .dw $q] 7hloq 3io 5hv 7rwdo 3uhlv 8ol 5rwdfk 6fkzhqgh 6fk w]hqyhuhlq (jjhuvwdqghq 6fk w]hqyhuhlq](https://img.pdfslide.org/doc/110x75/5a70d4c57f8b9abb538c548e/hwwhqdxhu-hlkhu-6fklhvvhq-nbsppdf-file5dqjlhuwh-9huhlqh-5dqj9huhlq.jpg)
![Í ë Ë å 0 f w [ q ] J - SEIKEI](https://img.pdfslide.org/doc/110x75/626267fad1abd17b985c5bb8/-0-f-w-q-j-seikei.jpg)
![æ q · µu W l lµu ìXí ooP u ]v ̵u oµ( W l lµu æ Å æ](https://img.pdfslide.org/doc/110x75/5e21e38aba7f301ba7539cb0/-q-u-w-l-lu-x-oop-u-v-oeu-o-w-l-lu-.jpg)
