Ökonometrie und Unternehmensforschung Econometrics and Operations Research – serie

Max-Min problems are two-step allocation problems in which one side must make his move knowing that the other side will then learn what the move is and optimally counter. They are fundamental in parti­ cular to military weapons-selection problems involving large systems such as Minuteman or Polaris, where the systems in the mix are so large that they cannot be concealed from an opponent. One must then expect the opponent to determine on an optlmal mixture of, in the case men­ tioned above, anti-Minuteman and anti-submarine effort. The author's first introduction to a problem of Max-Min type occurred at The RAND Corporation about 1951. One side allocates anti-missile defenses to various cities. The other side observes this allocation and then allocates missiles to those cities. If F(x, y) denotes the total residual value of the cities after the attack, with x denoting the defender's strategy and y the attacker's, the problem is then to find Max MinF(x, y) = Max [MinF(x, y)] .

89 TABLE 5 USE OR PLANNED USE OF MAJOR ENGINES IN AIR FORCE AND NAVY AIRCRAFT a Engine Air Force Aircraft Navy Aircraft F-80, T-33, XF-92, YB-61, AJ2, F9F-7, TV-I, J-33 YB-62, F-94 (A, B), TM- T2-V, P4M-I 61 ( tactical missile) X-3, XF-88 F3D, F2H, F6U, F7U J-34 F-84 (B, C, D, E, G, H) J-35 FJ-I B-45, XB-51, XF-9J, B-36, J-47 B-47, F-86 (D, F, K) J-48 F-94C F9F J-57 B-52, YB-60, F-lOO, A3D, F4D, F8U F-I02A, F-I0l (A, B), SNARK, F-105A, F-I07, KC-135A, B-57D, X-16 F-84F, B-57 FIIF, A4D, FJ-3, J-65 FJ-4, F9F YQ-l, YQ-2, T-37 J-69 SNARK, YF-89E, B-66 J-71 F-I01, F-I02B, F-I05, J-75 F-I07 F8U, XP6M B-58, F-I04, F-IOIA (see J-79 note c, Table 4) F5D, FIIF, A3J, F4H T-34 C-133A, YC-97J, YC-12IF R7V-2 XF-84H T-40 R3Y,XFY,A2D YC-130, YC-131C T-56 Note: a Aircraft in which engine was used or was planned to be used. For at least one (and generally more) of the aircraft in the list associated with a given engine, the decision to use the engine was made when the engine was in the final stages of develop­ ment. (In the case of the J -57, J-79, andJ-75 this is true of nearly all the aircraft listed. ) No Jist extends beyond 1956. Summary For an engine developed independently of an airframe the de­ veloper may constrain the performance, weight, and size of an engine at the start.

Todaymanyeconomists, engineers and mathematicians are familiar with linear programming and are able to apply it. This is owing to the following facts: during the last 25 years efficient methods have been developed; at the same time sufficient computer capacity became available; finally, in many different fields, linear programs have turned out to be appropriate models for solving practical problems. However, to apply the theory and the methods of linear programming, it is required that the data determining a linear program be fixed known numbers. This condition is not fulfilled in many practical situations, e. g. when the data are demands, technological coefficients, available capacities, cost rates and so on. It may happen that such data are random variables. In this case, it seems to be common practice to replace these random variables by their mean values and solve the resulting linear program. By 1960 various authors had already recog­ nized that this approach is unsound: between 1955 and 1960 there were such papers as "Linear Programming under Uncertainty", "Stochastic Linear Pro­ gramming with Applications to Agricultural Economics", "Chance Constrained Programming", "Inequalities for Stochastic Linear Programming Problems" and "An Approach to Linear Programming under Uncertainty".

In classical analysis, there is a vast difference between the class of problems that may be handled by means of the methods of calculus and the class of problems requiring combinatorial techniques. With the advent of the digital computer, the distinction begins to blur, and with the increasing emphasis on problems involving optimization over structures, tIlE' distinction vanishes. What is necessary for the analytic and computational treatment of significant questions arising in modern control theory, mathematical economics, scheduling theory, operations research, bioengineering, and so forth is a new and more flexible mathematical theory which subsumes both the cla8sical continuous and discrete t 19orithms. The work by HAMMER (IVANESCU) and RUDEANU on Boolean methods represents an important step in this dnectlOn, and it is thus a great pleasure to welcome it into print. It will certainly stimulate a great deal of additional research in both theory and application. RICHARD BELLMAN University of Southern California FOf(,WOl'

Dynamic Programming is the analysis of multistage decision in the sequential mode. It is now widely recognized as a tool of great versatility and power, and is applied to an increasing extent in all phases of economic analysis, operations research, technology, and also in mathematical theory itself. In economics and operations research its impact may someday rival that of linear programming. The importance of this field is made apparent through a growing number of publications. Foremost among these is the pioneering work of Bellman. It was he who originated the basic ideas, formulated the principle of optimality, recognized its power, coined the terminology, and developed many of the present applications. Since then mathe­ maticians, statisticians, operations researchers, and economists have come in, laying more rigorous foundations [KARLIN, BLACKWELL], and developing in depth such application as to the control of stochastic processes [HoWARD, JEWELL]. The field of inventory control has almost split off as an independent branch of Dynamic Programming on which a great deal of effort has been expended [ARRoW, KARLIN, SCARF], [WIDTIN] , [WAGNER]. Dynamic Programming is also playing an in­ creasing role in modem mathematical control theory [BELLMAN, Adap­ tive Control Processes (1961)]. Some of the most exciting work is going on in adaptive programming which is closely related to sequential statistical analysis, particularly in its Bayesian form. In this monograph the reader is introduced to the basic ideas of Dynamic Programming.

Reihenfolgeprobleme stehen im Fachgebiet des Operations Research seit einiger Zeit im Mittelpunkt des Interesses. Nachdem bis vor wenigen Jahren für viele Reihenfolgeprobleme noch keine brauchbaren Lösungs­ verfahren bekannt waren, wurden seit etwa 1960 verschiedene Verfahren entwickelt, die kleine und mittelgroße Probleme mit wirtschaftlich ver­ tretbarem Aufwand exakt und größere Probleme mit hinreichender Genauigkeit zu lösen gestatteten. In der vorliegenden Arbeit sollen diese Verfahren diskutiert und vor allem über die mit ihnen an zahlreichen Beispielen gewonnenen Erfahrungen berichtet werden. Bei der Beschrei­ bung der Verfahren stehen algorithmische Gesichtspunkte und Fragen der Eignung zur Programmierung für elektronische Rechenautomaten im Vordergrund. Einige neuere Verfahren wurden auf Rechenautomaten getestet. Die dabei erzielten Ergebnisse werden ausführlich analysiert. Bei der Darstellung habe ich mich von der Maxime leiten lassen, ein schnell lesbares Buch hervorzubringen. Dem Leser, gleichgültig ob Theoretiker oder Praktiker, möchte ich damit die Gelegenheit bieten, sich mit einem Minimum an Zeit in die wesentlichen Strukturen der Reihenfolgeprobleme und deren Lösungsverfahren einzuarbeiten. Zu diesem Zweck habe ich bei der Beschreibung der Lösungsverfahren jeweils nach einführenden Erörterungen Beispiele zur Demonstration herangezogen und erst abschließend die allgemeingültigen Formulierun­ gen der Verfahren gegeben. Auf mathematischen Formalismus habe ich weitgehend verzichtet, soweit er nicht zum Verständnis der Probleme und Verfahren erforderlich oder zum Lesen der wichtigsten Fachliteratur unumgänglich war.

Das vorliegende Buch soll die große Lücke zwischen Theorie und Praxis des Operations Research schließen helfen. Während einerseits die Forschung auf diesem Gebiet mächtig und mit guten Resultaten vorangetrieben wird, sind andererseits die erfolgreichen Anwendungen auf praktische Probleme noch nicht überaus zahlreich. Welches sind die Gründe für diesen Rückstand der praktischen Anwendung? Das Studium der vier Teile des Buches soll zeigen, wie einige inter­ essante und bedeutende praktische Optimierungsprobleme gelöst wor­ den sind und wie ähnliche Probleme angepackt werden können. Da realistische Probleme meistens kompliziert und nicht leicht überblick­ bar sind, wurde bei der Beschreibung der Problemstellung darauf geachtet, daß die wichtigsten Gegebenheiten und Zusammenhänge in den Vordergrund gerückt und Nebensächlichkeiten nur am Rande erwähnt werden. Folgende bekannte und wichtige Methoden des Operations Research wurden zur Lösung der Probleme verwendet: lineare und quadratische Optimierung, dynamische Optimierung, Netzwerkfluß-Algorithmus (Out of Kilter-Methode) und Branch-and-Bound. Daß aber auch heuristische Verfahren zweckmäßig und erfolgreich eingesetzt werden können, zeigt der 2. Teil des Buches. In allen Fällen waren die Ver­ fasser bemüht, die Methoden ausführlich, korrekt und möglichst gut verständlich darzustellen. Eines geht aus allen Lösungsbeschreibungen der Probleme dieses Buches mit D~utlichkeit hervor: die dominierende Rolle, die der Computer bei der Berechnung der Resultate und Aufbereitung der Daten spielt. Der Computer hat für den Operations Research-Praktiker eine ähnliche Bedeutung wie das Auto für den Taxichauffeur. Ohne dieses Hilfsmittel kann man wohl planen und vorbereiten, doch nie ein praktischesResultat erzielen.

Existing works on stochastic processes belong to a field of abstract mathematics which puts them beyond the scope of the non-specialist. The preoccupations of research mathematicians being more often than not distant from the practical problems of experimental methodology, the needs of practical workers, though real, are not met by the majority of works that. deal with processes. By "practical workers", we mean research scientists in all the different disciplines: Physics, Chemistry, Biology, Medicine, Population, Economics, Organisation, Operational Research etc. Indeed, all scientific research today touches upon complex fields in which deterministic models can be useful for no more than an element­ ary and simple approximation. The Calculus of Probability although offering some interesting models is still inadequate in many instances, particularly in the study of evolving systems. The practical worker must therefore have at his disposal a set of original and varied stochastic models. These models must not be too general, for in that case not only would their theoretical study prove difficult, but above all the adaptation of such models to an observed system would lead to an estimation of a great number of parameters on the basis of a necessarily restricted sample. This would constitute an insuperable difficulty for the practical scientist. It is therefore essential for him to have at his disposal a varied range of very characteristic models.

Im letzten Jahrzehnt hat die Mathematisierung von Fachgebieten, die vorher heuristisch bearbeitet wurden, große Fortschritte erzielt. Dies gilt für das Straßenverkehrswesen ebenso wie für die Steuerung und überwachung umfangreicher Projekte. Meist handelt es sich darum, aufgrund eines Modells der Wirklichkeit Entscheidungen zu treffen, die eine Zielfunktion optimieren. Dabei kann die Anzahl der möglichen Entscheidungen endlich sein, wie bei der Frage, in welcher Reihenfolge vier Orte besucht werden sollen, damit die zurückgelegte Strecke mög­ lichst klein wird; oder das Modell kann sich der abstrakten Vorstellung unendlich vieler Möglichkeiten bedienen, wie bei der Auswahl eines Zeitpunkts aus einer kontinuierlich ablaufenden Zeit. Die endlichen Modelle können bei aller Verschiedenheit wegen ihres kombinatorischen Charakters vorteilhaft mit· graphentheoretischen Methoden behandelt werden. Der vorliegende Band liefert dafür exemplarische Beispiele. Die Aus­ wahl erfolgte dabei aufgrund meiner persönlichen Neigung und Erfah­ rungen, so daß Probleme der Straßenverkehrstechnik im Vordergrund stehen. Ordnungsgesichtspunkt bei der Gliederung des Stoffes waren jedoch nicht die Anwendungsgebiete, sondern die verwendeten Modelle und Methoden, wie es sich in den Überschriften der Kapitel 2 - 5 wider­ spiegelt. Die Methoden sind bis zu rechenfähigen Algorithmen ausge­ arbeitet. Meine Absicht war verständliche Darstellung der Zusammen­ hänge und Fassung des Erarbeiteten in Rechenvorschriften, nicht aber eine bloß rezeptmäßige Aufzählung von Techniken. In Kapitell sind die benützten graphentheoretischen Begriffe für den Nichtmathematiker zusammengestellt und erklärt.