Simplex Method – Algorithm of Solving Linear Programming Problems

Simplex Method – Algorithm of Solving Linear Programming Problems




The simplex method is used in linear programming to optimize an objective function unprotected 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 form:

Maximize: Z = 1x1 + 2x2

unprotected to:
3x1 + 4x2 ≤ 5
6x1 + 7x2 ≥ 8
x1 ≥ 0, x2 ≥ 0

********* (1) *********

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

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

unprotected to:
3x1 + 4x2 + 1x3 + 0x4 = 5
6x1 + 7x2 + 0x3 + -1x4 = 8

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0

**************** (2)***************

observe 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 restriction. In the end, they must all be equal to 0 for the form below to be equivalent with the form above. This trick allows us to acquire the unit vectors of the vector space and start iterations for an auxiliary minimum form (minimizing the sum of artificial variables). The maximum form above leads us to the following minimum form:

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

unprotected 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. consequently, in the first phase we minimize the sum of artificial variables:

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

unprotected 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 vector space

• XB = (5, 8): Column of the basic possible 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 however 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 component where the entering vector (“a2↓”) and the leaving vector (“a6←”) intersect is known as the pivot component ( 7 ). We must divide all elements in the pivot row {8, 6, 7, 0, -1, 0, 1} by the pivot component to acquire a +1 in the pivot component 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 component. This is done by simple Gaussian operations. To remove the pivot column component 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 however 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 consequence that the minimum sum of artificial variables is Z’3 = 0. consequently, the form of minimum below has solutions.

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

unprotected 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 past tableau and with coefficients of new objective function “Z” from above form. We will rebuild the other calculations and then begin again 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 however 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. consequently, maximum of the initial form (1) is Z = -Z2 = -(0 * 3/4 + (-2) * 5/4) = 5/2. The optimal solution is (x1, x2) = (0, 5/4).




leave your comment

Search

Top