How to use the simplex method for linear programs?

Question

I believe to be missing something important in the Simplex algorithm, because I can't get it to work.

From what I gather, there are three steps per iteration, given a matrix for a linear program in standard form:

• Look for negative terms in the objective function's row.
• If you find one, look for the pivot if there is any.
• We need to transform the pivot into a 1 and all other terms in the column to 0 using row operations.
• Repeat

---

Well then:

$$min z = x_2-x_1 + 1$$

subject to

$$\begin{cases}-2x_1 + x_2 \le 2\\ x_1 - 2x_2 \le 2\\ x_1+x_2 \le 5\\ x_i \le 0 \forall i \end{cases}$$

---

We require the standard form. We convert the inequalities to equations:

$$\begin{cases}-2x_1 + x_2 + x_3 + 0 + 0= 2\\ x_1 - 2x_2 + 0 + x_4 + 0 = 2\\ x_1+x_2 + 0 +0 + x_5= 5\\ x_i = 0 \forall i \end{cases}$$

We have the following matrix, where the last row represents the objective function:

$$\begin{bmatrix} -2 & 1 & 1 & 0 & 0 & 2 \\ 1 & -2 & 0 & 1 & 0 & 2 \\ 1 & 1 & 0 & 0 & 1 & 5 \\ -1 & 1 & 0 & 0 & 0 & z - 1 \end{bmatrix}$$

We proceed with the Simplex algorithm.

---

First iteration

Step 1: Look for negative terms in the objective function. The first column has a $-1$.

Step 2: Find the pivot. It is the first $1$ in the first column.

Step 3: We require the pivot to be $1$ and the rest of the column to be $0$. We do this with elemental row operations:

$$\begin{bmatrix} -2 & 1 & 1 & 0 & 0 & 2 \\ [1] & -2 & 0 & 1 & 0 & 2 \\ 1 & 1 & 0 & 0 & 1 & 5 \\ -1 & 1 & 0 & 0 & 0 & z - 1 \end{bmatrix}$$

$$2r_2 + r_1$$

$$\begin{bmatrix} 0 & -3 & 1 & 2 & 0 & 6 \\ [1] & -2 & 0 & 1 & 0 & 2 \\ 1 & 1 & 0 & 0 & 1 & 5 \\ -1 & 1 & 0 & 0 & 0 & z - 1 \end{bmatrix}$$

$$r_3 + r_4$$

$$\begin{bmatrix} 0 & -3 & 1 & 2 & 0 & 6 \\ [1] & -2 & 0 & 1 & 0 & 2 \\ 1 & 1 & 0 & 0 & 1 & 5 \\ 0 & 2 & 0 & 0 & 1 & z + 4 \end{bmatrix}$$

$$-r_2 + r_3$$

$$\begin{bmatrix} 0 & -3 & 1 & 2 & 0 & 6 \\ [1] & -2 & 0 & 1 & 0 & 2 \\ 0 & 3 & 0 & -1 & 1 & 3 \\ 0 & 2 & 0 & 0 & 1 & z + 4 \end{bmatrix}$$

---

Second iteration

Step 1: Look for negative terms in the objective function. There are none. The algorithm ends.

---

... But I know this is wrong, because according to the exercise's answer, I should have ended up with matrix of the form

$$\begin{bmatrix} 0 & 0 & 1 & 1 & 1 & 9 \\ 1 & 0 & 0 & 1/3 & 2/3 & 4 \\ 0 & 1 & 0 & -1/3 & 1/3 & 1 \\ 0 & 0 & 0 & 2/3 & 1/3 & z + 2 \end{bmatrix}$$

And done three iterations. Unfortunately the details of those iterations are not shown so I'm not sure what did I do wrong.

Answer 1

If I were you, I would change to another textbook/notes for clearer instructions. Using negative-valued variables is a source of mess. I'll change the original problem

$\min z = x_2-x_1 + 1$ such that

\begin{cases} -2x_1 + x_2 &\le 2 \\ x_1 - 2x_2 &\le 2\\ x_1 + x_2 &\le 5\\ x_i &\le 0 \forall i \tag{*} \end{cases}

to

$\min z = x_1-x_2 + 1$ such that

\begin{cases} 2x_1 - x_2 &\le 2 \\ -x_1 + 2x_2 &\le 2\\ -x_1 - x_2 &\le 5\\ x_i &\ge 0 \forall i \end{cases}

Note that the third constraint is redundant, so I'll omit it due to my laziness to simplify matter.

It's easy to graphically solve

$\min z = x_1-x_2 + 1$ such that

\begin{cases} 2x_1 - x_2 &\le 2 \\ -x_1 + 2x_2 &\le 2\\ x_i &\ge 0 \forall i \tag{#}. \end{cases}

Nonetheless, since you ask for a solution using the simplex method, I'll use this algorithm. Let $s_1$ and $s_2$ be the slack variables for the first and the second constraint in $(\#)$ respectively. Therefore, we have the following simplex tableau.

\begin{equation*} \begin{array}{rrrrr|l} & x_1 & x_2 & s_1 & s_2 & \text{RHS} \\ \hline s_1 & 2 & -1 & 1 & 0 & 2 \\ s_2 & -1 & 2 & 0 & 1 & 2 \\ \hline z & -1 & 1 & 0 & 0 & 1 \\ \end{array} \end{equation*}

In the last row, I change $z=x_1-x_2+1$ to $z-x_1+x_2 = 1$. The coefficient of $z$ is never changed, so I omit that to save ink. I write the tableau in this way so that you can directly read the objective function value at the lower right hand corner (reason: in the $z$ row of the tableau, we have zero coefficient for basic variables ($s_1$ and $s_2$); for non-basic variables ($x_1$ and $x_2$), their value is zero), and the basic feasible solution on the RHS.

From your calculations, I assume that you understand why the pivot element needs to be positive (for feasibility of the basic solution). Since we've assume that every variables (except $z$) is non-negative (so that things become easier), every entry on the RHS (except the lower right hand corner) is non-negative.

Now, forget the rule "look for negative terms in the objective function's row". Just treat this as pivot row operations (you need $\mathbf{e}_i$'s and the coefficient for basic variables to be zero in the objective function row of the tableau), and remember that the lower right hand corner is the objective function value which you want to minimize. What will you do? You'll do a pivot row operation to improve the objective function value.

In the following tableau, I just include the essential elements so as to see things clearly.

\begin{equation*} \begin{array}{rr|l} & \text{a non-basic variable} & \text{RHS} \\ \hline \text{a basic variable} & \heartsuit > 0 & \spadesuit \ge 0 \\ \hline z & \clubsuit & \text{obj. fct. val.} \end{array} \end{equation*}

After each pivot row operation, you'll have

\begin{equation*} \text{new obj. fct. val.} = \text{obj. fct. val.} - \frac{\spadesuit\clubsuit}{\heartsuit} \end{equation*}

Now, it's clear that

• in a maximization problem, you need $\clubsuit < 0$ so that the new objective function value will become greater than the original one;
• in a minimization problem (in this case), you need $\clubsuit > 0$ so that the new objective function value will become smaller than the original one.

Therefore, we choose $x_2$ and $s_2$ to be the entering and leaving variables respectively.

\begin{equation*} \begin{array}{rrrrr|l} & x_1 & x_2 & s_1 & s_2 & \text{RHS} \\ \hline s_1 & 2 & -1 & 1 & 0 & 2 \\ s_2 & -1 & 2^* & 0 & 1 & 2 \\ \hline z & -1 & 1 & 0 & 0 & 1 \\ \end{array} \end{equation*}

\begin{equation*} \begin{array}{rrrrr|l} & x_1 & x_2 & s_1 & s_2 & \text{RHS} \\ \hline s_1 & \frac32 & 0 & 1 & \frac12 & 3 \\ x_2 & -\frac12 & 1 & 0 & \frac12 & 1 \\ \hline z & -\frac12 & 0 & 0 & -\frac12 & 0 \\ \end{array} \end{equation*}

Therefore, $(x_1,x_2,s_1,s_2)=(0,1,3,0)$ is a basic feasible solution to $(\#)$. Hence, the solution to $(*)$ is $(x_1,x_2) = (0,-1)$ with objective function value $z=0$.

---

You may verify this using a LPP solver. Here's an example using GNU Octave.

octave:1> c=[-1 1]'; A=[-2 1; 1 -2; 1 1]; b=[2 2 5]';
octave:2> [x_min,z_min]= glpk(c,A,b,[-inf -inf]',[0,0]',"UUU","CC")
x_min =

   0
  -1

z_min = -1

In the objective function c, I skipped the term $+1$ for simpler code. As a result, $(x_1,x_2)=(0,-1)$ is the optimal solution to $(*)$.