A hybrid algorithm for solving convex separable network flow problems

Based on computational experiments with different approaches to convex separable network flow problems a hybrid algorithm is developed and implemented. Phase one of the algorithm uses a rapidly converging series of piecewise linear secant approximations in order to determine a good solution within some distance of the optimum. Starting from this solution, a feasible direction method, based on reduced Newton directions, is used in the second phase of the algorithm to determine the optimal solution. Since nonlinear network flow problems tend to be degenerate, special emphasis is put on the construction of a basis that yields a strictly positive step length at the beginning of phase two of the hybrid algorithm.A number of test problems have been solved successfully. It is expected that the approach can be extended to solve large-scale problems with convex separable objective functions. Details of the implementation and computational results are presented.

---

Zusammenfassung Ausgehend von experimentellen Ergebnissen mit unterschiedlichen Lösungsverfahren für separable Netzwerkflußprobleme wurde ein zweistufiges Verfahren entwickelt und implementiert. Auf der ersten Stufe wird in einem iterativen Prozeß das zu lösende Problem mehrfach stückweise linearisiert. Man erhält eine bereits sehr gute Lösung. Mit dieser wird ein Richtungsverfahren initialisiert, das unter Verwendung reduzierter Newton Richtungen die optimale Lösung bestimmt. Das Richtungsverfahren bildet die zweite Stufe des Verfahrens. Da nichtlineare Netzwerkflußprobleme im allgemeinen stark entartet sind, wird zu Beginn der zweiten Stufe des beschriebenen Verfahrens eine Basis konstruiert, die eine positive Schrittlänge zuläßt.Es wurden zahlreiche Testprobleme mit bis zu 600 Knoten und 1400 Kanten mit dem beschriebenen Verfahren erfolgreich gelöst. Es wird erwartet, daß das Verfahren auch auf sehr viel größere Probleme mit konvexer, separabler Zielfunktion angewendet werden kann. Es wird auf Fragen zur Implementation eingegangen und es werden numerische Ergebnisse diskutiert.

     

Ein lexikographischer Suchalgorithmus zur ganzzahligen Programmierung: L E X S

Zusammenfassung Für solche ganzzahligen Optimierungsprobleme, deren Ziel- und Restriktionsfunktionen monoton in jeder Variablen sind, wird ein Lösungsalgorithmus vorgestellt. Trotz der ähnlichkeit mit dem Verfahren vonLawler undBell bestehen Unterschiede in der Realisierung der Idee des überspringens von Vektoren. Ferner ist das Verfahren LEXS für ganzzahlige und nicht nur für 0–1 Probleme formuliert. Die Rechenzeiten derHaldi- und IBM-Beispiele werden mit denen anderer Algorithmen verglichen.

---

Summary An algorithm for solving monotonic integer programming problems is suggested. It is closely related toLawler andBell's lexicographical search for the optimum but is different in allowing integer variables instead of 0–1 variables only. The idea of skipping is performed slightly different, too. The computing times of theHaldi- and IBM-examples are compared to those for other algorithms.

     

Verkehrsplanung einer Großstadt

Zusammenfassung Die im voranstehenden dargelegte Methode setzt sich das Ziel, mit naturwissenschaftlichen Methoden quantitative Aussagen bei der Analyse und Prognose des Verkehrs einer Großstadt zu machen. Sie erhebt zwar weder den Anspruch, sämtliche Verkehrsprobleme zu lösen, noch soll behauptet werden, daß es sich dabei um das einzig mögliche Verfahren handelt. Die geschilderte Methode besitzt aber den Vorteil, daß sie in der Praxis bereits mit geringen Kosten zu brauchbaren Ergebnissen geführt hat.Alle Entwicklungen auf diesem Gebiet stehen jeden Interessenten grundsätzlich zur Verfügung, nur legt das Mathematische Labor, das in Zusammenarbeit mit allen zuständigen Stellen der Wiener Verkehrsplanung die Entwicklungsarbeiten durchgeführt hat, Wert darauf, als Sammelpunkt der Erfahrungen bei der Durchführung an anderen Orten zu fungieren. In einem Fall wurde von einer deutschen Stelle bereits konkreter Gebrauch von der dargelegten Möglichkeit gemacht. Das lebhafte Interesse nationaler und internationaler Instanzen für die Wiener Bearbeitung läßt hoffen, daß sich die Städteplaner in steigendem Maße bei ihren immer schwierigeren Aufgaben naturwissenschaftlicher Hilfsmittel bedienen werden.     

über die Optimierung einer bedingt konvexen Funktion unter linearen Nebenbedingungen

Zusammenfassung Es zeigt sich, da\ auch für die allgemeinere Klasse der bedingt konvexen Funktionen der von A. Orden für quadratische Zielfunktionen formulierte Satz gültig bleibt. Ferner lassen sich aus diesem Satz auch für das Programmierungsproblem ganz ähnliche Schlüsse ziehen wie im quadratischen Fall. Es ist damit gezeigt, da\ derartige nichtkonvexe Programmierungsprobleme grundsätzlich lösbar sind. In Zukunft wird es darauf ankommen, bessere Verfahren zur Lösung dieser Probleme zu finden.     

Numerische Polynomapproximation mit Knotenpolynomen

Zusammenfassung Numerische Polynomapproximation mit Knotenpolynomen. Alle Verfahren zur Konstruktion von Polynomen bester Approximation für Funktionen aus dem reellen RaumC [0, 1] sind mit beträchtlichem Aufwand verbunden. Nimmt man jedoch zum sonst üblichen Alternantensatz einen Satz von de la Vallée-Poussin dazu, so läßt sich das Polynom bester Approximation bestimmen, ohne daß bei jedem Iterationsschritt ein Gleichungssystem zu lösen oder ein Interpolations-polynom zu bestimmen ist. An Beispielen haben wir dieses Verfahren mit einem einfachen Austauschverfahren verglichen, das für tabellarisch gegebene Funktionen die approximationsaufgabe genähert löst.

---

Summary Numerical Polynomal Approximation by Knot-Polynomials. All methods to construct polynomial of best approximation for functions ofC [0, 1] over are laborious. With the Alternanten-Theorem and a theorem of de la Vallée-Poussin, the polynomial of best approximation can be calculated without solving a linear algebraic equation system or constructing an interpolation polynomial in each iteration. We have compared this method with a simple selection method in some examples that solves the approximation problem for given tabulated functions approximately.

     

Operations-Research-Modelle in der Betrieblichen Ertragsteuerplanung

Zusammenfassung Die Probleme der Ertragsteuerplanung stellen eines der wichtigsten Anwendungsgebiete des Operations Research in der Betriebswirtschaftlichen Steuerlehre dar. Da vor allem in jüngster Zeit zahlreiche Forschungsbeiträge aus diesem Bereich vorgelegt wurden, versucht der folgende Beitrag, einen aktuellen Überblick über den Stand der Entwicklung solcher steuerbilanzpolitischer Entscheidungsmodelle zu geben. Die Modelle stellen sich vor allem deshalb so problematisch dar, als einerseits ein möglichst realistisches Abbild der steuerrechtlichen Entscheidungssituation erreicht werden soll, die wegen der teilweise äußerst komplexen gesetzlichen Regelungen, insbesondere aber auch wegen des nichtlinearen Einkommensteuertarifs sehr schnell zu inoperationalen Modellansätzen führt. Andererseits sollen die Verfahren zur numerischen Lösung dieser nichtlinearen Optimierungsprobleme auch für den Nichtmathematiker unter den Modellbenutzern anwendbar sein.

---

Summary Planning the distribution of profits and profit-taxes over a given period is one of the most important fields of application of Operations-Research-Methods to taxation problems in business administration. The problem represents a typical nonlinear, strictly speaking convex minimization problem under linear, respectively convex constraints. Thus the main topic of OR-application is to build sufficient realistic models, which can nevertheless be solved by more or less simple mathematical methods (e.g. Lagrangian Multipliers or linear approximations).

     

Multiterminal network flows and applications

The paper discusses the ways to use the condensation technique of Gomory/Hu in the case of non-symmetric networks. Sufficient conditions to get the value of a maximal flow as row resp. column sum of the capacity matrix are derived. Procedures to determine the cut with minimal capacity are developed and applications of the minimal cut technique to problems of optimal sequencing are given.

---

Zusammenfassung Das Papier diskutiert die Möglichkeiten, die Kondensationstechnik von Gomory/Hu auf den Fall unsymmetrischer Netzwerke zu übertragen. Es werden hinreichende Bedingungen dafür abgeleitet, daß der Wert eines maximalen Flusses mit der Zeilenbzw. Spaltensumme der Kapazitätsmatrix übereinstimmt. Es werden Verfahren entwickelt, den Schnitt minimaler Kapazität zu bestimmen. Anwendungen der minimalen Schnitt-Technik auf Probleme der optimalen Reihenfolge werden vorgestellt.

     

Zwei Algorithmen zur Lösung eines komplexen Reihenfolgeproblems

Zusammenfassung Bei der Ordnung von Input-Output-Matrizen treten Kriterien auf, die wesentlich komplexer sind als die Ordnungsbedingungen bei klassischen Reihenfolgeproblemen (z. B.Traveling-Salesman-Problem). Ausgehend von den Arbeiten vonHelmstädter werden im folgenden die mathematische Formulierung eines solchen Reihenfolgeproblems sowie zwei Algorithmen zu dessen Lösung angegeben. Ein Verfahren ist ein lexikographischer Suchalgorithmus, das andere eine Modifikation des bekanntenJacobi-Verfahrens zur Berechnung von EigenwertenHermitescher Matrizen.

---

Summary On the ordering of input-output matrices we use some criteria which are more complex than the order conditions of classical sequencing problems (e. g.Traveling-Salesman-Problem). Basing on the papers ofHelmstädter we will give a mathematical formulation of this sequencing problem and two algorithms solving them. One procedure is a lexicographic searching algorithm, the other one a modification of the well knownJacobi-method which calculates the eigenvalues ofHermiteian matrices.

---

---

Ein Teil dieser Arbeit wurde als Referat auf der Jahrestagung der Deutschen Gesellschaft für Unternehmensforschung (DGU) am 23. September 1968 in Dortmund vorgetragen.

---

Vorgel. v.:W. Krelle.     

Some new results in flow shop scheduling

The problems of finding a schedule with minimal maximum lateness, respectively with minimal mean flow time for 2-machine flow shops with no wait in process, and related problems, including versions with unit processing times and a single resource constraint, are shown to be NP-hard in the strong sense. An algorithm is presented which finds a minimum makespan schedule with no wait in process for the 2-machine unit processing time flow shop under a single resource constraint inO (n logn) time. The obtained results continue to hold for the corresponding preemptive respectively nonpreemptive cases.

---

Zusammenfassung Ablaufplanungsprobleme für Werkstücke, die ohne zeitliche Unterbrechnung nacheinander auf einer Reihe von Maschinen zu bearbeiten sind, werden untersucht. U.a. wird nachgewiesen, daß im Gegensatz zur Minimierung der Planlänge die Minimierung anderer elementarer Kriterien, nämlich der größten auftretenden Verspätung bzw. der durchschnittlichen Fertigstellungszeit der Werkstücke bereits bei zwei Maschinen im strengen Sinne NP-schwierig ist. Es zeigt sich ferner ein enger Zusammenhang zu entsprechenden Problemstellungen, bei denen die Bearbeitung der Werkstücke auf den Maschinen eine beschränkt verfügbare Ressource in Anspruch nimmt, und alle Bearbeitungsdauern gleich sind. Hierzu wird ein Verfahren mit AufwandO (n logn) angegeben, das für zwei Maschinen Ablaufpläne minimaler Länge liefert. Wie ebenfalls gezeigt wird, gelten die dargestellten Ergebnisse auch für die Fälle, daß zeitliche Unterbrechnung zwischen den Maschinen bzw. auf und zwischen den Maschinen zugelassen wird.

     

Shortest route with time dependent length of edges and limited delay possibilities in nodes

Summary Few algorithms have been proposed for the solution of the shortest route problem with time dependent lengths of edges. These algorithms are valid only under the assumption that parking in the nodes is unlimited and any desirable delay in departure time from a given node is permitted. This paper considers the case where such an assumption is not acceptable, and presents an efficient algorithm for the solution of the shortest route problem in networks with time dependent lengths of edges and parking regulations at the nodes. Some other possible extensions are discussed.

---

Zusammenfassung Es wird das Problem betrachtet, kürzeste Wege in Graphen zu finden, bei denen die Kantenlängen zeitabhängig sind. Die hierfür bisher vorgeschlagenen Algorithmen sind nur anwendbar, wenn keine Einschränkungen für die Parkmöglichkeiten in den Knoten bestehen. Hier wird ein Algorithmus angegeben, der derartige Einschränkungen berücksichtigt. Einige mögliche Erweiterungen werden diskutiert.

     

The effectiveness of finite improvement algorithms for finding global optima

This paper investigates the effectiveness of using finite improvement algorithms for solving decision, search, and optimization problems. Finite improvement algorithms operate in a finite number of iterations, each taking a polynomial amount of work, where strict improvement is required from iteration to iteration. The hardware, software, and way of measuring complexity found in the polynomial setting are modified to identify the concept of repetition and define the new classes of decision problems,FI andNFI. A firstNFI-complete problem is given using the idea ofFI-transformations. Results relating these new classes toP, NP, andNP-complete are given. It is shown that if an optimization problem in a new classPGS isNP-hard, thenNP=co-NP. TwoPGS problems are given for which no polynomial algorithms are known to exist.     

Die optimale Anordnung von Gütern in Vorratslägern mit Hilfe der Mehrdimensionalen Skalierung

Zusammenfassung In dem Beitrag wird ein Verfahren zur Lösung innerbetrieblicher Standortprobleme vorgestellt, das sich sowohl methodisch als auch hinsichtlich seiner universellen Anwendbarkeit von bisher bekannten Verfahren abhebt. Die Platzzuweisung erfolgt auf das Basis empirisch ermittelter Verbundintensitäten, die mit Hilfe eines Verfahrens der nichtmetrischen mehrdimensionalen Skalierung (NMDS) auf ihre strukturellen Beziehungen hin untersucht werden. Es wird gezeigt, wie sich die NMDS-Lösung an räumliche Gegebenheiten anpassen läßt und wie das Verfahren zur Lösung eines konkreten Problems eingesetzt werden kann. Abschließend wird die Leistungsfähigkeit des Verfahrens im Vergleich zu einigen bekannten Heuristiken für verschiedene Problemgrößen überprüft.

---

Summary The article presents an approach for solving plant-layout problems which differs from previously proposed heuristic techniques both with regard to the underlying methodology as well as its broad applicability. In the example chosen for demonstration the assignment of goods to locations in a warehouse is based on an operational definition of joint demand which allows the goods in question to be placed in a two- or three-dimensional space by a nonmetric multidimensional scaling procedure. It is shown how the resulting configuration can be modified in order to meet space restrictions. The article concludes with an experimental comparison of frequently cited heuristic techniques for solving analogous problems with up to 20 facilities to cope with.

     

Duality for a class of continuous-time homogeneous fractional programming problems

In this note we present a continuous-time analogue of a duality formulation due to Craven and Mond for a class of homogeneous fractional programming problems. In this duality formulation, the dual problem is also a fractional program with the same objective function as the primal problem.

---

Zusammenfassung In dieser Arbeit wird der Dualitätsansatz von Craven und Mond für homogene Quotientenprogramme in endlich vielen Variablen auf unendlich dimensionale Probleme verallgemeinert, wobei Zähler und Nenner sowie die Nebenbedingungsfunktionale als Integrale gegeben sind. Der Ansatz zur Dualität ist dadurch gekennzeichnet, daß das duale Problem wieder ein Quotientenprogramm ist und die gleiche Zielfunktion wie das primale Problem hat.

     

Eine Faktorisierung der bei der rationalen Interpolation auftretenden Matrizen

Zusammenfassung Die rationale Interpolation führt auf ein homogenes oder inhomogenes lineares Gleichungssystem (2) bzw. (3). Hier sollen Faktorisierungen für die zu diesen Gleichungssystemen gehörenden Matrizen angegeben werden.Wandelt man das Gleichungssystem (2) durch Fixieren des höchsten oder niedrigsten Koeffizienten in Zähler oder Nenner in ein inhomogenes Gleichungssystem um, so wird durch die Faktorisierung die explizite Angabe der Auflösung des Systems geliefert. Sie stellt eine übersichtliche Formulierung des Wetterling-Algorithmus für inhomogene Systeme der genannten Art dar.Ergänzt man das System (2) durch eine weitere Gleichung zu einem System vonn+2 Gleichungen fürn+2 Unbekannte, so kann man mit Hilfe dieser Faktorisierung sofort die Kettenbruchentwicklung angeben. Es zeigt sich, daß man vom Rechenaufwand aufwand her dem Kettenbruchalgorithmus gegenüber, dem zuerst genannten Algorithmus bei der rationalen Interpolation den Vorzug geben sollte.Mit dem Wetterlingschen Algorithmus kann man jedoch allgemeinere Probleme lösen, wie sie z. B. bei derT-Approximation auftreten.In einer anderen Arbeit soll die Faktorisierung benutzt werden, um die numerische Stabilität der Algorithmen zu untersuchen.

---

Summary Rational interpolation may be reduced formally to the homogeneous or inhomogeneous system of linear equations (2) resp. (3). This paper presents a factorization of the matrices belonging to those systems.If the highest or lowest coefficient of numerator or denominator is normalized to 1, the coefficients may be represented by an explicit formula using this factorization. This is the matrix representation of the Wetterling-algorithm.The system (2) may also be bordered by an additional equation to given+2 homogeneous equations inn+2 unknowns. Then the factorization furnishes the matrix-representation of the Kettenbruch-algorithm.This facilitates the comparison of the Kettenbruch- and the Wetterling-algorithm. In the special case of rational interpolation the first one is superior, while the Wetterling-algorithm is more generally applicable.

     

Über eine optimale Feedback-Kontrolle unter der Verwendung von ARMA-Modellen

Zusammenfassung Es wird ein dynamisches System betrachtet, dessen Ausgang sich additiv aus einer Kontroll- und einer Störgröße ergibt. Kontroll- und Störgröße entstehen dabei selbst als Ausgänge von ARMA-Filtern, deren Eingänge die Steuerung des Systems bzw. weißes Rauschen sind. Es sind dabei Kosten zu minimieren, die durch die Abweichung des Systemausgangs von einer Zielgröße bzw. durch die Steuerung des Systems entstehen. Die Fragestellung führt auf ein dynamisches Optimierungsproblem, das mit dem Verfahren der rückschreitenden Induktion gelöst wird. In einigen speziellen Fällen kann man auch explizite Formeln für die Berechnung der optimalen Systemsteuerung angeben.

---

Summary The aim of this paper is the solution of a feedback control problem. We concern a dynamic system whose output is the sum of the outputs of two ARMA-filters. The inputs of these filters are the control of the system and white noise respectively. We have to minimize costs arising from the deviation of the system-output from a fixed target and by the control of the system. This leads to a problem of dynamic optimization, which is solved by the method of backward induction. In some special cases the computation of optimal system controls is possible by means of explicit formulas.

     

Euclidean matching problems and the metropolis algorithm

The Euclidean matching problem consists in partitionning a cloud ofn points inton/2 pairs such that the sum of the euclidean distances between the endpoints of each couple is minimized, resp. maximized.In this paper the thermodynamically inspired approach of simulated annealing is applied to find good approximations to large scale problems of the above kind. Also the asymptotic behaviour of random euclidean matching problems is studied, in particular computational results on the rate of convergence towards the asymptote are given.

---

Zusammenfassung Euklidische Matching-Probleme bestehen darin, eine ausn Punkten bestehende Wolke derart inn/2 Paare zu partitionieren, daß die Summe der Abstände zwischen den Endpunkten der Paare minimal bzw. maximal wird. Vorliegende Arbeit beschreibt die Anwendung der simulierten Abkühlung, eines durch die Thermodynamik inspirierten Verfahrens, zur Lösung großer derartiger Probleme. Zudem wird das asymptotische Verhalten zufälliger euklidischer Matching-Probleme studiert, insbesondere werden numerische Angaben zur Konvergenzrate gegen die Asymptote gegeben.

     

Methods of elastoplastic analysis

Summary The paper presents a number of alternative procedures for the solution of elasto-plastic problems by the matrix displacement or finite element method. In particular, the iterative initial strain and stress approaches are fully developed. Attention is also focused on the tangent stiffness method in association with an efficient modification technique. Convergence criteria are set up for the initial strain and stress methods. It is proved that the latter will only diverge, if an actual break-down of the structure occurs. In order to speed up the eventually slow convergence of the initial stress method a procedure is suggested which has proved very useful in conjunction with the initial strain approach.The theoretically deduced convergence properties of the iterative methods are verified by the numerical results obtained for some illustrative elasto-plastic problems.

---

Zusammenfassung In dieser Arbeit werden verschiedene Methoden zur Lösung elastoplastischer Probleme vorgelegt, die auf der Matrizenverschiebungsmethode (Methode finiter Elemente) beruhen. Insbesondere werden zwei iterative Verfahren vollständig hergeleitet, bei denen plastische Anfangsdehnungen bzw. Anfangsspannungen angesetzt werden. Auch die Methode der tangentialen Steifigkeit wird betrachtet, die in Verbindung mit der Modifikationstechnik besonders wirkungsvoll eingesetzt werden kann. Für die beiden iterative Verfahren mit Anfangsdehnungen bzw.-spannungen werden Konvergenzkriterien aufgestellt. Es läßt sich zeigen, daß die zweite Methode nur dann divergiert, wenn das Tragwerk tatsächlich zusammenbricht, was bei ideal plastischem Materialverhalten vorkommen kann. Um die in einigen Fällen langsame Konvergenz beim Ansatz von Anfangsspannungen zu beschleunigen, wird ein Verfahren vorgeschlagen, das sich in der Methode der Anfangsdehnungen bestens bewährt hat. Die zunächst theoretisch hergeleitelen Konvergenzeigenschaften der Iterationsverfahren werden bestätigt durch die Ergebnisse der Berechnung von einigen typischen plastisch deformierbaren Systemen.

---

---

Dedicated to Professor Kurt Magnus on his 60th birthday     

Anwendung derWienerschen Filtertheorie auf Probleme der Produktion und Lagerhaltung

Zusammenfassung DieWienersche Filtertheorie wird auf einfache Probleme der Produktion und Lagerhaltung angewandt. Diese Theorie gestattet, im Gegensatz zu den sonst verwendeten regelungstechnischen Verfahren, die Berechnung der kostenoptimalen Produktionspolitik eines vorgegebenen Modells. Die Einschränkungen, die dasWiener-Verfahren der Menge der regelungstechnisch unter-suchbaren Modelle auferlegt, werden diskutiert, und es wird gezeigt. daß sich mit diesem Verfahren ein Großteil der ökonomisch relevanten Modelle erfassen läßt.

---

Summary TheWiener Filtering Theory is applied to simple problems of production and inventory. In contrast to approaches using servo-mechanical methods, this theory allows the calculation of the optimal production policy of a given model. The restrictions caused by theWiener-approach on the set of models being investigable by servo-mechanical methods are discussed. It is shown that this approach may be applied to many of the economically relevant models.

---

---

Vorgel. v.:F. Ferschl.     

Optimal control of processes governed by partial differential equations part II: Vibrations

This paper is concerned with damping of vibrations of one-dimensional media by distributed or boundary control. Given an initial state of vibration at the timet=0, the problem is considered to find a control along the medium or on its boundary by which the initial state is transferred to the position of rest at some given timeT>0. At first the problem of null-controllability is studied where the control functions are taken fromL ₂ [0,T]. Then the problem of timeminimal null-controllability is investigated where null-controllability is tried to be achieved by norm-bounded controls inL ₂ [0,T] forT being as small as possible. The main result here is that time-minimal norm-bounded controls are controls with least norm on the minimum time interval which in addition equals the prescribed bound on the norm.The main tool for the treatment of these control problems is the theory of trigonometric moment problems.

---

Zusammenfassung Diese Arbeit beschäftigt sich mit der Dämpfung eindimensionaler Media durch verteilte Steuerung oder Randsteuerung. Zu vorgegebenem Anfangszustand der Schwingung zum Zeitpunktt=0 wird das Problem betrachtet, eine Steuerung entlang dem Medium oder auf seinem Rande zu finden, die den Anfangszustand in die Ruhelage zu irgendeiner gegebenen ZeitT>0 überführt. Zunächst wird das Problem der Null-Steuerbarkeit behandelt, bei dem die Steuerungsfunktionen demL ₂ [0,T] entnommen werden. Sodann wird das Problem der zeit-minimalen Nullsteuerbarkeit untersucht, bei dem versucht wird, Nullsteuerbarkeit mit norm-beschränkten Steuerungen inL ₂ [0,T] für möglichst kleinesT zu erzielen. Das Hauptresultat besteht hier in der Aussage, daß zeit-minimale norm-beschränkte Steuerungen zugleich Steuerungen mit minimaler Norm auf dem minimalen Zeitintervall sind, die überdies mit der vorgegebenen Normschranke übereinstimmt.Das Haupthilfsmittel zur Behandlung dieser Steuerungsprobleme ist die Theorie der trigonometrischen Momentenprobleme.

---

---

Invited Survey.     

Lösung großer linearer Regionalplanungsprobleme mit der Methode vonDantzig undWolfe

Kurzfassung Ein großes, für den Agrarsektor der BRD konzipiertes räumliches Gleichgewichtsmodell ist als lineares Optimierungsproblem zu groß, um ohne Schwierigkeiten mit einem Standard-LP-Programm gerechnet werden zu können. Zur Lösung solcher Probleme wird ein Programmkonzept entworfen, das die Verwendung von Standard-LP-Programmen vorsieht und sich am Vorgehen der Dekompositionsmethode vonDantzig undWolfe orientiert. In Versuchsrechnungen mit einem ca. 1250 Spalten und 900 Zeilen umfassenden kleineren Problem wird dieses Konzept getestet und untersucht, inwieweit der Rechenaufwand durch die Wahl der Ausgangslösung sowie bestimmte Matrixzerlegungen beeinflußt werden kann.

---

Summary The programming formulation of a large spatial equilibrium model of the agricultural sector of Germany, which is in preparation, results in a very large linear programming problem. For solving it, existing computer programs for linear programming (LP-programs) provide too little capacity. The author traces out the solution of such problems by a decomposition program, which allows the unchanged use of existing LP-programs. The underlying method is the decomposition principle ofDantzig andWolfe. This concept is tested by solving a problem with about 1250 colums and 900 rows. Furthermore, it is investigated to which extend an appropriate starting solution or specific matrix divisions influence optimization time.

---

---

Überarbeitete Fassung eines Vortrags, der auf der Jahrestagung 1973 der Gesellschaft für Operations Research (DGOR) in Karlsruhe unter dem Titel Zur Anwendung linearer Dekomposition gehalten wurde.