RE USNR TD where Ab, > 0 and Abs <0. Let (i) or (i pAb and ry = A lo UH anh ra Use the fact that Show dat fry + ra = 1 th corent basis remains optimal nae : cs (Hint: You must show that (64, 65) = rilUy, ba] + rab. La} + (L — = rab, bal to show this.) 6.5 Finding the Qual of an LP Associated with any LP is another LP, called the dual. Knowing the relation between an LP and its dual is vital to understanding advanced topics in linear and nonlinear pro- ‘gramming. This relation is important because it gives us interesting economic insights. Knowledge of duality will also provide additional insights into sensitivity analysis. In this section, we explain how to find the dual of any LP; in Section 6.6, we discuss the economic interpretation of the dual; and in Sections 6.7-6.10, we discuss the relation. ‘that exists between an LP and its dual, ‘When taking the dual of a given LP, we refer to the given LP as the primal. If the pri- mal is a max problem, then the dual will be a min problem, and vice versa. For coavenience, ‘we define the variables for the max problem to be z, x1, 42...» %, and the variables for the min problem to be ¥, 1, 3y-+- » Jw We begin by explaining how to find the dual of a max problem in which all variables are required to be non-negative and all constraints are = con- straints (called a normal max problem). A normal max problem may be written as max 2 = oxy + exe H+ Cate st | ayy Farm bt aunty = bt F tagkn Ba 0, GaxX, + aka + * Amit + Gmaks Fo + Brin 20 G=LQ.n) ‘The dual of a normal max problem such as (16) is defined to be min w = by, + Boye + = + byt st ayy + @2iy2 + + etm = C1 ean + aaava +o" + gan B 2 om ait + aagda +t Godin = Cn w20 G=1,2...,m) ‘A min problem such as (17) that has all = constraints and all variables non-negative is called a normal min problem. Ifthe primal is a nonmal min problem such as (17), then ‘we define the dual of (17) to.be (16). Finding the Dual of a Normal Max or Min Problem A tabular approach makes it easy to find the dual of an LP. If the primal is a normal max problem, then it-can be read across (Table 14); the dual is found by xeading down. Simi- larly if the primal is a normal min problem, we find it by reading down; the dual is-found, ©. Fog te Deal et an LP 295TABLE 14 Finding th Dealt Normal Ma we Ma rte a g mas iw =o &ED O20 yn ay au ae Shy on Sb EO) eg lg zc, 2er =e, « by reading across in the table, We illustrate the use of the table by finding the dual of the Dakota problem and the dual of the diet problems. The Dakota problem is “max z = 60r, + 30x + 20% st 8x + Giz + x32 48 (Lumber constraint) 4x, + 2x + 15x; 20 Finishing constraint) 2x; + 15x + 05x58 — (Canpentry constraint) 1 2, X= 0 where number of desks manufactured number of tables manufactured 5 = number of chairs manufactured Using the format of Table 14, we read the Dakota problem across in Table 15. Then, reading down, we find the Dakota dual to be min w = 48), + 20y» + 8ys st BF dt 2p, 260 6 + yn t Sy B30 Di + 152 + 0.575 = 20 Yi Ya Is BO ‘The tabular method of finding the dual makes it clear that the ith dual constraint corre- sponds to the ith primal variable x,, For example, the first dual constraint corresponds to 2 (desks), becanse each number comes from the x; (desk) column of the primal. Simi- TABLE 15 Fig the Dal tthe kota Prien i » % OF 8 6 1 <4 2) 4 2 1s 520 B20 on 2 13 os 8 =o 30 0 5 296 SHarten © Seestty Anais and Duty _earmenneeeeytt eer nner eterlarly, the second dual constraint corresponds to x2 (tables), and the third dual constraint corresponds t0 x, (chairs) In a similar fashion, dual variable y; is associated with the ith primal constraint. For example, y; is associated with the first primal constraint (umber constraint), because each coefficient of y, in the dual comes from the luraber constraint, or the availability of lumber. The importance of these correspondences between the pri= ‘mal and the dual will become clear in Section 6.6. ‘We now find the dual of the diet problem. Because the diet problem is a min problem, ‘we follow the convention of using w to denote the objective function and yi, ya, ys. and ‘ys for the variables. Then the diet problem may be written as min w = SOy, + 20y2 + 30ps' + 80y% SL 400y4 + 200y2 + 150) +-500)4= 500 (Calorie constraint) Bt Br =6 (Chocolate constraint) Qt Bt 4+ 4210 (Sugar constraint) g Wt drt wt Sees (Fat constraint) S Vo Yo Is Ye =O where Ji = number of brownies eaten daily 1-2 = number of scoops of chocolate ice cream eaten daily Ys = Dottles of soda drunk daily ‘ya = pieves of pineapple cheesecake eaten daily ‘The primal is 2 normal min problem, so we can read it down, and read its dual across, in ‘Table 16. We find that the dual of the diet problem is 3 max z= 500r, + Gry + 1x5 + Bry St 400x; + 3x2 + 2 + ey = 50 i 200, + 2xy + 2x5 + 4x4 = 20 z 150% + 4x + 5, = 30 500, + dry + Sxe = 80 iy Xa Xs Xe ZO ‘As in the Dakota problem, we see that the ith dual constraint corresponds fo the ith primal variable. For example, the third dual constraint may be thought of as the soda con- straint Also, the ith dual variable corresponds to the ith primal constraint. For example, 2 (the third dual variable) may be thought of as the dual sugar variable. TABLE 16 E a HzQ> y 400 3 2 2 =50 229 ys 200 2 2 4 =20 20 150 o 4 1 330 Hn2D ye 500 ° 4 5 =80 2500 26 210 28 e 6.5 Fig the Deal of a0 LF 297Finding the Dual of a Nonnormai LP Unfortunately, many LPs are not normal max or min problem max z= 2x, +x, st my tma2 2-2 =3 fe) ams v1 20,2 urs is not a normal max problem because it has a = constraint, an. cquslizy consteint, and 2 unrestricted-in-sign variable, As another example of a noanormal LP, consider min w = 2y, + 4y> + 65 st yt yn ty E2 ve Ty et on Yat yal wrt ye =3 Pr WS, Yay Ys =O This LP is not a normal min problem because it contains on equality constraint, a = con- straint, and an unrestricted-in-sign variable. Fortunately, an LP can be transformed into normal form (either (£6) or ‘a.max problem into normal form, we proceed as follows: 1). To piss Step 1 Multiply each = constraint by ~1, converting it into a constraint. example, in (18), 2x1 — x2 & 3 would be transformed into ~~ Step 2 Replace each equality constraint by two inequality constraints (3 2 = constraint). Then convert the = constraint to a = constraint. Por ‘we would replace: + xa = 2>by the two inequalities 2 + 2 ‘we would convert x; +¥ x2 2 to —¥ ~ x2 = 2. The net sesuit is the replaced. by the two inequalities x, + 2x2 = 2 and —xy — x) = Step 3 As in Section 4.14, replace each urs variable x, by x and xf 2 0. In (18), we would replace x2 by xi.— 24. ‘After these transformations are complete, (18) has been transfixmed into che following (equivalent) LP: max z = 2x, +23 — 4 st x tah—xs2 mates 2 7 ~2xy tag xfs 3 ~xtast Hi, ¥4, x3 =O ‘Because (18") is a normal max problem, we could use (16) and (19) to & as). IF the primal is not a normal min problem, then we can tanstorm # problem as follows: euseven 6 Seanty ays and DalyThis is the objective function for the dual of the diet problem, But in setting nutrient prices, Candice must set prices low enough so that it will be in the dieter’s economic in terest to purchase all nutrients from her. For example, by purchasing 2 brownie for SO¢, the dieter can obtain 400 calories, 3°0z of chocolate, 2 oz of sugar, and 2 oz of fat. So Candice cannot charge more than 50¢ for this combination of nutrients. This leads to the following (brownie) constraint: 400x, + 3x2 + 2x3 + 2xe = 50 the first constraint in the diet problem dual. Similar reasoning yields the second dual (ioe cream) constraint, the third (soda constraint), and the fourth (cheesecake constraiat) Again, the sign restrictions x = 0, x2 = 0,25 = 0, and x, = 0 must be satisfied. ‘Our discussion shows that the optimal value of x; may. be interpreted as a price for 1 unit of the nutrient associated with the ith dual constraint. Thus, x; would be the price for Fealorie, x2 would be the price for 1 oz of chocolate, and so on. Again, we see that it is reasonable to associate the ith dual variable (x) and the ith primal constraint, In summary, we have shown that when the primal is a normal max problem or @ nor- | mal min problem, the dual problem has an intuitive economic interpretation. In Section 6.8, we explain more about the proper interpretation of the dual variables. i PROBLEM i Group A 1 Find the dual of Example 3 in Chapter 3 (an auto 2 Find the dual of Example 2 in Chapter 3 (Dorian Auto) company) and give an economic interpretation of the dual __and give an economic interpretation of the dual problem. problem. 6.7 The Qual Theorem and Its Consequences In this section, we discuss one of the most important results in linear programming: the Dual Theorem. In essence, the Dial Theotem states that the primal and dual have equal optixnal objective function values (if the problems have optimal solutions). This result is interesting in its own right, but we will see that in proving the Dual Theorem, we gain ‘many important insights into linear programming, To simplify the exposition, we assume thatthe primal is a normal max problein with m constraints and x variables. Then the dual problem will be a normal min problem with me variables and n constraints, In this case, the primal and the dual may be written as follows: max 2 = cy + ep Ft + Cy St Qyrty + Qyaky + + aint Sb; 5 Gaz tame to + ann S by Primal Problem z i i Gax1 + Gar + + dinky Sb: @ GiB + Oya + = + on S bm 420 G=L2,--.,7) warren G Sotstnty Araki and ayminw = by + Baya +o + Badin st aus + ava to + aan = C1 Muay + daade + - ¥ Gyan = C2 Dual Problem : : Eee co) ay t aan +o + ann = Aut F Gada + + nde = Cn 20 @=1,2...,m) ‘Weak Duality If we choose any feasible solution io the primal and any feasible solution to the dual, the ‘wevalue for the feasible dual solution will be at least as large as the z-valuc for the feasi- ble primal solution. This result is formally stated in Lerma 1. 6.7 Toe Dsl Themem and ts Consequences 305Ficure 7 stration of Weak Duality FIGURE & Whastration of Weak Duality {fa feasible solution to either the primal or the dual is readily available, weak duality can be used to obtain a bound on the optimal objective function value for the other prob- lem. For example, in looking at the Dakota problem, it is easy to see that x; xs = Lis primal feasible. This solution has a z-value of 60 +30 + 20 = 110. Weak du- ality now implies that any dual feasible solution (p1, ya, ys) must satisfy A8y, + 20y2 + 83 = 110 Because the dual is a min problem, and any dual feasible solution must have w = 110, this means that the optimal w-value for the dual = 110 (see Figure 7). This shows that weak duality enables us to use any primal feasible solution to bound the optimal valuc of the dual objective function. ‘Analogously, we can use any feasible solution ‘to the dual to develop a bound on the optimal value of the primal objective function. For example, looking at the Dakota dal it can'readily be verified that y1 = 10, y2 = 10, ys = 0 is dual feasible. This dual solu- tion has a dual objective function value of 48(10) + 20(10) + 8(0) = 680. From weak duality, we see that any primal feasible solution Hl 60x, + 30x, + 20x; = 680 Because the primal is a max problem and every primal feasible solution has z = 680, we may conclude that the optimal primal objective function value == 680 (see Figure 8). If we define must satisfy and. c= [e. cp Gy] then for a point, the primal objective function value may be written as ex, and fora pointy =(y; y2 Yn] the dual objective function value may be written as yb. We now use weak duality to rove the following important result. zen Nod fsbo poiet ‘2 110 mactbold frat base el0 dea faite prats w= 60 £600 mast eld for all ‘Nopwimal ate pat lial Fate pois bse 600 7 euarren 6G Sensi Analysis and OraiySEY ‘We use the Dakota problem to illustrate the use of Lemma 2. The reader may verify that “i is primal feasible and that ¥= [0 10 10] is dual feasible. Because <° Lemma 2 implies that X is optimal for the Dakota primal, and yis ootim= ual. Lemma 2 plays an important role in our proof of the Dual Theorem The Dual Theorem Before proceeding with our proof of the Dual Theorem, we note that weal: dusiity can be used to prove the following results. ©.7 The ol Tenrem an ts Conseyences 307 IEE ‘Adding a New Ac We want to add a new activity. Suppose Dakota is considering manufacturing footstools (e). A footstool sells for $15 and uses 1 board foot of lumber, | finishing hour, and 1 carpentry hour, Does the current basis remain optimal? Introducing the new activity (footstoots) leaves the three dual constraints unchanged, but the new variable xz adds a new dual constraint (comesponding to footstools). The new dual constraint will be Wty + weEls ‘The current basis remains optimal ify: = 0, y2 = 10, 75.= 10 satisfies the new dual con- : straint. Because 0 + 10 + 10 = 15, the current basis remains optimal. in terms of shadow prices, a stool utilizes 1(0) = $0 worth of lumber, 1(10) = $10 worth of finishing hours, and 1(10) = $10 worth of carpentry time. A stool uses 0 + 10 + 10 = $20 worth of re- sources and sells for only $15, so Dakota should not make footstools, and the current ba- sis remains optimal. PROBLEMS Group A 1. For the Dakots problem, suppose computer tables sell for $35 and use 6 board feet of lumber, 2 hours of finishing. time, and { hour of carpentry time, Is the current basis still ‘optizal? Interpret this result in terms of shadow prices. 2. The following questions refer to the Sugareo problem (Problem 6 of Section 6.3): a For what values of profit on a Type 1 candy bar does 3. Suppose, in the Dakota problem, a desk still sells for ‘$60 but now uses 8 board ft of lumber, 4 finishing hours, ‘and 15 carpentry hours. Determine whether the current ‘basis remains optimal. What is wrong with the following reasoning? “The change in the column for desks leaves the second and third dual constraints unchanged and changes the first 0 Sys + ya + 1595 2 60 Because »1'= 0, yo = 10, 9 = 10 satisfies the new dusi the current basis remain optimal? constraint, the current basis remains optimal. Ifa Type 1 candy bar used 0.5 o7 of sugar and 0.75 oz of chocolate, would the current basis remain ‘optimal? © A Type 4 candy bar is under consideration. A Type 4 candy bar yields a 10¢ profit and uses 2 02 of sugar and J oz of chocolate. Does the current basis remain optimal? 6.10 Complementary Slackness ‘The Theorem of Complementary Slackness is an important result that reletes the optimal primal and dual solutions. To state this theorem, we assume that the primal is 2 normal ‘max problem with variables x,, 2, ..., x, and m < constraints. Let st, Sa... » Sm be the slack variables for the primal. Then the dual is a normal min problem with variables y1, Yan-++ > Yn and n = constraints. Let €1, €2,--.» &q be the excess variables for the dual. ‘A statement of the Theorem of Complementary Slackness follows. 6:10 Comlonentay staciness 325In Problem 4 at the end of this section, we sketch the proof of the-Theorem of Com- plementary Slackness, but first we discuss the intuitive meaning of this theorem. From (38), it follows that the optimal primal and dual solutions must satisfy ith primal slack > 0 implies ith dual variable = 0 s) ith dual variable > 0 implies ith primal slack =0 0 ~ oy From (39) it follows that the optimal primal and dual solutions must satisfy 4th dual excess > 0 implies jth primal variable = 0 2) jth primal variable > 0 implies jth dual excess = 0 « From (40) and (42), we see that if @ constraint in ether the primal or dual is non- binding (has either s; > 0 or e; > 0), then the corresponding variable in the other (or complementary) problem must equal 0. Hence the name complementary slackness. To illustrate the interpretation of the Theorem of Complementary Slackness, we return to the Dakota problem. Recall that the primal is max z= 60x, + 3023 + 20%5 st 8 + G+ 35548 - (Camber constraint) 4x, + 2xg 15x 20.” Finishing constraint) 2x; + 15m + 05x <8 | (Carpentry constraint) xptn ts 20 and the dual is min w = 48y; + 20y2 + 8ys st. 8+ 42 2 = 60 © (Desk constraint) Gy + a+ 15ys = 30 “CTable constraint) 34 + LSy2 + 0.5ys = 20 (Chair constraint) Fir Fa Ys =O “The optimal primal solution is 0 — (42) + 200) + 1.58) $3 = 8 — 22) + 15@) + 058) =0 caapren G Sexy Anais and OcityThe optimal dual solution is 280, y= ye (8(0)}-+ 4(10) + 2(10)) — 60 = 0 (6(0) + 2(10) + 1.5(10)) — 30 = 5 e3 = (1(0) + 1.5(10) + 0.5(10)) — 2¢ For the Dakota problem, (38) reduces to SOL = 52 = sayy = 0 which is indeed satisfied by the optimal primal and dual solutions. Also, (39) reduces emt = ert = ests = 0 ‘which is also satisfied by the optimal primal and dual solutions. We now illustrate the interpretation of (40)-(43). Note that (40) tells us that because the ‘optimal primal solution has s1 > 0, the optimal dual solution must have py = 0. In the con- text of the Dakota problem, this means that positive stack in the lumber constraint implies that lumber must have a zero shadow price. Slack in the Lumber constraint means that ex- tra lumber would not be used, so an extra board foot of lumber should indeed be worthless Equation (41) tells us that because y2 > 0 in the optimal dual solution, 8 = 0 must hold in the optimal primal solution. This is reasonable because y2 > 0 means that za ex- ta finishing hour has some value. This can only occue if we are at present using all avail- able finishing hours (or equivalently, if sy = 0). Observe that (42) tells us that because ¢2 > 0 in the optimal dual solution, x2 = 0 must hold ia the optimal primal solution. This is reasonable because e2 = 61 + 2y2 + 1.Sys — 30. Because y1, y2, and ys are resource shadow prices, e may be written as 2 = (value of resources used by table) — (sales price of a table) Thus, if ¢ > 0, tables are selling for a price that is less than the value of the resources used to make 1 unit of x, (tables). This means that no tables should be made (or equiva- Jenily, that x, = 0). This shows that e, > 0 in the optimal dual solution implies that x mast hold in the optimal primal solution. Note that for the Dakota problem, (43) tells us that 21 > 0 for the optimal primal so- lution implies that ¢, = 0, This result simply reflects the following important fact, For any variable x; in the optimal primal basis, the marginal revenue obtained from produc~ ing a unit of x must equal the marginal cost of the resources used to produce @ unit of 44 This is a consequence of the fact that each basic variable must have a zero coefficient in row 0 of the optimal primal tableau. In short, (43) is simply the LP version of the well- known economic maxim that an optimal production strategy must have marginal revenue equal marginal cost. ‘To be more specific, observe that x; > 0 means that desks are in the optimal basis. Then Marginal revenue obtained by manufacturing desk = $60 ‘To compute the marginal cost of manufacturing a desk (in terms of shadow prices), note that Cost of lumber in desk = 8(0) = $0 Cost of finishing hours used to make a desk = 4(10) = $40 Cost of carpentry hours used to make a desk = 2(10) = $20 Marginal cost of producing a desk = 0 + 40 +20 = $60 ‘Thus, for desks, marginal revenue is equal to marginal cost. 6.10 Complementary Sixes 327Using Complementary Slackness to Solve LPs Jf the optimal solution to the primal or dual is known, complementary slackness c: sometimes be used to determine the optimal solution to the complementary problem. © example, suppose we were told that the optimal solution to the Dakota problem was z = 280, x; = 2, x2 = 0,3 = 8, 5; = 24, 5; = 0, 53 = 0. Can we use Theorem 2 to help us find the optimal sofution to the Dakota dual? Because s, > 0, (40) tells us that the opti- mal dual solution must have y, = 0. Because x, > 0 and x3 > 0, (43) implies that the optimal dual solution must have ¢, = 0, and ey = 0. This means that for the optimal dua! solution, the first and third constcaints must be binding. We know that y1 = 0, so we know that the optimal values of yp and ys may be found by solving the first and third dual con- straints as equalities (with y, = 0). Thus, the optimal values of y, and ys must satisfy 20 4y, + 2yy= 60 and Sy, + O.Sys Solving these equations simultaneously shows that the optimal dual solution must have Ja = 10 and y. solution yr = 0, ys 10. Thus, complementary slackness has helped us find the optimal dual 10, ys = 10. (From the Dual Theorem, we knovs, of course, that the ‘optimal dual solution must have # = 280.) PROBLEMS Group A 1. Glassco manufactures glasses: wine, beer, champagne, and whiskey. Bach type of glass requires time in the molding shop, time in the packaging shop, and a certain amount of, lass, The resources required to make cach type of glass are given in Table 32. Currently, 600 minutes of molding time, 400 minutes of packaging time, and 500 oz of glass are available. Assuming that Glassco wants to maximize revenue, the following LP should be solved: max z = Gey + 10k, + 955 + 206 St 4x, + Oxy + Ty + Oxy = 600 (Molding constraint) at am t3y +40 400 Packaging constraint) Bx tant Qe + 4500 | Glas constraint) Hua x5, ee EO Itean be shown that the optimal solution to this LP is= 02 = 05 Sdingpice $6 S10 39 328 exaptes @ Sensivty Arps 2a Orly ‘a. Find the dual of the Glasseo problem. ‘be Using the given optimal primal solution and the The- ‘orem of Complementary Slackness, find the optimal so- Intion to the dual of the Glassco problem. © Find anexample of each of the complementary slack- ness conditions, (40)-(43). As in the text, interpret each ‘example in terms of shadow prices. 2. Use the Theorem of Complementary Slackness to show ‘that in the LINDO outpat, the SLACK or SURPLUS and DUAL PRICE entries for any row cannot both be positive. 3. Consider the following LP: max z = Sx + 3m + % st dt mtn sé x +2 tay =7 Hank 20 Graphically solve the dual of this LP. Then use comple- mentary slackness to solve the max problem.