Chance Constrained Programming with one Discrete Random Variable in Each Constraint by Emilio Cerdá Tena^** ** Julio Moreno Lorente DOCUMENTO DE TRABAJO 2009-05

January 2009

A previous version of this paper has been presented in the International Workshop on Operational Research In Honour of Laureano Escudero (Madrid, July, 2008). Financial support from the Spanish Ministry of Education (project SEJ2005-05085/ECON) is gratefully acknowledged. We are grateful to J.B. Readman for his linguistic revision of the text. Any error is our responsibility.

**

Universidad Complutense de Madrid. ecerdate@ccee.ucm.es , juliomor@ccee.ucm.es.

Los Documentos de Trabajo se distribuyen gratuitamente a las Universidades e Instituciones de Investigación que lo solicitan. No obstante están disponibles en texto completo a través de Internet: http://www.fedea.es. These Working Paper are distributed free of charge to University Department and other Research Centres. They are also available through Internet: http://www.fedea.es.

ISSN:1696-750

Jorge Juan, 46 28001 Madrid -España Tel.: +34 914 359 020 Fax: +34 915 779 575 infpub@fedea.es

ABSTRACT

Stochastic programming problems in which there are linear constraints containing one discrete random variable among either the technical coefficients or the resource (which are all positive), and non-negativity constraints for the variables, are studied. First, the case of just one linear constraint with stochastic resource is presented. Next is the case of just one linear constraint where one of the technical coefficients is a random variable. In both cases, initially the case of two decision variables is studied, which permits us to solve the problems taking advantage of the corresponding graphical representations. The corresponding generalizations for the case of n decision variables follow. The general case of several of such constraints is also presented. All the specific solution methods obtained are based on the chance constrained method. Each of the cases is illustrated with an example taken from Economics.

Key words: stochastic programming, chance constrained programming, discrete random variables.

Classification AMS : 90C15.

RESUMEN

En este artículo se estudian problemas de programación estocástica en los que hay restricciones lineales conteniendo una variable aleatoria discreta, ya sea entre los coeficientes técnicos o en el recurso (todos ellos positivos), siendo las variables de decisión no negativas. En primer lugar se presenta el caso de una sola restricción lineal con recurso estocástico. En segundo lugar se estudia el caso de una sola restricción lineal en la que uno de los coeficientes técnicos es una variable aleatoria. En ambos casos se estudia primero el caso de dos variables de decisión, que permite resolver los problemas ayudándose del análisis gráfico. Posteriormente se generalizan los problemas anteriores para n variables de decisión. Finalmente se presenta el caso general de varias restricciones de las consideradas en los apartados anteriores. Todas las soluciones se obtienen a partir del método de restricciones de azar. Cada uno de los casos se ilustra con un problema con significado económico.

1. INTRODUCTION

Stochastic programming is an approach for modelling optimization problems that involve uncertainty. Stochastic programming models try to take advantage of the fact that probability distributions governing those data are known or can be estimated. With René Henrion we can say that chance constraints offer a way to model reliability in optimization problems. In many applications of mathematical programming problems with random variables appearing in the constraints, it is necessary to look for decisions guaranteeing feasibility “as much as possible”. This loose term refers to the fact that constraint violation can hardly ever be avoided because of unexpected extreme events. On the other hand, when knowing or approximating the distribution of the random parameter, it makes sense to call decisions feasible with high probability, that is, only a low percentage of realizations of the random parameter leads to constraint violation under fixed decision.

The chance constrained programming method was introduced in Charnes, Cooper and Symonds (1958) and Charnes and Cooper (1959). The general characteristics of the method can be seen in Birge and Louveaux (1997), Kall and Wallace (1994), Prekopa (1995) and Cerdá and Moreno (2004).

In Caballero, Cerdá, Muñoz and Rey (2000, 2002, 2004) and also in Caballero, Cerdá, Muñoz, Rey and Stancu-Minasian (2001) different problems of stochastic programming with one objective function and also with multiple objective functions are studied. In all the cases it is assumed that the set of constraints is a deterministic set or has been transformed into its deterministic equivalent by the criterion of chance constraint. On the other hand, in these papers all the random variables are assumed to be continuous and one of the lines for further research consists of studying what happens with similar problems in which the random variables are discrete. This is the first paper in this line of research with discrete random variables.

In this paper some stochastic programming problems in which the objective function is deterministic and all the stochastic elements are in the feasible set are studied. It is assumed that the feasible set contains at least one linear constraint in which either one of the technical coefficients or the right hand side (the resource) is a discrete random variable whose probability distribution is known. The technical coefficients and the right hand side are assumed to have only positive values. All the decision variables have to be non negative. In order to solve the stochastic problems, the chance constrained method is used.

* René Henrion, Introduction to chance constrained programming, in the Stochastic Programming Community Home Page, sponsored by the Committee on Stochastic Programming (COSP), (www.stoprog.org).

In Section 2 we study problems with just one linear constraint in which the right hand side is a discrete random variable. In Section 3 we study problems with again just one linear constraint in which one of the technical coefficients is a discrete random variable, the rest of the coefficients and the resource being deterministic. Section 4 presents the case of several linear constraints in which each has one of the forms studied in the two previous sections. Section 5 concludes.

2. STOCHASTIC RESOURCE

We start with the case of two decision variables, where we can take advantage of the graphical representation of the problem, and then we generalize the obtained results to the case on n decision variables.

2.1. The case of 2 decision variables

Let us consider the stochastic programming problem with discrete random variable, deterministic objective function and a sole linear constraint. In this section we have just two decision variables, only the resource of the constraint being random:

\[\begin{array}{l} \underset {\mathbf {x}} {\max} \mathrm{g} _ {0} \left(\mathrm{x} _ {1}, \mathrm{x} _ {2}\right) \\ \text {s.a.:} \mathrm{a} _ {1} \mathrm{x} _ {1} + \mathrm{a} _ {2} \mathrm{x} _ {2} \leq \tilde {\mathrm{b}} \\ \mathrm{x} _ {1}, \mathrm{x} _ {2} \geq 0 \end{array}\]

the discrete random variable being :

\[\begin{array}{c c c c c c} \mathsf {b} ^ {1} & \mathsf {b} ^ {2} & \ldots & \mathsf {b} ^ {\mathrm{s}} & \ldots & \mathsf {b} ^ {\mathrm{s}} \\ \hline \mathsf {p} ^ {1} & \mathsf {p} ^ {2} & \ldots & \mathsf {p} ^ {\mathrm{s}} & \ldots & \mathsf {p} ^ {\mathrm{s}} \end{array}\]

where , for and, . It is assumed that:

\[\mathrm{a} _ {1} > 0, \quad \mathrm{a} _ {2} > 0 \quad \mathrm{y} \quad \mathrm{b} ^ {1} > \mathrm{b} ^ {2} > \dots > \mathrm{b} ^ {\mathrm{s}} > \dots > \mathrm{b} ^ {\mathrm{s}} > 0\]

which permits us to construct the corresponding deterministic constraints for the different values of the random variable :

\[\mathrm{H} ^ {\mathrm{s}}: \quad \begin{array}{l} \mathrm{a} _ {1} \mathrm{x} _ {1} + \mathrm{a} _ {2} \mathrm{x} _ {2} \leq \mathrm{b} ^ {\mathrm{s}} \\ \mathrm{x} _ {1}, \mathrm{x} _ {2} \geq 0 \end{array} , \quad \text { with } \quad \mathrm{P} [ \mathrm{H} ^ {\mathrm{s}} ] = \mathrm{p} ^ {\mathrm{s}},\]

s ∈{1, 2, ..., S}.

In Figure 1, the deterministic constraint set for different possible values of the random variable is represented.

Figure 1. Deterministic constraint set for taking different values.

From the graphical analysis it can be easily seen that the deterministic feasible sets defined are related in the following way:

\[\mathrm{H} ^ {1} \supset \mathrm{H} ^ {2} \supset ... \supset \mathrm{H} ^ {\mathrm{s}} \supset ... \supset \mathrm{H} ^ {\mathrm{s}},\]

with the position in the nest depending on the value taken by the random variable.

Now, the chance constrained method is applied in order to relate the random constraint to its deterministic equivalent with a minimum probability α .

\[\mathrm{P} \left[ a _ {1} x _ {1} + a _ {2} x _ {2} \leq \tilde {b} \right] \geq \alpha ,\]

obtaining in Table 1 the deterministic feasible sets C(α) as a function of which, permits us to construct the corresponding deterministic sub-problems and in that way to calculate in the usual way the optimal value of deterministic problems with linear constraints, for the different values of .α

Table 1. Deterministic feasible sets

Example 1. Let us consider a classical problem of a consumer choice. A consumer has to choose the quantities to consume of two goods 1 and 2, whose respective prices, 10 and 5, are known. He does not know exactly the amount of money he will have to buy the goods, but he knows the discrete probability distribution of that amount. He has to take the decision before knowing the realization of the random variable. His preferences are represented by the Cobb-Douglas utility function The problem is:.

\[\begin{array}{l} \max _ {\mathbf {x}} \mathrm{x} _ {1} ^ {1 / 3} \mathrm{x} _ {2} ^ {2 / 3} \\ \text {s.t.:} 1 0 \mathrm{x} _ {1} + 5 \mathrm{x} _ {2} \leq \tilde {\mathrm{b}} \\ \mathrm{x} _ {1}, \mathrm{x} _ {2} \geq 0 \end{array}\]

where the values which the random variable can take and their corresponding probabilities are:

which permits us to obtain the following deterministic constraints, and the corresponding feasible sets with their respective probabilities:

\[\mathrm{H} ^ {1}: \quad \begin{array}{l} 1 0 \mathrm{x} _ {1} + 5 \mathrm{x} _ {2} \leq 1 0 0 \\ \mathrm{x} _ {1}, \mathrm{x} _ {2} \geq 0 \end{array} , \quad \text { with } \quad \mathrm{P} [ \mathrm{H} ^ {1} ] = \mathrm{p} ^ {1} = \frac {1}{3}\]

\[\mathrm{H} ^ {2}: \quad \begin{array}{l} 1 0 \mathrm{x} _ {1} + 5 \mathrm{x} _ {2} \leq 8 0 \\ \mathrm{x} _ {1}, \mathrm{x} _ {2} \geq 0 \end{array} , \quad \text { with } \quad \mathrm{P} [ \mathrm{H} ^ {2} ] = \mathrm{p} ^ {2} = \frac {1}{2}\]

\[\mathrm{H} ^ {3}: \quad \begin{array}{l} 1 0 \mathrm{x} _ {1} + 5 \mathrm{x} _ {2} \leq 5 0 \\ \mathrm{x} _ {1}, \mathrm{x} _ {2} \geq 0 \end{array} , \quad \text { with } \quad \mathrm{P} [ \mathrm{H} ^ {3} ] = \mathrm{p} ^ {3} = \frac {1}{6}\]

It is satisfied that

\[\mathrm{H} ^ {1} \supset \mathrm{H} ^ {2} \supset \mathrm{H} ^ {3}.\]

Now, applying the chance constrained method, that is substituting the stochastic constraint by the following:

\[\mathrm{P} \left[ \mathrm{a} _ {1} \mathrm{x} _ {1} + \mathrm{a} _ {2} \mathrm{x} _ {2} \leq \tilde {\mathrm{b}} \right] \geq \alpha ,\]

we obtain the corresponding deterministic feasible sets as a function of

which permits us to construct the corresponding deterministic sub-problems and calculate the optimal value for each of them, for the different values of

Constructing the deterministic equivalent subproblems and solving them for the corresponding subintervals as a function of α , we obtain:

In Figure 2 the three sub-programs are solved graphically. It can be observed that the consumer can choose higher quantities of both goods, the higher the amount of rent he has, and therefore obtain a higher level of utility. However, the choice of higher quantities (assuming higher rent) implies higher risk of being out of the budget set if the realization of the random variable is unfavourable.

Let us note that in the stated problem, which is the classical problem of choice of a consumer, there exists no penalization for not having enough income (in the case in which the random variable takes a value for which the optimal choice is not feasible, ex post), nor an additional contribution to the utility (objective function) for the saving of income (when the random variable takes a value for which the optimal solution is slack, ex post).

Let us note that the evolution of the value of the optima of the objective function, as a function of the value of α is decreasing. That is, the smaller the risk of infeasibility (or greater the probability of feasibility α ), the smaller is the optimal value for the objective function

Figure 2. Graphical solution of the three sub-programs

2.2. Generalization to n decision variables

Let us consider the stochastic programming problem with discrete random variable, deterministic objective function and just one linear constraint. In this case, we assume that there are n decision variables, the technical coefficients are deterministic and the resource of the constraint is a discrete random variable:

\[\begin{array}{l} \max _ {\mathbf {x}} \mathrm{g} _ {0} (\mathbf {x}) \\ \text {s.t.:} \sum_ {j = 1} ^ {n} a _ {j} x _ {j} \leq \tilde {b} \\ \mathbf {x} \geq \mathbf {0} \end{array}\]

where . The values which the discrete random variable can take and their respective probabilities are given by:

\[\begin{array}{c c c c c c} \mathsf {b} ^ {1} & \mathsf {b} ^ {2} & \ldots & \mathsf {b} ^ {\mathrm{s}} & \ldots & \mathsf {b} ^ {\mathrm{s}} \\ \hline \mathsf {p} ^ {1} & \mathsf {p} ^ {2} & \ldots & \mathsf {p} ^ {\mathrm{s}} & \ldots & \mathsf {p} ^ {\mathrm{s}} \end{array}\]

where , for and . It is assumed that

\[a _ {j} > 0, \forall j \in \{1, 2, \dots , n \} a n d b ^ {1} > b ^ {2} > \dots > b ^ {s} > \dots > b ^ {s} > 0.\tag{1}\]

In matrix form:

\[\begin{array}{c} \underset {\mathbf {x}} {\max} \mathrm{g} _ {0} (\mathbf {x}) \\ \text {s.t.: a^{\mathrm{T}} x\leq\tilde {b}} \\ \mathbf {x} \geq \mathbf {0} \end{array}\]

where , which permits us to construct the deterministic feasible constraints for the different values of the random variable .

For , let us define

\[\begin{array}{l l} \mathrm{H} ^ {\mathrm{s}}: & a _ {1} \mathrm{x} _ {1} + a _ {2} \mathrm{x} _ {2} + \ldots + a _ {\mathrm{n}} \mathrm{x} _ {\mathrm{n}} \leq b ^ {\mathrm{s}}, \\ & \mathbf {x} \geq 0 \end{array}\]

\[\text { with } \quad P \left[ H ^ {s} \right] = p ^ {s}, \quad \text { being } \quad s \in \{1, 2, \dots , S \}.\]

That is:

\[\mathrm{H} ^ {\mathrm{s}} = \left\{\mathbf {x} \in \mathrm{R} ^ {\mathrm{n}}: \mathbf {a} ^ {\mathrm{T}} \mathbf {x} \leq \mathrm{b} ^ {\mathrm{s}}, \mathbf {x} \geq 0 \right\}.\]

Next three propositions are presented, which justify the construction of nested feasible sets, the allocation of probabilities to the feasible sets, the construction of the deterministic feasible set as a function of the threshold of probability α given in the chance-constrained method and prove that the optimal value of the deterministic equivalent problem decreases when α increases.

Proposition 1 For s, , with , it is satisfied that

Proof By definition, we have that :

\[\mathrm{H} ^ {\mathrm{t}} = \left\{\mathbf {x} \in \mathrm{R} ^ {\mathrm{n}}: \mathbf {a} ^ {\mathrm{T}} \mathbf {x} \leq \mathsf {b} ^ {\mathrm{t}}, \mathbf {x} \geq 0 \right\}.\]

\[\mathrm{H} ^ {\mathrm{s}} = \left\{\mathbf {x} \in \mathrm{R} ^ {\mathrm{n}}: \mathbf {a} ^ {\mathrm{T}} \mathbf {x} \leq \mathrm{b} ^ {\mathrm{s}}, \mathbf {x} \geq 0 \right\}.\]

For (1), it is known that , then as , it is

and and . ■

Therefore, we have proved that

\[\mathrm{H} ^ {1} \supset \mathrm{H} ^ {2} \supset \mathrm{H} ^ {3} \supset ... \supset \mathrm{H} ^ {\mathrm{s}} \supset ... \supset \mathrm{H} ^ {\mathrm{s}}.\]

For the stochastic programming problem we are studying in this section:

\[\begin{array}{c} \underset {\mathbf {x}} {\max} \mathrm{g} _ {0} (\mathbf {x}) \\ \text {s.t.: a^{\mathrm{T}} x\leq\tilde {b}} \\ \mathbf {x} \geq \mathbf {0} \end{array}\]

we consider the corresponding deterministic equivalent, using the chance-constrained method, which depends on the parameter

\[\begin{array}{l} \max _ {\mathbf {x}} \mathrm{g} _ {0} (\mathbf {x}) \\ \text {s.t.:} \mathrm{P} \left[ \mathbf {a} ^ {\mathrm{T}} \mathbf {x} \leq \tilde {\mathbf {b}} \right] \geq \alpha \\ \mathbf {x} \geq \mathbf {0} \end{array}\]

Therefore, for each , the largest deterministic feasible set satisfying the given condition has to be found.

The following proposition establishes the deterministic feasible set which has to be used in each case (the largest deterministic feasible set which satisfies the probabiliy condition), as a function of the value of the parameter α .

Proposition 2 For belonging to the sub-interval s of the interval defined byα (0,1] and, , for , the deterministic

equivalent set C(α), as a function of the parameter is the set .

Proof For Proposition 1 it is known that:

\[\mathrm{H} ^ {1} \supset \mathrm{H} ^ {2} \supset \mathrm{H} ^ {3} \supset ... \supset \mathrm{H} ^ {\mathrm{s}} \supset ... \supset \mathrm{H} ^ {\mathrm{s}},\]

therefore the set will be feasible only if the random variable takes the highest of the possible values: , which happens with probability

If , the largest feasible set compatible with the probability condition which imposes the chance-constrained method is , because

, when the random variable takes the value

If , then does not ensure feasibility with probability higher than or equal to

The set will be feasible if the random variable takes the value , but also if it takes the value , because , and then the set will be feasible with probability equal to . Therefore:

If , the largest feasible set compatible with the given probability constraint is , because:

, when the value taken by the random variable is or

If , then does not ensure feasibility with probability higher than or equal to .

In general, for , will be feasible if the random variable ^s H takes the value , but also if it takes whichever of the values , because , and therefore, will be feasible with probability H . Then:

If , the largest feasible set compatible with the given probability constraint is , because: H

, when the random variable takes the values ^s b .

If , then does not ensure feasibility with probability higher than or equal to α .

Finally, the set will be feasible for certain, whatever the value that the random variable takes, because being the biggest feasible set compatible with the given probability condition, when

\[\sum_ {i = 1} ^ {S - 1} p ^ {i} < \alpha \leq 1,\]

that is, when α is such that will be non feasible with probability higher or equal to α .

For , let us consider the feasible set defined in Proposition 2.

The following function is defined:

\[\begin{array}{c}\mathrm{G}: (0; 1 ] \rightarrow \mathrm{R}\\\alpha \rightarrow \mathrm{G} (\alpha) = \max \left\{\mathrm{g} _ {0} (\mathbf {x}): \mathbf {x} \in \mathrm{C} (\alpha) \right\}\end{array}\]

As the set is closed and bounded, if the function is continuous, it can be assured that the maximization problem has an optimal solution, and then the function G is well defined.

Proposition 3 For , if .Therefore, the function G is monotonous, decreasing.

Proof There are two possible situations:

a) belong to the same sub-interval s, as defined in Proposition 2. In that case, and then:

\[\mathrm{G} \left(\alpha_ {1}\right) = \max \left\{\mathrm{g} _ {0} (\mathbf {x}): \mathbf {x} \in \mathrm{C} \left(\alpha_ {1}\right) \right\} = \max \left\{\mathrm{g} _ {0} (\mathbf {x}): \mathbf {x} \in \mathrm{C} \left(\alpha_ {2}\right) \right\} = \mathrm{G} \left(\alpha_ {2}\right).\]

b) belong to different sub-intervals.

Let belong to the sub-interval s, and let belong to the sub-interval t. It has to be . It is known then that and by Proposition 1:

\[\mathrm{G} \left(\alpha_ {1}\right) = \max \left\{\mathrm{g} _ {0} (\mathbf {x}): \mathbf {x} \in \mathrm{C} \left(\alpha_ {1}\right) = \mathrm{H} ^ {\mathrm{s}} \right\}\]

\[\mathrm{G} \left(\alpha_ {2}\right) = \max \left\{\mathrm{g} _ {0} (\mathbf {x}): \mathbf {x} \in \mathrm{C} \left(\alpha_ {2}\right) = \mathrm{H} ^ {\mathrm{t}} \right\}\]

but as every is such that

3. A STOCHASTIC COEFFICIENT

As in the previous section, we start with the case of just two decision variables, where we can take advantage of the graphical representation of the problem, and then the obtained results are generalized to the case of n decision variables where the results have to be proved.

3.1. The case of 2 decision variables

Let us now consider a stochastic programming problem containing one discrete random variable, with deterministic objective function and a sole linear constraint. In this section we have just two decision variables, with just one of the technical coefficients of the constraint (let´s assume that the first one) being random and the other technical coefficient and also the resource deterministic:

\[\begin{array}{c} \underset {\mathbf {x}} {\max} \mathrm{g} _ {0} \left(\mathrm{x} _ {1}, \mathrm{x} _ {2}\right) \\ \text {s.t.:} \tilde {\mathrm{a}} _ {1} \mathrm{x} _ {1} + \mathrm{a} _ {2} \mathrm{x} _ {2} \leq \mathrm{b} \\ \mathrm{x} _ {1}, \mathrm{x} _ {2} \geq 0 \end{array}\]

The discrete random variable is the following:

\[\begin{array}{c c c c c c} a _ {1} ^ {1} & a _ {1} ^ {2} & \ldots & a _ {1} ^ {r _ {1}} & \ldots & a _ {1} ^ {R _ {1}} \\ \hline p _ {1} ^ {1} & p _ {1} ^ {2} & \ldots & p _ {1} ^ {r _ {1}} & \ldots & p _ {1} ^ {R _ {1}} \end{array}\]

where , for with, and being:

\[0 < a _ {1} ^ {1} < a _ {1} ^ {2} < \dots < a _ {1} ^ {r _ {1}} < \dots < a _ {1} ^ {R _ {1}}, \quad a _ {2} > 0 \quad \text { and } \quad b > 0.\]

The random variable will take the value with probability in which case, the, feasible set with its corresponding probability will be:

\[\mathrm{H} ^ {\mathrm{r} _ {1}}: \begin{array}{l} \mathrm{a} _ {1} ^ {\mathrm{r} _ {1}} \mathrm{x} _ {1} + \mathrm{a} _ {2} \mathrm{x} _ {2} \leq \mathrm{b} \\ \mathrm{x} _ {1}, \mathrm{x} _ {2} \geq 0 \end{array} , \text {with} \quad \mathrm{P} \left[ \mathrm{H} ^ {\mathrm{r} _ {1}} \right] = \mathrm{p} ^ {\mathrm{r} _ {1}} \quad \text {for} \quad \mathrm{r} _ {1} \in \{1, 2,..., \mathrm{R} _ {1} \}.\]

In Figure 3, the deterministic constraint set for different possible values of the random variable is represented.

Figure 3. Deterministic constraint set for taking different values.

Again, it is possible to establish a hierarchy of inclusions among the different deterministic feasible sets, obtaining a nest in the following way:

\[\mathrm{H} ^ {1} \supset \mathrm{H} ^ {2} \supset ... \supset \mathrm{H} ^ {\mathrm{r} _ {1}} \supset ... \supset \mathrm{H} ^ {\mathrm{R} _ {1}}.\]

Now, the feasible stochastic set of the problem defined in this section has to be transformed in its deterministic equivalent, using the chance-constraint method, in the following way:

\[\begin{array}{l} \mathrm{P} \big [ \tilde {\mathbf {a}} _ {1} \mathrm{x} _ {1} + \mathbf {a} _ {2} \mathrm{x} _ {2} \leq \mathbf {b} \big ] \geq \alpha , \\ \mathrm{x} _ {1} \geq 0, \mathrm{x} _ {2} \geq 0. \end{array}\]

In Table 2 the corresponding deterministic feasible sets C(α) for the different values of the parameter are obtained. Then, for each sub-interval a deterministic mathematical programming problem, with the original objective function and the corresponding deterministic equivalent feasible set, can be stated, and then solved, using the methods of deterministic mathematical programming.

Table 2 Deterministic feasible sets

Example 2. Let us again consider the problem of choice of a consumer, whose preferences are represented by a Cobb-Douglas utility function. In this case, both the price of the good 2 and the income are known in advance, but the price of the good 1 is a random variable, with known probability distribution. The consumer has to make his decision before the value taken by the random variable is known. The problem is:

\[\begin{array}{r l} & \max _ {\mathbf {x}} \mathrm{x} _ {1} ^ {1 / 3} \mathrm{x} _ {2} ^ {2 / 3} \\ & \text { s.t.: } \tilde {\mathrm{a}} _ {1} \mathrm{x} _ {1} + 5 \mathrm{x} _ {2} \leq 1 0 0 \\ & \quad \mathrm{x} _ {1}, \mathrm{x} _ {2} \geq 0 \end{array}\]

The price of good 1 is a random variable defined by:

The possible feasible sets with their corresponding probabilities are:

\[\mathrm{H} ^ {1}: \begin{array}{l l} & 5 \mathrm{x} _ {1} + 5 \mathrm{x} _ {2} \leq 1 0 0 \\ & \mathrm{x} _ {1}, \mathrm{x} _ {2} \geq 0 \end{array} ,\]

with

\[\mathrm{P} \left[ \mathrm{H} ^ {1} \right] = \mathrm{p} ^ {1} = \frac {1}{6}\]

\[\mathrm{H} ^ {2}: \begin{array}{l l} & 1 0 \mathrm{x} _ {1} + 5 \mathrm{x} _ {2} \leq 1 0 0 \\ & \mathrm{x} _ {1}, \mathrm{x} _ {2} \geq 0 \end{array} ,\]

with

\[\mathrm{P} \left[ \mathrm{H} ^ {2} \right] = \mathrm{p} ^ {2} = \frac {1}{2}\]

\[\mathrm{H} ^ {3}: \quad \begin{array}{l} 1 5 \mathrm{x} _ {1} + 5 \mathrm{x} _ {2} \leq 1 0 0 \\ \mathrm{x} _ {1}, \mathrm{x} _ {2} \geq 0 \end{array} , \quad \text { with } \quad \mathrm{P} [ \mathrm{H} ^ {3} ] = \mathrm{p} ^ {3} = \frac {1}{3}\]

Now, the original stochastic feasible set of the problem has to be transformed into its deterministic equivalent in accordance with the chance-constrained method:

\[\begin{array}{l} \mathrm{P} \big [ \tilde {a} _ {1} x _ {1} + a _ {2} x _ {2} \leq b \big ] \geq \alpha , \\ x _ {1} \geq 0, \quad x _ {2} \geq 0. \end{array}\]

The deterministic feasible set , as a function of according to the results of Table 2 are:

Having obtained the deterministic feasible set for each value of , it is simple to state and solve the complete deterministic equivalent mathematical programming problem for each of the subintervals previously obtained:

In Figure 4 the three sub-programs are solved graphically. Figure 4. Graphical solution of the three sub-programs

It can be observed that the smaller is the price of good 1, the higher is the quantity of that good that the consumer can choose, consequently reaching higher levels of utility. However, the choice of higher quantities (assuming a smaller price), has a higher risk of leading to an unfeasible solution if the realization of the random variable is unfavourable.

As in the case of stochastic resource, it can be observed that the value taken by the objective function, expressed as a function of the parameter α , is decreasing. That is, the higher the value of α (or smaller the risk of unfeasibility), the smaller is the utility of the consumer for the optimal solution,

2.2. Generalization to n decision variables

Let us consider the problem:

\[\begin{array}{l} \max _ {\mathbf {x}} \mathrm{g} _ {0} (\mathbf {x}) \\ \text {s.t.:} \tilde {\mathbf {a}} _ {1} \mathbf {x} _ {1} + \mathbf {a} _ {2} \mathbf {x} _ {2} + \dots + \mathbf {a} _ {n} \mathbf {x} _ {n} \leq b \\ \mathbf {x} \geq \mathbf {0} \end{array}\]

where for and b are deterministic and is the following discrete random variable:

\[\begin{array}{c c c c c c} \mathsf {a} _ {1} ^ {1} & \mathsf {a} _ {1} ^ {2} & \ldots & \mathsf {a} _ {1} ^ {\mathrm{r} _ {1}} & \ldots & \mathsf {a} _ {1} ^ {\mathrm{R} _ {1}} \\ \hline \mathsf {p} _ {1} ^ {1} & \mathsf {p} _ {1} ^ {2} & \ldots & \mathsf {p} _ {1} ^ {\mathrm{r} _ {1}} & \ldots & \mathsf {p} _ {1} ^ {\mathrm{R}} \end{array}\]

where , for with, . It is assumed that

\[a _ {j} > 0, \forall j \in 2, \dots , n, b > 0 \text { and } 0 < a _ {1} ^ {1} < a _ {1} ^ {2} < \dots < a _ {1} ^ {r _ {1}} < \dots < a _ {1} ^ {R _ {1}}\tag{2}\]

Using matrix notation:

\[\begin{array}{c} \underset {\mathbf {x}} {\max} \mathrm{g} _ {0} (\mathbf {x}) \\ \text {s.t.:} \tilde {\mathbf {a}} ^ {\mathrm{T}} \mathbf {x} \leq \mathsf {b} \\ \mathbf {x} \geq \mathbf {0} \end{array}\]

where

For each of the values that the random variable can take, we can write the feasible set with the corresponding probability. That is, the feasible set will be

\[\mathrm{H} ^ {\mathrm{r} _ {1}}: \begin{array}{l} a _ {1} ^ {\mathrm{r} _ {1}} x _ {1} + a _ {2} x _ {2} + \dots + a _ {n} x _ {n} \leq b \\ \mathbf {x} \geq 0 \end{array} ,\]

if the random variable takes the value and this will happen with probability ,

\[\mathrm{P} \left[ \mathrm{H} ^ {\mathrm{r} _ {1}} \right] = \mathrm{p} ^ {\mathrm{r} _ {1}} \quad \text { with } \quad \mathrm{r} _ {1} \in \left\{1, 2, \dots , \mathrm{R} _ {1} \right\}.\]

In matrix form:

\[\mathrm{H} ^ {\mathrm{r} _ {1}} = \mathrm{H} = \left\{\mathbf {x} \in \mathrm{R} ^ {\mathrm{n}}: \tilde {\mathbf {a}} ^ {\mathrm{T}} \mathbf {x} \leq \mathrm{b}, \mathbf {x} \geq 0 \right\}.\]

Next three propositions are presented. In the first one it is proved that the deterministic feasible sets form a nested structure.

Proposition 4 For , with , it is satisfied that Proof By definition, we have that :

\[\mathrm{H} ^ {\mathrm{r} _ {1} ^ {\prime}} = \left\{\mathbf {x} \in \mathrm{R} ^ {\mathrm{n}}: a _ {1} ^ {\mathrm{r} _ {1} ^ {\prime}} \mathrm{x} _ {1} + a _ {2} \mathrm{x} _ {2} + \dots + a _ {\mathrm{n}} \mathrm{x} _ {\mathrm{n}} \leq b, \mathbf {x} \geq 0 \right\}\]

\[\mathrm{H} ^ {\mathrm{r} _ {1} ^ {\prime \prime}} = \left\{\mathbf {x} \in \mathrm{R} ^ {\mathrm{n}}: a _ {1} ^ {\mathrm{r} _ {1} ^ {\prime \prime}} \mathrm{x} _ {1} + a _ {2} \mathrm{x} _ {2} + \dots + a _ {\mathrm{n}} \mathrm{x} _ {\mathrm{n}} \leq b, \mathbf {x} \geq 0 \right\}\]

For (2), it is known that Therefore, it is. because,

\[\text { Let's take } \mathbf {x} \in H ^ {\mathrm{r} _ {1} ^ {\prime \prime}} \Rightarrow \mathbf {x} \geq 0 \text { y } a _ {1} ^ {\mathrm{r} _ {1} ^ {\prime \prime}} x _ {1} + a _ {2} x _ {2} + \dots + a _ {n} x _ {n} \leq b.\]

As and it is

\[\text { Moreover } \mathrm{a} _ {1} ^ {\mathrm{r} _ {1} ^ {\prime}} \mathrm{x} _ {1} + \mathrm{a} _ {2} \mathrm{x} _ {2} + \dots + \mathrm{a} _ {\mathrm{n}} \mathrm{x} _ {\mathrm{n}} < \mathrm{a} _ {1} ^ {\mathrm{r} _ {1} ^ {\prime \prime}} \mathrm{x} _ {1} + \mathrm{a} _ {2} \mathrm{x} _ {2} + \dots + \mathrm{a} _ {\mathrm{n}} \mathrm{x} _ {\mathrm{n}} \Rightarrow\]

\[\mathrm{a} _ {1} ^ {\mathrm{r} _ {1} ^ {\prime}} \mathrm{x} _ {1} + \mathrm{a} _ {2} \mathrm{x} _ {2} + \dots + \mathrm{a} _ {\mathrm{n}} \mathrm{x} _ {\mathrm{n}} < \mathrm{a} _ {1} ^ {\mathrm{r} _ {1} ^ {\prime \prime}} \mathrm{x} _ {1} + \mathrm{a} _ {2} \mathrm{x} _ {2} + \dots + \mathrm{a} _ {\mathrm{n}} \mathrm{x} _ {\mathrm{n}} \Rightarrow\]

\[\Rightarrow \mathbf {x} \geq 0 \text {y} a _ {1} ^ {\mathrm{r} _ {1} ^ {\prime}} \mathrm{x} _ {1} + a _ {2} \mathrm{x} _ {2} + \dots + a _ {\mathrm{n}} \mathrm{x} _ {\mathrm{n}} \leq b \Rightarrow \mathbf {x} \in H ^ {\mathrm{r} _ {1} ^ {\prime}}. \text {Therefore} H ^ {\mathrm{r} _ {1} ^ {\prime \prime}} \subset H ^ {\mathrm{r} _ {1} ^ {\prime}}.\]

ied thatTherefore, it is satisf

\[\mathrm{H} ^ {1} \supset \mathrm{H} ^ {2} \supset \mathrm{H} ^ {3} \supset ... \supset \mathrm{H} ^ {\mathrm{r} _ {1}} \supset ... \supset \mathrm{H} ^ {\mathrm{R} _ {1}}.\]

Now, for the stochastic programming problem we are studying in this section:

\[\begin{array}{l} \underset {\mathbf {x}} {\max} \mathrm{g} _ {0} (\mathbf {x}) \\ \text {s.t.:} \tilde {\mathrm{a}} _ {1} \mathrm{x} _ {1} + \mathrm{a} _ {2} \mathrm{x} _ {2} + \dots + \mathrm{a} _ {\mathrm{n}} \mathrm{x} _ {\mathrm{n}} \leq b \\ \mathbf {x} \geq \mathbf {0} \end{array}\]

we consider the corresponding deterministic equivalent, using the chance-constrained method, which depends on the parameter

\[\begin{array}{l} \underset {\mathbf {x}} {\max} \mathrm{g} _ {0} (\mathbf {x}) \\ \text {s.t.:} \mathrm{P} \left[ \tilde {a} _ {1} \mathrm{x} _ {1} + a _ {2} \mathrm{x} _ {2} + \dots + a _ {n} \mathrm{x} _ {n} \right] \leq b \\ \mathbf {x} \geq \mathbf {0} \end{array}\]

Therefore, for each , the bigest deterministic feasible set satisfying the givenα condition has to be found.

he following proposition establishes the deterministic feasible set which has to be usedT in each case (the largest deterministic feasible set which satisfies the probability condition), as a function of the value of the parameter α .

Proposition 5 For belonging to the sub-interval α of the interval defined by , for , and , for , the deterministic

equivalent set C(α), as a function of the parameter α , is the set

Proof For Proposition 4 it is known that

\[\mathrm{H} ^ {1} \supset \mathrm{H} ^ {2} \supset ... \supset \mathrm{H} ^ {\mathrm{r} _ {1}} \supset ... \supset \mathrm{H} ^ {\mathrm{R} _ {1}}.\]

The set will be feasible only if the realization of the random variable is , which happens with probability .

If , the largest feasible set which satisfies the probability condition establis by the chahed nce-constrained method is , because

, when the realization of the random variable is

If , then and therefore , is not the feasible set to be used in this case.

The set will be feasible if the random variable takes the value , but also if it takes the value , because . Therefore, will be feasible with probability equal to . Then,

if , the largest feasible set compatible with the probability condition of the chance-constrained method is , because

, when the realization of the random variable is or

If , then does not ensure feasibility with probability higher or equal to

In general, for will be feasible if the random variable takes the value , but also if it takes whichever of the values because, Therefore, . will be feasible with probability equal to . Then,

the largest feasible set compatible with,

the given probability condition is because,

, when the realization of the random

variable is or

If , then does not ensure feasibility with probability higher or equal to . α

Finally, the set will be feasible for certain, whatever the value the random variable takes, because being the biggest feasible set compatible with the given probability condition, when

\[\sum_ {i = 1} ^ {R _ {1} - 1} p ^ {i} < \alpha \leq 1,\]

that is when α is such that is not feasible with probability higher or equal to

Let us define the function:

\[\begin{array}{c}\mathrm{G}: (0, 1 ] \rightarrow \mathrm{R}\\\alpha \rightarrow \mathrm{G} (\alpha) = \max \left\{\mathrm{g} _ {0} (\mathbf {x}): \mathbf {x} \in \mathrm{C} (\alpha) \right\}\end{array}\]

As for each the set is closed and bounded, if the function is continuous, the maximization problem which appears in the definition of function G has an optimal solution and therefore, function G is well defined.

In the following proposition it is proved that the function G is monotonous (not strictly) decreasing

Proposition 6 For

Proof There are two possible situations:

a) belong to the same sub-interval r₁, as defined in Proposition 5. In that case, and then:

\[\mathrm{G} \left(\alpha_ {1}\right) = \max \left\{\mathrm{g} _ {0} (\mathbf {x}): \mathbf {x} \in \mathrm{C} \left(\alpha_ {1}\right) \right\} = \max \left\{\mathrm{g} _ {0} (\mathbf {x}): \mathbf {x} \in \mathrm{C} \left(\alpha_ {2}\right) \right\} = \mathrm{G} \left(\alpha_ {2}\right).\]

b) belong to different sub-intervals.

Let belong to the sub-interval , and belong to the sub-interval . As it has to be, . From Proposition 4, it is known then that By. Proposition 5,

\[\mathrm{G} \left(\alpha_ {1}\right) = \max \left\{\mathrm{g} _ {0} (\mathbf {x}): \mathbf {x} \in \mathrm{C} \left(\alpha_ {1}\right) = \mathrm{H} ^ {\mathrm{r} _ {1} ^ {\prime}} \right\},\]

\[\mathrm{G} \left(\alpha_ {2}\right) = \max \left\{\mathrm{g} _ {0} (\mathbf {x}): \mathbf {x} \in \mathrm{C} \left(\alpha_ {2}\right) = \mathrm{H} ^ {\mathrm{I} _ {1} ^ {\prime \prime}} \right\},\]

and then as for every it is,

4. SEVERAL CONSTRAINTS

We start with some general definitions about chance constrained problems with several constraints and then we solve the stochastic programming problem which has several constraints, each of them belonging to the class of constraints studied in the two previous sections.

4.1. General considerations

Let us now consider a general stochastic programming problem with several stochastic constraints, in which the objective function is deterministic.

\[\begin{array}{l} \underset {\mathbf {x}} {\max} \mathrm{g} _ {0} (\mathbf {x}) \\ \text {s.t.:} \tilde {\mathrm{g}} _ {\mathrm{i}} (\mathbf {x}, \tilde {\xi}) \leq 0, \quad \mathrm{i} = 1, 2,..., \mathrm{m}, \\ \mathbf {x} \in D \end{array}\tag{4.1}\]

As has been used in previous sections, the idea of the chance constrained method is to transform the given problem into a deterministic equivalent in which the constraints are satisfied with, at least, a probability fixed previously. Two cases have to be distinguished depending on whether the probability is fixed either for the set of all the constraints or for each of them separately.

Joint Chance Constrained Problems: Let given. The deterministic equivalent of problem (4.1) is

\[\begin{array}{l} \underset {\mathbf {x}} {\max} \mathrm{g} _ {0} (\mathbf {x}) \\ \text {s.t.:} \mathrm{P} \left[ \tilde {\mathbf {g}} _ {1} (\mathbf {x}, \tilde {\xi}) \leq 0, \tilde {\mathbf {g}} _ {2} (\mathbf {x}, \tilde {\xi}) \leq 0, \dots , \tilde {\mathbf {g}} _ {\mathrm{m}} (\mathbf {x}, \tilde {\xi}) \leq 0 \right] \geq \alpha , \\ \mathbf {x} \in D \end{array}\tag{4.2}\]

For this problem, is the admissible risk for the decision maker that the solution of the problem will be non feasible.

In the particular case in which for every the random variables are mutually, statistically independent, the previous deterministic equivalent problem can be expressed as

\[\begin{array}{l} \underset {\mathbf {x}} {\max} \mathrm{g} _ {0} (\mathbf {x}) \\ \text {s.t.:} \mathrm{P} \left[ \tilde {\mathrm{g}} _ {1} (\mathbf {x}, \tilde {\xi}) \leq 0 \right] \mathrm{P} \left[ \tilde {\mathrm{g}} _ {2} (\mathbf {x}, \tilde {\xi}) \leq 0 \right]... \mathrm{P} \left[ \tilde {\mathrm{g}} _ {\mathrm{m}} (\mathbf {x}, \tilde {\xi}) \leq 0 \right] \geq \alpha , \\ \mathbf {x} \in D \end{array}\tag{4.3}\]

Separate Chance Constrained: Let us consider problem (4.1). For each constraint let be given. The deterministic equivalent of problem (4.1) is defined as:

\[\begin{array}{l} \max _ {\mathbf {x}} \mathrm{g} _ {0} (\mathbf {x}) \\ \text {s.t.:} \mathrm{P} \left[ \tilde {\mathrm{g}} _ {\mathrm{i}} (\mathbf {x}, \tilde {\xi}) \leq 0 \right] \geq \alpha_ {\mathrm{i}}, \quad \text {for} \quad \mathrm{i} = 1, 2, \dots , \mathrm{m}, \\ \mathbf {x} \in D \end{array}\tag{4.4}\]

The following Proposition, well known in the specialized literature, relates both cases.

Proposition Let us assume that is a feasible solution of problem (4.4) for the values Then for. , it is satisfied that is feasible for problem (4.2).

4.2. Our problem

Let us consider now the more general problem to study in this paper, for the case of several variables and several constraints:

^† The proof (an immediate consequence of Boole´s inequality) can be seen, for example, in Cerdá and Moreno (2004)

\[\begin{array}{c} \max _ {\mathbf {x}} \mathrm{g} _ {0} (\mathbf {x}) \\ \text {s.t.:} \tilde {\mathrm{A}} \mathbf {x} \leq \tilde {\mathbf {b}} (*) \\ \mathbf {x} \in D \\ \mathbf {x} \geq \mathbf {0} \end{array}\tag{4.5}\]

The first block of constraints (*) consists of m linear constraints, each one being either

of the form we have studied in section 2 or of the form studied in section 3. That for

the constraint

\[\mathbf {i} \quad \tilde {\mathbf {a}} _ {i} ^ {T} \mathbf {x} \leq \tilde {\mathbf {b}} _ {i}\]

1,2,…, m,

\[\begin{array}{l} a _ {i 1} x _ {1} + \ldots + a _ {i j} x _ {j} + \ldots + a _ {i n} x _ {n} \leq \tilde {b} _ {i} \\ \text {or} \\ a _ {i 1} x _ {1} + \ldots + a _ {i j - 1} x _ {j - 1} + \tilde {a} _ {i j} x _ {j} + a _ {i j + 1} x _ {j + 1} + \ldots + a _ {i n} x _ {n} \leq b _ {i} \end{array}\]

that is, each linear constraint is such that either the resource is stochastic and the technical coefficients are all deterministic or one of the technical coefficients is stochastic and the other coefficients and the resource are deterministic. All the conditions about the positivity of the constants and also of the realizations of the random variables and the order about their corresponding values established in sections 2 and 3 are also assumed.

The deterministic equivalent of problem (4.5), using the joint chance constrained method is (given the admissible risk for the decision maker that the solution of the problem will be non-feasible):

\[\begin{array}{l} \underset {\mathbf {x}} {\max} \mathrm{g} _ {0} (\mathbf {x}) \\ \text {s.t.:} \mathrm{P} \Big [ \tilde {\mathbf {A}} \mathbf {x} \leq \tilde {\mathbf {b}} \Big ] \geq \alpha \\ \quad \mathbf {x} \in D \\ \quad \mathbf {x} \geq \mathbf {0} \end{array}\tag{4.6}\]

The deterministic equivalent of problem (4.5), using the separate chance constrained method is (given for each constraint ):

\[\begin{array}{l} \max _ {\mathbf {x}} \mathrm{g} _ {0} (\mathbf {x}) \\ \text {s.t.:} \mathrm{P} \left[ \tilde {\mathrm{a}} _ {\mathrm{i}} ^ {\mathrm{T}} \mathbf {x} \leq \tilde {\mathrm{b}} _ {\mathrm{i}} \right] \geq \alpha_ {\mathrm{i}}, \quad \text {for} \quad \mathrm{i} = 1, 2, \dots , \mathrm{m}, \\ \mathbf {x} \geq \mathbf {0} \\ \mathbf {x} \in D \end{array}\tag{4.7}\]

The way to proceed with problem (4.7) is immediate, using:

Proposition 2 if the constraint is and then substituting by the corresponding set

\[\begin{array}{l l} \bullet & \text {Proposition} \quad 5 \quad \text {if} \quad \text {the} \quad \text {constraint} \quad \tilde {\mathbf {a}} _ {i} ^ {T} \mathbf {x} \leq \tilde {\mathbf {b}} _ {i} \quad \text {is} \\ & a _ {i 1} x _ {1} +... + a _ {i j - 1} x _ {j - 1} + \tilde {a} _ {i j} x _ {j} + a _ {i j + 1} x _ {j + 1} +... + a _ {i n} x _ {n} \leq b _ {i} \quad \text {and} \quad \text {then} \quad \text {substituting} \\ & P [ \tilde {a} _ {i} ^ {T} \mathbf {x} \leq \tilde {b} _ {i} ] \geq \alpha_ {i}, \mathbf {x} \geq \mathbf {0} \quad \text {by the corresponding set H} _ {i} ^ {r _ {i}}. \end{array}\]

In order to solve problem (4.6), given and using Proposition in (0, 1] have to be chosen satisfying that . Then proceed with problem (4.7).

Example 3. Let us consider a stochastic version of the activity-analysis problem of a simple furniture company which appears in Gass (1991). A manufacturer of furniture has to decide how many chairs , tables , desks and bookcases he has to produce weekly in order to maximize the profit. The following resources are needed: mahogany wood, labor, glue, leather and glass, available in quantities (in board-feet), (in labor-hours), 2000 (in ounces), (in square feet) and 500 (in square feet), respectively. The needs of each of the resources for unit produced appear in the coefficients of the constraints of the mathematical programming problem, which is:

\[\begin{array}{l l} \text {Max} & 4 5 x _ {1} + 8 0 x _ {2} + 1 1 0 x _ {3} + 5 5 x _ {4}, \\ \text {s.t.:} & 5 x _ {1} + 2 0 x _ {2} + 1 5 x _ {3} + 2 2 x _ {4} \leq \tilde {b} _ {1} \\ & 1 0 x _ {1} + 1 5 x _ {2} + 2 5 x _ {3} + 2 0 x _ {4} \leq \tilde {b} _ {2} \\ & 3 x _ {1} + 8 x _ {2} + 1 5 x _ {3} + 1 0 x _ {4} \leq 2 0 0 0 \\ & 4 x _ {1} + 2 0 x _ {3} \leq \tilde {b} _ {3} \\ & 2 0 x _ {4} \leq 5 0 0 \\ & x _ {i} \geq 0, i = 1, 2, 3, 4 \end{array}\tag{4.8}\]

where the values which the random variables and can take and their corresponding probabilities are:

The optimal solution of the stochastic problem has to be obtained, in accordance to the joint chance constrained method, for

First, in (0, 1] such that have to be chosen. Let us take, for example and

Now, Proposition 2 has to be used for each of the stochastic constraints in the following way:

is such that , the constraints

\[\mathrm{P} \left[ 5 \mathrm{x} _ {1} + 2 0 x _ {2} + 1 5 x _ {3} + 2 2 x _ {4} \leq \tilde {\mathrm{b}} _ {1} \right] \geq \alpha_ {I}; \quad x _ {\mathrm{i}} \geq 0, i = 1, \dots , 4\]

have to be substituted by

is such that , the constraints

\[\mathrm{P} \left[ 1 0 \mathrm{x} _ {1} + 1 5 x _ {2} + 2 5 x _ {3} + 2 0 x _ {4} \leq \tilde {\mathrm{b}} _ {2} \right] \geq \alpha_ {2}; \quad x _ {\mathrm{i}} \geq 0, i = 1, \dots , 4\]

have to be substituted by

is such that , the constraints

\[\mathrm{P} \left[ 4 x _ {1} + 2 0 x _ {3} \leq \tilde {\mathrm{b}} _ {3} \right] \geq \alpha_ {3}; \quad x _ {\mathrm{i}} \geq 0, i = 1, \dots , 4\]

have to be substituted by

\[\alpha ,\]

\[\alpha =\]

Therefore, the deterministic equivalents with their optimal solutions for and for are:

5. CONCLUSIONS

In this paper, a wide class of stochastic programming problems with stochastic elements in the feasible set is studied. For each of the problems, the deterministic equivalent under the chance constrained criterion is constructed and then the corresponding optimal solution is obtained.

Each of the problems studied in the paper has at least one linear constraint, in which either one of the technical coefficients or the right hand side is a discrete random variable (that is, each linear constraint contains just one random variable, which is discrete. It is assumed that all the values which both the technical coefficients and the right hand side can take are positive, which permits us to be sure that whatever the realizations of the random variables are, the problem has an optimal solution (assuming non emptiness of the feasible set and continuity of the objective function).

In order to illustrate the methods presented to solve the stated problems some examples are presented. The examples of sections 2 and 3 are taken from Consumer Theory, where the income of the consumer is assumed to be a random variable (section 2), or the price of one of the goods is assumed to be a random variable (section 3). The problems studied in sections 2 and 3 with just one linear constraint, and non-negativity of variables correspond very well to problems with a budget as constraint or, in general, resource allocation problems. An interesting problem to study is the case of a dynamic setting. In section 4 an activity-analysis problem is presented.

The next problem to be studied in this line of research consists of the case in which there is more than one random variable in some of the linear constraints.

REFERENCES

1. • Birge, J.R. and Louveaux, F.V. (1997). Introduction to Stochastic Programming. Springer, New York.
2. • Caballero, R., Cerdá, E., Muñoz, M.M. and Rey, L. (2000). Relations among several efficiency concepts in stochastic multiple objective programming. Lecture Notes in Economics and Mathematical Systems, 487, pp. 57-68.
3. • Caballero, R., Cerdá, E., Muñoz, M.M. and Rey, L. (2002). Analysis and comparisons of some solution concepts for stochastic programming problems. TOP, 10(1), pp. 101-123.
4. • Caballero, R., Cerdá, E., Muñoz, M.M. and Rey, L. (2004). Stochastic approach versus multiobjective approach for obtaining efficient solutions in stochastic multiobjective programming problems. European Journal of Operational Research, 158(3), pp. 633-648.
5. • Caballero, R., Cerdá, E., Muñoz, M.M., Rey, L. and Stancu-Minasian, I. (2001). Efficient solution concepts and their relations in stochastic multiobjective programming. Journal of Optimization. Theory and Application 110(1), pp. 53-74.
6. • Charnes, A. and Cooper, W.W. (1959). Chance Constrained Programming. Management Science, 5, pp. 73-79.
7. • Charnes, A., Cooper, W.W. and Symonds, G.H. (1958). Cost Horizons and Certainty Equivalents: An Approach to Stochastic Programming of Heating Oil. Management Science, 4, pp. 235-263.
8. • Cerdá, E. and Moreno, J. (2004). Programación Estocástica. In: Optimización bajo Incertidumbre. [Alonso-Ayuso, A., Cerdá, E., Escudero, L. and Sala, R. (coord.)]. Serie Monografías, N. 2 de ASEPUMA. Tirant lo Blanch, Valencia.
9. • Gass, S. (1991). Decision Making, Models and Algorithms. Reprint Edition 1991 with corrections. Krieger Publishing Company, Malabar, Florida.
10. • Kall, P. and Wallace, S.W. (1994). Stochastic Programming. John Wiley and Sons, Chichester, England.
11. • Prekopa, A. (1995). Stochastic Programming. Kluwer Academic Publishers, Dordrecht, The Netherlands.
12. 2009-05: “Chance Constrained Programming with one Discrete Random Variable in Each Constraint”, Emilio Cerdá Tena y Julio Moreno Lorente.
13. 2009-03: “Population Ageing, Inequality and the Political Economy of Public Education”, Francisco Martínez-Mora.
14. 2009-02: “Real Wages over the Business Cycle: OECD Evidence from the Time and Frequency Domains”, Julian Messina, Chiara Strozzi y Jarkko Turunen.
15. 2009-01: “The Determinants Of Misreporting Weight And Height: The Role Of Social Norms”, Joan Gil y Toni Mora.
16. 2008-42: “Social Security incentives, exit from the workforce and entry of the young”, Michele Boldrin, Pilar García-Gómez y Sergi Jiménez-Martín.
17. 2008-41: “The evolution and main determinants of productivity in Brazilian electricity distribution 1998-2005: an empirical analysis”, Francisco Javier Ramos-Real, Beatriz Tovar, Mariana Iootty, Edmar Fagundes de Almeida y Helder Queiroz Pinto Jr..
18. 2008-40: “Immigration and Housing Prices in Spain”, Simón Sosvilla.
19. 2008-39: “Modeling the Immigration Shock”, Ana Montes y Michele Boldrin.
20. 2008-38: “Immigration and the Demand for Health in Spain”, Sergi Jiménez, Natalia Jorgensen y José María Labeaga.
21. 2008-37: “Immigration and Students' Achievement in Spain”, Natalia Zinovyeva, Florentino Felgueroso y Pablo Vázquez.
22. 2008-36: “Immigration and Social Security in Spain”, Clara Isabel González, J. Ignacio Conde-Ruiz y Michele Boldrin.
23. 2008-35: “Complements or Substitutes? Immigrant and Native Task Specialization in Spain”, Catalina Amuedo-Dorantes y Sara de la Rica.
24. 2008-34: “Immigration and Crime in Spain, 1999-2006”, Cesar Alonso, Nuno Garoupa, Marcelo Perera y Pablo Vázquez.
25. 2008-33: “A Social Network Approach to Spanish Immigration: An Analysis of Immigration into Spain 1998-2006”, Rickard Sandell.
26. 2008-32: “The Consequences on Job Satisfaction of Job-Worker Educational and Skill Mismatches in the Spanish Labour Market: a Panel Analysis”, Lourdes Badillo Amador, Ángel López Nicolás y Luis E. Vila.
27. 2008-31: “Students’assessment of higher education in Spain”, César Alonso-Borrego, Antonio Romero-Medina.
28. 2008-30: “Body image and food disorders: Evidence from a sample of European women”, Joan Costa-Font y Mireia Jofre-Bonet.
29. 2008-29: “Aggregation and Dissemination of Information in Experimental Asset Markets in the Presence of a Manipulator”, HelenaVeiga y Marc Vorsatz.
30. 2008-28: “The Measurement of Consensus: An Axiomatic Analysis”, Jorge Alcalde-Unzu y Marc Vorsatz.
31. 2008-27: “Macroeconomic Consequences of International Commodity Price Shocks”, Claudia S. Gómez-López y Luis A. Puch.
32. 2008-26: “The Effect of Short–Selling on the Aggregation of Information in an Experimental Asset Market”, Helena Veiga y Marc Vorsatz.
33. 2008-25: “Adult height and childhood disease”, Carlos Bozzoli, Angus Deaton y Climent Quintana-Domeque.
34. 2008-24: “On Gender Gaps and Self-Fulfilling Expectations: Theory, Policies and Some Empirical EvidenceffiSara de la Rica, Juan J. Dolado y Cecilia García-Peñalosa.
35. 2008-23: “Fuel Consumption, Economic Determinants and Policy Implications for Road Transport in Spain”, Rosa M. González-Marrero, Rosa M. Lorenzo-Alegría y Gustavo A. Marrero.
36. 2008-22: “Trade-off between formal and informal care in Spain”, Sergi Jiménez-Martín y Cristina Vilaplana Prieto.
37. 2008-21: “The Rise in Obesity Across the Atlantic: An Economic Perspective”, Giorgio Brunello, Pierre-Carl Michaud y Anna Sanz-de-Galdeano.
38. 2008-20: “Multimarket Contact in Pharmaceutical Markets”, Javier Coronado, Sergi Jiménez-Martín y Pedro L. Marín.
39. 2008-19: “Financial Analysts impact on Stock Volatility. A Study on the Pharmaceutical Sector”, Clara I. Gonzalez y Ricardo Gimeno.