Minimax procedure for a class of linear programs under uncertainty.

Abstract

tribution functions are otherwise unspecified. A minimax solution of the stochastic programming model is obtained by solving an equivalent deterministic convex programming problem. We derive these deterministic equivalents under different assumptions regarding the stochastic nature of the random parameters. IN FORMULATING a stochastic linear programming model, we generally assume definite probability distribution for the parameters (A, b, c) of the model. In this note we avoid making the assumption that the precise form of the probability distribution of the parameters is known. What we assume, however, is that the random aij and bi elements have known (finite) means and variances. The problem is then to obtain a minimax solution that minimizes the maximum of the objective function over all distributions with the given mean and standard deviation. The situation of a decision maker facing an unknown probability distribution can be viewed as a zero-sum game against nature. Zackova [3] proves that the general min-max theorem holds in this case if the set P of all possible distributions is assumed to be convex and compact (in the sense of Levy's distance). However, neither the above result nor its proof presents any effective method for finding the value of the game or determining explicit solutions. In Section 1 we obtain some results that are used later in determining minimax solutions under different assumptions regarding the stochastic nature of the random parameters of a linear programming model. Section 2 considers a stochastic linear programming problem with random RHS elements and obtains a minimax solution of the problem as an optimal solution of an equivalent deterministic convex separable programming problem. Section 3 presents similar results for the case of random aii elements.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 44 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.