MATP6960 Stochastic Programming, Homework 4

Due: Thursday, October 24, 2002.

You may want to use AMPL on some of these questions.

1.

Birge and Louveaux, page 151, question 3.

2.

Birge and Louveaux, page 169, question 2.

3.

Consider again the Northam Airlines example of question 1 on page 43, which was part of Homework 1.

(a)

Show that the second stage problem has six constraints and nine variables, once slacks are included, but that there are only eight bases which need to be considered. What are the corresponding dual optimal solutions?

(b)

Solve the problem using the L-shaped method. Take $\bar{x}=(5,10,150)^T$ as the first stage variables in the solution to the initial relaxation. Include the simple bounds that x should be no larger than the maximum demand. Also include the simple bounds that the revenue in any scenario can be no larger than the revenue obtained from the maximum demand for that scenario. For example, the maximum possible revenue under Scenario 2 is 255, normalizing so that the revenue from an economy class passenger is 1. Use the multicut method. If there are multiple optimal dual solutions, add all the possible constraints. You should get the optimal solution after three rounds of adding cutting planes.

4.

The second stage constraints of a two-stage problem look as follows:

$$\begin{array}{rcl} \left[ \begin{array}{rrrr}1&3&-1&0\\ 2&-1... ...5&-1&0\\ 0&2&4\end{array}\right] x \\ y & \geq & 0 \end{array}$$

where $\xi$ is a random variable with support $\Xi = [0,1]$. Write down the linear program (both primal and dual formulation) needed to check whether a given $\bar{x}$ produces a feasible second-stage problem. If the second stage problem is not feasible, show how to use your formulation to produce an inequality in x that cuts off the given $\bar{x}$. Construct the inequality explicitly if $\bar{x}=(1,1,1)^T$. (Taken from Kall and Wallace.)

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