Planning for repetitive cycles using an infinite horizon linear program

Summary Termination conditions are often difficult to model in a linear program. This paper discusses the use of an infinite horizon linear program which may enable the termination conditions to be modeled more accurately. It can be applied situations where a repetitive cycle (i. e. season) exists and generates steady state values of the decision variables. Examples are then given illustrating the use of the infinite horizon linear program.

---

Zusammenfassung Vielfach ist es schwierig, Abschlußbedingungen in ein LP-Modell einzubauen. In diesem Aufsatz wird die Verwendung eines linearen Modellansatzes mit unendlichem Horizont diskutiert, der es ermöglicht, Abschlußbedingungen auf sehr sorgfältige Weise zu formulieren. Er kann in solchen Fällen verwendet werden, in denen ein sich wiederholender Zyklus (z.B. Saisonzyklus) gegeben ist, und liefert stabile Werte für die Entscheidungsvariablen. Es werden Beispiele zur Anwendung des linearen Modellansatzes mit unendlichem Horizont gegeben.

---

---

The author thanksJohn McClain of Cornell University for suggesting this topic and making numerous helpful suggestions.     

On duality in linear fractional functionals programming

Summary The paper formulates a dual program for a given linear fractional functionals program (L.F.F.P.) and proves the duality theorem and its converse for the same. Special feature of the paper is that both the primal and the dual programs are L. F. F. Ps. and can easily be solved by the existing standard techniques.

---

Zusammenfassung Für ein lineares Optimierungsproblem, dessen Zielfunktion als Quotient zweier linearer Funktionen gegeben ist (LP-Problem mit gebrochener Zielfunktion), wird ein duales Problem formuliert und das Dualitätstheorem bewiesen. Es wird gezeigt, daß sowohl das primale als auch das duale Problem lineare Probleme mit gebrochener Zielfunktion sind und leicht mit den bekannten Standardtechniken gelöst werden können.

     

On establishing a two-term scattering law in the theory of radiative transfer

The inverse problem for a linearly anisotropically scattering model in the theory of radiative transfer or neutron transport is solved, in terms only of surface quantities, for a finite slab.

---

Zusammenfassung Das inverse Problem für ein linear anisotropes Streumodell in der Theorie der Strahlungsübertragung oder der Neutronen-Transporttheorie wird gelöst; für eine endliche Schicht wird die Lösung mit Hilfe von Oberflächengrössen ausgedrückt.

     

Ein Beitrag zur quasi-konvexen Optimierung in topologischen linearen Räumen

Zusammenfassung In dieser Arbeit wird für das Problem, ein quasikonvexes Funktional unter konkaven Ungleichungs- und affin linearen Gleichungsrestriktionen auf einer konvexen Teilmenge eines linearen Raumes zu minimieren, eine notwendige globale Optimalitätsbedingung in Form einer verallgemeinerten Multiplikatorenregel hergeleitet und einige einfache Folgerungen wie eine Dualitätsaussage und alternative Sätze in endlich dimensionalen Räumen diskutiert.

---

Summary In this paper we present a global necessary optimality condition in form of a generalized multiplier rule for the problem of minimizing quasiconvex functionals subject to concave inequality — and affine linear equality — constraints over a convex subset of a linear space and discuss some consequences as a duality theorem and alternative conditions for finite dimensional problems.

     

Network design and dynamic routing under queueing demand

Given a nonhierarchical network and time-varying flow requirements, the problem of determining optimal capacities is termed design; that of determining optimal flows as dynamic routing. We formulate a linear program to solve both simultaneously in the case of deterministic flow requirements. A probability distribution termed the Erlang Difference Distribution is derived from a queueing model to describe random flow requirements, and this case leads to a separable convex program that has a linear programming equivalent. Both linear programs are amenable to Dantzig-Wolfe decomposition, which reveals subproblems that yield to special techniques of solution.

---

Zusammenfassung Gegeben sei ein nicht hierarchisches Netzwerk mit zeitabhängigen Flüssen. Das Problem, optimale Kapazitäten festzusetzen, wird als Netzwerk-Entwurf bezeichnet. Die Bestimmung optimaler Flüsse bezeichnet man als dynamische Flußführung. Es wird ein lineares Programm formuliert, das beide Probleme gleichzeitig löst, sofern deterministische Flüsse vorliegen. Sodann wird eine Wahrscheinlichkeitsverteilung namens Erlang'sche Differenzen-Verteilung aus einem Warteschlangenmodell abgeleitet, um zufällige Flüsse zu beschreiben. Dies führt auf ein separables konvexes Programm mit einem linearen Programm als Äquivalent. Bei beiden betrachteten linearen Programmen kann die Dantzig-Wolfe Dekomposition angewendet werden, wobei die auftretenden Teilprobleme durch spezielle Techniken gelöst werden können.

---

---

Research partially supported by National Science Foundation Grant ECS-8300214.     

Anmerkungen zu einem Mehrgitterverfahren für lineare Komplementaritätsprobleme

Zusammenfassung Es wird ein Mehrgitterverfahren zur Lösung großer, dünn besetzter, symmetrischer, positiv definierter, linearer Komplimentaritätsprobleme beschrieben. Die Konvergenz des Verfahrens kann bewiesen werden.

---

Notes on a multigrid method for linear complementarity problems

Summary A multigrid method for the solution of large, sparse, symmetric, positive definite linear complementarity problems is described. The convergence of the method can be proved.

     

Solving stochastic dynamic programming problems by linear programming — An annotated bibliography

Summary As has been known for a long time, stochastic dynamic decision processes with finite state and action spaces can be handled by policy and value iteration, both typical dynamic programming techniques, as well as by linear programming. In the present paper, the most important results concerning the latter are reported and an outlook on more general settings is given.

---

Zusammenfassung Seit langem ist bekannt, daß zur Optimierung stochastischer dynamischer Entscheidungsprozesse im Falle endlicher Zustands- und Aktionenräume neben den für die dynamische Optimierung typischen Verfahren der Politik- und Wertiteration auch die lineare Programmierung herangezogen werden kann. In der vorliegenden Arbeit werden die wichtigsten diesbezüglichen Resultate referiert und ein Ausblick auf allgemeinere Ansätze gegeben.

     

A solution procedure for the two-stage stochastic program with simple recourse

For the stochastic program with simple recourse a solution procedure is given which generates a finite sequence of linear substitutive-programs so that, finally either the initially given problem is proved to be unsolvable or an optimal solution for it is given by the optimal solution of the substitutive program.

---

Zusammenfassung Für das stochastische Programm mit einfacher Kompensation wird ein Lösungsverfahren vorgeschlagen. Dieses Verfahren erzeugt eine endliche Folge linearer Ersatzprogramme derart, daß schließlich die Lösung eines dieser Ersatzprogramme als Lösung der ursprünglichen Aufgabe erkannt oder die Unlösbarkeit des gestellten Problems aufgedeckt wird.

---

---

This research has been supported by Sonderforschungsbereich 72, University of Bonn.     

Computational methods for solving two-stage stochastic linear programming problems

Approximating a given continuous probability distribution of the data of a linear program by a discrete one yields solution methods for the stochastic linear programming problem with complete fixed recourse. For a procedure along the lines of [8], the reduction of the computational amount of work compared to the usual revised simplex method is figured out. Furthermore, an alternative method is proposed, where by refining particular discrete distributions the optimal value is approximated.

---

Zusammenfassung Für das zweistufige Modell der stochastischen linearen Programmierung mit vollständiger Kompensation werden Verfahren untersucht, die sich aus der Annäherung einer gegebenen stetigen Wahrscheinlichkeitsverteilung der Daten durch endlich diskrete Verteilungen ergeben. Beim Vorgehen nach [8] wird die Reduktion des Rechenaufwandes im Vergleich zur üblichen revidierten Simplexmethode ermittelt. Als Alternative wird ein Verfahren vorgeschlagen, in dem durch sukzessive Verfeinerung speziell gewählter diskreter Verteilungen der Optimalwert monoton angenähert wird.

---

---

Herrn Prof. Dr. Eduard Stiefel in kollegialer Verbundenheit     

A duality theorem for continuous-time linear programming problems

Summary In dealing with dynamic economic policy models one encounters optimization problems whose objective function is an integral of a linear function of a finite number of continuous variables and whose constraints are linear integral inequalities. A set of intertemporal efficiency conditions (equilibrium conditions) yielding the optimal policy are given. By approximating the continuous problem by a set of discrete problems and appealing to a well known convergence theorem in functional analysis a continuous analog of the duality theorem is proved.

---

Zusammenfassung Bei der Beschäftigung mit dynamischen Modellen der ökonomischen Politik stößt man auf Optimierungsprobleme, deren Zielfunktion ein Integral einer linearen Funktion von einer endlichen Anzahl stetiger Variablen ist und deren Beschränkungen lineare Integral-Ungleichungen sind. Eine Menge intertemporaler Effizienz-Bedingungen (Gleichgewichtsbedingungen), die zur optimalen Politik führen, sind gegeben. Durch Approximation des kontinuierlichen Problems mittels einer Menge von diskreten Problemen und Berufung auf einen wohlbekannten Konvergenzsatz aus der Funktionalanalysis wird ein stetiges Analogon des Dualitätstheorems bewiesen.

---

---

The author is indebted to Mr.Arnold Faden for helpful suggestions and to ProfessorKarl A. Fox andGerhard Tintner for encouragement during the preparation of the paper. This research has been partially supported by a grant from the Ford Foundation to the School of Business Administration administered by the Center for Research in Management Science, University of California, Berkeley.

---

Vorgel. v.:G. Tintner.     

On Markovian decision models with a finite skeleton

We present a class of countable state space Markovian decision models that can be investigated by means of an associated finite-state, finite-action reduced model which we call the skeleton. In particular, we obtain a turnpike theorem for the original model (Theorem 2 in Section 5) from a known turnpike theorem for the reduced finite model. For illustration, we present in detail an application of this approach to an inventory model (re-establishing a known turnpike result) and sketch analogous results for a cash-balance model and a growth model.

---

Zusammenfassung Wir führen eine Klasse von Markovschen Entscheidungsmodellen mit abzählbarem Zustandsraum ein, die mittels eines verbundenen, reduzierten Modells mit endlichem Zustands- und Aktionsraum, welches wir das Skelett nennen, untersucht werden können. Insbesondere erhalten wir ein Turnpike Theorem für das ursprüngliche Modell (Theorem 2 im Abschnitt 5) von einem bekannten Turnpike Theorem für das reduzierte endliche Modell. Zur Erläuterung stellen wir im einzelnen eine Anwendung dieses Ansatzes für ein Lagerhaltungsmodell (Wiederherleitung eines bekannten Turnpike Ergebnisses) dar, und wir skizzieren analoge Ergebnisse für ein Kassenhaltungsmodell und ein Wachstumsmodell.

     

On the relationship of goal programming and utility functions

Summary We solve the problem under which circumstances the set of solutions of a goal program may also be considered as the set of points maximizing a continuous, concave, isotonic utility function. The converse question is also answered, and there are given conditions ensuring the efficiency of the optimal points of a goal program.

---

Zusammenfassung Es werden Bedingungen für die Effizienz der Lösungen eines goal program entwickelt, ferner wird gezeigt, wann die Lösungsmenge eines goal program ebenfalls durch Maximierung konkaver, stetiger, isotoner Nutzenfunktionen zu erhalten ist. Schließlich wird die umgekehrte Frage beantwortet, unter welchen Bedingungen an eine Nutzenfunktion die zugehörige Lösungsmenge auch durch ein goal program, das mit einer normerzeugten Metrik arbeitet, induziert wird.

---

---

This research has been supported by the Deutsche Forschungsgemeinschaft, project number 88/3.     

Ein Verfahren zur Lösung parameterabhängiger,nichtlinearer Maximum-Probleme

Zusammenfassung Der Gegenstand dieser Arbeit ist die Behandlung parameterabhängiger Maximum-Probleme mit der Zielsetzung, die optimale Lösung explizit als Funktion des Parameters darzustellen.Zu diesem Zweck wird ein Verfahren entwickelt, das es gestattet, das vorgegebene Parameter-intervall eindeutig so in endlich viele Teilintervalle aufzuteilen, daß sich jedem Teilbereich ein vom Parameter abhängiges Gleichungssystem zuordnen läßt, dessen Lösung mit der optimalen Lösung übereinstimmt. Für Maximum-Probleme mit quadratischer Zielfunktion und linearen Nebenbedingungen sind diese Gleichungssysteme linear. Ihre Auflösung ergibt die Komponenten der optimalen Lösung in der Gestalt von Quotienten gebildet aus Polynomen des Parameters.Als eine Anwendung dieses Verfahrens erhält man eine Methode zur Lösung quadratischer Maximum-Probleme mit streng konkaver Zielfunktion und linearen Nebenbedingungen.

---

Summary In this paper parametric maximum problems are treated with the aim to represent the optimal solution explicitly as a function of the parameter.The method developped to this purpose permits to divide the given parameter interval uniquely into a finite number of subintervals in such a manner that it is possible to attach to each of these a system of equations depending from the parameter the solution of which corresponds with the optimal solution. These systems of equations are linear for maximum problems with quadratic object function and linear restrictions. Their solutions give the components of the optimal solution in the form of quotients of polynoms of the parameter.A further extension of this method enables the solution of quadratic maximum problems with strict concave object function and linear restrictions.

---

---

Diese Arbeit wurde von der Deutschen Forschungsgemeinschaft gefördert.

---

Vorgel. v.:H. Görtler     

Upper bounds for the homogeneous case of a two-dimensional packing problem

A method for determining an upper bound for the homogeneous case of a two-dimensional packing problem is presented in this paper. It is based on an analysis of the problem's structure and can be evaluated as the optimal solution of a non-convex minimization problem which can be transformed to a piecewise linear problem by using its special properties. Finally a comparative analysis of solution quality and time complexity is presented.

---

Zusammenfassung In dieser Arbeit wird ein Verfahren zur Bestimmung oberer Schranken für ein homogenes zweidimensionales Packproblem vorgestellt. Auf der Grundlage von Analysen der Problemstruktur kann man eine obere Schranke als optimale Lösung eines nichtkonvexen Minimierungsproblems ermitteln, das unter Ausnutzung spezieller Eigenschaften in ein stückweise lineares Problem transformiert werden kann. Den Abschluß dieser Arbeit bildet eine vergleichende Analyse von Lösungsqualität und Rechenzeitbedarf.

     

Explizite Lösung des dreidimensionalen Minimax-Standortproblems in der City-Block-Distanz

Zusammenfassung Minimax-Standortprobleme in der City-Block-Distanz sind sowohl in der Ebene als auch im dreidimensionalen Anschauungsraum von praktischer Bedeutung. Das Problem kann in ein lineares Programm umformuliert werden, für dessen Optimallösungen im Fall der Ebene eine gewisse untere Schranke der Zielfunktion stets angenommen wird und die sämtlich explizit angegeben werden können. Verallgemeinert man dieses Vorgehen auf den Raum, so stellt man fest, daß die entsprechende untere Schranke nicht in allen Fällen angenommen wird. Hier erhält man dann schließlich alle Lösungen explizit, indem man auf das duale Problem übergeht. Numerische Beispiele werden angegeben.

---

Summary Rectilinear minimax location problems have practical applications both in the plane and in the three-dimensional space. The problem can be reformulated as a linear program for whose optimal solutions a certain lower bound of the objective function is always attained and which can be given explicitly in case of the plane. Extending this method to space it happens that the corresponding lower bound is not attained in all cases. Here a complete explicit solution set can be obtained by considering the dual program. Numerical examples are given.

     

Bifurcation equation for planar systems of differential equations

An oscillator with a small linear damping forced by a non-linear autonomous perturbation is considered. Conditions for the existence of small periodic solutions are derived. This was already done by Flockerzi [2], but the method of averaging used thereby is rather demanding. Here instead, a more elementary and more tractable approach is presented. In particular an algorithm is given by which all small oscillations as well as their stability are established.

---

Zusammenfassung Es wird ein Oszillator mit einer kleinen linearen Dämpfung und einer nicht-linearen zeitunabhängigen Erregung betrachtet. Die Bedingungen für die Existenz kleiner periodischer Schwingungen werden angegeben. Eine Lösung dieses Problems wurde schon von Flockerzi [2] vorgelegt. Die dabei angewandte Mittelungsmethode ist aber ziemlich aufwendig. In dieser Arbeit wird ein elementarerer und handlicherer Zugang aufgezeigt. Insbesondere wird ein Algorithmus angegeben, welcher es erlaubt, alle kleinen periodischen Schwingungen sowie deren Stabilitätsverhalten zu bestimmen.

     

Ein neues Differenzenverfahren für die Behandlung von Balken und Platten, 1. Teil

Zusammenfassung Es wird ein Differenzenverfahren hergeleitet, welches einerseits exakte Lösungen eines modifizierten Problems erzeugt und andererseits als Näherungsverfahren brauchbar ist. Die Vorteile liegen in der Einfachheit der Herleitung, in der computerorierten Methode und in der Genauigkeit als Näherung.

---

Summary A finite differences method is proposed, which produces on one hand exact solutions of a modified problem and can be used on the other hand as an approximation procedure. The method is simple in its derivation, computer-oriented and extremely accurate as an approximation.

     

Redundante Ungleichungen bei linearen Ungleichungssystemen

Zusammenfassung Es wird ein allgemeines Kriterium für die Identifikation redundanter Ungleichungen bei linearen Ungleichungssystemen angegeben. Das Kriterium wird mit bekannten Kriterien verglichen, und es wird gezeigt, wie man es in einem Spezialfall auf einfache Weise anwenden kann.

---

Summary A general criterion for identification of redundant inequalities of linear inequality systems is given. The criterion is compared with other well-known criteria and it is shown by an example how it can be applied practically in a special case.

     

Blow-up of solutions of semilinear parabolic differential equations

For a semilinear parabolic initial boundary value problem we establish criterions on blow-up of the solution in finite time and give bounds for the blow-up time. We treat several applications in both finite and infinite domains. For comparison, sufficient conditions are also given for the existence of global solutions.

---

Zusammenfassung Für ein semilineares parabolisches Rand- und Anfangswertproblem stellen wir Kriterien für die Explosion der Lösung in endlicher Zeit auf und geben Schranken für die Explosionszeit an. Einige Anwendungen in beschränkten und unbeschränkten Gebieten werden untersucht, wobei wir als Gegenüberstellung auch hinreichende Bedingungen für die Existenz globaler Lösungen angeben.

     

A property of convex piecewise linear functions with applications to mathematical programming

Summary It is proved a lemma on convex piecewise linear functions and there are given some applications of this result to non-linear and parametric programming.

---

Zusammenfassung Es wird ein Hilfssatz über konvexe stückweise lineare Funktionen bewiesen und einige Anwendungen des erlangten Ergebnisses bei nichtlinearer und parametrischer Programmierung werden gegeben.

---

---

Vorgel. v.:H. P. Künzi