Search

The paper presents a method for solving the linear programming problems, which is itself a step towards the generalization of the classical Simlex Method. It replaces two basic variables by two non-basic variables at each iteration. Naturally this will reduce the total number of steps to reach the final solution. The paper also includes the solution of one example to illustrate the applicability of the method. [ABSTRACT FROM AUTHOR]

This paper presents an approach, similar to penalty functions, for solving arbitrary mathematical programs. The surrogate mathematical program is a lesser constrained problem that, in some cases, may be solved with dynamic programming. The paper deals with the theoretical development of this surrogate approach. [ABSTRACT FROM AUTHOR]

This paper introduces a generalization of the frequently discussed problem of finding the optimum redundancy that maximizes the reliability of a network of components. Past work has restricted consideration to arrangements of redundant components called series-parallel networks. This paper allows a much broader class of arrangements called series-parallelseries networks. It is important to consider such arrangements for realistic situations in which components have more than one failure mode, or the combination of parallel paths introduces a failure probability. A dynamic programming algorithm is used to solve the more general problem for the case in which there are no constraints on the optimum solution. The algorithm is extended to handle multiple constraints using dominance and a variety of elimination methods to reduce the storage required in a compurer implementation of the algorithm. Problems with as many as 15 serial components and three constraints have been solved with reasonable digital computer computation times. [ABSTRACT FROM AUTHOR]

This paper describes a stochastic game in which the play terminates in a finite number of steps with probability 1. The game is called a terminating stochastic game. When the play terminates at any step, the play is regarded to reach to an absorbing state in the Markov chain under consideration. Hence, the terminating stochastic game is a nonstationary Markov chain with rewards in which our concern is the transient behavior before absorption. In particular, when one of the players is a dummy, the stochastic game reduces to a Markovian decision process of special type. This paper discusses such games. We introduce a new concept of rewards and formulate three problems arising in the games by linear programming. Finally, numerical examples are presented. [ABSTRACT FROM AUTHOR]

The first part of this paper is concerned with the semi-infinite linear programs studied by Charnes, Cooper and Kortanek. A form of the Farkas lemma stated by Haar appears to apply to such programs and leads to a duality theorem. In this paper an example of a semi-infinite program is given which is consistent and which has a finite minimum. However the dual program is found to be inconsistent. With a variation of the example a situation is exhibited in which both the program and its dual are consistent and have finite extrema. In this case, however, the minimum of the former is not equal to the maximum of the latter. The existence of such a ‘duality gap’ indicates that Haar's statement needs qualification. In the second part of the paper a correct form of Haar's theorem is stated and proved. The proof invokes the infinite programming theory of Duffin and Kretschmer. The last part of the paper develops a new duality theory for infinite programs which, as a special case, insures a weak form of duality for programs typified by the examples. This new duality theory is somewhat simpler than previous theories of infinite programming. [ABSTRACT FROM AUTHOR]

The paper evaluates and compares classes of multi-item inventory problems where joint order of several items may save a part of the setup cost. A cost ratio and simple decision rule are determined for joint versus individual orders in specified cases. The comparisons call for the necessity of a new policy for reorder point-triggered random output multi-item systems. This policy, "the random joint order policy," operates through the determination of a reorder range within which several items can be ordered. The existence of an optimum reorder range is proved, and a computational technique is demonstrated with the help of a machine-interference type queueing model. Under favorable conditions the results exhibited on the diagram of optimum reorder ranges are generally applicable. The random joint order policy model is especially suitable for computer controlled inventory systems. [ABSTRACT FROM AUTHOR]

Status consistency research has been severely criticized for its inability to reconcile certain problems of theory and method. As the validity of these criticisms has become evident, researchers have turned from classic research designs to more powerful methods. One popular approach has incorporated typological procedures based on two-factor profiles of status inconsistents. In this paper, a serious fault of the two-factor technique is delineated, and the analysis of differences between types is shown to be without substance. Researchers are provided with a simple procedure for avoiding this pitfall before research is initiated, and elementary combinatorial analysis is utilized to derive a proper procedure. Two research designs, a 2 × 4 and a 3 × 4, receive special attention because of their popularity and complexity, respectively. [ABSTRACT FROM AUTHOR]

This paper develops an algorithm for pure integer programming problems. It first transforms the integer programming problem to an algebraically equivalent Hermite canonical problem, and then employs the Fourier-Motzkin elimination. These algebraic operations transform the problem into a form that leads to an efficient implicit enumeration scheme to calculate an optimal solution. The algorithm constructs, in a finite number of operations, an optimal solution to an integer program with n variables and n or n + 1 inequality constraints. If the original problem has more than n + 1 constraints, then the integer program with only the constraints that are binding at an optimal linear programming solution is solved in place of the original problem. Computational results are presented. [ABSTRACT FROM AUTHOR]

This paper considers a class of optimization problems characterized by constraints that themselves contain optimization problems. The problems in the constraints can be linear programs, nonlinear programs, or two-sided optimization problems, including certain types of games. The paper presents theory dealing primarily with properties of the relevant functions that result in convex programming problems, and discusses interpretations of this theory. It gives an application with linear programs in the constraints, and discusses computational methods for solving the problems. [ABSTRACT FROM AUTHOR]

This paper considers optimal design models for queuing systems in which the decision variables are the number of servers and the mean rate at which each serves, the total cost per unit time of operating the system is the sum of a service cost per unit time and a waiting cost per unit time, and the optimality criterion is long-run expected average cost per unit time. It is shown that a single-server system is optimal for a wide class of arrival processes and service-time distributions, and for a wide variety of waiting cost functions. [ABSTRACT FROM AUTHOR]

This paper analyzes priority rules that are mixtures of preemption and postponable rules. Whether a preemption occurs is made to depend on some factor in addition to priority class; dependence on the completed portion of service (age) of the lower-priority customer in service and the number of prior preemptions of the lower-priority customer in service are each considered. The stochastic model (without priorities) is that of the M/G/1 queue. The paper obtains first-moment expressions (e.g., expected number of customers in the system) in the steady-state case for each priority class as a function of the particular factor being considered. It then introduces a linear cost model that is a function of expected waiting time and expected number of preemptions, and formulates the problem of finding an optimal rule from each class by considering a parametric class of rules determined by each factor. In each case, conditions are sought for the global optimality of a rule over a class of rules, but results are obtained only after restrictions (e.g., monotone failure rates) on service distributions are imposed. [ABSTRACT FROM AUTHOR]

Many problems of the practicing operations analyst do not fit the standard forms of analytic OR procedures and do not lend themselves to precise optimization methods. The voracious appetite of the computer demands numerical algorithms in order to give answers. Very often an optimum is not absolutely essential to management, as long as the answer is efficient or superior to guesswork. So heuristic approaches are adapted to the problem. This paper presents a heuristic approach to a nonstandard, practical assignment problem. It concerns a problem that the analyst had to solve in the field' at Cape Canaveral (now Cape Kennedy) wherein 74 telemetry channels for 19 missiles had to be assigned to 28 available frequency bands. A conflict for a channel occurs if (a) time for use of the range by the missile channels is demanded and (b) another channel on another missile has the same frequency assignment and also wishes the same time. A conflict means one or more missiles must be denied time on the range, which causes costly delay. It is desirable to assign channels to frequencies (which is done at the time the missile is designed) so as to minimize the total expected amount of conflict (or cost of conflict). This paper shows a general, heuristic (not-necessarily optimum) procedure for handling typical, nonstandard assignment problems and gives details of the Cape Kennedy application. This is an example of what can happen 'in the field' when standard mathematical forms are not available. [ABSTRACT FROM AUTHOR]

The author responds to the paper "The Loading Problem," by Eilon and Christofides. He focuses on suggesting a solution to the problem. The recommended solution involves a heuristic algorithm that allegedly requires fewer computations than the one proposed by Eilon and Christofides. It is suggested that the simpler algorithm offered by the author reaches mathematical optimization as often as the aforementioned algorithm. It is further proposed that the algorithm presented by Eilon and Christofides cannot be used to solve multi-dimensional programming problems. The author goes on to discuss a numerical analysis that can be used for the allocation of industrial resources. Related mathematical models are discussed in detail. A table comparing the results of the two algorithms is also presented.

This paper considers the maximization of certain equivalent reward generated by a Markov decision process with constant risk sensitivity. First, value iteration is used to optimize possibly time-varying processes of finite duration. Then a policy iteration procedure is developed to find the stationary policy with highest certain equivalent gain for the infinite duration case. A simple example demonstrates both procedures. [ABSTRACT FROM AUTHOR]

A framework of concepts is developed which helps to unify a substantial portion of the literature on large-scale mathematical programming. These concepts fall into two categories. The first category consists of problem manipulations that can be used to derive what are often referred to as "master" problems; the principal manipulations discussed are Projection, Inner Linearization, and Outer Linearization. The second category consists of solution strategies that can be used to solve the master problems, often with the result that "subproblems" arise which can then be solved by specialized algorithms. The Piecewise, Restriction, and Relaxation strategies are the principal ones discussed. Numerous algorithms found in the literature are classified according to the manipulation/strategy pattern they can be viewed as using, and the usefulness of the framework is demonstrated by using it (see Part II of this paper) to rederive a representative selection of algorithms. The material presented is listed in the following order: The first section is introductory in nature, and discusses types of large-scale problems, the scope of discussion and the literature, and the notation used. The second section, entitled "Problem Manipulation: Source of 'Master' Problems" covers the subjects of projection, inner linearization and outer linearization. The third section, "Solution Strategies: Source of 'Subproblems'," discusses piecewise strategy, restriction and relaxation. The fourth section is entitled "Synthesizing Known Algorithms from Manipulations and Strategies," and is followed by a concluding section and an extensive bibliography. [ABSTRACT FROM AUTHOR]

In this paper the Fiacco-McCormick SUMT technique is embedded in a class of inside-out algorithms. Convergence is demonstrated for the nonlinear programming problem under fairly general conditions and the algorithms are interpreted in a geometric structure. [ABSTRACT FROM AUTHOR]

Beckmann [1] and Mills [7] consider production smoothing problems in which demands are random variables. This paper generalizes and extends Beckmann's results which predicate backlogging of excess demand. Convex expected holding and penalty cost functions pertain to inventory and the cost of changing the production rate is proportional to the change. The model has a finite horizon and permits nonstationary costs and demand distributions. Beckmann shows that two curves in the plane determine an optimal policy (minimum expected discounted cost) each period. It is shown here that the curves have slopes between minus one and zero, are differentiable, and are bounded by two straight lines with a slope of minus one. The results are not changed by an upper bound on the quantity produced or by a lag between the time a product is manufactured and the time it is available to satisfy demand. [ABSTRACT FROM AUTHOR]

This paper deals with the application of dynamic programming to systems whose duration is uncertain, and which duration may or may not be a function of the decisionmaker's policy. It extends some of Bellman's work in that the transformed states at successive stages may not have the properties demanded by Bellman; e.g., the state norm need not diminish at all, and can, in fact, increase. The paper deals primarily with computational considerations since, in general, analytic solutions to functional equations are not forthcoming. Both discrete and continuous formulations are considered, the appropriate one to choose depending on the number of states one wishes to cater for, the continuous formulation having certain advantages which the discrete case does not have when a very large number of states are to be differentiated. [ABSTRACT FROM AUTHOR]

The article presents a test to determine the optimal time temperature at which pork and gravy should be processed during canning for the maximum palatibility to the consumer. The test uses a mathematical optimization technique when the variables involved represent consumer preferences. 135 respondents rated preference samples from six different meat packing plants, rating each sample on a nine-point scale from "extremely disliked" to "extremely liked." An equation is derived from the data collected and the confidence limits are described. Some other applications for the test are also discussed.

Optimization techniques are widely used in many areas and frequently developments of a technique in one area open up opportunity for its use in other areas. This paper presents examples of how the newer techniques have contributed to the improvement in technological processes.
After a brief discussion of optimization, available optimization techniques are classified and the principles of constraint and uncertainty programming outlined.
The application of current techniques to design problems in various production disciplines are then discussed and the Appendix presents some problem solutions. [ABSTRACT FROM AUTHOR]

This paper considers tandem queues for which the order of performing service tasks can be changed, the service times being independent of this order. It determines the optimal order of service when either the service times of different tasks are nonoverlapping or, for two queues in tandem, the service time of one task is constant. For the optimal ordering, the waiting time of every customer is stochastically smaller than for any other. [ABSTRACT FROM AUTHOR]

Copyright of INFOR is the property of Taylor & Francis Ltd and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

This article presents a response to an article discussing the majority rule under transitivity constraints, by V.J. Bowman and C.S. Colantoni, published in a previous issue. The authors say that the original papers' optimization model was a linear integer programming problem. They believe a quadratic assignment type of the optimization model is better suited to the problem.

This paper examines the problem of finding the sequencing of a finite set of expansion projects that meets a deterministic demand projection at minimum discounted cost. For the particular situation defined, the timing for a next ex-. pansion may be determined directly from knowledge of projected demand and present capacity. A dynamic programming formulation for sequencing projects is developed, and solution of an example problem demonstrates that other methods proposed for this problem are not, in general, valid, Extensions of the dynamic programming formulation to include interdependence between projects and joint selection of project scale and sequencing are indicated, conditions far decomposition or direct solution of the sequencing problem are derived. [ABSTRACT FROM AUTHOR]

This paper derives the mean time and the Laplace-Stieltjes transform of the distribution of the first time to system-down for a two-unit standby redundant system when failure of the unit in standby is allowed. Further, it shows that special cases of the results obtained hers coincide with earlier results for the two-unit standby redundant system and the two-unit parallel redundant system. Finally, it discusses numerical examples and some interesting models. [ABSTRACT FROM AUTHOR]

This paper considers an efficient algorithm for finding the optimal design of a module under a special set of circumstances that prevail in the design of a module for logistical applications. The method is based on primal-dual relations between generalized polynomial minimization and its quasi dual. [ABSTRACT FROM AUTHOR]

Given a mathematical program, this paper constructs an alternate problem with its feasibility region a superset of the original mathematical program. The objective function of this new problem is constructed so that a penalty is imposed for solutions outside the original feasibility region. One attempts to choose an objective function that makes the optimal solutions to the new problem the same as the optimal solutions to the original mathematical program. [ABSTRACT FROM AUTHOR]

This paper deals with the solution to a discrete optimization problem by decomposition. It develops a criterion for ranking the decomposition procedures, discusses the properties of the optimal decompositions, and gives an algorithm for finding the best decomposition in the case of no storage limitation. [ABSTRACT FROM AUTHOR]

This paper describes an algorithm, based on a recently proposed method due to D.D. Morrison, for solving constrained optimization problems, and shows that it compares favorably with existing methods in several examples. [ABSTRACT FROM AUTHOR]

This paper considers the problem of optimum allocation of redundant elements in a simple series system (maximizing system reliability subject to several linear cost constraints). Under the approximation that the components of the redundancy vector can be treated as continuous variables, the paper formulates this optimization problem as a geometric programming problem, describes techniques for obtaining numerical solutions in general, and obtains asymptotic closed-form solutions. A standard numerical example is used to illustrate that the asymptotic solution, when suitably rounded, compares favorably with the discrete optimal solution. [ABSTRACT FROM AUTHOR]

This paper describes an algorithm that will yield the minimum make-span sequence for n-jobs requiring processing through M-machines when no passing is allowed. Theoretical development utilizing combinatorial analysis and proof of sequence optimality precedes the algorithm and an example problem. [ABSTRACT FROM AUTHOR]

This paper establishes the relation between two approaches for solving two-stage programming under uncertainty with discrete distribution function. To accomplish this we use optimality conditions and a simple change in variables. We also review, as special cases, a transportation problem and a production-inventory model. For the transportation model we show that any of the corresponding deterministic equivalent linear programs represents a directed network. For the inventory problem we show that the demand constraints can be eliminated in the equivalent linear program. Finally, a stochastic Leontief production model is introduced. Under reasonable assumptions, we establish that its solution can be obtained by solving a certainty Leontief program. Also, we show that the optimal selection of alternative substitute activities is independent of the demand distribution. [ABSTRACT FROM AUTHOR]

This article focuses on the computational aspects of dynamic programming. Dynamic programming is a method of solving multi-stage decision-process problems. Several computational difficulties are characteristic of all dynamic-programming solutions. In the theory of dynamic programming one find dealing with functions whose arguments are states of a system and whose values are optimal yields. In dynamic programming of low dimension the functions are generally defined by a table of values calculated at a grid of points. For problems of increased complexity it may prove desirable to approximate these functions. In this way only the appropriate coefficients need be computed at each iteration of the recurrence relation. The evaluation of a 10-dimensional function at only 10 grid points in each dimension would generate or 10 billion numbers. Yet this same function might be adequately defined by only 100 parameters of a suitably chosen approximating form. Furthermore, if one is dealing with analytic functions rather than tabular ones, tools of mathematical analysis such as calculus can be used to determine the maximum required by equation otherwise slower search techniques must be employed.

This paper is an extension of previously published work by Bernard O. Koopman to the general case of any number of tasks and any effect function. A systematic method for the numerical calculation of the maximum effect and its corresponding optimum distribution is presented in a form which is also suitable for solution on an automatic digital computer. For the special case of additive returns which saturate, a special graphical or numerical method for any number of tasks is presented with an example worked out in detail A similar method for multiplicative effects is sketched. [ABSTRACT FROM AUTHOR]

Suppose there are n men available to perform n jobs. The n jobs occur in sequential order with the value of each job being a random variable X. Associated with each man is a probability p. If a "p" man is assigned to an "X = x" job, the (expected) reward is assumed to be given by px. After a man is assigned to a job, he is unavailable for future assignments. The paper is concerned with the optimal assignment of the n men to the n jobs, so as to maximize the total expected reward. The optimal policy is characterized, and a recursive equation is presented for obtaining the necessary constants of this optimal policy. In particular, if p1 ≦ p2 ≦ ߪ pn the optimal choice in the initial stage of an n stage assignment problem is to use pi if x falls into an ith nonoverlapping interval comprising the real line. These intervals depend on n and the CDF' of X, but are independent. of the p's. The optimal policy is also presented for the generalized assignment problem, i.e., the assignment problem where the (expected) reward if a "p" man is assigned to an "x" job is given by a function r(p, x). [ABSTRACT FROM AUTHOR]

A number of analytic formulations of resource allocation activities in decentralized organizations have considered the effects of economic or technological externalities but most treatments have neglected concomitant organizational or behavioral effects. This paper introduces the concept of a behavioral externality and relates it to the decision-making process in decentralized organizations. Alternative analytic formulations of behavioral externalities are examined, and a numerical example is presented. [ABSTRACT FROM AUTHOR]

The decomposition of a finite partially ordered set of elements as a union of chains was considered by Dilworth [2]. Dantzig and Hoffman [1] formulated this problem as a linear programming problem and obtained Dilworth's theorem from duality theory. For some practical applications and for a method to obtain a minimal decomposition see Ford & Fulkerson [3]. In this paper we generalise this problem to the case when the set is not necessarily partially ordered and obtain a method of finding a minimal chain decomposition of the set. [ABSTRACT FROM AUTHOR]

If the constraint matrix of a linear program has special structure it may be possible to speed computation. Techniques have been developed to take advantages of such special structures as generalized networks, generalized upper bounding, and decomposition. For these matrix structures, it is shown in this paper how to extend the techniques to Zangwill's mathematical programming algorithm, the convex simplex method. [ABSTRACT FROM AUTHOR]

This paper treats a Markov decision problem with an infinite planning horizon and no discounting. This model is analyzed by application, perhaps repeated, of a simple linear program. [ABSTRACT FROM AUTHOR]

This paper presents an algorithm for the solution of the knapsack problem. The method involves searching the nodes of a tree along a single branch at a time. The algorithm eliminates the computational drawbacks inherent in the usual branch and bound schemes. [ABSTRACT FROM AUTHOR]

Conditions which are necessary and sufficient for convergence of a nonlinear programming algorithm are stated. It is also shown that the convergence conditions can be easily applied to most programming algorithms. As examples, algorithms by Arrow, Hurwicz and Uzawa; Cauchy; Frank and Wolfe; and Newton-Raphson are proven to converge by direct application of the convergence conditions. Also the Topkis-Veinott convergence conditions for feasible direction algorithms are shown to be a special case of the conditions stated in this paper. [ABSTRACT FROM AUTHOR]

In this paper, a dynamic continuous time model of the firm, encompassing operations and investments, is formulated as an optimal control problem in an activity analysis context. In the model, the objective of the firm is to maximize, subject to various constraints, the discounted value of operating profits less the costs of new capacity and the interest on borrowed funds (or plus the interest on savings) over a fixed decision-making interval plus the discounted value of capacity at the end of the period. The state variables are capacity and debt, and the controls are scale of operation and rate of purchase of new capacity; the final capacity and debt are control parameters. There are several inequality constraints. Using results in control theory, the optimal controls are determined for the case the rate of production is linear in the scale variable, the growth of capacity is linear in the rate of purchase of new capacity and the attrition of capacity is linear in the amount of capacity. Extensions of the model are made to include multiple processes. [ABSTRACT FROM AUTHOR]

Let us consider some particular optimization problem. Most of its data is determined by the economic "environment". However, this environment is evolutive, and may be the subject of an optimization research. The particular problem first considered then appears to be a suboptimization, and its results will be valid only if it is separable from its environment. This point of view can be expressed in mathematical terms by considering a "principal" programming problem from which one tries to separate a "reduced" subproblem. The concept of "separability" is defined and studied in the first part of this paper. In the second part, it is used to justify the "Method of Extended Models" as a tool for building optimization models. [ABSTRACT FROM AUTHOR]

A machine is to be bought, used for productive purposes for a length of time, and then sold. It is possible to do preventive maintenance while the machine is being used, if desired, in order to slow down the degradation of the machine's capability. The value of owning the machine is the sum of the discounted value of its production while it is owned plus its discounted value when sold. In this paper a modification of a model due to B. Naslund for the problem is discussed. Using Pontryagin's maximum principle, the problem is treated as one of optimal control with the control variables being the use or nonuse of preventive maintenance and the selection of the sale date. It is shown that the optimal maintenance policy is bang-bang, and methods for finding the optimal sale date are determined. Simply examples show the various kinds of solutions that can be obtained with varying assumptions concerning the actual functions used in the model. [ABSTRACT FROM AUTHOR]

This paper focuses upon the problem of a monopolist who has no control over the rate of arrivals into inventory and who ships his product to distant markets where the price per unit is a randomly shifting inverse function of the quantity shipped, it is assumed that the firm seeks to minimize its expected losses over a many-period horizon where the quantity shipped during any period is subject to last minute reconsideration. Given certain assumptions about the cost and revenue functions and the level of inventory, it will be shown that the optimal shipping quantity is a linear function of the storage level and that the solution of the many-period nonstationary problem can be expressed in closed form. [ABSTRACT FROM AUTHOR]

In certain problem areas it is not possible to establish one objective function. There may be several, sometimes conflicting, goals. This paper presents a method of reconciling such conflicting goals by establishing a global objective function. A combinatorial example is given and solved by "modified" dynamic programming. [ABSTRACT FROM AUTHOR]

This paper characterizes optimal service policies in terms of the frequency and timing of services which are intended to maintain a stock of assets. The model is non-stochastic. The results are obtained by a two-stage step-wise minimization procedure wherein dynamic programming is first used to characterize sub-optimal policies and then the calculus of finite differences is utilized to select the optimal policy. The effect of the time horizon on the optimal policy is emphasized throughout and, in two specific interpretations of the model, the classical results of the economic lot-size and equipment replacement policy are shown to be limits of more general policies. [ABSTRACT FROM AUTHOR]

The designing of some multi-factor "analytical" studies of survey data is considered in this paper. It is assumed that, for each factor, there are two categories of interest and these are to be compared. The main objective is to allocate the sample so that the desired precision for the specified contrasts is obtained at minimum cost. It is assumed that one may sample independently in each of the sub-populations under investigation. A model is employed to facilitate designing and analyzing such a survey. We discuss the relevance of this model for "analytical studies," and a few examples are presented. Several survey objectives are explored, and an optimal allocation is obtained for each. Two, three and four-factor studies are considered explicitly. [ABSTRACT FROM AUTHOR]

Investigation is continued of inventory models in which customer good will is lost when stockout occurs. Several models are formulated and optimal policies for the firm are derived conceptually (i.e., algebraic equations satisfied by the optimal parameter values are determined). Both constant and distributed demand are considered, and it is shown that the same formulation applies to both. [ABSTRACT FROM AUTHOR]