Math340/Solution 3

Question 1 (Wednesday May 27)

The primal LP:

$\begin{array}{ll} m a x i m i z e & 3 x_{1} + 5 x_{2} + 2 x_{3} \\ s u b j e c t t o & - 2 x_{1} + 2 x_{2} + x_{3} \leq 5, \\ 3 x_{1} + x_{2} - x_{3} \leq 10, \\ x_{1}, x_{2}, x_{3} \geq 0 . \end{array}$

a. The dual LP problem is

$\begin{array}{ll} m i n i m i z e & 5 y_{1} + 10 y_{2} \\ s u b j e c t t o & - 2 y_{1} + 3 y_{2} \geq 3, \\ 2 y_{1} + y_{2} \geq 5, \\ y_{1} - y_{2} \geq 2 \\ y_{1}, y_{2} \geq 0 . \end{array}$

b. The best solution to the primal problem with $x_{2} = 0$ satisfies

$- 2 x_{1} + x_{3} \leq 5$

$3 x_{1} - x_{3} \leq 10 .$

As we try to make $x_{1}$ large as possible this implies that $x_{1} = 15$ and $x_{3} = 35$ (alternatively, since we know there are only two non zero basic variables in the optimal solution, both slack variables must be zero, and so we know both above inequalities are really equalities and we can solve a linear system of equations).

c. By complementary slackness, the dual variables should satisfy

$- 2 y_{1} + 3 y_{2} = 3,$

$y_{1} - y_{2} = 2$

Which means $y_{1} = 9, y_{2} = 7$ . We also need to check that $(7, 9)$ satisfies the second inequality- $2 y_{1} + y_{2} \geq 5$ and it does. Thus, the dual is feasible and the solution $(15, 0, 35)$ is indeed optimal.

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

[Here] is the solution (updated to the full solution now, you might have to refresh your browser to see it).

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) Here's the first matrix:

$(\begin{array}{ccccccc} 2 & 3 & 1 & 1 & 0 & 0 & 5 \\ 4 & 1 & 2 & 0 & 1 & 0 & 11 \\ 3 & 4 & 2 & 0 & 0 & 1 & 8 \end{array})$

and the second: $(\begin{array}{ccccccc} 1 & 3 / 2 & 1 / 2 & 1 / 2 & 0 & 0 & 5 / 2 \\ 0 & - 5 & 0 & - 2 & 1 & 0 & 1 \\ 0 & - 1 / 2 & 1 / 2 & - 3 / 2 & 0 & 1 & 1 / 2 \end{array})$

b) To pass from the first to the second the row operations are:

- divide the first row by 2 (so that $x_{1}$ has coefficient 1),

-subtract 4*(row 1) from row 2,

-subtract 3*(row 1) from row 3.

And

$E_{1} = (\begin{matrix} 1 / 2 & 0 & 0 \\ - 2 & 1 & 0 \\ - 3 / 2 & 0 & 1 \end{matrix})$

c)

$B = (\begin{matrix} 2 & 0 & 0 \\ 4 & 1 & 0 \\ 3 & 0 & 1 \end{matrix}) = E_{1}^{- 1}$

Question 4 (Friday June 5)

[Here] it is.