<<

. 62
( 63 .)



>>

< c, x > ≥ < Aty, x > = < y, Ax > = < y, b > .



Das obige Ergebnis bezeichnet man als schwachen Dualit¨tssatz. Ein st¨rkeres Ergebnis
a a
ist der folgende sogenannte starke Dualit¨tssatz
a


Satz 9.56
Es gilt:

(a) Ist Z = …, Z — = …, so sind (LOP) und (LOP)* losbar und es gilt:
¨

’∞ < ± = ±— < ∞.

(b) Ist Z = … und Z — = …, so gilt ± = ’∞.

(c) Ist Z = … und Z — = …, so gilt ±— = ∞.
Beweis:
Sei x ∈ Z, y ∈ Z —. Dann gilt mit Lemma 9.56 < c, x > ≥ < b, y > . Also

∞ > < c, x > ≥ ± ≥ ±— ≥ < b, y > > ’∞.

Wir zeigen die Existenz einer L¨sung von (LOP) und ± = ±— . Die Existenz einer L¨sung
o o
von (LOP)* folgt dann aus Symmetriegrunden (siehe unten).
¨
Annahme: Es gibt kein x ∈ IR mit < c, x > = ±— , Ax = b, x ≥ θ. Das Lemma von Farkas
n

(siehe 9.35) liefert u ∈ IRm , x ∈ IR mit

Atu + γc ≥ θ, < b, u > +γ±— < 0.

Wahle v ∈ Z. Damit folgt
¨

0 ¤ < At u + γc, v > = < u, b > +γ < c, v > < ’γ±— + γ < c, v >,
Baumeister: Lineare Algebra II / Stand: August 1996 259


d.h. (mit ± ≥ ±— )
γ(< c, v > ’±— ) > 0 , γ > 0.
1
Setze y := ’ γ u. Dann gilt:

1
Aty = ’ Atu ¤ c, < b, y > > ±— .
γ
Dies ist ein Widerspruch zur De¬nition von ±— . Also gibt es x ∈ Z mit

±— ¤ ± ¤ < c, x > = ±— ,

d.h. x ist L¨sung von (LOP).
o
Zu (c)
Sei y ∈ Z — . Da Z = … gilt, hat das System

Ax = b, x ≥ θ

keine L¨sung. Mit dem Lemma von Farkas (siehe 9.35) folgt die Existenz von u ∈ IR m
o
mit
Atu ≥ θ, < b, u > < 0.
Also folgt fur y( ) := y ’ u , ≥ 0 :
¨

At y( ) = At y ’ Atu ¤ Aty ¤ c , ≥ 0,

sup < b, y( ) > = < b, y > + sup ’ < b, u > = ∞.
≥0 ≥0

Zu (b)
Folgt aus Symmetriegrunden (siehe unten).
¨

Wir haben oben zweimal mit einer Symmetrie argumentiert. Dies soll heißen, daß das
duale Problem von (LOP)* wieder (LOP) ist. Um dies zu veri¬zieren, ist zun¨chst aber
a
(LOP)* selbst als ein Problem in Standardform zu verstehen. Dies geht so:
(LOP)* ist ¨quivalent mit
a

Minimiere < ’b, u ’ v >
unter den Nebenbedingungen At u ’ At v + w = c, u ≥ θ, v ≥ θ, w ≥ θ .

Das dazu duale Problem ist

Maximiere < c, x >
unter den Nebenbedingungen Ax ¤ ’b, ’Ax ¤ b, x ¤ θ.

Daraus liest man durch Ersetzen von x durch ’x ab, daß das Problem (LOP) entstanden
ist.

Das duale Problem (LOP)*, genauer die dualen Variablen, haben im allgemeinen ei-
ne physikalische“ Interpretation, wenn die primalen Variablen, d.h. die Variablen von

(LOP), eine physikalische“ Interpretation haben.

Baumeister: Lineare Algebra II / Stand: August 1996 260


Bemerkung 9.57
Hat man mit dem Simplexverfahren das Problem (LOP) gel¨st und liegt das optimale
o
Tableau mit Basisvariablen µ1 , . . . , µm vor, dann kann man auch die L¨sung y des dualen
o
Problems (LOP)* ablesen, denn es gilt ja

∆µi =< aµi , y > ’cµi = yi ’ cµi , 1 ¤ i ¤ m.

d.h.
yi = ∆µi + cµi , 1 ¤ i ¤ m.
2
Beispiel 9.58
Das optimale Tableau unseres Illustrationsbeispiels war

1 2 3 4
3 1 010 2
4 1 101 3
-1 -3 0 0 0

Also l¨st y := (0, 0) das duale Problem
o

Maximiere 4y1 + 3y2
unter den Nebenbedingungen 2y1 + y2 ¤ 1, y2 ¤ 3, 2y1 ¤ 0, y2 ¤ 0.

2
Literaturverzeichnis

[1] AITKEN, A.,C.: Determinanten und Matrizen, Bibliographisches Institut, Mann-
heim, 1969

[2] ANTON, H.: Lineare Algebra, Spektrum“Verlag, Heidelberg, 1994

[3] ARTIN, E.: Geometric Algebra, Wiley-Interscience, Chichester, 1966

[4] BEHR, H.: Lineare Algebra und analytische Geometrie, Vorlesungsskript, Universit¨t
a
Frankfurt/Main, 1977/78
¨
[5] BEIGLBOCK, W.: Lineare Algebra, Springer, New York, 1983

[6] BEUTELBACHER, A.: Lineare Algebra, Vieweg, Braunschweig, 1993

[7] BOURBAKI, N.: Algebre lin´aire, Hermann, Paris, 1962
e

[8] BRIESKORN, E.: Lineare Algebra und Analytische Geometrie I und II, Vieweg,
Braunschweig, 1983 (I), 1985 (II)

[9] BUNSE, W., BUNSE-GERSTNER, A.: Numerische lineare Algebra, Teubner, Stutt-
gart, 1985

[10] BURDE, G.: Vorlesung uber Analytische Geometrie und Lineare Algebra, Vorle-
¨
sungsskript, Universitat Frankfurt/Main, 1973/74
¨
[11] CIGLER, J.: Einfuhrung in die lineare Algebra und Geometrie (2 Teile), Manz-Verlag,
¨
Wien, 1977

[12] COLLATZ, L., WETTERLING, W.: Optimierungsaufgaben, Springer, New York,
1971

[13] EBBINGHAUS, H.D., u.a.: Zahlen, Springer, New York, 1988

[14] DIEDONNE, J.: Geschichte der Mathematik 1700 “ 1900, Vieweg, Braunschweig,
19851

[15] FISCHER, G.: Lineare Algebra, Vieweg, Braunschweig, 1991

[16] FISCHER, G.: Analytische Geometrie, Vieweg, Braunschweig, 1991

[17] FORSTER, O.: Analysis 1 und 2, Vieweg, Braunschweig, 1976 (Teil 1) und 1979 (Teil
2)

i
[18] GABRIEL, P.: Matrizen, Geometrie, Lineare Algebra, Birkhauser, Basel, 1996
¨

[19] GAWRONSKI, W.: MGrundlagen der Linearen Algebra, Aula“Verlag Wiesbaden,
1996

[20] GERICKE, H.: Mathematik in Antike und Orient, Fourier, Wiesbaden, 1992

[21] GOLUB, G.H., VAN LOAN, C.F.: Matrix Computations, North Oxford Academic,
Oxford, 1983

[22] GREUB, W.H.: Lineare Algebra, Springer, New York, 1967

[23] GREUB, W.H.: Multilinear Algebra, Springer, New York, 1978

[24] HALMOS, P.R.: Finite-dimensional Vector Spaces, D. van Nortstrand, Princeton,
1958

[25] HOFFMANN, K., KUNZE, R.: Linear Algebra, Prentice Hall, New Jersey, 1961
¨
[26] JANICH, K.: Lineare Algebra, Springer, New York, 1991

[27] KADISON, L., KROMAN, M.T.: Projektive Geometrie and modern Algebra,
Birkh¨user, Basel, 1996
a

[28] KARLOFF, H.: Linear programming, Birkhauser, Basel, 1991
¨
[29] KLINGENBERG, W.: Lineare Algebra und Geometrie, de Gruyter, Berlin, 1990
¨
[30] KOCHENDORFER, R.: Determinanten und Matrizen, Springer, New York, 1957

[31] KOECHER, M.: Lineare Algebra und analytische Geometrie, Springer, New York,
1985

[32] KOWALSKY, H.-J., Michler, G.O.: Lineare Algebra, de Gruyter, Berlin, 1995

[33] LANG, S.: Linear Algebra, Addison-Wesley, New York, 1971

[34] LENZ, H.: Vorlesungen uber projektive Geometrie, Akademische Verlagsgesellschaft,
¨
Leipzig, 1965

[35] LINGENBERG, R.: Lineare Algebra, Bibliographisches Institut, Mannheim, 1969

[36] LIPSCHUTZ, S.: Lineare Algebra “ Theorie und Anwendungen, Mc Graw Hill, New
York, 1977

[37] LORENZ, F.: Lineare Algebra I und II, B.-I. Wissenschaftsverlag, Mannheim, 1989

[38] NEF, W.: Lehrbuch der linearen Algebra, Birkhauser, Basel, 1966
¨

[39] NIEMEYER, H., WERMUTH, E.: Lineare Algebra “ Analytische und numerische
Behandlung, Vieweg, Braunschweig, 1987

[40] OELJEKLAUS, E., REMMERT, R.: Lineare Algebra I, Springer, New York, 1974

ii
Baumeister: Lineare Algebra II / Stand: August 1996 iii


[41] PICKERT, G.: Analytische Geometrie, Akademische Verlagsgesellschaft, Leipzig,
1953

[42] PRASOLOV, V,V.: Problems and Theorems in Linear Algebra, Translations of Ma-
thematical Monographs, Vol. 134, AMS, Providence, 1991

[43] SCHAAL, H.: Lineare Algebra und analytische Geometrie (2 Teile), Vieweg, Braun-
schweig, 1976

[44] SCHIKIN, J.: Lineare Raume und Abbildungen, Akademischer Verlag, Berlin, 1994
¨
[45] SCHRIJVER, A.: Theory of linear and integer programming, Wiley-Interscience,
Chichester, 1986

[46] STAMMBACH, U.: Lineare Algebra, Teubner, Stuttgart, 1988

[47] STROTH, G.: Lineare Algebra, Heldermann, Lemgo, 1995

[48] STRANG, G.: Linear Algebra and its Applications, Academic Press, 1976

[49] STRUIK, D.J.: Abriß der Geschichte der Mathematik, VEB Deutscher Verlag der
Wissenschaften, Berlin, 1980

[50] VAN DER WAERDEN, B.L.: Algebra, Springer, New York, 1959

[51] WALTER, R.: Einfuhrung in die lineare Algebra, Vieweg, Braunschweig, 1982

<<

. 62
( 63 .)



>>