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