Dual Simplex Method

Dual simplex method (cont.):

In regular simplexmethod, we first decide incoming variable. In dual simplex we first decide outgoing variable, i.e., key row.

(a) Criterion for outgoing variable:

The row, which has got the largest negative value (highest number with negative sign) in the capacity column, becomes the key row and the variable having a solution in that row becomes outgoing variable. If all the values in the capacity column are non-negative and if all net evaluation row elements are negative or zeros, the solution is optimal basic feasible solution. In the given example, the row containing S2 is having highest number with negative sign; hence S2 is the outgoing variable.

(b) Criterion for incoming variable:

Divide the net evaluation row elements by corresponding coefficients (if negative) of the key row. The column for which the coefficient is smallest becomes key column and the variable in that column becomes entering variable. (If all the matrix coefficients in the key row are positive, the problem has no feasible solution). In the problem given, variable satisfies the condition, hence variable 'b' is the incoming variable. The rest of the operation is similar to regular simplex method.

The solution is infeasible. As net evaluation row elements are negative the solution remains optimal and as basic variables are negative, it is infeasible. Now both rows of S1 and S3 are having –1 in capacity column, any one of them becomes key

row. Let us select first row as key row. The quotient row shows that ‘a’ as the incoming variable.

As the net evaluation row elements are negatives or zeros, the solution is optimal and feasible. Answer is a = 3/5 and b = 6/5 and profit Z = – Rs. 12/5. That is for minimization problem the minimum cost is Rs. 12/5.