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.

2 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).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.

3 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. 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).

4 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.

5 We denote this profit byz( ), defined to bethe maximal objective value associated with the linear programmaximizecTxsubject toAx b+ x 0.( )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].

6 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. To understand why, considerthe illustration in Figure , where the engine assembly capacity is increasedby a small amount.

7 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.

8 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. 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 ][ ]=[ ].

9 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.

10 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.