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

Rating: 5.0. From 3 votes.
Please wait...

, , , , , , ,

Sin Comentarios aun. Se el primero en comentar!

Leave a Reply