1
$\begingroup$

I'm trying to understand how the two-phase simplex algorithm works, this site explains it using a simple example: http://optlab.mcmaster.ca/feng/4O03/Two.Phase.Simplex.pdf

I've tried to come up with some edge cases myself, and I'm stuck on this one, what am I doing wrong?

Minimize $x$ where $x \ge 1000$ and $x \ge 1000$

Obviously this is a dumb example, but the same issue arises when some constraints are linear combinations of each other.

Phase 1

We rewrite this linear program as a system of equations, where $s_1$, $s_2$ are the surplus variables and $a_1$ and $a_2$ are the artificial variables:

$\left\{ \begin{array}{c} x - s_1 +a_1=1000\\ x - s_2 +a_2=1000 \end{array} \right.$

We start by minimizing $a_1 + a_2$, so maximize $p = -a_1 - a_2 = (x - s_1 - 1000) + (x - s_2 - 1000) = 2x - s_1 - s_2 - 2000$

$\iff -2x - s_1 - s_2 + p = -2000$

This gives our starting tableau:

$$ \begin{array}{c|cccccc|c} &x&s_1&s_2&a_1&a_2&p&A\\ \hline a_1&1&-1&0&1&0&0&1000\\ a_2&1&0&-1&0&1&0&1000\\ \hline p&-2&1&1&0&0&1&-2000 \end{array} $$

After pivoting around column $1$, row $1$:

$$ \begin{array}{c|cccccc|c} &x&s_1&s_2&a_1&a_2&p&A\\ \hline x&1&-1&0&1&0&0&1000\\ a_2&0&1&-1&-1&1&0&0\\ \hline p&0&-1&1&2&0&1&0 \end{array} $$

The next column to pivot around is row $2$, but there's no row that works! There isn't a positive $\frac{A}{pivot}$ ratio:

$\frac{1000}{-1} = -1000 \le 0$

$\frac{0}{1} = 0 \le 0$

It seems like every explanation of the algorithm assumes there will always be a row with a positive ratio. It looks like the algorithm got stuck, we didn't even get to Phase 2, but the program definitely has a valid solution. What went wrong?

I'm looking for an answer that works in every case, not just this trival example. Just removing one of the constraints isn't a real solution.

$\endgroup$
1
$\begingroup$

The salient point is that the entries of the RHS have to be non-negative. You calculate the minimum of the fractions. Only the entries in the matrix has to be positive. The short notation is

$\min\bigg\{\frac{b_i}{a_{ij^*}}|a_{ij^*}>0\bigg\} $

where $b_{i}\geq 0$

In your case $\min\bigg\{\frac{b_2}{a_{22^*}}\bigg\}= \min\bigg\{\frac{0}{1}\bigg\}= 0 \quad \color{green} \checkmark $

Thus the final simlex tableau is

$$ \begin{array}{c|cccccc|c} &x&s_1&s_2&a_1&a_2&p&RHS\\ \hline x&1&0&-1&-1&1&0&1000\\ s_2&0&1&-1&-1&1&0&0\\ \hline p&0&0&0&1&1&1&0 \end{array} $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.