Home | ARTS | Operations Management | Simplex Algorithm - Linear Programming – Problem Solving [SIMPLEX METHOD]

Operations Management - Introduction to Operations Research

Simplex Algorithm - Linear Programming – Problem Solving [SIMPLEX METHOD]

   Posted On :  22.06.2018 10:43 pm

Check whether the objective function of the given L.P.P. is to be maximized or minimized.

Simplex Algorithm
 
 

Step 1

 
 
Check whether the objective function of the given L.P.P. is to be maximized or minimized.
 
If it is to be minimized then convert it into a problem of maximizing it by using the result

Minimum= -Maximum (-z)
 
 

Step 2

 
 
Check whether all ‘b’ values are non-negative. If any one of b is negative then multiply the corresponding inequality constraints by –1, so as to get all b values as non-negative.
 

Step 3

 
 
Convert all the in equations of the constraints into equations by introducing slack and/or surplus variables in the constraints. Put the costs of these variables equal to zero in the objective function, if the variables are slack variables. If surplus / artificial variables are added, then we need to use ‘Big M’ Method, which is a modified algorithm of the same simplex method.
 

Step 4

 
 
Obtain an initial basic feasible solution to the problem in the form Xb=B^-1 b and put it in the first column of the simplex table.
 

Step 5

 
 
Compute the net evaluations zj-cj (j=1,2…n) by using the relation,
 
Zj-Cj=CB yj-cj.
 
Examine the sign zj-cj.
 
i.        If all values are >=0, then initial basic feasible solution is an optimum feasible solution.

ii.      If at least one value < 0, go to next step.
 

Step 6

 
 
If there is more than one negative value, then choose most negative.
 
 
 

Step 7

 
 
Compute the ratio
 
{xb/yi, yi>0,I=1,2…. m} and choose the minimum of them.
 
The common element in the kth row and rth column is known as the leading element (pivotal element) of the table.
 

Step 8

 
 
Convert the leading element to unity by dividing its row by the leading element itself and all other elements in its column to zeros.
 

Step 9

 
 
Go to step 5 and repeat the process until either an optimum solution is obtained or there is an indication of unbounded solution.
 

Tags : Operations Management - Introduction to Operations Research
Last 30 days 159 views

OTHER SUGEST TOPIC