Simplex Method – Linear Programming Problem Solving Algorithm

The simplex method is used in linear programming to optimize an objective function subject to a series of linear constraints. If you ever need a tabular representation of data when writing articles for EzineArticles, consider using ASCII art tables within the HTML Pre tag. I have used them to illustrate iterations of simplex algorithms. They can 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 are converted to equations). A constraint of type “≤ 0” becomes an equation by adding a non-negative variable (slack variable) and a constraint of type “≥ 0” becomes an equation by subtracting one (slack 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
maximum{-7, -3, 0, +4, +6} = 6 = –
min{+7, +3, 0, -4, -6}. That’s why
maximum(Z(x)) = –
min(-Z(x)). In other words, we get the
maximum(Z(x)) calculating the
min(-Z(x)) and changing the sign at the end of the algorithm.

The two-stage approach to building the initial basis needed 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 so that the model below is equivalent to the model above. This trick allows us to obtain the unit vectors of the R² vector space and start iterations for a minimal auxiliary model (minimizing the sum of artificial variables). The maximum model above leads 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 the calculations, all the artificial variables (“x5”, “x6”) must become 0. Since the 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 the 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) **********************

We now start the 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←” coming out of basis B. The element of the frame where the entering vector (“a2↓”) and the leaving vector (“a6←”) intersect “) is known as the pivot element (
7 ). We must split all the elements in the pivot row {8, 6,
70, -1, 0, 1} by the pivot element to obtain a
+1 at the pivot element position {8/7, 6/7,
+1, 0, -1/7, 0, 1/7}. The remaining elements of the pivot column are converted to 0.

Now we need to remove all the coefficients in the pivot column except the pivot element. This is done by simple Gaussian operations. To remove the element from the pivot column 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 elements Δj: {-3/7, 0, 1, 4/7, 0, -11/7} are ≤ 0, we have not yet reached 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 elements Δj: {0, 0, 0, 0, -1, -1} are ≤ 0, the minimum of the objective function Z’ has been reached. In the last table it turns out that the minimum sum of artificial variables is Z’3 = 0. Therefore, the model of minima 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 for reusing data. In the second phase, we will complete the following table with the data of the columns “aj”, “XB”, “B” of the previous table and with the coefficients of the new objective function “Z” of the previous model. We’ll rebuild the other calculations, and then resume the 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 elements Δj: {-5/7, 0, 0, 2/7} are ≤ 0, we have not yet reached 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 elements Δj: {-1/2, 0, -1/2, 0} are ≤ 0, the minimum (Z2 = -5/2) of the 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).