Benutzer Diskussion:Chi-Vinh/Testgelände/Lineare Algebra Sätze

Einbau dieser Textschicht über grosse Sätze

Theorem 1. Falls LP eine optimale Lösung hat, dann hat das LP eine Basislösung.

Informell. Das ist eines der Eckpunkte des Simplex-Algorithmus. Der konstruktive Beweis zeigt, wie man eine Nichtbasislösung auf eine Basislösung reduziert, ohne den Zielfunktionswert zu degradieren. Dieses THeorem bezieht sich dabei auf ein LP Problem in der Normalform.

Theorem 2.

Jeder Extremalpunkt ist eine Basislösung und umgekehrt.

Informell. Das ist die Brücke zwischen der Algebra (Basislösung) und der Geometrie (Extrempunkt). Die Korrespondenz ist aber keine 1-1 eineindeutige, isomorphe Abbildung. Denn ein Extrempunkt kann mit mehreren Basen mit gleicher Basislösung korrespondieren. Informativ ist auch: zwei Extremalpunkte sind nur dann adjazent, benachbart, wenn zwei korrespondierende Basen benachbart, adjazent sind - anders ausgedrückt: sie unterscheiden sich nur in einem Spaltenvektor. Theoretisch ist es dann möglich durch einen Zyklus aus Basen zu wandern, ohne den korrespondierenden Extrempunkt zu verlassen.

Theorem 3.

Das primäre LP hat eine optimale Lösung dann und genau dann, wenn das duale Problem eine optimale Lösung hat mit dergleichen Zielwerten. In Konsequenz bedeutet das bei einem unbeschränkten primären LP ist das duale LP unlösbar und umgekehrt. Informell. Das ist das wichtige Fundamentale Dualitätstheorem. Zu diesem Theorem gibt es viele Korollare.

Z.B.

• Falls x eine Basislösung im primären LP und entsprechen y eine Basislösung im dualen LP. Dann sind sie dann und genau dann optimal, falls cx = yb. Beweisskizze: über das Farka's Lemma oder mit der Simplex Methode.

• Falls x eine Basislösung im primären LP und entsprechen y eine Basislösung im dualen LP. Dann erfüllt x,y die sogenannten complementary slackness Bedingung.

Theorem 4. If the primal and dual LPs have optimal solutions, they have a strictly complementary optimal solution.

Falls das primäre und das duale LPs optimale Lösungen haben, dann haben sie streng komplementäre optimale Lösungen.

Informell. Dieses Theorem ist ein weitere Eckpunkt. Es macht Aussagen über die Lösungsstruktur für gewisse Klassen mit dem interior point methods. Eine strictly complementary Lösung enthält qualitative Aussagen für die Sensitivitätsanalyse. Ursprünglich it es 1956 von Goldman und Tucker bewiesen worden mit Methoden aus dem Studium Linearen Ungleichungen. Moderne Annäherung verwertet konvexe Analysis.

Theorem 5. The simplex method converges in a finite number of iterations, using an anticycling rule if necessary. The worst-case time complextity is exponential.

Die Simplex Methode konvergiert in einer endlichen Iterationszahl mit notwendigen Antizyklus-Regeln. Der schlimmste Fall ist die exponentielle Komplexität.

Informell. Die Konvergenz ist trivial zu beweisen, wenn keine Entartung da ist. Schließlich wächst der Zielwert streng monoton. Frühe Ansätze bei den Anti-Zyklus Regeln war die Epsilon Methode und die Lexikographie. Eine populäre Antizklus Methode ist die Bland Regeln, die einfach den Zyklus bei der Pivotwahl unterbricht. Es wird nämlich die ivotreihe mit dem niedrigsten Index gewählt. Die exponentielle Komplexität des worst case wurde von Klee und Minty bewiesen. In der Praxis ist der Simplex Algorithmus meist von polynomialer Komplexität.

Theorem 6.

Einige interior point methods konvergieren mit einem strictly complementary optimale Lösung in polynomialer, zeitlichen Komplexität.

Informell.

Sehr vage im Vergleich zu den anderen Theoremen. Es ist nicht genau gesagt, für welches der vielen interior point methods es gelten soll. Ds erste Mal zeigte Khachiyan für das Schor`s ellipsoid method die polynomiale Komplexität. Das war ein wichtiges theoretisches Ergebnis - praktisch von der Performanz wertlos. Erst Karmakar`s Methode war praktisch performativ ein Algorithmus von polynomialer Komplexität. Seit der Karmakar`s Methode fing die Flut der Forschungen an, die zu der Klasse der Interior Point Methods führte.

Referenzen

• 0. H.J. Greenberg. Wolfe’s example and the zigzag phenomenon. In A. Holder, editor, Mathematical Programming Glossary, [1], zuletzt geprüft 2010/01/09, 1996. INFORMS Computing Society.
• 1. G.B. Dantzig, 1963. Linear Programming and Extensions, Princeton University Press, Princeton, NJ.
• 2. I.J. Dikin, 1967. Iterative Solution of Problems of Linear and Quadratic Programming, Doklady Akademii Nauk SSSR 174, 747-748.
• 3. T. Gal, 1995. Postoptimal Analyses, Parametric Programming, and Related Topics, 2nd ed., Walter de Gruyter, Berlin, Germany.
• 4. S.I. Gass, 1985. Linear Programming, 5th ed., McGraw-Hill, Inc., New York, NY.
• 5. A.J. Goldman and A.W. Tucker, 1956. Theory of Linear Programming, in Linear Inequalities and Related Systems, H.W. Kuhn and A.W. Tucker (eds.), Annals of Mathematical Studies 38, Princeton University Press, Princeton, NJ, 53-97.
• 6. H.J. Greenberg, 1999. Post-solution Analysis in Mathematical Programming, SIOPT short course, Atlanta, GA.
• 7. N.K. Karmarkar, 1984. A New Polynomial-Time Algorithm for Linear Programming, Combinatorica 4, 373-395.
• 8. L.G. Khachiyan, 1979. A Polynomial Algorithm in Linear Programming, Doklady Akademii Nauk SSSR 244, 1093-1096.
• 9. V. Klee and G.J. Minty, 1972. How Good is the Simplex Algorithm?, in Inequalities, III, O. Shisha (ed.), Academic Press, New York, NY, 159-175.
• 10. C. Roos, T. Terlaky and J.-Ph. Vial, 1997. Theory and Algorithms for Linear Optimization: An Interior Point Approach, John Wiley & Sons, New York, NY.
• 11. A. Schrijver, 1986. Theory of Linear and Integer Programming, Wiley-Interscience, New York, NY.
• 12. S.J. Wright, 1997. Primal-Dual Interior-Point Methods, SIAM, Philadelphia, PA.