#Theorema Magnum MCMXLVIII: das Simplex-Verfahren – Mathlog

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 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 und definieren ein Polyeder. Die Maximierung von entspricht der Verschiebung der Hyperebene 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 c^Tx 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.