Dual method for the solution of a one-stage stochastic programming problem with random RHS obeying a discrete probability distribution. (English) Zbl 0724.90048

A linear program with discretely distributed random right hand side is handled by incorporating a mean penalty term into the objective function to penalize the violations of the stochastic constraints; moreover, an additional chance constraint is used in case of inequality constraints in the original random program. Introducing some additional, linear constraints, the objective function can then be written in the form of a separable, piecewise linear, convex function. If the original random linear program contains only equality constraints, then, using the so- called \(\lambda\)-representation of univariate piecewise linear convex functions, the substituting problem can be represented by a deterministic LP having a special structure. This LP is then solved by a special dual type algorithm. In order to use this method also in case of additional chance constraints, first the notion of a “p level efficient point” of the probability distribution of the random elements is introduced, which implies then certain additional linear constraints. Thus, the same dual type linear programming method as in the first case can be used also here.


90C15 Stochastic programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming
Full Text: DOI


[1] E.M.L. Beale (1955) On Minimizing a Convex Function Subject to Linear Inequalities, Journal of the Royal Statistical Society Ser. B. 17, 173-184 · Zbl 0068.13701
[2] R.G. Bland (1977) New Finite Pivoting Rules for the Simplex Method, Mathematics of Operations Research 2, 103-107 · Zbl 0408.90050
[3] A. Charnes, W.W. Cooper and G.H. Symonds (1985) Cost Horizons and Certainty Equivalents: An Approach to Stochastic Programming of Heating Oil Production, Management Science 4, 236-263
[4] G.B. Dantzig (1955) Linear Programming under Uncertainty, Management Science 1, 197-206 · Zbl 0995.90589
[5] C.E. Lemke (1954) The Dual Method for Solving the Linear Programming Problem, Naval Research Logistic Quarterly 1, 36-47. · Zbl 0128.39605
[6] K. Murty (1968) Linear Programming under Uncertainty: A Basic Property of the Optimal Solution, Zeitschrift für Wahrscheinlichkeitstheorie ver. Geb. 10, 284-288 · Zbl 0169.51403
[7] A. Prékopa (1973) Contributions to the Theory of Stochastic Programming, Mathematical Programming 4, 202-221 · Zbl 0273.90045
[8] A. Prékopa (1990) The Discrete Moment Problem and Linear Programming. To appear in Discrete Applied Mathematics · Zbl 0712.90045
[9] R.J.B. Wets (1983) Solving Stochastic Programs with Simple Recourse, Stochastics 10, 219-242 · Zbl 0584.90067
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.