This engine was desiged to support the module on the Dual Simplex Method. Recall that the method deals with situations where we have a simplex tableau with the following features:
- Some of the right-hand side values (bi) are negative.
- The reduced costs satisfy the optimality condition.
These conditions are satisifed, for instance, in the framewrok of a mimimization problem whose cost coefficients are positive, the right hand side values are positive and the constraints are of the ">= " type. Here is such a simple problem:min 3x + 4y + 5z
2x + 3y + 7z >= 12
3x + 5y + 4z >= 10
x,y,z >= 0
If we multiply the constraints by -1, we obtain the following equivalent problem:min 3x + 4y + 5z
-2x -3y -7z <= -12
-3x -5y - 4z <= -10
x,y,z >= 0
So if we add two slack variables and set-up the conventional simplex tableau for this problem, the reduced costs will satisfy the optimality conditions but the first basic solution is not feasible because the right hand side values are negative.
A similar situation will arise when attempt to add one or more constraints to a "final" simplex tableau.
The method attempts to restore feasibility (make the right-hand side values non-negative) without causing the reduced costs to violate the optimality condition. If it fails, the conclusion is that the problem is infeasible.
If you are not familiar at all with this method you might be interested in reading our short description of the Dual Simplex Method.
© The University of Melbourne 1994-2000.
Disclaimer and Copyright Information. Conditions of use.