Tutorial: The simplex method: Solving general linear programming problems

(This topic is also in Section 6.4 in Finite Mathematics and Applied Calculus)

I don't like this new tutorial. Take me back to the older tutorial!

Resources

Pivot and Gauss-Jordan tool

Excel pivot and Gauss-Jordan tool

Simplex method tool

Nonstandard maximization problems; slack and surplus variables

%%Note You need to know how to do standard maximization problems in order to follow this tutorial, so go back to the %%lpstd if necessary.

In the %%lpstd we learned that a standard maximization problem is a LP problem where:

We are to find the maximum (not minimum) value of the objective function.
All the decision variables $x_1, x_2, ..., x_n$ are constrained to be non-negative.
All further constraints have the form $bx_1 + bx_2 + ... + bx_n \bold{\color{#b50b0b}{\leq}} c$ (and not $\geq c$), and $c$ cannot be negative.

A general maximization problem is almost the same, except that we drop the last requirement above:

General maximization problem
A general maximization problem is an LP problem satisfying (1) and (2) above, but where the further constraints can have the form either

$bx_1 + bx_2 + ... + bx_n \color{#b50b0b}{{}\leq{}} c$

for non negative $c$ as in standard maximization problems, or

$bx_1 + bx_2 + ... + bx_n \color{#b50b0b}{{}\geq{}} c$

for positive $c$. (If $c = 0$ we multiply through by $-1$ to convert it to a ${}\leq 0$ inequality as we would with standard maximization problems.)

%%Examples
1. #[The following is a general maximization problem:][El siguiente es un problema de maximización general:]#

#[Maximize][Maximizar]# \t $p = 2x - 3y + z$ \\ #[subject to][sujeto a]# \t $3y + z \leq 0$ \\ \t $2x + y - z \geq 10$ \\ \t $x \geq 0, y \geq 0, z \geq 0$.

2. The following LP problem can be rewritten a general maximization problem:

#[Maximize][Maximizar]# \t $p = 3x-3y-8z$ \\ #[subject to][sujeto a]# \t $x-z = 5$ \\ \t $3y+5z \geq 3$ \\ \t $9x-2z \geq 0$ \\ \t $x \geq 0, y \geq 0, z \geq 0$.

Look at the first constraint: to say that $x-z$ equals 5 is the same as saying that $x-z$ is simultaneously $\geq 5$ and $\leq 5$. Thus, we can replace the equality constraint by two inequality constraints:

#[Maximize][Maximizar]# \t $p = 3x-3y-8z$ \\ #[subject to][sujeto a]# \t $x-z \geq 5$ \\ \t $x-z \leq 5$ \\ \t $3y+5z \geq 3$ \\ \t $9x-2z \geq 0$ \\ \t $x \geq 0, y \geq 0, z \geq 0$.

Finally, we convert ${}\geq 0$ constraints to ${}\leq 0$ constraints by multiplying both side by $-1$, leaving us with a general maximization problem:

#[Maximize][Maximizar]# \t $p = 3x-3y-8z$ \\ #[subject to][sujeto a]# \t $x-z \geq 5$ \\ \t $x-z \leq 5$ \\ \t $3y+5z \geq 3$ \\ \t $-9x+2z \leq 0$ \\ \t $x \geq 0, y \geq 0, z \geq 0$.

As with the simplex method for standard maximization problems, the first step is to rewrite the problem as system of linear equations. The only difference here is how we deal with $/geq$ constraints:

Converting to equation form
If, for example, we have the constraint $3x-y+z \geq 8$, then to obtain an equation, we need to subtract a non-negative qualtity, called the surplus from the left-hand side:

$3x-y+z - s = 8 \qquad$ \t #[s is a nonnegative quantity called a surplus variable.][s es una cantidad no negativa llamada una variable de excendente.]#

%%Example A
#[Consider the following general LP maximization problem.][Vamos a considerar el siguente problema PL de maximización:]#

#[Maximize][Maximizar]# \t $p = 2x + 3y + z$ \\ #[subject to][sujeto a]# \t $x + y + z \leq 40$ \\ \t $-y + z \geq 10$ \\ \t $2x + y - z \geq 10$ \\ \t $x \geq 0, y \geq 0, z \geq 0$.

Next, we first convert all the constraints except those in the last line to equations using slack and surplus variables:

$x + y + z + s = 40$ \t $s$ is a slack variable. \\ $-y + z - t = 10$ \t $t$ is a surplus variable. \\ $2x + y - z - u = 10$ \t $u$ is a surplus variable. \\ $-2x - 3y - z + p = 0$ \t Objective function

One for you

Once we have converted the problem to equation form, we set up the first tableau and read off the first basic solution. Here is the first tableau for Example A:

%%Q Why are the second and third rows starred?
%%A The current values of $t$ and $u$ are both negative, indicating that the current basic solution with $x = y = z = 0$ is not feasible:

$0 + 0 + 0 \leq 40 \qquad$ \t ✔ \\ $-0 + 0 \geq 10$ \t ✘ \\ $2(0) + 0 - 0 \geq 10$ \t ✘

In the simplex method, none of the decision variables are allowed to be negative. If a slack or surplus variable is negative, that would indicate that the associated inequality is not ssatisfied, as we see above. Thus, In every tableau we always star all rows whose decision variables are negative to indicate that the current solution is not feasible.

Phase 1: Getting rid of the stars

To motivate what we will do, we make the following observation: As the "test ratio" rules for selecting a pivot in a given column guarantess that the resulting entering decision variable with be nonnegative (and the departing one will be zero) and so no new stars can get created, it follows that if a pivot happens to be in a starred row, that star will vanish for good! Thus in Phase 1, we try our best to find pivots that are in starred rows, regardless of what is going on in the bottom row, using the following rule:

How to choose the pivots in Phase 1
As with the simplex method for standard maximization problems, we will first select a column, then a specific entry in that column.

Pivot column The rule for the selecting a pivot column is this: Look at all the entries in the first starred row, excluding the last entry on the right (in the "answers" column). From these, choose the positive number with the largest magnitude; its column is the pivot column. If there are two or more candidates, choose any one. If there are no positive numbers to choose, that indicates that the feasible region is empty, and so the LP problem has no solution.

%%Example
In the initial tableau of the demonstration LP problem, the positive entry in the first starred row with the largest numerical value (excluding the answer column) is the 1, so the pivot column is the z-column. The actual pivot will be somewhere in this column.

Selecting the pivot We the same rules as we do for standard maximization problems to decide which entry to use as the pivot in the pivot column, but with a different tie-breaker rule:

The pivot must always be a positive number (zeros or negative numbers are not permitted as pivots).
For each positive entry $b$ in the pivot column, compute the ratio $a/b$, where $a$ is the number in the rightmost column in that row. We call this a test ratio.
Of these ratios, choose the smallest one. The corresponding number $b$ is the pivot.
Tie-breaker rule: If the test ratios for two or more entries in the pivot column qualify as the smallest, choose one that is in a starred row if possible.

Removing stars Once you have pivoted, then if the pivot happened to be in a starred row, the incoming variable for that row will have a positive value, so that star should be removed.

Removing additional stars If, in addition, the active variables assciated with other starred rows become zero after pivoting, those stars should be removed as well (as the associated surplus variables are no longer negative) and the row should be multiplied by $-1$ (to prevent that row from ever having to become starred in the future). Do this only with starred rows whose associated active variables beome zero.

%%Example
#[In the demonstration example we are working with, the pivot will be one of the 1s in the z-column. Here are the test ratios for these candidates:][En el ejemplo demonstración con el que estamos trabajando, el pivote será uno de los 1 en la columna-z. Aquí están las razones de prueba para estos candidatos:]# Because the smallest test ratio is in row 2, our pivot will be the highlighted 1 as shown.

#[Because the pivot is in a starred row, pivoting there will result in the star being (permanently) removed from that row becuase the entering variable ($z$) is non nogative:][Debido a que el pivote está en una fila marcada con estrella, pivotar allí hará que la estrella se elimine (permanentemente) de esa fila porque la variable entrante ($z$) no es negativa:]# Had the pivot not been in one of the starred rows, then both stars would have remained for the time being, but eventually the process described here results in all the stars being removed.

As we commented, repeated pivoting in Phase 1 eventually removes all the stars, at which point Phase 1 is done, and so we go to Phase 2:

Phase 2: proceed as with standard maximization problem.

Once we have eliminated the stars, we select the pivot as usual in the column of a decision variable with the most negative entry and continue until the problem is solved.

The simplex method for general maximization problems: Start to finish

Steps in the solution of a general maximization problem

Convert the problem to equation form using slack and surplus variables. (Eliminate decimals and fractions of possible by either multiplying the both sides of the constraints by suitable positive integers, or by multiplying both sides of the resulting equations by suitable positive integers.)
Set up the first tableau, where the active variables are the slack and surplus variables. Star all active variables whose values are negative; these will be the surplus variables in the first tableau.
Phase 1: Getting rid of the stars If there are starred rows, select a column of a decision variable whose entry in the first starred row is the most positive.
In that column, select a positive pivot whose test ratio is the smallest among other such entries.
Pivot on the selected entry using row operations of the specific type described in %%gjtutB, remembering to also indicate the entering active variable in the pivot row.
If the pivot was in a starred row, the new entering variable is positive, so the star should be removed. If, in addition, other active variables in starred rows become zero, remove those stars as well, but multiply those rows by $-1$.
Repeat steps 3 to 6 until there are no starred rows left.
Phase 2: Continue pivoting as in the simplex method for standard maximization problems until there are no negative indicators in the bottom row. The basic solution at that point gives a solution to the LP problem.

%%Example
#[Here is the complete solution to the LP problem we looked at above in Example A.][Aquí está la solución completa al problema de LP que vimos arriba en Ejemplo 1]#

#[Maximize][Maximizar]# \t $p = 2x + 3y + z$ \\ #[subject to][sujeto a]# \t $x + y + z \leq 40$ \\ \t $-y + z \geq 10$ \\ \t $2x + y - z \geq 10$ \\ \t $x \geq 0, y \geq 0, z \geq 0$.

Convert the problem to equation form using slack and surplus variables.
$x + y + z + s = 40$ \\ $-y + z - t = 10$ \\ $2x + y - z - u = 10$ \\ $-2x - 3y - z + p = 0$.
Set up the first tableau, where the active variables are the slack and surplus variables. Star all active variables whose values are negative.

Phase 1: Getting rid of the stars If there are starred rows, select a column of a decision variable whose entry in the first starred row is the most positive.

In that column, select a positive pivot whose test ratio is the smallest among other such entries.
Pivot on the selected entry using row operations of the specific type described in %%gjtutB, remembering to also indicate the entering active variable in the pivot row.

↓
If the pivot was in a starred row, the new entering variable is positive, so the star should be removed. If, in addition, other active variables in starred rows become zero, remove those stars as well, but multiply those rows by $-1$.

Repeat steps 3 to 6 until there are no no starred rows left.
As there is still a starred row, we choose its largest positive entry and need to pivot in that column:

↓

#[Therefore we pivot on the boxed 1.][Por lo tanto, pivotamos en la 1 encajada.]#

↓

As there are no more starred rows, Phase 1 is done, and so we go to Phase 2:

#[The most negative indicator in the bottom row is the $-4$ in the $y$-column, and the only possible pivot we can use is the $4$ in the first row:][El indicador más negativo en la fila inferior es $-4$ en la columna $y$, y el único pivote posible que podemos usar es $4$ en la primera fila:]#

↓

As there are no more negative entries in the bottom row under the decision variables, we are done, so the solution to the LP problem is the current basic solution:

$x = 20/2 = 10$; \t $y = 40/4 = 10$ \\ $z = 80/4 = 20$; \t $s = 0$; (#[inactive][inactiva]#) \\ $t = 0$; (#[inactive][inactiva]#); \t $u = 0$; (#[inactive][inactiva]#) \\ $p = 70/1 = 70$; \t (#[Maximum value of $p$][Valor má'ximo de $p$]#)

Your main task in this tutorial to do a complete calculation from start to finish for a nonstandard Lp problem:

General minimization LP problems

#[You might wonder why we have concentrated on maximization problems so much. What about minimization problems?][Quizás te preguntes por qué nos hemos concentrado tanto en los problemas de maximización. ¿Qué pasa con los problemas de minimización?]#

Solving general minimization LP problems
We deal with minimization problems by simply converting them to maximization problems, as illustrated in the following example:

%%Example
#[Here is a general LP minimization problem.][Aquí está un problema PL de minimización:]#

#[Minimize][Minimizar]# \t $c = 2x - 3y + 4z + w$ \\ #[subject to][sujeto a]# \t $4x + 2y + w \leq 10$ \\ \t $4x - 3y + z + w \geq 3$ \\ \t $2x + y - z \leq 10$ \\ \t $x \geq 0, y \geq 0, z \geq 0$.

#[In general, the minimum value of $c$ would be the maximum vaue of its negative, we can instead maximize the negative of $c$, which we will call $p$:][En general, el valor mínimo de $c$ sería el valor máximo de su negativo, en su lugar podemos maximizar el negativo de $c$, que llamaremos $p$:]#

#[Maximize][Maximizar]# \t $p = -2x + 3y - 4z - w$ \\ #[subject to][sujeto a]# \t $4x + 2y + w \leq 10$ \\ \t $4x - 3y + z + w \geq 3$ \\ \t $2x + y - z \leq 10$ \\ \t $x \geq 0, y \geq 0, z \geq 0$,

#[which we can now solve according to the instructions for general maximization problems.][que ahora podemos resolver de acuerdo con las instrucciones para problemas generales de maximización.]#

#[If you want to see the tableaus in solving this problem, simply copy and paste the following text in the][Si deseas ver los cuadros para resolver este problema, simplemente copie y pegue el siguiente texto en la]# Pivot and Gauss-Jordan tool. Maximize p = -2x + 3y - 4z - w subject to 4x + 2y + w <= 10 4x - 3y + z + w >= 3 2x + y - z <= 10

Now try some of the exercises in Section 6.4 in Finite Mathematics and Applied Calculus.