Chapter 4 Duality - Stanford University

1 Chapter 4 DualityGiven any linear program, there is another related linear program called thedual. In this Chapter , we will develop an understanding of the dual linearprogram. This understanding translates to important insights about manyoptimization problems and algorithms. We begin in the next section byexploring the main concepts of Duality through the simple graphical exampleof building cars and trucks that was introduced in Section Then, wewill develop the theory of Duality in greater generality and explore moresophisticated A Graphical ExampleRecall the linear program from Section , which determines the optimalnumbers of cars and trucks to build in light of capacity constraints. There aretwo decision variables: the number of carsx1in thousands and the numberof trucksx2in thousands. The linear program is given bymaximize3x1+ (profit in thousands of dollars)subject to 100(car assembly capacity) 100(truck assembly capacity)4x1+ 100 (metal stamping capacity)3x1+ 6x2 100(engine assembly capacity)x 0(nonnegative production).

2 The optimal solution is given approximately byx1= andx2= ,generating a profit of about $ million. The constraints, feasible region,and optimal solution are illustrated in Figure assemblyengine assemblymetal stampingcar assemblyfeasible solutionstrucks produced (thousands)cars produced (thousands)optimal solutionFigure : The constraints, feasible region, and optimal solution of the linearprogram associated with building cars and in matrix notation, the linear program becomesmaximizecTxsubject toAx bx 0,wherec=[ ],A= 00 andb= 100100100100 .The optimal solution of our problem is a basic feasible solution. Sincethere are two decision variables, each basic feasible solution is characterizedby a set of two linearly independent binding constraints. At the optimalsolution, the two binding constraints are those associated with metal stamp-ing and engine assembly capacity.

3 Hence, the optimal solution is the uniquesolution to a pair of linear equations:4x1+ 100 (metal stamping capacity is binding)3x1+ 6x2= 100(engine assembly capacity is binding).In matrix form, these equations can be written asAx=b, whereA=[(A3 )T(A4 )T]andb=[b3b4].c Benjamin Van Roy and Kahn Mason85 Note that the matrixAhas full rank. Therefore, it has an inverseA some calculations, we get (approximately)A 1=[ ].The optimal solution of the linear program is given byx=A 1b, and there-fore, the optimal profit iscTA 1b= Sensitivity AnalysisSuppose we wish to increase profit by expanding manufacturing such a situation, it is useful to think of profit as a function of a vector <4of changes to capacity. We denote this profit byz( ), defined to bethe maximal objective value associated with the linear programmaximizecTxsubject toAx b+ x 0.

4 ( )Hence, the maximal profit in our original linear program is equal toz(0). Inthis section, we will examine how incremental changes in capacities influencethe optimal profitz( ). The study of such changes is a situation where the metal stamping and engine assembly ca-pacity constraints are binding at the optimal solution to the linear program( ). Then, this optimal solution must be given byx=A 1(b+ ), and theoptimal profit must bez( ) =cTA 1(b+ ), where =[ 3 4].Furthermore, the difference in profit isz( ) z(0) =cTA 1 .This matrix equation provides a way to gauge the impact of changes incapacities on optimal profit in the event that the set of binding constraintsdoes not change. It turns out that this also gives us the information requiredto conduct sensitivity analysis. This is because small changes in capacitieswill not change which constraints are binding.

5 To understand why, considerthe illustration in Figure , where the engine assembly capacity is increasedby a small amount. Clearly, the new optimal solution is still at the inter-section where metal stamping and engine assembly capacity constraints arebinding. Similarly, though not illustrated in the figure, one can easily see that86incremental changes in any of the other capacity constraints will not changethe fact that metal stamping and engine assembly capacity constraints produced (thousands)cars produced (thousands)original optimumnew optimumFigure : Changes in the optimal solution brought about by a small increase incapacity for engine observation does not hold when we consider large changes. As illus-trated in Figure , sufficiently large changes can result in a different set ofbinding constraints. The figure shows how after a large increase in engineassembly capacity, the associated constraint is no longer binding.

6 Instead,the truck assembly capacity constraint becomes profit to quantity of theith resource is the rateat whichz( ) increases as iincreases, starting from i= 0. It is clearthat small changes in non binding capacities do not influence profit. Hence,y1=y2= 0. From the preceding discussion, we havez( ) z(0) =cTA 1 ,and therefore[y3y4]=cTA 1=[3 ][ ]=[ ].In other words, the sensitivity is about $ million per percentage ofmetal stamping capacity and $ million per percentage of engine assem-bly capacity. If a 1% increase in metal stamping capacity requires the sameinvestment as a 1% increase in engine assembly, we should invest in Benjamin Van Roy and Kahn Mason871020304010203040trucks produced (thousands)cars produced (thousands)original optimumnew optimumFigure : Changes in the optimal solution brought about by a large increase incapacity for engine Shadow Prices and Valuation of the FirmThe sensitivities of profit to resource quantities are commonly calledshadowprices.

7 Eachith resource has a shadow priceyi. In our example of buildingcars and trucks, shadow prices for car and truck assembly capacity are prices of engine assembly and metal stamping capacity, on the otherhand, are $ and $ million per percent. Based on the discussionin the previous section, if the metal stamping and engine assembly capacityconstraints remain binding when resource quantities are set atb+ , theoptimal profit is given byz( ) =z(0) +yT .A shadow price represents the maximal price at which we should be willingto buy additional units of a resource. It also represents the minimal price atwhich we should be willing to sell units of the resource. A shadow price mighttherefore be thought of as the value per unit of a resource. Remarkably, if wecompute the value of our entire stock of resources based on shadow prices,we get our optimal profit!

8 For instance, in our example of building cars andtrucks, we 100 + 100 = we will now explain, this is not just a coincidence but reflects a funda-mental property of shadow the discussion above we know that as long as the metal stampingand engine assembly constraints are binding, thatz( ) =z(0) +yT . Ifwe let = b, then the resulting linear program has 0 capacity at each88plant, so the optimal solution is 0, with associated profit of 0. Moreover,both the metal stamping and engine assembly constraints are still means that 0 =z( b) =z(0) +yT( b). Rearranging this gives thatz(0) =yTb. This is a remarkable fundamental result: the net value of ourcurrent resources, valued at their shadow prices, is equal to the maximalprofit that we can obtain through operation of the firm , the value ofthe The Dual Linear ProgramShadow prices solve another linear program, called thedual.

9 In order todistinguish it from the dual, the original linear program of interest in thiscase, the one involving decisions on quantities of cars and trucks to build inorder to maximize profit is called theprimal. We now formulate the understand the dual, consider a situation where we are managing thefirm but do not know linear programming. Therefore, we do not know exactlywhat the optimal decisions or optimal profit are. Company X approaches usand expresses a desire to purchase capacity at our factories. We enter into anegotiation over the pricesy <4that we should charge per percentage ofcapacity at each of our four have any chance of interesting us, the prices must be nonnegative:y 0. We also argue that there are fixed bundles of capacity that we can useto manufacture profitable products, and the pricesymust be such that sellingsuch a bundle would generate at least as much money as manufacturing theproduct.

10 In other words, we impose requirements + 4y3+ 3y4 3 and + + 6y4 first constraint ensures that selling a bundle of capacity that could beused to produce a car is at least as profitable as producing the car. Thesecond constraint is the analog associated with production of our requirements, Company X solves a linear program to determineprices that minimize the amount it would have to pay to purchase all of ourcapacity:minimize100y1+ 100y2+ 100y3+ 100y4(cost of capacity)subject to + 4y3+ 3y4 3(car production) + + 6y4 (truck production)y 0(nonnegative prices).c Benjamin Van Roy and Kahn Mason89In matrix notation, we haveminimizebTysubject toATy cy optimal solution to this linear program isy= ,and the minimal value of the objective function is Remarkably, we haverecovered the shadow prices and the optimal profit!