Simplex Method – Algorithm of Solving Linear Programming Problems

The simplex method is used in linear programming to optimize an objective function subject to a number of linear constraints. If you ever need tabular representation of data when writing articles for EzineArticles, consider using ASCII art tables inside HTML Pre tag. I’ve used them to illustrate simplex algorithm iterations. They might be a source of inspiration for you.

Now let’s see how to solve a linear programming model:

Maximize: Z = 1x1 + 2x2
subject to:

3x1 + 4x2 ≤ 5

6x1 + 7x2 ≥ 8

x1 ≥ 0, x2 ≥ 0
********* (1) *********

This model will be converted to canonical form (all constraints become equations). A constraint of the type “≤ 0” becomes equation by adding a non-negative variable (slack variable) and a constraint of the type “≥ 0” changes into equation by subtracting one (surplus variable).

Maximize: Z = 1x1 + 2x2 + 0x3 + 0x4
subject to:

3x1 + 4x2 + 1x3 + 0x4 = 5

6x1 + 7x2 + 0x3 + -1x4 = 8
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0
**************** (2)***************

Note that max{-7, -3, 0, +4, +6} = 6 = –min{+7, +3, 0, -4, -6}. That’s why max(Z(x)) = –min(-Z(x)). In other words, we get the max(Z(x)) by calculating the min(-Z(x)) and changing the sign at the end of the algorithm.

Two-phase method of building the necessary initial basis for the first iteration of the simplex algorithm requires adding an artificial variable for each constraint. In the end, they must all be equal to 0 for the model below to be equivalent with the model above. This trick allows us to obtain the unit vectors of the R² vector space and start iterations for an auxiliary minimum model (minimizing the sum of artificial variables). The maximum model above leads us to the following minimum model:

Minimize: Z = -1x1 + -2x2 + 0x3 + 0x4 + 0x5 + 0x6
subject to:

3x1 + 4x2 + 1x3 + 0x4 + 1x5 + 0x6 = 5

6x1 + 7x2 + 0x3 + -1x4 + 0x5 + 1x6 = 8
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0, x6 ≥ 0
********************** (3) **********************

As we mentioned, after calculations, all artificial variables (“x5”, “x6”) must become 0. Since artificial variables also satisfy the non-negativity condition (“≥ 0”) we conclude that they are all equal to 0 if and only if their sum is the minimum value 0. Therefore, in the first phase we minimize the sum of artificial variables:

Minimize: Z' = 0x1 + 0x2 + 0x3 + 0x4 + 1x5 + 1x6
subject to:

3x1 + 4x2 + 1x3 + 0x4 + 1x5 + 0x6 = 5

6x1 + 7x2 + 0x3 + -1x4 + 0x5 + 1x6 = 8
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0, x6 ≥ 0
********************** (4) **********************

Now we start first iteration of the simplex method.

.----+----+----+----+---+----+---+---+---+----+---.

|CB *|B * |XB *|cj * 0 * 0 ** 0 * 0 * 1 * 1 * | * |

+----+----+----+----+---+----+---+---+---+----+---+

| ** | ** | ** | ** |a1 |a2↓ |a3 |a4 |a5 |a6 *|θi |

|1 * |a5 *|5 * | ** |3 *|4 * |1 *|0 *|1 *|0 * |5/4|

|1 * |a6← |8 * | ** |6 *|7 * |0 *|-1 |0 *|1 * |8/7|

+----+----+----+----+---+----+---+---+---+----+---+

|Z'1 = 13 **** |zj * 9 * 11 * 1 * -1* 1 * 1 * | * |

+--------------+----+---+----+---+---+---+----| * |

| ************ |Δj * 9 * 11 * 1 * -1* 0 * 0 * | * |

'--------------+----+---+----+---+---+---+----+---'
******************** Tableau 1 ********************

Legend:

• cj: Objective function (Z') coefficients, j = 1...6
• aj: Column vectors of the constraints, j = 1...6
• B = {a5, a6}: Standard basis of R² vector space
• XB = (5, 8): Column of the basic feasible solution
(the elements of the solution
X = (x1, x2, x3, x4, x5, x6) = (0, 0, 0, 0, 5, 8)
corresponding to vectors outside the basis B are all equal to 0)
• CB: Coefficients of vectors from basis B of objective function (Z')
• Z'1 = ((CB)^T)*(XB) = (1, 1) * ((5, 8)^T)

Z'1 = 1 * 5 + 1 * 8 = 13

(CB)^T: Transpose of column vector CB
• zj = ((CB)^T)*(aj), j = 1...6
• Δj = zj - cj, j = 1...6

Since not all Δj: {9, 11, 1, -1, 0, 0} elements are ≤ 0,

we have not yet achieved the minimum of the objective function Z'.

Δ2 = 11 = max{9, 11, 1, -1, 0, 0}

Δ2 ⇒ a2↓
• θi = XBi / a2↓i, i ∈ {5, 6 } and a2↓i > 0

θi = --, if a2↓i ≤ 0

θ6 = 8/7 = min{5/4, 8/7}

θ6 ⇒ a6←

The new vector “a2↓” replaces in basis B the old vector “a6←” which is leaving the basis B. The tableau element where the entering vector (“a2↓”) and the leaving vector (“a6←”) intersect is known as the pivot element ( 7 ). We must divide all elements in the pivot row {8, 6, 7, 0, -1, 0, 1} by the pivot element to obtain a +1 in the pivot element position {8/7, 6/7, +1, 0, -1/7, 0, 1/7}. The remaining elements of the pivot column become 0’s.

Now we need to eliminate all the coefficients in the pivot column except the pivot element. This is done by simple Gaussian operations. To remove the pivot column element in some row “k” for example, we proceed as follows:

• (new row “k”) = (row “k”) – (pivot column coefficient in row “k”) * (pivot row)

• (3/7, -3/7, 0, 1, 4/7, 1, -4/7) = (5, 3, 4, 1, 0, 1, 0) – 4 * (8/7, 6/7, 1, 0, -1/7, 0, 1/7)

The second iteration is starting.

.----+----+----+----+------+---+----+------+---+------+---.

|CB *|B * |XB *|cj * 0 **** 0 * 0 ** 0 **** 1 * 1 *** | * |

+----+----+----+----+------+---+----+------+---+------+---+

| ** | ** | ** | ** |a1 ** |a2 |a3↓ |a4 ** |a5 |a6 ** |θi |

|1 * |a5← |3/7 | ** |-3/7 *|0 *|1 * |4/7 * |1 *|-4/7 *|3/7|

|0 * |a2 *|8/7 | ** |6/7 * |1 *|0 * |-1/7 *|0 *|1/7 * |-- |

+----+----+----+----+------+---+----+------+---+------+---+

|Z'2 = 3/7 *** |zj * -3/7 * 0 * 1 ** 4/7 ** 1 * -4/7 *| * |

+--------------+----+------+---+----+------+---+------| * |

| ************ |Δj * -3/7 * 0 * 1 ** 4/7 ** 0 * -11/7 | * |

'--------------+----+------+---+----+------+---+------+---'
*********************** Tableau 2 ************************

Since not all Δj: {-3/7, 0, 1, 4/7, 0, -11/7} elements are ≤ 0, we have not yet achieved the minimum of the objective function Z’.

.----+----+----+----+------+---+---+------+----+------+---.

|CB *|B * |XB *|cj * 0 **** 0 * 0 * 0 **** 1 ** 1 *** | * |

+----+----+----+----+------+---+---+------+----+------+---+

| ** | ** | ** | ** |a1 ** |a2 |a3 |a4 ** |a5 *|a6 ** |θi |

|0 * |a3 *|3/7 | ** |-3/7 *|0 *|1 *|4/7 * |1 * |-4/7 *| * |

|0 * |a2 *|8/7 | ** |6/7 * |1 *|0 *|-1/7 *|0 * |1/7 * | * |

+----+----+----+----+------+---+---+------+----+------+---+

|Z'3 = 0 ***** |zj * 0 **** 0 * 0 * 0 **** 0 ** 0 *** | * |

+--------------+----+------+---+---+------+----+------| * |

| ************ |Δj * 0 **** 0 * 0 * 0 **** -1 * -1 ** | * |

'--------------+----+------+---+---+------+----+------+---'
************************ Tableau 3 ************************

Since all Δj: {0, 0, 0, 0, -1, -1} elements are ≤ 0, the minimum of objective function Z’ has been reached. In the last table result that the minimum sum of artificial variables is Z’3 = 0. Therefore, the model of minimum below has solutions.

Minimize: Z = -1x1 + -2x2 + 0x3 + 0x4
subject to:

3x1 + 4x2 + 1x3 + 0x4 = 5

6x1 + 7x2 + 0x3 + -1x4 = 8
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0
***************** (5)****************

It is useful to reuse data. In the second phase, we will complete the next table with data from “aj”, “XB”, “B” columns of the previous tableau and with coefficients of new objective function “Z” from above model. We will rebuild the other calculations and then resume iterations:

.----+----+----+----+-------+----+---+------+----.

|CB *|B * |XB *|cj * -1 **** -2 * 0 * 0 *** | ** |

+----+----+----+----+-------+----+---+------+----+

| ** | ** | ** | ** |a1 *** |a2 *|a3 |a4↓ * |θi *|

|0 * |a3← |3/7 | ** |-3/7 * |0 * |1 *|4/7 * |3/4 |

|-2 *|a2 *|8/7 | ** |6/7 ** |1 * |0 *|-1/7 *| -- |

+----+----+----+----+-------+----+---+------+----+

|Z1 = -16/7 ** |zj * -12/7 * -2 * 0 * 2/7 * | ** |

+--------------+----+-------+----+---+------| ** |

| ************ |Δj * -5/7 ** 0 ** 0 * 2/7 * | ** |

.--------------+----+-------+----+---+------+----.
******************** Tableau 4 ******************

Since not all Δj: {-5/7, 0, 0, 2/7} elements are ≤ 0, we have not yet achieved the minimum of the objective function Z.

.----+----+----+----+------+----+------+----+---.

|CB *|B * |XB *|cj * -1 ** -2 ** 0 **** 0 * | * |

+----+----+----+----+------+----+------+----+---+

| ** | ** | ** | ** |a1 ** |a2 *|a3 ** |a4 *|θi |

|0 * |a4 *|3/4 | ** |-3/4 *|0 * |7/4 * |1 * | * |

|-2 *|a2 *|5/4 | ** |3/4 * |1 * |1/4 * |0 * | * |

+----+----+----+----+------+----+------+----+---+

|Z2 = -5/2 *** |zj * -3/2 * -2 * -1/2 * 0 * | * |

+--------------+----+------+----+------+----| * |

| ************ |Δj * -1/2 * 0 ** -1/2 * 0 * | * |

.--------------+----+------+----+------+----+---.
******************* Tableau 5 *******************

Since all Δj: {-1/2, 0, -1/2, 0} elements are ≤ 0, the minimum (Z2 = -5/2) of objective function Z has been reached. Therefore, maximum of the initial model (1) is Z = -Z2 = -(0 * 3/4 + (-2) * 5/4) = 5/2. The optimal solution is (x1, x2) = (0, 5/4).