DualitySlide 3PowerPoint PresentationSlide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Complete Regularization of the Primal ProblemSlide 15Slide 16Slide 17Slide 18Slide 19Duality theoremsSlide 21Slide 22Slide 23Slide 24Slide 25Slide 26Duality theorem of liner progrmming.Slide 28Duality forlinear programmingDuality•One of the most important discoveries in the early development of linear programming was the concept of duality. •Every linear programming problem is associated with another linear programming problem called the dual. •The relationships between the dual problem and the original problem (called the primal) prove to be extremely useful in a variety of ways.Duality•it is the relationship between the primal and its dual, both on a mathematical and economic level, that is truly the essence of duality theory.•There is a small company in Melbourne which has recently become engaged in the production of office furniture. The company manufactures tables, desks and chairs. The production of a table requires 8 kgs of wood and 5 kgs of metal and is sold for $80; a desk uses 6 kgs of wood and 4 kgs of metal and is sold for $60; and a chair requires 4 kgs of both metal and wood and is sold for $50. We would like to determine the revenue maximizing strategy for this company, given that their resources are limited to 100 kgs of wood and 60 kgs of metal.•Now consider that there is a much bigger company in Melbourne which has been the lone producer of this type of furniture for many years. They don't appreciate the competition from this new company; so they have decided to tender an offer to buy all of their competitor's resources and therefore put them out of business.•The challenge for this large company then is to develop a linear program which will determine the appropriate amount of money that should be offered for a unit of each type of resource, such that the offer will be acceptable to the smaller company while minimizing the expenditures of the larger company.The dual problem uses exactly the same parameters as the primal problem, but in different location.Primal and Dual ProblemsPrimal Problem Dual ProblemMaxs.t.Mins.t.njjjxcZ1,miiiybW1,njijijbxa1,mijiijcya1,for for.,,2,1 mi .,,2,1 nj for.,,2,1 mi for.,,2,1 nj ,0jx,0iyIn matrix notationPrimal Problem Dual ProblemMaximizesubject to.0x.0yMinimizesubject tobAx cyA ,cxZ ,ybW Where and are row vectors but and are column vectors.c myyyy ,,,21bxExampleMaxs.t.Mins.t.Primal Problemin Algebraic FormDual Problem in Algebraic Form,5321xxZ ,18124321yyyW 182321 xx1222x41x0x,0x2152232 yy333 y1y0y,0y,0y321Maxs.t.Primal Problem in Matrix FormDual Problem in Matrix FormMins.t. ,5,321xxZ18124,22030121xx.0021xx .0,0,0,,321yyy 5,3220301,,321yyy 18124,,321yyyWDualityThe primal-Dual RelationshipComplete Regularization of the Primal Problem•Consider the following primal problem:•The second inequality can be changed to the less-than-or-equal-to type by multiplying both sides of the inequality by -1 and reversing the direction of the inequality; that is,•The equality constraint can be replaced by the following two inequality constraints:If both of these inequality constraints are satisfied, the original equality constraint is also satisfied.•Multiplying both sides of the inequality by –1 and reversing the direction of the inequality yields:•The primal problem can now take the following standard form:•The dual of this problem can now be obtained as follows:Duality theorems•Weak duality theorem If (i.e., x is feasible for the primal problem) and if (i.e., y is feasible for the dual problem), then Proof Indeed, 0,: xbAxxx{ }T:y y A y cΣT Tb y c x�T T T T Tsince and 0.b y x A y x c A y c x= � � �•What does this mean? It means that the objective function value of the primal is always greater than or equal to the objective function value of the dual. In other words any feasible solution of the primal minimization problem is an upper bound on the dual maximization optimum. Similarly, any feasible solution of the dual maximization task is a lower bound on the primal minimization optimum.•What is the significance of all this? We can see that either task (primal and dual) yields a bound on the optimal value of the other. Therefore, we obtain the following consequence:Duality theorems•Corollary If and , and if , then x* and y* are optimal solutions for the primal and dual problems, respectively.. Proof It follows from the weak duality theorem that for any feasible solution x of the primal problem Consequently x* is an optimal solution of the primal problem. We can show the optimality of y* for the dual problem using a similar proof. 0,:* xbAxxx{ }* T:y y A y cΣT * T *b y c x=T T * T *.c x b y c x� =•This is very useful in the following situation. Assume we found a feasible solution to the primal problem and we claim it is optimal. The fact that it is feasible can be easily checked by substituting it into the constraints, and seeing that all constraints are satisfied. But how do we prove that it is optimal? How can we make sure that there was no error in the program that found it?•An opportunity is offered by the above Corollary. If we can exhibit a dual feasible solution, such thatctx0 = λ0t bholds, then this proves the optimality of the primal solution, since the left-hand side is the primal objective function value, which is always bounded from below by the dual objective function value that is on the right-hand side. That is, we always havectx >= λt b•Now, if they are actually equal, then both must be optimal. In other words, if the primal objective function value is equal to the dual one, then this primal value must be the smallest possible, since the dual is always a lower bound. Thus, the dual solution can serve as a certificate of the optimality of the primal solution.•Note that in order to check
View Full Document
Unlocking...