What are the Steps of Simplex Algorithm?

Simplex Algorithm (Manimization Case) :

Steps :

1.      Formulate the linear programming model.

2.      Convert the inequalities in the constraints into equalities by introducing slack, surplus and artificial variables. Whenever surplus variable is introduced, add artificial variable. Also in case of equality in the constraints split it into two constraints one with (£) and other with (³). Then introduce slack, surplus and artificial variables as required.

3.      Express the Objective function in terms of slack, surplus and artificial variables by assigning a 0 (zero) to slack, surplus and M as coefficient to artificial variables. Here M is considered a vary large number so as to finally drive out the artificial variables of basic solutions.

4.      Set up the initial simplex tableau as discussed in above procedure.

5.      Obtain Z_j, and C_j – Z_­j rows.

6.      Test for optimality : Test the current solution for optimality. If all the entries in the index row above are positive, then the current solution is optimum. If there exists any negative or zero number, the current solution can be improved by removing one basic variable from the basic and replacing it by non basic variable.

7.      Further iterate towards an optimum solution : To improve the current solution decide outgoing variable or departing variable and incoming variable or entering variables as follows :

(i)      Identify the column with highest negative value in C_j – Z row.  This column is known as key column or pivot column. Indicate this column with (­). The non basic variable at the top of the key column is the entering variable in the next iteration.

(ii)     Work out the ratios in the last column of the simplex tableau as by dividing each number in X_B column by the corresponding number the key column selected in above step. Identify the raw corresponding to minimum ratio.

This row is called key row or Pivot row. Indicate the row by (¬)

The corresponding variable in the kay row in known as departing variable or leaving variable.

(iii)    Identify the key element or pivot element as the number in the cell corresponding to key row and key column.

8.      Evaluate the new solution by constructing second simplex table.

Update the simplex table I as follows :

(a)     Divide all the entries in the key row by key element.

(b)     The entries in the rows are obtained by performing elementary row operations on all rows so that all elements except the key elements in the key column are zero. In other words for each row other than the key row use the formula :

New row elements = (Element in old rows)

{[Corresponding element above or below key element] x [Corresponding element above or below key element in the row replaced in (a)]}

New entries in the C_B column and X_B column are entered in the new table of the current solution.

(f)      Compute Z_j and C_j – Z_j rows. If all the entires in C_j – Z_j row are either negative or zero, an optimum solution has been obtained.

9.      If any of the numbers in C_j – Z_j row is negative or zero, repeat the iterations until an optimal / optimum solution has been obtained.