Math340/Weeks 3-4

Question 1 (Wednesday May 27)

Consider the following LP:

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

a. What is the dual LP problem?

b. Find (directly, without using the simplex method) the best solution to the primal problem with $x_{2}=0$.

c. Use complementary slackness to check whether the solution you found in b is an optimal solution for the problem.

Question 2 (Friday May 29): A dual-based Phase I procedure

Consider the LP

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

a) Write down the initial dictionary for this problem and show that it is not feasible nor dual feasible.

b) We will devise an auxiliary LP by changing the objective function (but not the constraints) in such a way that the initial dictionary of this new LP is dual feasible. For example, we can replace the objective function with $w=-x_{1}-x_{2}-x_{3}.$ Give another example of an objective function that would make this problem dual feasible.

c) Solve the auxiliary LP with the objective function $w=-x_{1}-x_{2}-x_{3}.$

d) Finally, use the optimal dictionary of the auxiliary LP to solve the original LP. Specify the optimal value of the (original!) objective function.

Question 3 (Wednesday, June 3)

Consider our toy factory example. You have a complete solution of this using dictionaries starting on pages 13 in the textbook.

a) Write out the first and second dictionaries in augmented matrix forms.

b) What are the row operations needed to pass from the first to the second and what is the eta matrix $E_{1}$ that you need to multiply the first matrix by to perform these row operations?

c) What is the relationship between $E_{1}$ and the second $B$ matrix obtained in class when running the revised simplex method?

Question 4 (Friday June 5)

Solve the following LP using the revised simplex method

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

What is the optimal solution and what is the value of the objective function?

(If you do not take notes in class, there is an example in the textbook on page 101)