MATP6960 Stochastic Programming, Homework 7

Due: Thursday, December 5, 2002.

1.

Consider the three stage problem

$$\begin{array}{lrcl} \min && Q^2(x^1) \\ \mbox{s.t.} & 1 \leq & x^1 & \leq 3 \\ \end{array}$$

with $Q^2(x^1)=E_{\xi}[Q^2(x^1,\xi)]$,

$$\begin{array}{rlrcl} Q^2(x^1,\xi) = & \min & Q^3(x^2) \\ &\... ... = & \xi_1 - x^1 \\ && x^{2,+}, x^{2,-} & \geq & 0 \end{array}$$

and $Q^3(x^2)=E_{\xi}[Q^3(x^2,\xi)]$,

$$\begin{array}{rlrcl} Q^3(x^2,\xi) = & \min & x^{3,+} + x^{3,... ...- \xi_3 x^{2,-} \\ && x^{3,+}, x^{3,-} & \geq & 0. \end{array}$$

The random variable $\xi_1$ takes the value 0 or 4 each with probability 0.5. The random variable $\xi_2$ is equal to 2 if $\xi_1=0$; otherwise, it is equal to zero. The random variable $\xi_3$ is equal to 2 if $\xi_1=4$; otherwise, it is equal to zero.

Show that the optimal value of this problem is zero, achieved by any feasible x¹. Show that setting each $\xi_i$ equal to its mean and solving the resulting problem does not give a lower bound on Q²(x¹), unless x¹=2.

2.

Consider the three stage problem

$$\begin{array}{lrcl} \min && Q^2(x^1) \\ \mbox{s.t.} & 0 \leq & x^1 & \leq 4 \\ \end{array}$$

with $Q^2(x^1)=E_{\xi}[Q^2(x^1,\xi)]$,

$$\begin{array}{rlrcl} Q^2(x^1,\xi) = & \min & x^{2,+} + x^{2,... ...i_1 - x^1 \\ && 0 \leq x^{2,+}, x^{2,-} & \leq & 4 \end{array}$$

and $Q^3(x^2)=E_{\xi}[Q^3(x^2,\xi)]$,

$$\begin{array}{rlrcl} Q^3(x^2,\xi) = & \min & x^{3,+} + x^{3,... ... x^{2,+} \\ && 0 \leq x^{3,+}, x^{3,-} & \leq & 4. \end{array}$$

The random variables $\xi_1$ and $\xi_2$ each take the value 1 or 3 with probability 0.5, independently.

By formulating the extensive form of the problem as a linear programming problem, or otherwise, confirm that the optimal value is 2.5. Show that if x¹=0 then Q²(x¹)=3.

Take x¹=2 as the first stage solution in the nested L-shaped method for this problem. Find the first cut generated by the algorithm of the form $E^1_1x^1 + \theta^1 \geq e^1_1$. Show that E¹₁x¹ + Q²(x¹) > e¹₁ for all feasible x¹.

	John Mitchell	Amos Eaton 325
	x6915.	mitchj@rpi.edu
	Office hours:	Tuesday: 2pm - 4pm.