Math340/Week 2

Question 1 (Tuesday, May 19)

Suppose we choose a different leaving variable when passing from the first to the second dictionary in our [example of degeneracy]. Would that cancel the degeneracy in the next step (that is, when then passing to the third dictionary will the objective function increase)?

Question 2 (Wednesday, May 20 Thursday, May 21)

a. Solve Problem 3.4 from the textbook:

(Note: This just means arrange from the smallest to the largest)

b. Consider the following LP:

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

Is this a degenerate problem? If so, perturb it and solve. If not, simply solve using the simplex method for the unperturbed problem. Check that you increase the objective function at every step.

c* (bonus question). Prove that there is a simpler way of getting rid of degeneracy in dimension 2.

Question 3 (Friday, May 22)

Decide if the LP below is feasible. If it is find a feasible solution, if it isn't prove that no feasible solution exist.

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