USA: +1-585-535-1023

UK: +44-208-133-5697

AUS: +61-280-07-5697

Simplex Method

The algorithm is discussed below with the help of a numerical example i.e., consider

 

Maximize z = 4x1 + 8x2 + 5x3

Subject to,                   x1 + 2x2 + 3x3  ≤ 18,

2x1 + 6x2 + 4x3 ≤ 15,

x 1 + 4x2 + x3 ≤ 6,

x 1, x2, x3 ≥ 0.

 

Step 1. If the problem is in minimization, then convert it to maximization as

Min z = - Max (-- z).

191

Step 2. All the right side constants must be positive. Multiply by - 1 both sides for negative constants. All the variables must be non-negative.

 

Step 3. Make standard form by adding slack variables for '::::;' type constraints, surplus variables for ‘ ≥ ‘ type constraints and incorporate these variables in the objective function with zero coefficients.

 

For example,   Maximum z = 4x1 + 8x2 + 5x3 + 0, s1 + O.s2 + O.s3

Subject to, x1 + 2x2 + 3x3 + s1 = 18,

2x1 + 6x2 + 4x3 + s2 = 15,

x1 + 4x2 + x3 + s3 = 6,

X1, x2, x3 ≥  0, s1, s2, s3   0

 

Note that an unit matrix due to Sp s2 and s3 variables is present in the coefficient matrix which is the key requirement for simplex method.

 

Step 4. Simplex method is an iterative method. Calculations are done in a table which is called simplex table. For each constraint there will be a row and for each variable there will be a column.

 

Objective function coefficients cj are kept on the top of the table. x8 stands for basis column in which the variables are called ' basic variables'. Solution column gives the solution, but in iteration 1, the right side constants are kept. At the bottom zj- cj row is called 'net evaluation' row.

 

In each iteration one variable departs from the basis and is called departing variable and in that place one variable enter which is called entering variable to improve the value of the objective function.

 

Minimum ratio column determines the departing variable.

 

Iteration 1.

 

Note. Variables which are forming the columns of the unit matrix enter into the basis column. In this table the solution is s 1 = 18, s2 = 15, s3 = 6, x1 = 0, x2 = 0, x3 = 0 and z = 0.

 

To test optimality we have to calculate zj - cj for each column as follows

These are displayed in the following table :

Decisions : If all zj - cj ≥ 0. then the current solution is optimal and stop. Else, Select the negative most value from zj - cj and the variable corresponding to this value will be the entering variable and that column is called 'key column'. Indicate this column with an upward arrow symbol.

 

In the given problem '- 8' is the most negative and variable x2 is the entering variable. If there is a tie in the most negative, break it arbitrarily.

 

To detem1ine the departing variable, we have to use minimum ratio. Each ratio is calculated as

[ soln] / [key column  ]

 

Component wise division only for positive elements (i.e., > 0) of the key column.

 

In this example,

min{ 18 /2, 15/6, 6/4} = min. {9,2.5,1.5} = ~-5

 

The element corresponding to the min. ratio i.e., here s3 will be the departing variable and the corresponding row is called 'key row' and indicate this row by an outward arrow symbol. The intersection element of the key row and key colunm is called key element. In the present example, 4 is the key element which is highlighted. This is the end of this iteration, the fmal table is displayed below :

 

Iteration 1:

Step 5. For the construction of the next iteration (new) table the following calculations are to be made :

 

(a)  Update the xB column and the cB column.

(b)  Divide the key row by the key element.

Other elements are obtained by the following formula

(d) Then go to step 4.

Iteration 2.

Iteration 3.

Iteration 4.

Since all zj - cj  ≥ 0, the current solution is optimal.

 

x1* =9/2,  x2* =0, x3* =3 /2, z* =512.

Note (exceptional cases).

 

(a) If in the key column, all the elements are non-positive i.e., zero or negative, then min. ratio cannot be calculated and the problem is said to be unbounded.

 

(b) In the net evaluation of the optimal table all the basic variables will give the value zero. If any non-basic variable give zero net evaluation then it indicates that there is an alternative optimal solution.

 

To obtain that solution, consider the corresponding column as key column and apply one simplex iteration.

 

(c) For negative variables, x ≤ 0, set x = - x', x' ≥ 0.

 

For unrestricted variables set x = x' - x" where x', x" ≥ 0.

 

Example 6. Solve the following by simplex method :

Maximize z = x1 + 3x2

Subject to, - x1 + 2x2 ≤ 2, x1 - 2x2  2, x1, x20.

 

Solution. Standard form of the given LPP can be written as follows

Maximum z = x 1 + 3x2 + O.s1 + O.s2

Subject to, - x1 + 2x2 + s1 = 2, x1 - 2x2 + s2 = 2,

x1, x2 ≥ 0, s 1, s2 slacks ≥ 0.

Iteration 1.

Iteration 2.

Since all the elements in the key column are non-positive, we can not calculate min. ratio. Hence the given LPP is said to be unbounded.