Stochastic Programming
In stochastic programming, the uncertainty is commonly captured by set of scenarios. The scenario-representation of uncertainty can be straightforwardly formulated by the cell array of decisions in XProg. The example (Higle 2005) presented below illustrates how to use XProg to model the uncertainty in stochastic programming problems.
A furniture company manufactures desks, tables, and chairs, which sell for $60, $40, and $10, respectively. The manufacture of each type of furniture requires lumber and two types skilled labor: finishing and carpentry. The cost of each resource and the amount of needed to make each type of furniture is given in the following table.
In stochastic programming, the uncertainty is commonly captured by set of scenarios. The scenario-representation of uncertainty can be straightforwardly formulated by the cell array of decisions in XProg. The example (Higle 2005) presented below illustrates how to use XProg to model the uncertainty in stochastic programming problems.
A furniture company manufactures desks, tables, and chairs, which sell for $60, $40, and $10, respectively. The manufacture of each type of furniture requires lumber and two types skilled labor: finishing and carpentry. The cost of each resource and the amount of needed to make each type of furniture is given in the following table.
Resourses | Cost ($) | Desk | Table | Chair |
Carpentry | 5.2 | 2 | 1.5 | 0.5 |
Finishing | 4 | 4 | 2 | 1.5 |
Lumber | 2 | 8 | 6 | 1 |
It is assumed that the demand for each product is subject to uncertainty, and the demand uncertainty can be represented by three scenarios: "low", "most likely", and "high", as indicated by the table below.
Scenario | |||
Low | Most Likely | High | |
Desk | 50 | 150 | 250 |
Table | 20 | 110 | 250 |
Chair | 200 | 225 | 500 |
Probability | 0.3 | 0.4 | 0.3 |
Let \(\pmb{x}\) be the first-stage decisions indicating the amount of each type of resources purchased, and the recourse decisions \(\pmb{y}\) represent the numbers of desks, tables, and chairs produced in the \(s\)th scenario. The stochastic programming problem aiming at maximizing the expected profit is therefore expressed as follows.
\begin{align}
\max~&-2x_1-4x_2-5.2x_3+\sum\limits_{s=1}^3P_s\left(60y_{1s}+40y_{2s}+10y_{3s}\right) \\
\text{s.t.}~&8y_{1s}+6y_{2s}+y_{3s}\leq x_1 \\
&4y_{1s}+2y_{2s}+1.5y_{3s}\leq x_2 \\
&2y_{1s}+1.5y_{2s}+0.5y_{3s}\leq x_3\\
&y_{is}\leq D_{is}, ~~~~~\forall i=1,2,3;~\forall s=1,2,3\\
&x, y_{is}\geq 0, ~~~~~\forall i=1,2,3;~\forall s=1,2,3\\
\end{align} where \(D_{is}\) is the demaand of the \(i\)th product in the \(s\)th scenario. This three-scenario stochastic program can be implemented by the following code.
P= [0.3 0.4 0.3]; % probability of each scenario c= [2 4 5.2]; % cost of resources q= [60 40 10]; % price of selling each product model=xprog('SP Example'); % create a model, named "SP Example" x=model.decision(3); % define 1st-stage decisions to be a 3*1 vector y=cell(1,3); % create a cell array for three scenarios for s=1:3 y{s}=model.decision(3); % define recourse decisions to be a 3*1 vector for each scenario s end Exp=0; for s=1:3 Exp=Exp+P(s)*q*y{s}; % expected return from selling products end model.max(-c*x+Exp); W=[8 6 1; % define constraint matrix 4 2 1.5; 2 1.5 0.5]; D=[50 150 250; % define random demand 20 110 250; 200 225 500]; for s=1:3 model.add(W*y{s}<=x); % add the 1st~3rd constraints model.add(y{s}>=0); % bound of y(s) model.add(y{s}<=D(:,s)); % demand constriants end model.add(x>=0) % bound of x model.solve; % solve the program Obj=model.get; % get optimal objective X =x.get; % get optimal solution of x
The expectation of the maximum profit is $1730, as the optimal decision should be purchasing 1300 units of lumber, 540 units of finishing labor, and 325 units of carpentry labor.
It can be seen that the recourse decision for each scenario \(s\) is straightforwardly defined by the \(s\)th entry of the cell array. Besides decision variables, cell array structure can also be applied to random variables, decision rules, or even XProg model objects themselves. By using cells, users are able to group variables into different sets, so that they can easily express more complicated models.
It can be seen that the recourse decision for each scenario \(s\) is straightforwardly defined by the \(s\)th entry of the cell array. Besides decision variables, cell array structure can also be applied to random variables, decision rules, or even XProg model objects themselves. By using cells, users are able to group variables into different sets, so that they can easily express more complicated models.