Tag Archives: duality theory

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.

Primal Dual Relationships in Linear Programming (Duality Theory in LP)

The dual model of a Linear Programming problem consists of an alternative modeling instance that allows us to recover the information of the original problem commonly known as primal model. Therefore it is sufficient to solve one of them (primal or dual) to obtain the optimal solution and the optimal value of the equivalent problem (primal or dual as applicable). For this you can use the conditions of the Complementary Slackness Theorem.

Primal Dual Relationships can be summarized in the following table:

primal-dual-relationship

The above table can be interpreted both left to right and right to left. Below is an optimization model to consider as the primal problem and that in a previous article was resolved through the Two Phase Simplex Method.

example-linear-programming-

Because in this case the problem is a primal minimization, to define their respective dual problem we will read the table summarizing the relationships of duality from left to right. Consequently, the dual problem will be one of maximization. Additionally the first and second constraints of the primal problem will define the decision variables (dual variables) in the dual problem (Y1 and Y2, respectively), with the coefficients in the objective function the current values of the right sides of the primal problem constraints. Thus the function of the dual problem is defined by the following expression:

objective-function-duality

Then for each variable in the primal problem we will have the same amount of constraints than the dual problem. In this case the variables X1, X2 and X3 define the structure of restrictions 1, 2 and 3 in our dual problem. For example the first constraint of the dual problem (associated with primal variable X1) will be 2Y1+2Y2<=160. Note that the coefficients weighted to the dual variables are variable parameters associated with the primal X1 in the first and second constraint, respectively. The constraint on the dual problem is of the “<=” because the X1 variable in the primal minimization problem has the status of non-negativity “>=0”. Finally the right side of the restriction is the coefficient of the X1 variable of the objective function of the primal problem. Following this procedure the constraints of the dual problem will be:

constraints-dual

Finally, because the first 2 restrictions of the primal problem are “>=” type in the primal minimization problem, the dual respective variables associated in the maximization problem will not be negative. Thus the dual problem is:

dual-problem

Complementary Slackness Theorem (Duality Theory in Linear Programming)

One of the major theorems in the theory of duality in Linear Programming is the Complementary Slackness Theorem. This theorem allows us to find the optimal solution of the dual problem when we know the optimal solution of the primal problem (and vice versa) by solving a system of equations formed by the decision variables (primal and dual) and constraints (primal and dual model).

The importance of this theorem is that it facilitates the resolution of the models of linear optimization, allowing you to find the simplest model to address (from the algorithmic point of view) because either way you will get the results of the associated equivalence model (may it be a primal or dual model).

Let us consider the following Linear Programming model (here in after primal) in 2 variables whose optimal solution is X=14/5 and Y=8/5 with optimal value V(P)=20.8.

primal-model

The dual model associated with the primal model is:

dual-model

Then the Complementary Slackness Theorem shows us the following relationships:

complementary-slackness-the

As we know X=14/5 and Y=8/5 (primal optimal solution). If we replace these values of X and Y in the third and fourth equation we generate a 2×2 system of equations in terms of A and B whose solution corresponds to A=6/5 and B=2/5 (a feasible and optimal solution of the dual model). If we subsequently evaluate the objective function in the dual problem of this solution we obtain: V(D)=12(6/5)+16(2/5)=20.8 which is similar to the primal problem’s optimum value (satisfy the Strong Duality Theorem).

Notes: Note that the 1 and 2 constraints of the primal problem are active at the optimum, i.e. equality is met.