Please do all three problems. Show all work. No books or calculators allowed. You may use any result from class, the homeworks, or the texts, except where stated. You may use one sheet of handwritten notes. The exam lasts 110 minutes.

1. (45 points) We have a two stage stochastic program where the nonnegative first stage variables x ∈ ℝ² must satisfy x ₁ + 3x₂ = 6. The first stage costs are c^T x = 2x ₁ + 7x₂. There are two scenarios.
   • Scenario 1 occurs with probability . The second stage variable y ∈ ℝ must satisfy the constraints

   • Scenario 2 occurs with probability . The second stage variable y ∈ ℝ must satisfy the constraints

   1. (10 points) Assume x satisfies the first stage constraints. Show that in each scenario, there exists a recourse decision y that is feasible in the second stage problem.
   2. (10 points) Assume the cost of the second stage variables is 3y. Formulate the stochastic program in extended form as an LP. (Hint: your problem should have three equality constraints and four variables.)
   3. (10 points) Find all the basic feasible solutions to the LP formulation. Find the optimal solution.
   4. (5 points) What is the dual to the LP formulation?
   5. (10 points) Use complementary slackness to find the set of optimal solutions to the dual problem.
2. (20 points) Let A be a real p × n matrix and B be a real q × n matrix, with p, q, and n all positive integers. Show that exactly one of the following systems has a solution:

   System 1: Ax < 0, Bx = 0 for some x ∈ ℝⁿ.
   System 2: A^T u + B^T v = 0 for some u ∈ ℝ^p, v ∈ ℝ^q, with u ≥ 0 and u≠0.

3. (35 points) In a vehicle routing problem, a set of cities {1,…,n} must be visited, starting from a base city 0. More than one vehicle can be used, with each vehicle traversing a subtour that starts and ends at the base but only visits a subset of the cities. This problem can be formulated as an integer program with each variable corresponding to an allowable subtour. Let T be the set of allowable subtours. Let c_t be the cost of subtour t ∈ T. Let a^t ∈{0, 1}ⁿ be the incidence vector of subtour t ∈ T, so a_i^t = 1 if and only if tour t visits city i for i ∈{1,…,n}. The LP relaxation of the vehicle routing problem can then be expressed as

   Let n = 4. Assume the cost c_t of a tour is given by the sum of the edge lengths in the tour, and the edge lengths are as follows:

   city	0	1	2	3	4
   0	–	4	7	9	4
   1	4	–	4	6	8
   2	7	4	–	7	5
   3	9	6	7	–	7
   4	4	8	5	7	–

   

   No tour is allowed to visit more than three cities (plus the base city). A tour can visit just one city and the base city. So, for example, valid tours include 0 - 4 - 0 with cost 8 and 0 - 1 - 2 - 3 - 0 with cost 24.

   1. (5 points) What is the dual LP to (CP)?
   2. (10 points) Let the current dual solution be y = (6, 8, 10, 7)^T . Find a violated dual constraint.
   3. (10 points) There are 14 feasible tours for this problem. Enumerate them all and hence show that ŷ = (4, 8, 12, 5)^T is dual feasible.
   4. (10 points) What does complementary slackness imply about the primal solution if the dual solution is ŷ? Show there is a primal feasible solution satisfying complementary slackness with each positive x_t taking the same value. What do you conclude?