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.

     

A weak duality theorem for stochastic linear programming

Summary A linear programming problem is said to be stochastic if one or more of the coefficients in the objective function or the system of constraints or resource availabilities is known only by its probability distribution. A distinction is usually made between two related approaches to stochastic linear programming, the active and passive approach respectively. An extension of the duality theorem of non-stochastic or deterministic programming problem has been attempted in this paper in the area of stochastic linear programming in its two approaches. The method of proof is based on the idea that since the parameter space defined by a stochastic linear programme is the topological product of the real line with itself, it forms a first countable topological space. Using a set of distinct and selected points in the parameter space the concepts of feasibility, optimality and duality are extended to stochastic linear programming problems of arbitrary dimensionality. Based on the non-singular regions of the parameter space of a stochastic linear programming problem the theorem utilizes the conditions of convergence of the sequence of distinct and selected points in the parameter space to a limit point and thereby generalizes the duality theorem in the stochastic case. Furthermore it is shown that the regions of feasibility of the active and passive approaches of stochastic linear programming may be different, so that on this basis it may be possible to establish some inequality relations for the optimal solutions defined for the respective feasible regions.

---

Zusammenfassung Ein lineares Programmproblem wird stochastisch genannt, wenn ein oder mehrere Koeffizienten der Zielfunktion oder des Systems der Beschränkungen oder der verfügbaren Ressourcen nur durch ihre Wahrscheinlichkeitsverteilung bekannt sind. Gewöhnlich wird zwischen zwei verwandten Verfahren für das stochastische lineare Programmieren unterschieden, dem aktiven und dem passiven Verfahren.In der vorliegenden Arbeit wird versucht, das für nichtstochastische oder deterministische Programmprobleme gültige Dualitätstheorem unter Berücksichtigung beider Verfahrensweisen auf den Bereich des stochastischen linearen Programmierens auszudehnen. Der Beweis gründet sich auf den Gedanken, daß der Parameterraum einen abzählbaren topologischen Raum bildet, da er — durch ein stochastisches lineares Programm definiert — das topologische Produkt der reellen Achse mit sich selbst ist. Unter Benutzung einer Menge von verschiedenen und ausgewählten Punkten im Parameterraum werden die Begriffe der Zulässigkeit, der Optimalität und der Dualität auf stochastische lineare Programmprobleme beliebiger Dimension ausgedehnt. Auf der Grundlage nichtsingulärer Bereiche des Parameterraumes eines stochastischen linearen Programmproblems benutzt das Theorem die Bedingungen für die Konvergenz einer Folge verschiedener und ausgewählter Punkte des Parameterraumes nach einem Grenzpunkt und verallmeinert damit das Dualitätstheorem für den stochastischen Fall. Weiter wird gezeigt, daß die Zulässigkeitsbereiche der aktiven und passiven Verfahren des stochastischen linearen Programmierens verschieden sein können, so daß es möglich sein kann, gewisse Ungleichungen für die optimalen Lösungen aufzustellen, die für die entsprechenden zulässigen Bereiche definiert sind.

     

Equivalence of various linearization algorithms for linear fractional programming

This paper considers four algorithms for linear fractional programming and show that they are all Frank Wolfe type linearization algorithms. These algorithms are those proposed by Isbell and Marlow, Mangasarian, Bitran and Novaes; and Bhatt. It is shown that these algorithms all use essentially the same sequence of l.p.s to generate the same sequence of feasible points that leads to the optimal solution.

---

Zusammenfassung In dieser Arbeit werden vier Algorithmen zur linearen Quotientenoptimierung betrachtet und es wird gezeigt, daß alle vier Linearisierungsverfahren vom Frank Wolfe-Typ sind. Die betrachteten Algorithmen wurden von Isbell und Marlow, Mangasarian, Bitran and Novaes sowie von Bhatt vorgeschlagen. Es wird gezeigt, daß diese Verfahren alle im wesentlichen dieselbe Folge von linearen Programmen erzeugen und damit dieselbe Folge von zulässigen Punkten, die zur Optimallösung führt.

     

OnR.W. Llewellyn's rules to identify redundant constraints: A detailed critique and some generalizations

In his book Linear Programming [1964]Llewellyn devoted a chapter to simplifications and reductions of a linear programming problem by means of algebraic rules. These rules are claimed to be rather general. Here we give some counterexamples, where the rules ofLlewellyn do not hold. Furthermore we give some general rules to identify redundant constraints in the caseLlewellyn considers and show that the original rules ofLlewellyn together with an extra condition are a variant of these general rules. Finally we consider the question whether or not the rules ofLlewellyn should be used to identify redundant constraints.

---

Zusammenfassung Bereits 1964 hat sichLlewellyn in seinem Buch Linear Programming mit der Vereinfachung von linearen Programmen durch Ermittlung redundanter Nebenbedingungen beschäftigt. Der von ihm für seine Regeln erhobene Anspruch der Allgemeingültigkeit wird in diesem Beitrag durch Gegenbeispiele widerlegt. Ferner werden allgemeine Regeln zur Identifikation redundanter Nebenbedingungen hergeleitet und gezeigt, daß diese die Regeln vonLlewellyn, sofern man sie um eine zusätzliche Bedingung erweitert, umfassen.

     

Stresses in a transversely isotropic elastic cone under an asymmetric force at its vertex

Zusammenfassung Behandelt wird das Problem eines transversal isotropischen Körpers, der durch zwei konzentrische Kegelflächen begrenzt ist und durch eine asymmetrische Kraft an der Spitze belastet wird. Geschlossene Ausdrücke werden gegeben für den Spannungszustand und die Verformung. Ein interessanter Spezialfall ist das Cerruti-Problem, wo eine konzentrierte Kraft tangential an der Oberfläche eines elastischen Halbraumes wirkt. Die Lösung ist exakt im Rahmen der linearen Elastizitätstheorie.     

A note on superposition in Mindlin's problem

The problem of a half-space subjected to an interior concentrated force is posed as a superposition problem. For a free plane boundary it is shown that the boundary condition of traction may be expressed directly through the normal derivative of a harmonic Green's function by means of a linear operator. These circumstances at once generate the classical result. For a clamped boundary such a procedure becomes cumbersome and direct integration, in a manner proposed by Sanders, is performed.

---

Zusammenfassung Das Problem eines Halbraumes, der von einer inneren konzentrierten Kraft beeinflußt ist, wird als ein Überlagerungsproblem betrachtet. Für einen freien Rand wird so gezeigt, daß die Randbedingung des Spannungsvektors durch die Ableitung in der normalen Richtung einer harmonischen Greenschen Funktion mittels eines linearen Operators ausgedrückt werden kann. Diese Umstände ermöglichen sofort die Lösung des klassischen Problems. Für einen eingespannten Rand ist eine solche Lösungsmethode umständlich und eine direkte Integration, in einem Verfahren wie von Sanders vorgeschlagen, wird durchgeführt.

     

A note on non-uniqueness in linear elasticity theory

Zusammenfassung Es wird mit Hilfe von Gegenbeispielen gezeigt, dass die Annahme eines stark elliptischen Tensors der Elastizitätsmoduln für Spannungsaufgaben und gemischte Probleme der linearen Elastizität und sogar für das Verschiebungsproblem im Fall eines inhomogenen Körpers keine Eindeutigkeit garantiert. Für den Spezialfall eines isotropen Materials mit verschwindender Kompressibilität wird ein Ausdruck für die allgemeinste (nicht-eindeutige) Lösung des Spannungsproblems bei verschwindenden Oberflächenspannungen gegeben.     

A perturbation approach to the main duality theorem of quadratic geometric programming

Quadratic geometric programming as introduced by Hough and Goforth is an extension of posynomial geometric programming. By using the theory of generalized geometric programming, Jefferson and Scott defined its exact geometric dual. The fundamental relationship between the geometric dual and the original problem is that they assume a common value at their respective optima. This result formally stated as the main duality theorem is proved in this paper by using a dual perturbation approach and two simple geometric inequalities. As a by-product, the insight provided by this constructive proof establishes a numerically precise dual based solution procedure for quadratic geometric programs.

---

Zusammenfassung Die quadratische geometrische Optimierung wurde von Hough und Goforth eingeführt und stellt eine Erweiterung der posynomialen geometrischen Optimierung dar. Jefferson und Scott definierten unter Verwendung der verallgemeinerten geometrischen Optimierung ein duales Programm und leiteten Dualitätsbeziehungen ab, u. a. die Übereinstimmung der Optimalwerte des primalen und dualen Programms. Letzteres Resultat wird in der vorliegenden Arbeit unter Verwendung eines dualen Störproblems und zweier einfachen geometrischen Ungleichungen hergeleitet. Gleichzeitig macht die Beweismethode es möglich, ein Verfahren zur Lösung quadratischer geometrischer Optimierungsprobleme anzugeben.

     

Verallgemeinerungen in der Struktur und Erweiterungen in der Zeitanalyse bei Vorgangspfeil-Netzplänen

Zusammenfassung In diesem Beitrag zur Netzplantechnik wird eine verallgemeinerte Struktur für Vorgangspfeilnetze vorgestellt. Ein entsprechendes Verfahren zur Ermittlung der Ereignis- und Vorgangszeitpunkte wird beschrieben. Es wird eine verbesserte Berechnung von Pufferzeiten dargestellt und eine Interpretation gegeben.

---

Summary In this paper a generalized network approach is presented for Critical Path Planning. A corrected computation of floats is described and an interpretation is given.

     

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.

     

Discussion and modification of the Fandel-method solving linear vector maximum problems

Summary In this paper, the convergence-model of Fandel for determining an optimal compromise solution for a vector maximum problem is discussed. It will be shown that applied to linear vector maximum problems, the method will not always generate efficient compromise proposals and under certain conditions fails. A modification of the method is proposed which eliminates the demonstrated shortcomings.

---

Zusammenfassung In dieser Arbeit wird das Konvergenzmodell von Fandel zur Bestimmung einer optimalen Kompromißlösung eines Vektormaximumproblems diskutiert. Es wird gezeigt, daß das Verfahren für lineare Vektormaximumprobleme nicht immer effiziente Kompromißvorschläge erzeugt und daß es unter bestimmten Voraussetzungen versagen kann. Es wird eine Modifikation des Verfahrens vorgeschlagen, wodurch die aufgezeigten Mängel beseitigt werden.

     

Höhensteuerung eines Tagesspeicherkraftwerks

Zusammenfassung Der während eines bestimmten Zeitraumes, etwa einem Tag, anliegende Zufluß soll optimal in Energie umgesetzt werden, m.a.W. die Energieausbeute pro Tag soll maximiert werden. Es wird ein Tagesspeicherkraftwerk betrachtet, bei dem die Kapazität des Zuflußstollens von der jeweiligen Speicherhöhe abhängt.Das grundsätzliche Verhalten des Systems wird zunächst an einem Modell mit linearen Kennlinien und an Hand von idealisierten Zuflußsituationen studiert. Anschließend wird ein Modell, worin reale Kennlinien und Zuflußsituationen stückweise linear approximiert werden, formuliert und numerisch gelöst.

---

Summary A given influx during a certain time interval, say a day, is to be transformed into energy in an optimal way. In other words the production of energy per day is to be maximized. We discuss a small hydro energy storage plant (one day's reservoir capacity) where the capacity of the influx tunnel depends on the actual head of the reservoir.First we analyse the system with the help of a simplified model with both linear tunnel capacity and linear reservoir volume function and piecewise constant influx. Then reality is modelled with piecewise linear approximation and the system is solved numerically.

---

---

Die Arbeit wurde im Rahmen des Projekts Nr. 3472 vom Fonds zur Förderung der österreichischen Forschung unterstützt. Dem Fonds sei an dieser Stelle herzlich gedankt.     

A spectral algorithm for sequential aggregation ofm linear diophantine constraints

An algorithm is developed for the sequential determination of the coefficients of a generalized linear Diophantine constraint which is equivalent to a given system of generalized linear Diophantine constraints.

---

Zusammenfassung Ein Algorithmus wird entwickelt für die sequentielle Bestimmung der Koeffizienten einer verallgemeinerten linearen Diophantischen Restriktion, die einem vorgelegten System verallgemeinerter linearer Diophantischer Restriktionen äquivalent ist.

     

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     

Ein lexikographischer Suchalgorithmus zur Lösung allgemeiner ganzzahliger Programmierungsaufgaben

Zusammenfassung In dieser Arbeit wird ein slexikographischer Suchalgorithmus zur Lösung von allgemeinen diskreten Optimierungsaufgaben, bei denen Zielfunktion und Restriktionen beliebige Funktionen sein können, angegeben. Es handelt sich hierbei um ein spezielles Branch-and-Bound Verfahren, bei welchem die übliche Schrankenbedingung (Bound) nicht als Auswahlkriterium, sondern nur als Verwerfkriterium benutzt wird. Die Auswahlstrategie ist lexikographisch. Die Anwendbarkeit des Verfahrens auf ganzzahlige und gemischt-ganzzahlige Programmierungsprobleme und auf besondere Spezialfälle sowie auf diophantische Gleichungs- und Ungleichungssysteme wird diskutiert. Außerdem werden alle anderen bekannten Verfahren zur ganzzahligen Programmierung kurz erwähnt und deren Rechenzeiten und Effizienz mit den entsprechenden Daten des Suchalgorithmus an Hand von zahlreichen Testbeispielen verglichen.

---

Summary This paper presents a lexicographic search algorithm for solving general discrete optimization problems with arbitrary objective functions and constraints. It is a special branch-and-bound method in which the bound condition is used only as a reject criterion, but not as choice criterion. The choice strategy of the algorithm is lexicographical. The practical use of this method for integer and mixed integer programming and for solving systems of diophantine equations and inequalities is demonstrated. Moreover, there is a short discussion of all other known integer programming methods and of their computing time and efficiency compared with the search algorithm. This comparison is made by means of numerous test problems.

     

Lineare Charakterisierungen von Travelling Salesman Problemen

Zusammenfassung Wir betrachten die Formulierung des asymmetrischen Travelling Salesman Problems als lineares Programm und leiten mehrere Klassen neuer Ungleichungen ab, die eineschärfere Charakterisierung des Travelling Salesman Polytopen (konvexe Hülle der Touren) in Form von Ungleichungen ergeben.Es zeigt sich, daß einige der neuen Ungleichungen und auch einige der bekannten Kurzzyklus-Bedingungen tatsächlich Facetten des Travelling Salesman Polytopen sind, d.h. daß sie zu der Klasse von Ungleichungen gehören, die die konvexe Hülle aller Touren einesn-Städte Problems in eindeutiger Weise charakterisiert.

---

Summary We consider the linear programming formulation of the asymmetric travelling salesman problem. Several new inequalities are stated which yield asharper characterization in terms of linear inequalities of the travelling salesman polytope, i.e. the convex hull of tours.In fact some of the new inequalities as well as some of the well-known subtour elimination constraints are indeedfacets of the travelling salesman polytope, i.e. belong to the class of inequalities that uniquely characterize the convex hull of tours to an-city problem.

     

Das Problem der Diensteinteilung von Lokomotiven

Zusammenfassung Das Problem der Diensteinteilung von Lokomotiven wird mit Hilfe der Graphentheorie dargestellt. Es wird gezeigt, daß jedem Fahrplan ein Graph G zugeordnet werden kann, und daß die Symmetrie eines Fahrplans die notwendige und hinreichende Bedingung für seine periodische Realisierbarkeit ist. Ein Verfahren zur Bestimmung der optimalen Diensteinteilung wird angegeben. Mehrfach periodische Fahrpläne werden in Betracht gezogen.

---

Summary The problem of engine-scheduling is presented in terms of graph-theory. It is shown that each time-table can be represented by a graph G, and that the symmetry of a time-table is the necessary and sufficient condition for its periodical realizability. A method for the determination of an optimal engine-schedule is presented. Time-tables with multiple periods are taken into consideration.

---

---

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

The deflection and buckling of a beam-column with a one-sided constraint

Zusammenfassung Das Problem eines horizontalen, gelenkig gelagerten Stabes mit VertikalkraftQ am Mittelpunkt und mit axialer DurchlastP wird behandelt. Eine Durchbiegung infolgeQ wird jedoch durch eine Bodenebene verhindert. Die gekrümmten Formen des Stabes werden durch die lineare Stabtheorie und durch die Theorie der Elastika bestimmt. Die letztere ergibt eine Vergabelung der Gleichgewichtslagen, die in der linearen Theorie nicht erscheint. Schliesslich wird die Stabilität des geraden Stabes behandelt. Das kinetische Kriterium, das Energiekriterium und das klassische, auf nichttrivialen benachbarten Gleichgewichtslagen sich beziehende Kriterium werden alle in Betracht gezogen. Alle zeigen, dass eine beliebig kleine VertikalkraftQ die kritische DurchlastP um mehr als das Achtfache erhöht. Das heisst,P geht von der Knicklast für den gelenkig gelagerten Stab über auf die Knicklast für den halblangen, einerseits eingebauten Stab. Es wird gezeigt, dass die klassischen Kriterien in diesem Falle irreführend sind. Nicht nur die Grösse vonQ, sondern auch die der erwarteten Störung muss berücksichtigt werden.     

Ein heuristisches Verfahren zum Entwurf nachfrageorientierter Linienführung im öffentlichen Personennahverkehr

Zusammenfassung Auf einem gegebenen Verkehrsnetz ist ein Linienplan in der Weise zu entwerfen, daß unter Einhaltung betrieblicher Bedingungen eine möglichst geringe mittlere Reisezeit pro Verkehrswunsch erreicht wird. Ein heuristisches Verfahren zur Erzeugung nachfrageorientierter Linien wird für dieses Reihenfolgeproblem vorgestellt. Auf Grundlage der Verkehrsstromgrößen werden die Netzelemente nach Prioritäts- und Austauschregeln zum Linienplan verknüpft.

---

Summary On a given traffic network public transport routes must be designed in such a manner, that a low average travelling for the user will be achieved with regard to constraints of service. A heuristic procedure is represented to obtain demand oriented traffic routes. The elements of the network are connected according to rules of priority and exchange on the basis of traffic flow.

---

---

Diese Arbeit wurde im Rahmen des von Prof. Dr. H.H. Weber betreuten Forschungsprojekts Entwicklung eines Programmablaufs zur Berechnung von nachfrageorientierten Netzen des öffentlichen Personennahverkehrs auf Grundlage eines Planungsinformationssystems We 372/5 durch die Deutsche Forschungsgemeinschaft gefördert.     

A note on the effect of submerged obstacles on water waves in a channel

Summary By combining the results due to Jeffrey and Mvungi [1], with the work of Jeffrey and Saw Tin [2, 3], the transmission and reflection properties of an acceleration wave propagating on the surface of water at rest in a vertical walled channel of arbitrary continuously varying width and piecewise continuously varying depth are determined. An explicit expression derived for the amplitude of the transmitted wave as a function of position by Jeffrey and Mvungi is used to find the effect of a discontinuous change of depth on the wave amplitude and to derive a criterion for the breaking of the wave.

---

Zusammenfassung Durch Kombination der Resultate von Jeffrey und Mvungi [1] mit denen von Jeffrey and Saw Tin [2, 3] wird die Transmission und die Reflexion einer Beschleunigungswelle an der Oberfläche von ruhendem Wasser berechnet, in einem Kanal mit vertikalen Wänden, dessen Weite beliebig kontinuierlich und dessen Tiefe abschnittsweise kontinuierlich variiert. Ein expliziter Ausdruck für die Amplitude der durchgelassenen Welle in Funktion der Lage nach Jeffrey und Mvungi wird dazu benützt, um den Effekt einer Diskontinuität in der Tiefe zu finden und ein Kriterium für das Brechen der Welle herzuleiten.