Math340/Week 5

Question 1 (Tuesday, June 9)

Suppose we add another worker to the casting department in the toy factory example, changing the RHS of the first constraint in the problem on page 13 from 5 to 6. We saw in class this is beyond the region for which our estimate given by the shadow price holds, as the dual optimal solution changes, and so we expect the objective function to increase by less than 1. Run the revised simplex method on the dual problem (after the modification) to reach the optimal dual solution. By how much did the objective function change?

Question 2 (Thursday, June 10)

Consider the following problem:

${\begin{array}{ll}maximize&-x_{1}+x_{2}\\subject\ to&x_{2}\leq 1,\\&x_{1}+x_{2}\leq 2,\\&x_{1},x_{2}\geq 0.\end{array}}$

Sketch the domain and mark the optimal vertex.

a) What would be a good estimation for the direction $(\Delta x_{1},\Delta x_{2})$ of the $x$ part of the direction of the next step in the path following method- starting at the point $(1/3,1/3)$?

And at $(2,2)$?

b) What would be a reasonable choice for $M$ and $\varepsilon$ for any $2-$dimensional problem that has constants all of the order of 1?

Question 3 (Friday, June 12)

Consider the LP we discussed in class:

${\begin{array}{ll}maximize&-x_{1}+x_{2}\\subject\ to&x_{2}\leq 1,\\&-x_{1}\leq -1,\\&x_{1},x_{2}\geq 0.\end{array}}$

Compute one iteration of the path following algorithm, starting from the point:

${\begin{pmatrix}x_{1}\\x_{2}\\s_{1}\\s_{2}\\y_{1}\\y_{2}\\t_{1}\\t_{2}\end{pmatrix}}={\begin{pmatrix}2\\1/2\\1\\1\\2\\1/2\\1\\1\end{pmatrix}}$

and explain why this is a better choice than the one we had in class (which was a vector of all coordinates equal to 2).

The details of the algorithm are found on pages 269 to 273 on Venderbei's book. Note you should use the symmetry between the primal and the dual question to solve only half of the problem.