Editing Stochastic programming (section)

=== Stochastic linear programming===
A stochastic [[linear program]] is a specific instance of the classical two-stage stochastic program. A stochastic LP is built from a collection of multi-period linear programs (LPs), each having the same structure but somewhat different data. The <math>k^{th}</math> two-period LP, representing the <math>k^{th}</math> scenario, may be regarded as having the following form:

<math>	
\begin{array}{lccccccc}
\text{Minimize} & f^T x & + & g^T y & + & h_k^Tz_k &  &  \\ 	
\text{subject to} & Tx & + & Uy &  &  & = & r \\ 	
 &  &  & V_k y & + & W_kz_k & = & s_k \\ 
 & x & , & y & , & z_k & \geq & 0
\end{array}
</math>

The vectors <math>x</math> and <math>y</math> contain the first-period variables, whose values must be chosen immediately. The vector <math>z_k</math> contains all of the variables for subsequent periods. The constraints <math>Tx + Uy = r</math> involve only first-period variables and are the same in every scenario. The other constraints involve variables of later periods and differ in some respects from scenario to scenario, reflecting uncertainty about the future.

Note that solving the <math>k^{th}</math> two-period LP is equivalent to assuming the <math>k^{th}</math> scenario in the second period with no uncertainty. In order to incorporate uncertainties in the second stage, one should assign probabilities to different scenarios and solve the corresponding deterministic equivalent.

==== Deterministic equivalent of a stochastic problem====
With a finite number of scenarios, two-stage stochastic linear programs can be modelled as large linear programming problems. This formulation is often called the deterministic equivalent linear program, or abbreviated to deterministic equivalent. (Strictly speaking a deterministic equivalent is any mathematical program that can be used to compute the optimal first-stage decision, so these will exist for continuous probability distributions as well, when one can represent the second-stage cost in some closed form.)
For example, to form the deterministic equivalent to the above stochastic linear program, we assign a probability <math>p_k</math> to each scenario <math>k=1,\dots,K</math>. Then we can minimize the expected value of the objective, subject to the constraints from all scenarios:

<math>
\begin{array}{lccccccccccccc}
\text{Minimize} & f^\top x & + & g^\top y & + & p_1h_1^\top z_1 & + & p_2h_2^Tz_2 & + & \cdots & + & p_Kh_K^\top z_K &  &  \\ 
\text{subject to} & Tx & + & Uy &  &  &  &  &  &  &  &  & = & r \\ 
 &  &  & V_1 y & + & W_1z_1 &  &  &  &  &  &  & = & s_1 \\ 
 &  &  & V_2 y &  &  & + & W_2z_2 &  &  &  &  & = & s_2 \\ 
 &  &  & \vdots &  &  &  &  &  & \ddots &  &  &  & \vdots \\ 
 &  &  & V_Ky &  &  &  &  &  &  & + & W_Kz_K & = & s_K \\ 
 & x & , & y & , & z_1 & , & z_2 & , & \ldots & , & z_K & \geq & 0 \\ 
\end{array}
</math>

We have a different vector <math>z_k</math> of later-period variables for each scenario <math>k</math>. The first-period variables <math>x</math> and <math>y</math> are the same in every scenario, however, because we must make a decision for the first period before we know which scenario will be realized. As a result, the constraints involving just <math>x</math> and <math>y</math> need only be specified once, while the remaining constraints must be given separately for each scenario.