Linear Programming
Simplex Method:
Steps:
 Determine the objective function Z. Objective may be maximization or minimization.

 For maximation problem the constraints would be < sign.
For minimization problem the constraints would be > sign.
 Introduce slack variable
For < sign – add the slack variable ie. Add S1
For > sign – subtract the slack variable and add artificial variable
ie. Subtract S1, add A1.
4. Change the Objective function
For S1 – Add ‘0S1’
For A1 – Add ‘MA1’
5. Simplex table format:


Cj







Quantity

Variable

Const.

X

Y

Z

S1

S2

RR


S1









S2










Zj









Cj  Zj







6. Zj is arrived by summation of constant column with X,Y,Z columns
7. Criteria for selecting the key column :
For Maxima ion Problem – Highest value of Cj – Zj
For Minimization Problem – Lowest Value of Cj – Zj
8. Divide the Quantity Column with Key column to arrive at RR
9. Criteria for Selecting the Key row :
For Maximation & Minimization Problem – Lowest Positive RR is selected
10. The Meeting Point is key Element
11. Criteria for deciding the optimal solution
For Maximation Problem – All elements in Cj – Zj row is negative or zero.
For Minimization Problem – All elements in Cj – Zj row is positive or zero
Note – For finding whether all the elements in Cj – Zj row is positive or zero
for minimization problem substitute all the ‘M’ with highest value.
12. If solution is not reached next table is formed.
13. Input for next table is
First key row in the next table is filled by dividing all the numbers in the key row of the previous table with the key element.
Remaining all the rows is arrived as follows: 
Corresponding previous _ (Value relating to that * Corresponding
Table row element row in the key column element in key row
in the 2^{nd} table as
filled in previous step)
14. Check the optimal solution, if not reached form the third table.
15. If solution is reached then answer is amount in quantity column corresponding to the variable.
Other Points : 
 We can convert the Minimization Problem into Maximation Problem. This is known as duality.
 We can change the > sign to < sign to match the problem
E.g. X + Y < 100
is converted into X  Y > 100