How to Solve a Linear Programming Problem Using the Dual Simplex Method

Описание: In this lesson we learn how to solve a linear programming problem using the dual simplex method.

Note: You don't need to write the dual formulation of a problem to use the dual simplex. The Dual simplex is to solve the dual of given problem without actually writing its dual formulation. Sometime solving the dual problem is more economic (time -efficient) than primal problem. Since according to the dual theorem the value of primal and dual programming are the same at the optimal solution, we prefer to solve the dual instead of the original problem.
In general, to solve a linear programming problem, assuming that RHS is greater than or equal to zero, you can solve the problem Using
1- Regular simplex when all constraints are in from of less than or equal.
2- Big M or two phase when there are equal or greater than or equal constraints.
Problems of type 2, can also be solved using dual simplex if certain conditions are true for the problem : optimality condition and infeasibility.

Two conditions to solve a problem using dual simplex:
Optimality: recall that the optimal condition is when all values in the row of Z of the simplex table are positive or zero for a max problem and when all values of z-row of the simplex table are negative or zero for a min problem

Infeasibility: It means that you have to have at least one negative in the RHS of your initial table.

So, if any the above two conditions are not true you cannot use the dual simplex to solve the problem. You might instead use the big-M or two-phase to solve the problem.