Search

Commentary is presented for an article published in the July 1960 issue of "Management Science," written by L. V. Kantorovich with an introductory note by T. C. Koopmans. According to the author, in his introduction Koopmans addresses in particular a linear programming problem and a matrix game presented by Kantorovich. Also presented is an interpretation of the article's treatment of decision variables and mathematical optimization. The author notes that the article presents algorithms that have been improved from their contemporary presentations.

Copyright of International Journal of Production Research 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.)

In an earlier paper [5], we generalized and extended Beckmann's results [1] for a production and inventory problem with proportional smoothing costs and demands being random variables. Our previous results concerned the finite horizon nonstationary case. Here we consider the infinite horizon stationary case. Two curves in the plane determine an optimal policy. They are shown to have slopes between minus one and zero, to be differentiable, and to be bounded by two straight lines with a slope Of minus one. These results are used (a) to accelerate each iteration of a successive approximations algorithm and (b) to formulate a linear programming problem from whose solution an optimal policy can be determined. [ABSTRACT FROM AUTHOR]

A new conceptual and analytical vehicle for problems of temporal planning under uncertainty, involving determination of optimal (sequential) stochastic decision rules is defined and illustrated by means of a typical industrial example. The paper presents a method of attack which splits the problem into two non-linear (or linear) programming parts, (i) determining optimal probability distributions, (ii) approximating the optimal distributions as closely as possible by decision rules of prescribed form. [ABSTRACT FROM AUTHOR]

Markov duels are a general class of stochastic duels in which each weapon has Markov-dependent fire, that is, the outcomes of shots by each weapon form a Markov process. This paper develops duel models for the situation in which the outcomes form a finite stationary Markov chain and both weapons have an unlimited supply of ammunition, fire at constant intervals of time, and duel until one is killed. Based on these assumptions, the probability of a given side winning the duel is obtained for two sets of starting conditions: (1) both weapons begin with unloaded weapons and have tactical equity, and (2) one weapon has the advantage of surprise and can fire y rounds at the other before the two-sided duel begins, where y is a random variable with a geometric distribution. The mean and variance of the number of rounds to kill a passive target are also derived and two example duels are solved. Finally, methods are indicated for obtaining the solution to a Markov duel between weapons having exponential firing times and either fixed, limited ammunition supplies or infinite supplies. [ABSTRACT FROM AUTHOR]

This paper presents a theoretical basis for cost-effectiveness analysis. It is argued that, frequently, a range of effectiveness or cost levels may be acceptable to whoever must ultimately decide which military system (if any) should be acquired. The function of the analyst is to present a schedule of alternatives and not to optimize in the sense that he recommends the selection of a particular alternative. The formulation of the schedule is discussed where the cost and effectiveness associated with each alternative are viewed as random variables. The paper concludes with some general observations relating to military system selection. [ABSTRACT FROM AUTHOR]

This paper studies some of the theoretical questions of large opemngs or gaps in a single stream of traffic A gap in the traffic stream is defined as a headway between vehicles greater than or equal to some minimum size -- say x Several authors have studied the probability distribution of the wait that a randomly located observer must endure before he finds a gap This paper, while briefly reviewing the solutions of this well-known problem, is primarily concerned with expressions for (i) the distribution of gap sizes, (ii) the distribution of spacings between vehicles and gaps, (iii) the mean and variance of intervehicle and intergap spacings, (iv) the stationary flow rates of gaps, and (v) the distribution of blocked and unblocked periods It is assumed that the origin of measurements may be located (i) with the passing of a vehicle, (ii) at the beginning of a gap, or (iii) at random It is also assumed that the distribution of intervehicle spacings are independently, but identically, distributed random variables. [ABSTRACT FROM AUTHOR]

The variables ξ[SUB1], , ξ[SUBn] have a joint normal distribution We are concerned with the calculation or approximation of max(ξ[SUB1], , ξ[SUBn]) Current analyses and tables handle the case in which the ξ, are independently distributed with common expected values and common variances This paper presents formulas and tables for the most general case with n=2 When n>2, the problem becomes cumbersome This paper presents formulas and tables that permit approximations to the moments in case n>2 The moments are approximated by iteration of a three-parameter computation or, alternatively, through successive use of a three-parameter table, which is given Recent applications of the theory are described. [ABSTRACT FROM AUTHOR]

A renewal process is defined to represent the present value of a stream of money payments occurring at random times. The objective is to partially close a gap in the state of knowledge regarding the properties (asymptotic behavior) of certain cashflow models, scheduling models, and inventory models, all of which can be embedded in the context of replacement-reliability theory in general. The contribution of this paper is a characterization of the asymptotic distribution of a general capitalized random variable as the time-invariant rate of discount approaches zero. The main result is a central limit theorem demonstrating that the standardized distribution of the discounted random variable converges to the unit normal as the discount rate approaches zero. [ABSTRACT FROM AUTHOR]

This paper is concerned with characterizing decision rules for the sequential E-model of chance-constrained programming. A key feature of our characterization will be a detailed discussion of various interpretations of the probability operator in the chance constraints. Specifically we define two new classes of decision rules by exhibiting those sets of constraints which locally support the corresponding probability requirements. The question of how the probabilistic constraints for future periods are affected by previous decisions and realizations of the random variables is considered in detail. Since we are primarily concerned with the feasibility of decision rules, we deal mainly with the constraints of the model. The procedure for selecting the optimum rule from among a particular class of feasible rules depends on the objective function and is briefly discussed in the final section along with some implications concerning the form of the optimum rule. The application of our proposed rules to a two-period example previously appearing in the literature concludes the paper. [ABSTRACT FROM AUTHOR]

This paper develops a linear periodic review inventory model in which the reorder rule is an extension of the "order up to S" or (S, T) policy where S varies as a general linear function of demand and net inventory. Stationary and non-stationary demand processes are considered. Lead time is assumed to be an integral multiple of the review period and, at most, an independent and identically distributed random variable. Analysis of the model includes stability, transient response, steady-state response, and the effects of common nonlinearities. [ABSTRACT FROM AUTHOR]

In a team decision problem there are two or more decision variables, and these different decisions can be made to depend upon different aspects of the environment, or information variables, the resulting payoff being a random variable. The choice of optimal rules for selecting information variables and for making decisions is the central problem of the economic theory of teams. This paper shows, by means of an example, how linear programming can be applied to obtain optimal team decision functions in the case in which the payoff to the team is a convex polyhedral function of the decision variables. [ABSTRACT FROM AUTHOR]

The paper is concerned with randomized experiments with one treatment. Two randomization schemes are considered: randomized pairs and unrestricted randomization. If effective at all, the treatment is supposed to affect the conditional distribution of the "experimental" variable Y given another variable X, called "predictor". The distribution of X is not affected by the treatment. Using the general theory published elsewhere, the paper deduces the locally asymptotically optimal test of the hypothesis that the treatment has no effect. Apart from the usual difficulties connected with asymptotic tests (how large must N be?), the theory is easily applicable in many "live" cases even though the conditional distribution of Y given X may contain nuisance parameters and be of unusual form. [ABSTRACT FROM AUTHOR]

The article comments on the paper "Comparative Values of Information Structures," by Theodore J. Mock, that appears in the December 1, 1969 issue of the "Journal of Accounting Research." The author states that the statistical tests conducted by him assume that profit differences are independent random variables obtained in random sample. He explains that the participants of the study do not apparently comprise a random sample of a larger universe of businessmen or students. He states that these particular observations are not a random sample of how the particular subjects might perform out of a large number of repetitions of the experiment given random starting conditions.

This paper concerns developing methods for approximating a chance-constrained set when any information concerning the random variables must be derived from actual samples. Such a situation has not been presented in the literature. When existing chance-constrained programming techniques are used, it is not possible to relate the accuracy of sample-based assumptions to actual constraint satisfaction. The methods presented here employ the concept of a distribution-free tolerance region to construct various sets whose elements have the common property of satisfying the chance constraint with a preassigned level of confidence. The sample size required to meet the desired confidence is readily available in tabular or graphical form. [ABSTRACT FROM AUTHOR]

This paper shows that analytical techniques can be applied in the analysis of a wide class of combat problems by specializing the inputs of a general functional model. The generating functions of the losses, and the corresponding expected values and variances, are derived and expressed as integrals with respect to a supplementary time variable. [ABSTRACT FROM AUTHOR]

This paper provides a computational technique for the evaluation of the distribution of the net present value (NPV) of an investment, in which the cash inflows occur at random time points, as in the case of venture capital. The initial cash outlay is deterministic and the magnitudes of the cash inflows are nonnegative, random variables with known distributions. The lengths of the intervals between successive cash inflows are independently distributed and independent of the magnitude of the inflows. The Laplace transforms and the first two moments of the distribution are computed for both independent and perfectly correlated inflows. It is shown that the use of constant time intervals when the timing of the inflows is random underestimates the variance of the distribution of the NPV. [ABSTRACT FROM AUTHOR]

This paper presents an improved stochastic model for the behavior of the daily census and associated waiting variables in general-acute hospitals. The development and form of the distributions derived follow the general approach of a previous paper by Shonick [J. Amer. Statist. Assoc. 65, 1474–1500 (1970)], but greater flexibility is provided for the health-services planner by increasing the number of decision choices available for achieving given outcomes. This increased flexibility is attained via a generalization of the queuing discipline, permitting admissions of elective patients to be suspended when the number of occupied beds reaches a predetermined level (which may be less than the total bed complement). For any emergency-elective mix of the demand for hospitalization, this model permits the computation of many measures of operating efficiency, including expected overfill rate, percentage occupancy, waiting-list length, and loss of emergency patients. A variant of the model permits computation of the expected number of patient days that will be served in ‘nonapproved’ facilities when emergencies arriving during ‘full’ periods are accommodated therein, rather than turned away. [ABSTRACT FROM AUTHOR]

This paper considers the use of antithetic variates to reduce the variance of estimates obtained in the simulation of a GI/G/1 queue. Two experimental configurations are considered: in the first, 2n observations are taken in a single run; in the second, n observations are taken in each of two runs. If the sequences of uniform random variables that generate the realizations of the queuing system in the two runs are antithetic, we show that the variance of estimates of the mean and distribution of stationary waiting time and number in the queue is less in the second configuration than in the first. We also obtain sufficient conditions for the covariance of functions of a vector of uniform random variables to be nonnegative. Experimental results are given for M/M/1 queuing simulations to illustrate the magnitude of the variance reduction. [ABSTRACT FROM AUTHOR]

This paper evaluates the queue-length distribution, the busy-period density and other characteristics of the finite-source queuing process in which the server remains idle until a queue of n units is built up. It also determines values of n that optimize the net profits for discounted, as well as undiscounted, infinite-horizon models. [ABSTRACT FROM AUTHOR]

This paper presents a computational procedure for the solution--via reduction to a parametric quadratic program--of the 'minimum-risk problem' associated with a stochastic linear program where costs are random variables with normal multidimensional joint distribution, i.e., for the nonlinear program max[subx&isinX] (c'x--t)/(x'Vx)[sup1/2] where t is a given number, V a positive-definite matrix, and X a given convex polyhedron in n-dimensional Euclidean space R[si[n]. [ABSTRACT FROM AUTHOR]

Multistage minimum-cost network-flow analysis solves many practical problems in production-inventory-distribution, marketing, personnel, and finance. Unlike previous network papers, which generally restricted themselves to a deterministic situation, this paper investigates the stochastic environment. Starting from the standard multistage network-flow problem, we create a stochastic network by permitting the node requirements to be discrete random variables with known conditional probability distributions. Our goal is to determine the minimum-expected-cost flow and thereby solve the problem. Although linear programming under uncertainty can determine this flow, it would ignore the special structure of network-flow problems that allows development of computationally efficient algorithms. In this paper, we instead exploit the underlying network structure to produce both a new structure that is not a network but maintains many of the properties of a network, and a new node that replicates flows instead of conserving them. The new nodes, called replication nodes, together with the new structure, allow the development of an efficient computational algorithm that is capable of solving problems much larger than those solvable by linear programming under uncertainty. [ABSTRACT FROM AUTHOR]

This paper studies a particular random tour (continuous random walk): A particle moves in two dimensions at constant speed by choosing successive travel directions that are independent and uniformly distributed between 0 and 2π, with the lengths of the steps between direction changes being independent, exponentially distributed, random variables. An analytic expression for the probability density of the particle's position after a time t is derived, and an application is made to a military situation where the 'particle' is a target trying to escape being destroyed by an unseen enemy. The bulk of the paper is devoted to deriving the density function. [ABSTRACT FROM AUTHOR]

For a service facility serving more than one class of customers a problem arises as to the order in which customers should be served (i.e., the priority rule). A typical example is a manufacturing facility that produces two products to meet a random stream of incoming orders. In this paper the alternating priority nile (also known as the `zero switch rule') is introduced and investigated. Two classes of customers are served by a single service facility. Customers of class i(i= 1, 2) have priority over customers of class j(j=I, 2; ≠1) whenever a class i customer is in service. When the service facility is idle, the first arriving customer enters service and acquires the priority right for customers of his class. Within classes the `first-come, first-served' rule is observed. Customers' arrivals are assumed to be Poisson and service times are assumed to be arbitrarily distributed in- dependent random variables. The steady-state densities of queuing times are formulated by the use of a special mathematical procedure. The expectations of queuing times and sizes of queues as well as the first two moments of the busy periods are obtained in terms of the basic parameters of the arrival process and service time distributions. All the results are related to the case where switching from one type of customers to another is not penalized by setup time. The alternating priority rule is compared to the 'head-of-the-line' and the 'first-come, first-served' rules with respect to expected queuing times and queue sizes. The last part of the paper discusses the possibilities of extending the suggested rule to cases involving more than two classes of customers and nonzero setup times and setup costs. [ABSTRACT FROM AUTHOR]

The conventional analysis of variance applied to designs in which each subject is measured repeatedly requires stringent assumptions regarding the variance-covariance (i.e., correlations among repeated measures) structure of the data. Violation of these assumptions results in too many rejections of the null hypothesis for the stated significance level. This paper considers several alternatives when heterogeneity of covariance exists, including nonparametric tests, randomization and matching procedures, Box and Greenhouse-Geisser corrections, and multivariate analysis. The presentation is from an applied rather than theoretical standpoint. Multivariate techniques that make no covariance assumptions and provide exact probability statements represent the most versatile solution. [ABSTRACT FROM AUTHOR]

In this paper we consider chance constrained programming problems with joint constraints shown in the literature to be equivalent deterministic nonlinear programming problems. Since most existing computational methods for solution require that the constraints of the equivalent deterministic problem be concave, we obtain a simple condition for which the concavity assumption holds when the right-hand side coefficients are independent random variables. We show that it holds for most probability distributions of practical importance. For the case where the random vector has a multivariate normal distribution, nonexistence of any efficient numerical methods for evaluating multivariate normal integrals necessitates the use of lower bound approximations. We propose an approximation for the case of positively correlated normal random variables. [ABSTRACT FROM AUTHOR]

This paper presents simplified techniques for analyzing the effect of uncertainty in large decision problems. Starting with the development of approximate expressions for the moments of a value lottery, we show that the probabilistic assessments of jointly related random variables necessary for these approximations are quite reasonable in number. The concepts of risk aversion, certain equivalent, and exponential utility function then permit writing useful approximations for the certain equivalent of the value lottery. Deterministic sensitivity analyses are described first for the case when the decision variables are fixed and then for the case when they can be changed to compensate for variations in state variables. The approximate effect and value of clairvoyance (revelation of ultimate values of uncertain variables) is derived from the original probabilistic assessment and the results of the deterministic sensitivity analysis, we next determine the approximate value of wizardry (changing uncertain variables into decision variables). The amount by which decision variables must be adjusted to account for risk aversion is established from earlier results. The final portion of the paper discusses a simple economic example that illustrates the application of the development. [ABSTRACT FROM AUTHOR]

This paper presents results for queueing systems that are characterized by poisson arrival epochs with χ (a random variable) arrivals at each epoch, exponential service times and c servers. The steady state probabilities, the probability of blocking (not being served immediately) for both loss and delay systems are investigated. In addition, the average delay, the variance of the delay and the delay distribution for first-come-served by batches and arbitrary order of service within batches are presented. [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 describes a model for a computer stimulation designed to analyze and forecast the financial posture of a computer leasing company as a subsidiary to a large corporation. The simulation considers the rate of market growth, the year of the introduction of fourth generation hardware and the year that the computer manufacturers act to impede the growth of the leasing industry, as random variables. Other assumptions are input as equations or constants. Financial analyses are performed during a five year simulation period. The means and the 10% and 90% quantile range for several key financial indicators are determined and plotted. [ABSTRACT FROM AUTHOR]

This paper considers the problem scheduling of m immediately available tasks with random variable service times. It is shown that certain such problems can be reduced to equivalent deterministic problems. The existence of optimal schedules not involving the removal from service of incompletely processed tasks for some problems is proved and for other problems is disproved. [ABSTRACT FROM AUTHOR]

The starting point of the paper is a firm engaged in a risky business. It is assumed that the firm's gain in each operating period is a stochastic variable. It is further assumed that these stochastic variables are independent and identically distributed. If the capital of the firm becomes negative, the firm is ruined, and must go out of business. The optimal dividend policy is defined as the policy which will maximize the expected discounted value of the dividends paid before ruin occurs. It is then shown that the solution of the dividend problem gives the utility function, which will govern the firm's decisions under uncertainty. From this result it appears that a number of decisions which seem irrational when studied in isolation, become perfectly rational when analysed in their proper dynamic setting. [ABSTRACT FROM AUTHOR]

In linear programming under uncertainty the two-stage problem is handled by assuming that one chooses a first set of constrained decision variables; this is followed by observations of certain random variables after which another set of decisions must be made to adjust for any constraint violations. The objective is to optimize an expected value functional defined relative to the indicated choices. This paper shows how such problems may always be replaced with either constrained generalized medians or hypermedians in which all random elements appear only in the functional. The resulting problem is called a deterministic equivalent for the original problem since (a) the originally defined objective replaces all random variables by corresponding expected values and (b) the remaining constraints do not contain any random terms. Significant classes of cases are singled out and special attention is devoted to the structure of the constraint matrices for these purposes. Numerical examples are supplied and related to the previous literature. Other properties of these models are also examined and related to types of problems which are often of interest. For instance the hypermedian and generalized median formulations involve minimizations over absolute value terms in the functional. These, in turn, are developed for their possible pertinence in problems where minimizations are to be over the maximum of a set of functions under inequality constraints. Utilizing Moore-Penrose (generalized) inverses, other characterizations are also secured in which all relevant weights and coefficients are stated explicitly in terms of original data. [ABSTRACT FROM AUTHOR]

Consider an infinite-stage inventory process in which the cost of ordering an amount y of stock is ky, and the penalty cost incurred in meeting an excess demand y over the stock on hand is py + q; also, the process assumes that demands at successive stages are random variables drawn from a fixed probability distribution. Then, under conditions described in the paper, the extra costs incurred in using a policy that, instead of minimizing the statistical expectation of the total cost of the process, minimizes that of a process whose parameters are different from those of the process under consideration are determined. That is, in determining the policy, it is incorrectly assumed that (i) the penalty cost is p'y + q, (ii) the penalty cost is py + q', or (iii) the fixed discount ratio per period of time is a' instead of a. [ABSTRACT FROM AUTHOR]

The random walk theory consists of two distinct hypotheses, one economic, the other statistical. The economic argument assumes security markets are, for all practical purposes, efficient markets such that no investor can earn a systematically superior return. The statistical argument, on the other hand, asserts that, for any particular security, price changes are independent random variables. If the statistical hypothesis is to be completely consistent with the economic hypothesis, it is not sufficient simply for successive price changes to be independent, but rather price changes must be mutually stochastically independent and not just pairwise independent. If efficient markets exist, then mutual independence follows. Tests of the economic hypothesis are usually constructed so as to prove or disprove that, following some mechanical rule, a certain investment strategy can, or cannot, earn a greater return than a simple buy-and-hold strategy [1]. The buy-and-hold strategy under efficient markets is an optimal strategy since it minimizes transaction costs. [ABSTRACT FROM AUTHOR]

This paper is concerned with the role played by the standardized regression coefficients in linear regression analysis. The linear regression model is reparameterized to explicitly contain standardized regression coefficients. Several estimators of these coefficients are considered. It is shown that the usual beta coefficient is a good estimator of the coefficients in the linear regression model with random predictor variables. However, in the linear regression model with nonstochastic predictors, alternative estimators are better than the usual beta coefficient. A sociological application is included in order to display the empirical behavior of the various estimators. [ABSTRACT FROM AUTHOR]

Within the framework of chance-constrained programming, this paper formulates two related stochastic models for players competing in a random-payoff two-person zero-sum game. Under certain assumptions, it shows that a one-to-one correspondence (called stochastic pseudoduality) exists between the two formulations at their optimal values, and, furthermore, exact deterministic equivalents can be obtained for these formulations. The optimal solution for a deterministic equivalent can be found by considering an appropriate class of subproblems. [ABSTRACT FROM AUTHOR]

MILLER and WAGNER have shown that a deterministic equivalent of a joint chance-constrained programming model with independent random right-and-side elements is a concave programming problem. This paper obtains similar equivalents for chance-constrained programming models with coefficient matrices whose elements are normally distributed and with dependent random right-hand-side elements. [ABSTRACT FROM AUTHOR]

This paper considers the problem of describing optimal issuing policies when the field life, X (s), is a nonnegative random variable. A new optimality criterion involving stochastic ordering is introduced and sufficient conditions given for the optimality of FIFO and LIFO. Two specific models of perishable inventory are then considered; Model I allows for the perishing of items in the stockpile and Model II does not. It is demonstrated that both LIFO and FIFO are optimal for Model I when the items age at the same rate in the stockpile as in the field. Under the assumption that X (s) is uniformly distributed the optimality of FIFO is established for Model II. [ABSTRACT FROM AUTHOR]

This paper considers a stationary discrete dynamic programming model that is a generalization of the finite state and finite action Markov programming problem. We specify conditions under which an optimal stationary linear decision rule exists and show how this optimal policy can be calculated using linear programming, policy iteration, or value iteration. In addition we allow the parameters of the problem to be random variables and indicate when the expected values or these random variables are certainty equivalents. [ABSTRACT FROM AUTHOR]

In two papers by C. J. ANCKER, JR., A. F. GAFARIAN, AND R. K. GRAY, the structure of the headways at the passage of an oversaturated signalized intersection were studied. The statistical analysis performed by these authors seems to confirm the hypothesis that these headways are independent random variables. In this paper we consider the following simple model. Let the spacings and reaction times of the vehicles stopped at the intersection all be independent and let the trajectory relative to the start position and start time be the same for all stopped vehicles. It is shown that the head- ways at the intersection are independent if and only if this trajectory is linear in a certain region specified in the paper. [ABSTRACT FROM AUTHOR]

The lack of memory property of the exponential distribution plays an important part in the branch of applied probability. This property assumes the information regarding the probability distribution. In the present paper we give a characteristic property of the exponential distribution based on the means of the conditional distributions. Considering a random variable T with finite mean and such that P(T > O) > 0, and denoting by y a positive number such that P(T > y) > 0, we show that T has an exponential distribution if and only if the mean of the conditional distribution, given T > y, exceeds the mean of the unconditional distribution by the quantity y for all y. Also given in the paper is a similar characterization for the geometric distribution. Since the information concerning the expected values is easily accessible, we expect these properties to be useful in dealing with the practical problems. [ABSTRACT FROM AUTHOR]

In this paper confidence bands are given for the entire line for simple linear regressions. The conventional bands that have been given in the past are curvilinear. In this paper we consider confidence bands that are straight lines. It is shown that under certain conditions the "width" of these straight line bands is less than the width of the conventional curvilinear bands. [ABSTRACT FROM AUTHOR]