Die mathematische Optimierung hat ihren Beginn Ende der 1930er Jahre mit Arbeiten von Leonid Kantorowitsch.
Kantorowitsch hatte als 14-jähriger ein Studium in Leningrad aufgenommen, sich dort zunächst mit deskriptiver Mengenlehre und einigen von Lusin gestellten Problemen befasst, war dann zur Funktionalanalysis gewechselt, hatte sich 1935 im Alter von 23 Jahren habilitiert und im Jahr darauf mit einem Kollegen ein Lehrbuch über Näherungsmethoden der höheren Analysis geschrieben. Weil er neben seiner Professur 1938-39 mit der Optimierung der Produktion einer Furnierholzfabrik betraut worden war, entwickelte er mathematische Methoden, die als lineare Optimierung bekannt wurden.

In der linearen Optimierung geht es um die Lösung von Problemen der Form max_{x\in{\bf R}^n}\left\{c^Tx \mid Ax\le b, x\ge 0\right\} für eine gegebene Matrix A und Vektoren b und c, wobei die Ungleichungen in den Nebenbedingungen komponentenweise zu verstehen sind.
In seinem 1939 geschriebenen Manuskript „Die mathematische Methode der Produktionsplanung und Organisation und der beste Gebrauch von ökonomischen Betriebsmitteln“ legte Kantorowitsch die Grundlagen der linearen Optimierung. (In der Einleitung betonte er, „dass der größte Teil der Probleme, von denen ich sprechen werde, im Zusammenhang mit der Organisation und Planung der Produktion, spezifisch mit dem sowjetischen Wirtschaftssystem verbunden sind und in den meisten Fällen in der Wirtschaft einer kapitalistischen Gesellschaft nicht vorkommen.“)
Er diskutierte in seinem Skript zahlreiche Anwendungen, seine auf numerische Berechnungen ausgerichteten mathematischen Ansätze waren aber noch unvollständig. Daneben formulierte er auch das Problem des optimalen Transports, das etwa zehn Jahre zuvor schon in Arbeiten von A. N. Tolstoi bearbeitet worden war. Tolstoi hatte für zehn Fabriken und 68 sowjetische Städte von Taschkent bis Omsk mit insgesamt 155 Bahnverbindungen die optimalen Verbindungen von Hand berechnet, dabei eine Reihe von Methoden diskutiert und als erster als Optimalitätsbedingung das Kriterium der Abwesenheit negativer Zykel formuliert.
Kantorowitschs Arbeit wurde in der Sowjetunion zunächst kaum beachtet und im Westen kannte man sie ohnehin nicht. Kurz nach Kantorowitsch schrieb Frank Hitchcock 1941 eine (ebenfalls wenig beachtete) Arbeit zu einem Transportproblem, die schon Ansätze späterer Methoden der linearen Optimierung enthielt. In den USA war man aus militärischen Gründen an der Planungslogistik interessiert und bezeichnete in diesem Sinne einer systematischen militärischen Planung diese Wissenschaft auch als Programmierung. (Die Transportplanung wurde 1956 durch das Max-Flow-Min-Cut-Theorem und den Ford-Fulkerson-Algorithmus erleichtert. Bei der RAND entwickelten ein Mathematiker und ein Offizier dann Modelle zur Abschätzung von Transportkapazitäten – nicht um Transporte zu optimieren, sondern um ein Transportnetz möglichst effektiv zu unterbrechen.)

Man kann ein lineares Optimierungsproblem geometrisch veranschaulichen: die Ungleichungen Ax\le b und x\ge 0 definieren ein Polyeder. Die Maximierung von c^Tx entspricht der Verschiebung der Hyperebene c^Tx=0 in Richtung des Vektors c bis die verschobene Hyperebene den durch die Ungleichungen beschriebenen Polyeder gerade noch berührt. Die Frage ist aber, wie man dieses geometrische Prinzip praktisch realisieren soll.

George Dantzig hatte nach dem Studium zwei Jahre als Statistiker gearbeitet und daneben in Berkeley ein Promotionsstudium aufgenommen. Zur Legendenbildung führte später, als er in einer Vorlesung zwei vom Professor – dem Statistiker Neyman – an die Tafel geschriebene unbewiesene Vermutungen für Hausaufgaben hielt und löste. Sein Professor war beeindruckt und bereitete den Beweis zur Veröffentlichung vor. Dantzig unterbrach sein Promotionsstudium aber wegen des Krieges und wurde bei der Luftwaffe Leiter einer statistischen Abteilung. Nach dem Krieg nahm er sein Studium wieder auf und promovierte 1946 bei Neyman mit einer Ausarbeitung seines Beweises.

Ein Jahr nach der Promotion – jetzt beim Verteidigungsministerium beschäftigt – entwickelte er das Simplex-Verfahren, mit dem lineare Optimierungsprobleme erstmals systematisch gelöst werden konnten. Die zugrundeliegende Idee ist einfach: wenn es Lösungen der Ungleichungen gibt und der Zielfunktionswert cTx nicht beliebig groß wird, dann liegen alle optimalen Lösungen auf einer gemeinsamen Seitenfläche (irgendeiner Dimension) des durch die Ungleichungen gegebenen Polyeders. Insbesondere gibt es dann immer eine optimale Ecke. Die anschauliche Idee besteht nun darin, sich schrittweise von einer Ecke zu einer benachbarten mit besserem Zielfunktionswert zu hangeln, bis es keinen besseren Nachbarn mehr gibt. Da es sich bei der linearen Optimierung um ein konvexes Optimierungsproblem handelt, ist diese lokal optimale Ecke dann auch global optimal. (Algorithmisch gibt es für diesen Simplex-Schritt wie auch für das Finden eines geeigneten Startwerts verschiedene Möglichkeiten, hier waren dann seit den 70er Jahren die Entwicklungen der numerischen linearen Algebra von zentraler Bedeutung.)

Dantzig stellte seine Methode im September 1948 auf einem Treffen der Ökonometrischen Gesellschaft in einem Vortrag “Programming in a Linear Structure” vor. Noch im selben Jahr verkürzte er die Bezeichnung zu “Linear Programming”. Manche Experten fanden die Linearitätsannahmen zu restriktiv, vor allem John von Neumann verteidigte Dantzigs Methode gegen solche Kritik.
Eine der ersten dokumentierten Anwendungen der neuen Methode wurde das Diäten-Problem, dessen Ziel eine möglichst kostengünstige Nahrungszusammensetzung für Soldaten ist, die als Nebenbedingung bestimmte Mindest- und Höchstmengen an Vitaminen und anderen Inhaltsstoffen erfüllen sollen. George Stigler hatte dieses Problem 1945 formuliert:

Von einem mäßig aktiven Mann mit einem Gewicht von 154 Pfund sollte wie viel von jedem von 77 Lebensmittel täglich gegessen werden, damit die Aufnahme von neun Nährstoffen mindestens den 1943 vom Nationalen Forschungsrat empfohlenen Recommended Dietary Allowances (RDAs) entspricht und die Kosten der Diät dabei minimal bleiben?

Weil es damals noch keine fortgeschrittenen Methoden in der linearen Optimierung gegeben hatte, mußte Stigler dieses Problem mit heuristischen Ansätzen angehen: weil 62 der Lebensmittel nur wenige der Nährstoffe enthielten, betrachtete er nur die anderen 15 und berechnete unter diesen die optimale Lösung. Die jährlichen Kosten seiner Lösung betrugen 39,93 Dollar.
Mit dem Simplexverfahren konnte man nun die tatsächlich optimale Lösung berechnen. An den Berechnungen mit neun Ungleichungen und 77 Variablen wurden neun Personen beteiligt, die zusammen etwa 120 Manntage Rechenarbeit benötigten. Die jährlichen Kosten der berechneten optimalen Diät (mit den Preisen von 1939) betrugen dann 39,69 Dollar. Man sparte also 24 Cent gegenüber der ursprünglich berechneten Lösung.

Interesse an dieser Arbeit zeigte zunächst das amerikanische Militär, speziell die Luftwaffe, die militärische Einsätze optimieren wollte. Mathematischer Hintergrund dafür war die Spieltheorie, die John von Neumann und der Ökonom Oskar Morgenstern entwickelt hatten. (Ihr Buch „Theory of Games and Economic Behaviour“ war 1944 erschienen. Sie vertraten die Auffassung, dass sich die Ökonomie in Richtung einer formalen, mathematisch geprägten Wissenschaft entwickeln würde wie die Physik, die ihr in dieser Entwicklung schon einige Jahrhunderte voraus sei.) In der Spieltheorie kann die lineare Optimierung dazu verwendet werden, optimale Strategien in komplizierten Zwei-Personen-Nullsummenspielen zu berechnen. Von Neumann und Morgenstern entwickelten in diesem Zusammenhang dann auch das Simplexverfahren weiter.

Bild: https://lclub-mathematicians.blogspot.com/2011/05/george-dantzig.html

Kommentare (13)

  1. #1 Frank Wappler
    15. Oktober 2020

    Thilo schrieb (15. Oktober 2020):
    > […] Lösung von Problemen der Form \text{max}_{x \in {\bf R}^n} \left\{ c^T x \mid A x \le b, x \ge 0 \right\} für eine gegebene Matrix A und Vektoren b und c […]

    Die (Vergleichs-)Operatoren \le bzw. \ge haben in dieser zitierten Problemform offenbar eine Bedeutung, die von der üblichen, den (unmittelbaren) Vergleich zweier (reeller) Zahlen symbolisierenden abweicht bzw. für n \ge 2 darüber hinausgeht.

    Welcher Zusammenhang besteht zwischen Lösungen von Problemen der zitierten Form und Lösung von Problemen der Form \text{max}_{x \in {\bf R}^n} \left\{ c^T x \mid x^T (A x) \le x^T b, x^T x \ge 0 \right\}, ebenfalls für gegebene Matrix A und Vektoren b und c, und mit Vergleichs-Operatoren \le bzw. \ge in der üblichen Bedeutung ?

    p.s.
    > Die anschauliche Idee besteht nun darin, sich schrittweise von einer Ecke zu einer benachbarten mit besserem Zielfunktionswert zu hangeln, bis es keinen besseren Nachbarn mehr gibt. Da es sich bei der linearen Optimierung um ein konvexes Optimierungsproblem handelt, ist diese lokal optimale Ecke dann auch global optimal.

    Eine anschauliche Begriffsbildung von “Konvexität” (eines Polytops mit geeigneter “Zielfunktion” bzw. “Kosten”-Struktur) besteht entsprechend wohl darin, dass sich von einer (bzw. von jeder) Anfangs-Ecke, die mindestens zwei verschiedene Nachbarecke mit besserem Zielfunktionswert hat, zu (nicht unbedingt zur Anfangs-Ecke unmittelbar benachbarten) zwei weiteren Ecken unter ständiger Verbesserung des Zielfunktionswertes (oder zumindest: ohne den Zielfunktionswert in irgendeinem Hangelschritt zu verschlechtern) hangeln lässt,
    so dass, falls sich von der einen dieser beiden weiteren Ecken nicht durchgängig verbessernd (oder zumindest nie verschlechternd) zur anderen hangeln lässt,
    sich von jeder dieser beiden stets noch zu (mindestens) einer vierten Ecke durchgängig verbessernd (oder zumindest nie verschlechternd) hangeln lässt.

    Merkwürdig nur, dass der (bislang geprägte) Begriff der kausalen Konvexität anders (und damit wohl auch weniger anschaulich) definiert ist …

  2. #2 Thilo
    15. Oktober 2020

    Es steht ja in derselben Zeile, dass die Ungleichungen komponentenweise zu verstehen sind. Durch Anwenden von x^T bekommt man offensichtlich eine schwächere Ungleichung. Bspw.ist für reelle Zahlen stets x^Tx nichtnegativ, was für die einzelnen Komponenten von x natürlich nicht immer gilt.

  3. #3 Thilo
    15. Oktober 2020

    Bei kausaler Konvexität geht es einfach um Konvexität in Lorentz-Mannigfaltigkeiten. Hier, bei der linearen Optimierung, geht es um Konvexität im euklidischen R^n, der ja eine Riemannsche Mannigfaltigkeit ist.

  4. #4 Thilo
    15. Oktober 2020

    Es ist tatsächlich so, dass wenn eine Ecke einen besseren Wert liefert als eine andere, es dann möglich sein muß, sich schrittweise von der schlechteren über jeweils benachbarte Ecken bis zur besseren zu bewegen und dabei in jedem Schritt das Ergebnis zu verbessern. Das ist wohl der springende Punkt in Dantzigs Beweis (den ich mir aber nicht angesehen habe).

  5. #5 Alenx Groonwold
    USA
    15. Oktober 2020

    Where to buy a ready-made dating site – Interested in any options

  6. #6 Frank Wappler
    15. Oktober 2020

    hilo schrieb (#2, 15. Oktober 2020):
    > Es steht ja in derselben Zeile, dass die Ungleichungen komponentenweise zu verstehen sind.

    Oh — in meinem Browser steht das zwar nicht in der selben Zeile, aber (immerhin) im selben Satz.
    Es ist wohl nur ein (insbesondere mein) Vorurteil oder eine Idealvorstellung, dass \LateX-Ausdrücke hinsichtlich ihres mathematischen Inhaltes einigermaßen selbsterklärend dastünden;
    wie meinetwegen \text{max}_{x \in {\mathbb R}^n} \left\{ c^T x \mid \forall k \in \mathbb N, k \le n : (\bf e_k)^T (A x) \le (\bf e_k)^T b, (\bf e_k)^T x \ge 0, \text{ mit } (\bf e_j)^T \bf e_k = \delta^{\text{Kronecker}}_{jk}\right\}.

    p.s.
    Thilo schrieb (#3, 15. Oktober 2020):
    > Hier, bei der linearen Optimierung, geht es um Konvexität im euklidischen R^n […]

    Ja aber: Bei der “anschaulichen Idee [der Problemlösung]”, die im obigen ScienceBlog-Beitrag erläutert wurde und auf die ich mich im Kommentar #1 bezog, geht es offenbar um … bestimmte geordnete Teilmengen (“Hangel-Pfade”) einer durch Werte der “Zielfunktion” zumindest halb-geordneten Menge. (Zumindest halb-geordnet, weil es ja u.a. immerhin denkbar ist, dass einige bestimmte verschiedene Ecken dennoch den genau gleichen Zielfunktions-Wert haben.)

    Für ganz allgemeine halb-geordnete Mengen, und insbesondere im Extremfall sogenannter “Zäune”, versagt die beschriebene “anschaulichen Idee [der Problemlösung]” jedoch “offensichtlich”.
    Und damit im Zusammenhang steht die Feststellung, dass manche (insbesondere beschränkte) halb-geordnete Mengen nicht nur ein einziges “Maximum” haben, das durch “schrittweise zielführendes Hangeln” zwangsläufig erreicht würde, sondern mehrere verschiedene (lokale) Maxima, von denen höchstens eines “das globale Maximum” sein könnte.

    Deshalb: Gibt es eine spezielle Bezeichnung für die Eigenschaft mancher (aber eben nicht aller) (beschränkter) halb-geordneter Mengen, genau nur ein einziges Maximum (und/oder genau nur ein einziges Minimum) zu besitzen? — Etwa: “(Halbordnungs-)Konvexität” ?

    > Bei kausaler Konvexität geht es einfach um Konvexität in Lorentz-Mannigfaltigkeiten.

    Bei Kausal-Beziehungen handelt es sich in erster Linie jeweils um die (kausale) Halbordnung einer Ereignismenge. Und folglich lässt sich auch dafür untersuchen, welche beschränkten Teilmengen wie viele Maxima haben. (Diese Aufgabenstellung mag übrigens im Zusammenhang mit anderen Mathlog-Beiträgen bekannt vorkommen.)

    Der (bislang geprägte und im Kommentar #1 verlinkte) Begriff der “kausalen Konvexität” bezieht sich zwar ausdrücklich auf die kausale Halbordnung einer gegebenen Ereignismenge, die Anzahl “lokaler Maxima” spielt dabei aber offenbar keine Rolle.

  7. #7 Frank Wappler
    15. Oktober 2020

    Frank Wappler schrieb (#6, 15. Oktober 2020):
    > [T]hilo schrieb (#2, 15. Oktober 2020): […]

    (Bitte um Entschuldigung für meinen Schreib- bzw. Kopierfehler im Kommentar #6.)

    > Bei der “anschaulichen Idee [der Problemlösung]”, die im obigen ScienceBlog-Beitrag erläutert wurde und auf die ich mich im Kommentar #1 bezog, geht es offenbar um … bestimmte geordnete Teilmengen (“Hangel-Pfade”) einer durch Werte der “Zielfunktion” zumindest halb-geordneten Menge. (Zumindest halb-geordnet, weil es ja u.a. immerhin denkbar ist, dass einige bestimmte verschiedene Ecken dennoch den genau gleichen Zielfunktions-Wert haben.)

    Eine halb-geordnete Menge ganz wesentlich auch deshalb, weil (sicherlich, im Allgemeinen) nicht jede Ecke eines Polytops (im euklidischen \bf R^n) unmittelbarer Nachbar jeder anderen Ecke des selben Polytops ist.

    (Allerdings ist wohl jede Simplex-Ecke direkt zu jeder anderen benachbart. … Im obigen ScienceBlog-Artikel ging’s aber allgemein um Polyeder, und nicht ausdrücklich nur um Tetraeder, Dreiecke, oder höher-dimensionale Simplices.)

  8. #8 Vielen Dank
    16. Oktober 2020

    In einem Simplex-Verfahren wird jeweils eine Zeile (A_i) des linearen Gleichungssystems A*x=b mit einer reellen Zahl multipliziert und von einer anderen Zeile (A_j) abgezogen, so dass die neue Zeile A_j := A_j – a * A_i die alte Zeile Z_j ersetzt aber eine Dimension weniger hat bzw. ein x_k=0 ist.
    Wird das Verfahren m-mal angewendet, so dass die Matrix A zur Einheitsmatrix I wird, wird b zu b’ und I*x=b’ ist für x=(x_1,x_2,x_3, …) sofort lösbar. Als Nebenprodukt erhält man die inverse Matrix von A, wenn die auf A angewendeten arithmetischen Operationen auf eine neben A stehende Einheitsmatrix I angewendet werden.
    Das ist so erschreckend einfach, dass auszubildende Mathematiker diesen Algorithmus spätestens nach 2 Semestern Hochschul-Mathe-Training selber finden müssen.
    Tun sie aber nicht, weswegen ihnen dieses Verfahren und viele andere Verfahren von Mathe-Professoren beigebracht werden müssen.

    Thilos Liste Theorema Magna ist ein schöner Beweis, dass seit Beginn des 19ten Jahrhunderts in Mathe-Hochschulen Gehirne nicht mathematisch trainiert werden, so dass Mathe-Studenten schon nach dem ersten Mathe-Semester so konditioniert sind, dass ihnen in Mathe-Klausuren Beweise über unbewiesene Vermutungen zufließen, so wie George Dantzig die Beweise der unbewiesenen Vermutungen seines Dozenten Neyman zuflossen. Das hat sich rumgesprochen, so dass außer Fluss-Talenten niemand Mathematik studieren will
    (Rechnen ist Handwerk, Beweisen ist Kunst)

    Im Sinne der (Linearen) Optimierung bzw. wegen demokratischer Prozessökonomiegründe dürfen deutsche Landesregierungen Steuergelder nicht verschwenderisch verprassen, indem einer minimalen Mathe-Fluss-Talent-Menge, deren Minimalität eine ökonomische Nebenbedingung (Schuldengrenze) der Simplex-Methode verletzt, Mathe-Professoren (Vorlesungskurse) und Mathe-Doktoranden (Übungskurse) langjährig viel zu teuer zur Verfügung stellen.
    Aus undemokratischen Prestigegründen tun sie es trotzdem und zwingen Mediziner in den für sie sinnlosen Analysis-I-Grundkurs, um die ökonomische Nebenbedingung jährlich einzuhalten.

    Vielen Dank!

  9. #9 echt?
    16. Oktober 2020

    Vielen Dank für den schönen Artikel!

  10. #10 Thilo
    16. Oktober 2020

    @Frank Wappler: Alles richtig und das ist auch der Grund, warum Dantzigs Satz nicht trivial ist. Er hat bewiesen, dass auf dem konvexen Polytop die lokalen Maxima auch globale Maxima sind, was tatsächlich nicht offensichtlich ist.

  11. #11 Jan
    16. Oktober 2020

    @Frank Wappler(#6):
    Naja, ob das wirklich selbsterklärend ist, sei mal dahingestellt (persönlich finde ich die Darstellung im Artikel oben wesentlich klarer). Aber es ist auf jeden Fall nicht äquivalent.

    Zunächst einmal ist die Matrix A im allgemeinen nicht quadratisch, du brauchst also zwei Sätze von Basisvektoren.

    Und die Bedingung x ≥ 0 aus dem Artikel ist nur dann äquivalent zu deiner entsprechenden Bedingung, wenn die Basisvektoren (modulo Permutation) die kanonischen Einheitsvektoren sind. Das forderst du nicht explizit, also muss der Leser davon ausgehen, dass eine beliebige Orthonormalbasis zulässig ist. Das wird noch dadurch verstärkt, dass du explizit die Bedingung anführt, dass es sich um eine Orthonormalbasis handelt; würdest du implizit davon ausgehen, dass es sich um die kanonische Orthonormalbasis handelt, wäre diese Bedingung trivialerweise erfüllt, und damit wäre es überflüssig sie anzuführen.

    Analoges gilt natürlich auch für die andere Ungleichung.

  12. #12 Frank Wappler
    17. Oktober 2020

    Thilo schrieb (#10, 16. Oktober 2020):
    > @Frank Wappler: Alles richtig […]

    Vielen Dank!
    Sofern ich diese Erwiderung großzügig auslegen darf, würden wir folglich

    diese Art von Teilmengen-Konvexität (einer Teilmenge A \subset S hinsichtlich der Halbordnung \mathcal P \equiv (S, \le_{\mathcal P}) ) :
    \qquad \forall a, b, c \in S \mid a \le_{\mathcal P} b \le_{\mathcal P} c :
    \qquad \qquad (a, c \in A) \Rightarrow (b \in A)
            auch “relative Konvexität (der Menge A bezüglich ihrer Obermenge S, hinsichtlich der Halbordnung $\mathcal P$)” nennen; und dagegen

    • die Eigenschaft der Halbordnung \mathcal P \equiv (S, \le_{\mathcal P}) :
    \qquad \qquad \forall x, y \in S :
    \qquad \qquad \qquad \exists a, b \in S \mid (a \le_{\mathcal P} x), (a \le_{\mathcal P} y), (x \le_{\mathcal P} b), (y \le_{\mathcal P} b)
            “schwache intrinsische Konvexität (der Halbordnung $\mathcal P$, an sich)”, sowie

    • die Eigenschaft der Halbordnung \mathcal P \equiv (S, \le_{\mathcal P}) :
    \qquad \forall x, y \in S :
    \qquad \exists a, b \in S \mid (a \le_{\mathcal P} x), (a \le_{\mathcal P} y), (x \le_{\mathcal P} b), (y \le_{\mathcal P} b),
    \qquad \qquad (\forall j \in S : ((j \le_{\mathcal P} x), (j \le_{\mathcal P} y)) \Rightarrow ((a \le_{\mathcal P} j) \text{ oder } (j \le_{\mathcal P} a))),
    \qquad \qquad (\forall k \in S : ((x \le_{\mathcal P} k), (y \le_{\mathcal P} k)) \Rightarrow ((a \le_{\mathcal P} k) \text{ oder } (k \le_{\mathcal P} a)))
            “starke intrinsische Konvexität (der Halbordnung $\mathcal P$, an sich)”.

    p.s.
    Dass sich Deine oben zitierte Erwiederung auch auf den bislang (am 13. Oktober 2020) erreichten Stand meiner Argumentation zum Unterschied zwischen von Theorien und Modellen bezöge, wäre bestimmt eine zu großzügige Auslegung.

  13. #13 Frank Wappler
    17. Oktober 2020

    Jan schrieb (#11, 16. Oktober 2020):
    > @Frank Wappler(#6): Naja, ob das wirklich selbsterklärend ist, sei mal dahingestellt (persönlich finde ich die Darstellung im Artikel oben wesentlich klarer). Aber es ist auf jeden Fall nicht äquivalent.

    Okay. (Das ist immerhin auch eine Antwort auf meine Frage aus #6.)

    > Zunächst einmal ist die Matrix A im allgemeinen nicht quadratisch, […]

    Das hatte ich zwar nicht ausdrücklich bedacht, aber das Superskript-{}^T soll ja (bisweilen) wahre Wunder wirken.