# Simplex: duplicate constraints

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.

$\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$
$$\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}$$