Dual Simplex Method

Optimization · Axiom Academy

Learn how to maintain dual feasibility while achieving primal feasibility in linear programming The dual simplex method is useful when we have a dual feasible but primal infeasible starting tableau. This occurs when all objective row coefficients are non-negative (dual feasibility) but some right-hand side values are negative (primal infeasibility). 2. Choosing the Leaving Variable In dual simplex, we select the leaving variable by identifying the most negative value in the right-hand side (RHS) column. The corresponding row becomes the pivot row. 3. Choosing the Entering Variable Once the pivot row is selected, we determine the entering variable using the minimum ratio test: compute the ratio of the objective row coefficient to the pivot row coefficient (for negative pivot row coefficients only). Select the column with the smallest ratio in absolute value. After identifying the pivot element, perform the pivot operation to update the tableau. This eliminates the primal infeasibility in the selected row while maintaining dual feasibility throughout the entire tableau. 5. Comparison with Primal Simplex The primal simplex maintains primal feasibility while improving the objective function. The dual simplex maintains dual feasibility (optimal reduced costs) while achieving primal feasibility. Use primal when you have a feasible basic solution; use dual when you have optimal reduced costs but infeasible basic variables.

This is the written version of the interactive lesson above. See the full Optimization course.