Steps to Solve a Linear Programming Problem
(LPP) Using the Simplex Method
1. Convert the Problem into Standard Form
Write the objective function and all the constraints in standard form. If a constraint
is of the type ≤, add a slack variable. If a constraint is of the type ≥, subtract a
surplus variable and introduce an artificial variable whenever necessary. Also,
ensure that all decision variables satisfy the non-negativity condition
xi ≥ 0, i = 1, 2, . . . , n.
2. Obtain the Initial Basic Feasible Solution
Treat the slack variables (or artificial variables, if required) as the initial basic vari-
ables. Assign zero values to all decision variables. This gives the initial basic feasible
solution.
3. Construct the Initial Simplex Table
Prepare the initial simplex table consisting of:
• Basic variables,
• Their objective function coefficients (CB ),
• Coefficients of all variables,
• Right-hand side (RHS) values.
This table serves as the starting point of the simplex algorithm.
4. Compute Zj and Cj − Zj
For each column, calculate
∑
Zj = (CB × aij ),
where CB represents the objective function coefficients of the basic variables.
Then compute
C j − Zj .
These values indicate whether the current solution can be improved.
5. Select the Entering Variable
For a maximization problem, choose the variable corresponding to the largest positive
value of Cj − Zj . The corresponding column is called the pivot column, and the
selected variable is called the entering variable.
If all values of Cj − Zj are less than or equal to zero, the current solution is optimal
and the algorithm terminates.
1
6. Select the Leaving Variable
For every positive element in the pivot column, compute
RHS
.
Pivot Column Element
The row with the smallest positive ratio is called the pivot row, and its basic variable
becomes the leaving variable.
If no positive element exists in the pivot column, the problem has an unbounded
solution.
7. Identify the Pivot Element
The element located at the intersection of the pivot row and the pivot column is
called the pivot element. It is used to generate the next simplex table.
8. Construct the New Simplex Table
Perform the following elementary row operations:
• Divide the pivot row by the pivot element so that the pivot element becomes 1.
• Transform all other elements in the pivot column to zero using elementary row
operations.
Prepare the new simplex table and again calculate Zj and Cj − Zj .
9. Check the Optimality Condition
If all values of Cj − Zj are less than or equal to zero (for a maximization problem),
the obtained solution is optimal.
Otherwise, repeat Steps 5 to 8 until the optimality condition is satisfied.
10. Write the Final Optimal Solution
From the final simplex table,
• The values of the basic variables are given by the RHS column.
• The values of all non-basic variables are zero.
• The corresponding value of the objective function gives the optimal value of Z.
Important Remarks
• If all values of Cj − Zj are less than or equal to zero, the current solution is optimal.
• If the minimum ratio test cannot be performed, the problem has an unbounded
solution.
• If any non-basic variable has Cj − Zj = 0 in the final table, the problem may have
multiple (alternative) optimal solutions.
• If an artificial variable remains positive in the final solution, the problem is infea-
sible.