How to Solve a Linear Programming model with Dual Simplex Method

The Dual Simplex Method offers an alternative when solving Linear Programming (LP) models with algorithms. This method may be used in particular when the standard way to carry a linear programming model is not available from an initial basic feasible solution. Consider the following LP problem to illustrate the application of the Dual Simplex Method:

lp-dual-simplex-method

To solve the problem above in a standard form, we must add 2 excess non-negative variables for constraints 1 and 2, which we will respectively call X4 and X5. Thus the problem in its standard format is defined by:

standard-lp-dual-simplex-me

Then we build the initial tableau of the Simplex Method:

initial-tableau-dual-simple

How to continue the iterations of the Simplex Method? Before that, it is necessary to have an initial basic feasible solution. In this context if we want to use X4 and X5 as basic variables (and hence X1, X2 and X3 as basic variables) it is required that X4 and X5 are greater than or equal to zero, however, their coefficients in the respective rows are negative and therefore we can’t use them (matrix with “1” as a diagonal, and all the other coefficients at zero). So to form the identity we can multiply by “-1” row 1 and 2, obtaining the following:

transformation-tableau-dual

Now X4 and X5 are basic variables and adopt the values of -1 and -3/2, respectively, which clearly does not satisfy the conditions of non-negativity for the decision variables, i.e. they do not correspond to a basic feasible solution. However, in this instance we can apply the Dual Simplex Method as an alternative resolution. To do this, we will select a variable to leave the base and adopt as a criterion for basic variable associated with “more negative” right hand side (RHS). In this instance the variable is X5. Then to determine which variable will go into the base we find a minimum quotient between the negative of the reduced cost of the non-basic variables and the strictly less than zero entries for non-core variables in row 2 (row associated with more negative right). I.e.: Min {-160/-2; -120/-2; -280/-2} = 60, then the minimum quotient is reached in the second column associated with the non-basic variable X2, therefore said variable enters the base.

Finally one iteration is done by performing the operations of the necessary rows, so we enter X2 into the base, meanwhile at the same time X5 leaves the base. The results are:

iteration-simplex-dual-meth

Note that now the basic variables are X4 and X2 where only X4 = -1/4 which does not satisfy the condition of being a feasible basic solution. Therefore we make a new iteration, in this case taking the base to the X4 variable and calculate the minimum quotient: Min {-40/-1; -160/-3; -60/-1/2} = 40, then the minimum quotient is in the first column, therefore variable X1 enters the base. Consequently the remaining table is updated as follows:

final-tableau-dual-simplex-

The basic variables are now X1=1/4 and X2=1/2 (which meet the conditions of non-negativity). Additionally, the reduced cost of the non-basic variables is greater than or equal to zero, therefore we face the optimal solution. We can additionally recognize that the optimum value is V(P)=100 that would be obtained by evaluating the optimal solution to the objective function, however, the value is obtained by said process with a changed sign.

The example above allowed us to appreciate how through the Dual Simplex Method can solve a linear programming model that after being solved by the standard form does not provide an initial basic feasible solution. Significantly, it is not the only algorithmic alternative to which we can appeal. For example we could have achieved the same results using the Two-Phase Simplex Method with some more work. Alternatively we can define the proposed problem with the dual model and solve it by the Simplex Method so that we may later use the conditions of Complementary Slackness Theorem. In summary before we use an optimization model we have several alternatives for resolution and it is the duty of solver to evaluate the different paths that we can take in terms of its complexity.

Rating: 4.7/5. From 18 votes.
Please wait...

3 thoughts on “How to Solve a Linear Programming model with Dual Simplex Method

  1. Giuseppe

    There a typo: “I.e.: Min {-160/-2; -120/-2; -280/60} = -2”
    It should be “I.e.: Min {-160/-2; -120/-2; -280/-2} = 60”

    Reply

Leave a Reply to Giuseppe Cancel reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.