Solving a linear programming problem using its dual problem.

Solve the following linear programming problem using its dual problem.

\begin{align} \min&\quad z = -5x_1 -7 x_2 -12 x_3 + x_4 \\ \mathrm{s.t.}&\quad 2x_1 + 3x_2 +2x_3 +x_4 \leq 38 \\ &\quad 3x_1 +2 x_2 +4x_3 -x_4 \leq 55\\ &\quad x \geq 0 \end{align}

I'm going to write out all the steps in case I made an error there, so sorry in advance for the length.

The dual problem is:

\begin{align} \max&\quad w = 38y_1 + 55y_2 \\ \mathrm{s.t.}&\quad 2 y_1 + 3 y_2 \leq -5\\ &\quad 3 y_1 + 2y_2 \leq -7\\ &\quad 2 y_1 + 4y_2 \leq -12\\ &\quad y_1 - y_2 \leq 1\\ &\quad y_1 , y_2 \leq 0 \end{align}

I want to have $y_1 , y_2 \geq 0$ so rewrite the problem as:

\begin{align} \max&\quad w = -38y_1 - 55y_2 \\ \mathrm{s.t.}&\quad -2 y_1 - 3 y_2 \leq -5\\ &\quad -3 y_1 - 2y_2 \leq -7\\ &\quad -2 y_1 - 4y_2 \leq -12\\ &\quad -y_1 + y_2 \leq 1\\ &\quad y_1 , y_2 \geq 0 \end{align}

I want all the right hand number to be positive so we rearrange it as:

\begin{align} \max&\quad w = -38y_1 - 55y_2 \\ \mathrm{s.t.}&\quad 2 y_1 + 3 y_2 \geq 5\\ &\quad 3 y_1 + 2y_2 \geq 7\\ &\quad 2 y_1 + 4y_2 \geq 12\\ &\quad -y_1 + y_2 \leq 1\\ &\quad y_1 , y_2 \geq 0 \end{align}

I checked using SCIP that the objective function of this problem has the same value on its optimal solution as the primal problem so I think we're good until this point.

If I go straight for Simplex then I get the following problem:

\begin{align} \max&\quad w = -38y_1 - 55y_2 \\ \mathrm{s.t.}&\quad 2 y_1 + 3 y_2 - w_1 = 5\\ &\quad 3 y_1 + 2y_2 - w_2 = 7\\ &\quad 2 y_1 + 4y_2 - w_3 = 12\\ &\quad -y_1 + y_2 + w_4= 1\\ &\quad y_1 , y_2, w_1, w_2, w_3, w_4 \geq 0 \end{align}

I can easily take $w_4$ as part of my basis but can't easily use $w_1$, $w_2$ and $w_3$ since they would end up with negative values. Instead we use the Two Phase Method. The Phase 1 model is:

\begin{align} \max&\quad t = -a_1 - a_2 - a_3\\ \mathrm{s.t.}&\quad 2 y_1 + 3 y_2 - w_1 + a_1 = 5\\ &\quad 3 y_1 + 2y_2 - w_2 + a_2 = 7\\ &\quad 2 y_1 + 4y_2 - w_3 + a_3 = 12\\ &\quad -y_1 + y_2 + w_4= 1\\ &\quad y_1 , y_2, w_1, w_2, w_3, w_4, a_1, a_2,a_3 \geq 0 \end{align}

Using the dictionary method we get:

$$ a_1 = 5 - 2y_1 - 3y_2+w_1 \\ a_2 = 7 -3y_1 -2y_2 +w_2 \\ a_3 = 12 - 2y_1-4y_2+w_3 \\ w_4 = 1 +y_1-y_2 \\ t = -24 +7y_1 + 9y_2 -w_1-w_2-w_3 \\ $$

In the next step $y_2$ goes into the base and $w_4$ comes out: $$ y_2 = 1 + y_1 - w_4 \\ a_1 = 2 - 5y_1 +w_1+3w_4 \\ a_2 = 5 -5y_1 +w_2 +2 w_4\\ a_3 = 8 - 6y_1 +w_3 +4w_4 \\ t = -15 +16y_1 -w_1 - w_2 - w_3 -9w_4 \\ $$

In the next step now $y_1$ enters the base and $a_2$ leaves:

$$ y_1 = \frac{2}{5} + \frac{w_1}{5} +\frac{3}{5} w_4 - \frac{a_1}{5} \\ y_2 = \frac{7}{5} + \frac{w_1}{5} -\frac{2}{5} w_4 - \frac{a_1}{5}\\ a_2 = 3 -w_1 +w_2 -w_4 + a_1\\ a_3 =\frac{28}{5} - \frac{6}{5} w_1 + w_3+ \frac{2}{5}w_4 + \frac{6}{5} a_1 \\ t = \frac{-43}{5} + \frac{11}{5} w_1 - w_2 -w_3 +\frac{3}{5} w_4 - \frac{16}{5} a_1\\ $$

In the next step $w_1$ enters the base and $a_3$ leaves and this is where I have a problem:

$$ w_1 =\frac{14}{3} + \frac{5}{6} w_3 + \frac{w_4}{3} + a_1 - \frac{5}{6} a_3 \\ a_2 = \frac{-5}{3} + w_2 - \frac{5}{6} w_3 -\frac{4}{3} w_4 +\frac{5}{6} a_3\\ $$

Since $a_2 \geq 0$ this can't be correct. I've done the calculations a few times and can't find an error that leads to this so I'm thinking there's an issue in my solution that's not "numerical" but can't spot it either.

Any help would be greatly appreciated.

Solution 1:

You have two errors:

1. When $y_1$ enters the basis, $a_1$ (not $a_2$) leaves. I think this is just a typo because your dictionary correctly shows $a_2$.
2. When $w_1$ enters the basis, $a_2$ (not $a_3$) should leave.