Operations Research

Im Jahre 1967 schlug Blum ein Modell für Wahrnehmungsprozesse vor. Dieses Modell ist ein frühes Beispiel eines neuronalen Netzwerks. Unabhängig von seiner Bedeutung in der Wahrnehmungsphysiologie hat dieses Modell eine erhebliche Bedeutung in der Praxis der Bildverarbeitung gewonnen, da es sich leicht algorithmisch umsetzen läßt. Die daraus entwickelten Verfahren — sogenannte Verdünnungs- oder Skelettierungsalgorithmen — fanden weite Verbreitung als Vorverarbeitungsverfahren in der Bildverarbeitung.

We consider the following vertex enumeration problem:

The present article is connected with the article “About a special class of nonconvex optimization problems” (Grygarová 1990). This article deals with such nonconvex optimization problems (NOPs), feasible sets of which are so-called spherical polyhedrons (a spherical polyhedron is the intersection of a polyhedral cone having a vertex at the origin point a with a hypersphere with the centre at a) and objective functions are special nonconvex continuous strictly monotone functions of a certain argument. In the article of Grygarová (1990) it was proved that such NOP is globally solvable and that its optimal solution set (the set of all optimal points) represents a closure of a face of the considered spherical polyhedron. On the basis of these results we can suppose that there exists a certain close connection between such NOPs and linear optimization problems. It appears that these NOPs can be transfer into equivalent linear optimization problems.

The concepts of stationarity and pseudo duality (P.D.) were introduced in Passy and Yotav(1980). It was shown how to calculate pairs of P.D. programs via Legendre transformation. Despite the fact that the class of functions having such transform is restricted, it was possible to generate P.D. to a large class of programs. The techniques that were used in Passy and Yotav (1980) could be applied again and it is assumed, without loss of generality, that all functions treated in the present paper have a Legendre transform. It will further be assumed that the reader is familiar with the notation and terminology used in Passy and Yotav (1980).

Let us consider the following nontrivial decision problems. The president of a company faces a number of opportunities for producing and selling new products, and needs to decide which to undertake. His problem is complicated by the following:

This investigation is a continuation of the considerations in Guddat et al. (1985), Guddat and Guerra Vasquez (1987), Guddat et al. (to appear) using pathfollowing methods with jumps (cf. e.g. Gfrerer et al. 1983, Gfrerer et al. 1985, Guddat 1987, Guddat et al. to appear, Guddat et al. 1988, Guddat and Nowack 1990, Jongen 1988) based on information on the singularities (cf. Jongen et al. 1986a, Jongen et al. 1986b).

For many years mathematical optimization models with a single objective function subject to a set of rigid constraints have enjoyed extensive and successful application. These models are relatively simple, and a wide variety of computer software is readily available to efficiently find optimum solutions to such models. However, despite the obvious popularity of this approach, the “optimum” solution it provides may not be the best solution to a real world problem, and in many cases other approaches may be preferable.

The problem to be solved is the multiple objective linear program (MOLP) where S is the feasible region in decision space. Let \(Z \subset {R^k}\) be the feasible region in criterion space. Criterion vector \(\bar z \in Z\) iff there exists an \(\bar x \in S\) such that \(\bar z = ({c^1}\bar x,...,{c^k}\bar x)\). A point \(\bar x \in S\) is efficient iff there does not exist any x∈S such that \({c^i}x \geqslant {c^i}\bar x\) for all i and \({c^i}x > {c^i}\bar x\) for at least one i. A criterion vector is nondominated iff its inverse image is an efficient point. The set of all efficient points is the efficient set E and the set of all nondominated criterion vectors is the nondominated set N. Methods for computing all efficient extreme points and characterizing the entire nondominated set have been developed by Ecker et al. (1980), Fandel (1972), Gal (1977), Gal and Leberling (1981), Isermann (1977), and others.

Consider an even number n=2m of persons who must be paired, e.g., as roommates. It is assumed that the combined utilities or values to both partners in such a pairing can be discovered and are equal to

At first we consider two well-known deterministic single-machine scheduling problems (for the basic concepts and results from deterministic scheduling we refer to Lawler et al. 1982). In the min-max problem 1 ∣prec∣f _max, “1” stands for a single machine, “prec” means that the precedence constraints for the jobs are given by an acyclic directed graph, and the objective function f _max to be minimized is the maximum of nondecreasing functions f _v where f _v (t) is the cost arising when job v is completed at time t. The min-sum problem 1∣prec∣Σ w _v C _v says that the weighted sum of the completion times C _v of the jobs v (the so-called weighted flow-time) is to be minimized and the precedence constraints are given by an outtree. Both problems can be solved in polynomial time. For more general precedence constraints or more general objective functions, single-machine min-sum scheduling problems become NP-hard. For example, the problems 1∣prec∣Σ C _v (where all job weights are equal to one) and 1∣∣Σw _v T _v (where there are no precedence constraints for the jobs and T _v is the tardiness of job v) are NP-hard. Thus in deterministic scheduling, min-sum problems seem to be less tractable than min-max problems.

The applied statistician/econometrician who has to select an estimation method needs information about the relative performance of two or more estimators under empirically relevant conditions. The term “empirically relevant conditions” refers e.g. to small samples, to the presence of specification errors and to an econometric model which ist “complicated” in the following sense: It contains a large number of interdependent variables (equations), it is dynamic; its exogenous variables are not free of measurement errors, are autocorrelated and the data are collinear; at least some observable variables are cointegrated; the disturbances in the equations are autocorrelated within and across equations and are perhaps also heteroskedastic. Even more complicated are models which also contain present and future model consistent (= “rational”) expectations variables.

Die lineare Programmierung hat sich als nützliches Instrument der Betriebswirtschaftslehre erwiesen, mit dessen Hilfe Planungsprobleme in den einzelnen betrieblichen Teilbereichen, insbesondere in der Produktion und im Absatz sowie in der Investition und der Finanzierung abgebildet werden können; erst der Einsatz dieser Verfahren hat es ermöglicht, Konzepte einer bereichsübergreifenden Simultanplanung zu entwickeln.

In den letzten 10 bis 15 Jahren hat die Untersuchung und Lösung multikriterieller Entscheidungsprobleme eine stürmische Entwicklung genommen (siehe z.B. Fandel und Spronk 1985). Unterschiedlichste Verfahren wurden entwickelt, die von den nutzentheoretischen Ansätzen der Multi-Attributiven-Nutzentheorie (MAUT (Keeney und Raiffa 1976)) über interaktive Algorithmen (siehe z. B. Isermann 1979) bis hin zu den „konfliktanalytischen“Prävalenzverfahren der sog. französischen Schule (ELECTRE (Roy 1980), ORESTE (Pastijn und Leysen 1989) reichen.

Die Entwicklung der Elektronischen Datenverarbeitung (EDV) ist geprägt durch

Beim Eintritt in das Rentenalter wird sich jeder rational handelnde Mensch Gedanken darüber machen, wie das im Laufe des bisherigen Lebens akkumulierte materielle Vermögen verwendet werden soll. Dieses Vermögen besteht grundsätzlich aus zwei Teilen: aus Rentenansprüchen, die gewöhnlich bis zum Lebensende reichen sowie aus Realkapital und Finanzaktiva, die bei Bedarf veräußert und deren Erlös dann in Konsumgüter umgewandelt werden können. Die Entscheidungen, die vom Individuum getroffen werden müssen, beziehen sich zum einen auf die Höhe und die Verteilung der Konsumausgaben für die restliche Lebensspanne und zum anderen auf die Höhe des Vermögens, das der Betroffene seinen Kindern bei seinem Tod vererben möchte. Schenkungen zu Lebzeiten brauchen dabei nicht gesondert betrachtet zu werden; man kann sie wie Konsumakte des Schenkers behandeln. Zwischen der Planung des Konsumstroms und der beabsichtigten Höhe des Nachlasses besteht offensichtlich ein enger Zusammenhang: vererbt werden kann nur, was vorher nicht konsumiert worden ist.

For an overlapping-generations model with 2-period life-cycles for individuals and monopolistic competition in the goods markets, Chang (1989) demonstrates that deflationary monetary policy supported by lump-sum taxation is able to implement a Pareto-optimal allocation as stationary perfect-foresight equilibrium. He himself raises the question whether his “conclusions are robust to other assumptions about the nature of competition or the monetary sector” (p. 20). In Chang’s model fiat money is valued because it is the only store of value available to young individuals. In the present paper the positive value of money in equilibrium is secured by a cash-in-advance constraint on individual transactions. Furthersmore, the life-cycle OLG-structure is replaced by what Blanchard and Fischer (1989, pp. 115–122) call a “model of perpetual youth”, i.e. overlapping cohorts of individuals with infinite planning horizons but constant and identical finite life expectancies. In other respects this model does not differ significantly from Chang’s. There is also neither storage nor capital accumulation, and, in particular, monopolistic competition is likewise introduced via the now standard simple assumption of commodity heterogeneity with constant elasticity of substitution in consumption as discussed, e.g., by Blanchard and Fischer (1989, pp. 376–381). It turns out, however, that due to the role of money as means of payment imposed by the cash-in-advance constraint, Chang’S conclusions have to be significantly qualified: Monetary policy and lump-sum taxes alone cannot support a stationary perfect-foresight equilibrium that is Pareto-optimal.

Die Theorie der Geldpolitik geht implizit davon aus, daß sich die monetären Aktivitäten der Zentralbank auf einen homogenen Währungsraum richten. Er ist nicht nur durch die einheitliche Währung gekennzeichnet sondern insbesondere auch dadurch, daß die monetären Verhaltensweisen der Wirtschaftssubjekte und die monetären Transmissionsabläufe innerhalb des Währungsraumes einheitlich sind. Regionale Differenzierungen in den monetären Bedingungen liegen nicht vor, oder sie sind so gering, daß sie für die Geldpolitik irrelevant bleiben. Die Notenbank kann sich daher nur an gesamtwirtschaftlichen, über den gesamten Währungsraum aggregierten Daten orientieren, nicht aber an wirtschaftlichen Daten der einzelnen Regionen des Währungsraumes.

Most of the work which has been carried out in the field of portfolio theory, capital market theory under risk and theoretical work in finance based on the CAP- models, assumes that means and variances of the uncertain rates of return on the portfolios are known exactly. These informational assumptions have been generalized into two directions:

Firstly, informational asymmetries between different groups of investors and/ or their agents have been taken explicitly into account.¹⁾ Two basic cases of asymmetric information are considered. In the first case one group of investors (e.g. the shareholders) can not observe the actions taken by a second group (e.g. the management). This “hidden action” problem²⁾ may result in decisions of the second group which are not in the interest of the first. Interestingly, this additional risk introduced by the unobservability of actions can not be resolved by the capital market if only simple debt and equity contracts are available. But this moral hazard problem can be solved by the introduction of new contracts (e.g. options) which, therefore, are explained positively by the fact of unobservable actions.³⁾ In the second case of informational asymmetry one group of investors (e.g. old shareholders) has better information about the quality of the firm than the second (e.g. new shareholders). This “hidden information” problem⁴⁾ may result in an phenomenon called “adverse selection”.⁵⁾ Both types of asymmetric information lead to a better understanding of the financial behavior of firms and help to explain the wide variety of existing financial instruments and institutions.

Die empirische Marketingforschung dient im wissenschaftlichen Kontext in erster Linie Grundlagenuntersuchungen zum Verhalten von Marktteilnehmern und zur Wirkungsweise von Marketinginstrumenten. Die Fragestellungen der Praxis beziehen sich dagegen eher auf die quantitative Abschätzung gegenwärtiger und zukünftiger Märkte sowie die Vorbereitung von Entscheidungen bezüglich der Gestaltung und des Einsatzes konkreter Marketingmaßnahmen. Für beide Anwendungsbereiche ist das methodische Instrumentarium weitgehend identisch. Auch der Methodenbereich der empirischen Marketingforschung kann in zwei große Bereiche eingeteilt werden: Datenerhebung und Datenanalyse. Über lange Zeit stand dabei die Datenanalyse im Vordergrund des wissenschaftlichen Interesses. Gründe dafür sind u. a. in der Ausbreitung der multivariaten Analyseverfahren in der Marketingforschung während der 70er und 80er Jahre und in der durch die Statistik geprägten Geringschätzung von Problemen und Fehlermöglichkeiten bei der Datenerhebung („Daten fallen an.“) zu sehen. Hinzu kommt, daß bis vor einigen Jahren davon ausgegangen wurde, daß bei der Entwicklung von Meßinstrumenten (z. B. Fragebögen) Erfahrung und Kreativität des Forschers ein relativ großes Gewicht gegenüber formalisierten Vorgehensweisen haben (vgl. z. B. Noelle-Neumann 1963, S. 72ff.).

Das Frachtoptimierungsproblem (FOP) entstammt dem Bereich des Güterfernverkehrs, der im gewerblichen Transport von Gütern mit Lastkraftwagen (Lkw) besteht. Ein mit einem Lkw von einem Spediteur oder Frachtführer besorgter Transportauftrag umfaßt in der Regel mehrere Teilaufträge. Jeder Teilauftrag sieht die Versendung einer Gütermenge gleicher Güterart von einem Belade- zu einem Entladeort vor. Das Entgelt für die Beförderung eines Teilauftrags, das je nach Vereinbarung vom Versender oder Empfanger zu tragen ist, bezeichnet man als Fracht. Entsprechend sei als Gesamtfracht das Entgelt für den Transport einer Menge von Teilaufträgen mit einem Lkw bezeichnet.

Dem zweidimensionalen Packproblem P(L, B; l, b) liegt die folgende Aufgabenstellung zugrunde: Auf einer rechteckigen Grundfläche mit der Länge L und der Breite B ≤L ist eine maximale Anzahl identischer rechteckiger Packstücke mit der Länge l und der Breite b ≤l orthogonal anzuordnen. Bislang ist zur Lösung dieser Aufgabenstellung kein optimierender Lösungsalgorithmus mit polynomial begrenzter Zeitkomplexität bekannt. Jedoch lassen sich Heuristiken zur Lösung des zweidimensionalen homogenen Packproblems (vgl. z. B. Dowsland und Dowsland 1983, Isermann 1987, Naujoks 1990) erfolgreich einsetzen, da über die Bestimmung einer oberen Schranke für die Anzahl der auf der Grundfläche orthogonal anzuordnenden Packstücke in den meisten Fällen die Optimalität der durch die Heuristik ermittelten Lösungen nachgewiesen werden kann. Aus diesem Grunde sind in den letzten Jahren Verfahren zur Bestimmung immer schärferer oberer Schranken für die Anzahl der auf der Grundfläche orthogonal anzuordnenden Packstücke entwickelt worden (Dowsland 1983, Isermann 1987, Naujoks 1990). Im Rahmen dieses Beitrags sollen auf der Basis einer Analyse polyedrischer Mengen Möglichkeiten der Ermittlung noch schärferer oberer Schranken vorgestellt werden.

In the empirical determination of the production technology of firms in a certain industry, the indirect approach using dual variables (prices) has more and more superseded the direct estimation using primal variables (input and output quantities). For obvious econometric reasons,²⁾ it is much easier to achieve unbiased estimates of the parameters of the cost function - or, for firms that can freely choose their output levels, of the profit function - than of the underlying production function itself.

An investigation of case studies conducted by the author in cooperation with Tomas Gal and others shows that cutting stock (or trim loss) problems are of great importance in some industries (Dyckhoff et al. 1988). Furthermore, they are strongly related to packing and other problems (Dyckhoff 1990).

The just-in-time (JIT) delivery of products is a considerable challenge for many firms, because suitable planning methods have to be developed and practically installed. One main problem refers to the suppliers’ strategy, as they are no longer able to keep their optimal lot sizes and production rates due to customers’ reduced call-forward rates (cf. e.g. Fandel et al. 1988 and Fandel 1988). Thus, the suppliers have to choose different planning procedures in order to assure that there will be no avoidable in-process costs, as concerns particularly the production, inventory, and transportation of products. Obviously, there exist remarkable trade-offs between the design parameters of the whole process (cf. Reese 1991), which require a simultaneous optimization of all variables.

Kostenberücksichtigende Prüfplanung findet in den letzten Jahren zunehmend Beachtung in der einschlägigen Literatur zur Qualitätssicherung. Seit den bahnbrechenden Arbeiten von Hald (1960) und Guthrie und Johns (1959) haben zahlreiche Autoren eine explizitere Berücksichtigung von Kosten gefordert, als dies bei den klassischen Prüfplänen der Fall ist. Für eine eingehende Diskussion der Berechnung von kostenoptimalen Plänen bei Attributenprüfung in Losen und bei bekannter a-priori-Verteilung des Ausschußanteils sei beispielhaft auf Fitzner (1979) und Hald (1981) hingewiesen. Rödder (1990) erweitert diese Grundidee zu einem lernenden EDV-System zur kostenoptimalen Stichprobenprüfung, indem er nicht nur das Bayes-Risiko für die Berechnung des Stichprobenplans verwendet, sondern auch bayessch aus der Qualitätshistorie Informationen über die Prozeßkurve gewinnt. Er errechnet dann bei Eingang eines jeweils neuen Loses unter Verwendung der (a-priori)-Information über die erwartete Qualitätslage einen kostenoptimalen Stichprobenplan (n, c). Die Idee, der Verfahrensablauf, Simulationsvergleiche mit dem konkurrierenden System Mil Std 105 D bzw. DIN 40080, sowie die optimale Prüfplanberechnung bei Vorhandensein mehrerer attributiver Merkmale sind in der oben zitierten Arbeit beschrieben; über weitere Aspekte wie z.B. das zeitliche Verhalten des Prüfablaufs sowie die Berücksichtigung von beschränkter Prüfkapazität berichten Reidmacher und Rödder (1990) bzw. Rödderu.a. (1990).

Das Gebiet der Produktionsplanung und -Steuerung (PPS) umfaßt die Gesamtheit von Dispositionen, die auf die Festlegung eines Absatz- bzw. Produktionsprogramms und die Bestimmung des Vollzugs dieses Programms in mengenmäßiger und zeitlicher Hinsicht ausgerichtet sind. Entsprechend dieser Charakterisierung sind im Rahmen einer umfassenden Produktionsplanung und -Steuerung folgende Entscheidungsvariablen zu bestimmen:

Im Rahmen der wissensbasierten Systeme haben Expertensysteme (ES) in den letzten Jahren besonderes Interesse gefunden. Die Definitionen solcher Systeme reichen von „Expert systems are problem-solving programs that solve substantial problems generally conceded as being difficult and requiring expertise“(Stefik u. a. 1982) bis hin zu „An expert system is regarded as the embodiment within a computer of a knowledge-based component from an expert still in such a form that the system can offer intelligent advice or take intelligent decision about a processing function. A desirable additional characteristic, which many would consider fundamental, is the capability of the system, on demand, to justify its own line of reasoning in a manner directly intelligible by the inquirer. The style adopted to attain these characteristics is rule-based programming“(Holroyd 1985).