MthSc-440/640: Linear ProgrammingLecture 14Pietro BelottiDept. of Mathematical SciencesClemson UniversityOctober 12, 2010Reading: pages 65-68.Reading for Thursday: pages 97-113.Dual variables and their meaningDual variables are variables of an LP.◮We initially defined them as weights.◮We used them to build a lower bound on the minimum ofthe objective function of an LP.◮However, do they have any hidden meaning or utility?Consider a pair (primal,dual):(P) min c⊤x (D) max b⊤us.t. Ax ≥ b s.t. A⊤u ≤ cx ≥ 0 u ≥ 0◮We know what the optimal primal variables x⋆mean.i.e. They are the optimal solution to our problem . . .◮What does an optimal dual variable vector u⋆mean?Example1Problem: get the correct amount of nutrients from thefollowing menu:FF: Filet-O-FishFR: Fries (small)1M: 1% Lowfat MilkOJ: Orange JuiceEach food has a different combination of nutrient (proteins,Vitamin A, Iron, etc.) and a cost. You want to◮get the necessary nutrients every day (constraint)◮minimize the total cost of the foods (objective function)1A reduced, no-meat version of the diet problem,Chapter 1, Fourer’s book.Nutrients and c ostFF FR 1M OJCost 1.44 0.77 0.60 0.72 Req’dProt 14 3 9 1 55gVitC – 15% 4% 120% 100%Cals 370 220 110 80 2000Cal221Cal = 1000cal = 4.186kJ = 4,186J.ModelDefine F = {FF, FR, 1M, OJ} and N = {Prot, VitC, Carb}.◮define variable xias the amount of food i you will buyevery day (i ∈ F)◮define parameters:◮ciis the cost per unit of food i ∈ F◮ajiis the amount of nutrient j ∈ N per unit of food i ∈ F◮bjis the amount of nutrient j ∈ N required every dayThen the optimization model is an LP model:min c⊤xAx ≥ bx ≥ 0Primal and dualmin 1.44 xff+0.77 xfr+0.60 x1m+0.72 xojs.t. 14 xff+3 xfr+9 x1m+1 xoj≥ 55 (Prot)15 xfr+4 x1m+120 xoj≥ 100 (VitC)370 xff+220 xfr+110 x1m+80 xoj≥ 2000 (Energy)xff, xfr, x1m, xoj≥ 0Dual problem: define variables uProt, uVitC, uEnergy.max 55 uProt+100 uVitC+2000 uEnergys.t. 14 uProt+370 uEnergy≤ 1.44 (Fish)3 uProt+15 uVitC+220 uEnergy≤ 0.77 (Fries)9 uProt+4 uVitC+110 uEnergy≤ 0.60 (Milk)1 uProt+120 uVitC+80 uEnergy≤ 0.72 (OJ)uProt, uVitC, uEnergy≥ 0Constraints and objectives in the primalThe primal’s objective is:1.44$portionxff+ 0.77$portionxfr+ 0.60$portionx1m+ 0.72$portionxoj,and it’s a cost, measured in dollars; the constraints are:14g of proteinportionxff+ 3gportionxfr+ 9gportionx1m+ 1gportionxoj≥ 55g,15% of Vitamin Cportionxfr+%portion4x1m+ 120%portionxoj≥ 100%,370Calportionxff+ 220Calportionxfr+ 110Calportionx1m+ 80Calportionxoj≥ 2000Cal.xff, xfr, x1m, xojare real quantities, with unities.They are measured inportions.Can we do the same with the dual?The objective is a cost, too (Strong duality: c⊤x⋆= b⊤u⋆).55g · uProt+ 100% · uVitC+ 2000Cal · uEnergy⇒ duals u have a unit such that the resulting objective is a cost.uProt$g of proteinuVitC$% pointuEnergy$CalAll constraints agree with this. Example (Filet-O-Fish):14g of proteinportionuProt$g of protein+ 370CalportionuEnergy$Cal≤ 1.44$portion.Other example (Fries):3gportn.uProt$g+ 15%portn.uVitC$%+ 220Calportn.uEnergy$Cal≤ 0.77$portn..Interpretation of dual variablesNow we know what unit the duals are expressed in, but westill don’t know what they mean.◮First, complementary slacknessuProt(14xff+ 3xfr+ 9x1m+ 1xoj− 55) = 0◮implies (example):uProt> 0 ⇒ 14xff+ 3xfr+ 9x1m+ 1xoj= 55g of protein.◮Viceversa,14xff+ 3xfr+ 9x1m+ 1xoj< 55g of protein ⇒ uProt= 0Let’s compute the dualset Food;set Nutr;param price {Food};param reqd {Nutr};param npf {Nutr,Food};var x {Food} >= 0;minimize tot_cost: sum {i in Food} price [i]*x [i];RDA {j in Nutr}:sum {i in Food} npf [j,i]*x [i] >= reqd [j];Data fileset Food = {"FF", "FR", "1M", "OJ"};set Nutr = {"Prot", "VitC", "Energy"};param price :="FF" 1.44"FR" 0.77"1M" 0.60"OJ" 0.72;param reqd :="Prot" 55"VitC" 100"Energy" 2000;param npf: "FF" "FR" "1M" "OJ" :="Prot" 14 3 9 1"VitC" 0 15 4 120"Energy" 370 220 110 80;Solutionampl: model no-meat-diet.mod;ampl: data no-meat-diet.dat;ampl: option solver cplexamp;ampl: solve; display x; display RDA.dual;IBM ILOG License Manager: "IBM ILOG Optimization Suite forCPLEX 12.2.0.0: No LP presolve or aggregator reductions.optimal solution; objective 7.6102598273 dual simplex iterations (0 in phase I)x [*] :=1M 0FF 3.10016FR 3.74417OJ 0.365312;RDA.dual [*] :=Energy 0.00286742Prot 0.0270753VitC 0.00386276;All three duals are nonzeroTherefore, all three constraints are satisfied at equality:uProt(14xff+ 3xfr+ 9x1m+ xoj− 55) = 0uVitC(15xfr+ 4x1m+ 120xoj− 100) = 0uEnergy(370xff+ 220xfr+ 110x1m+ 80xoj− 2000) = 0Also, the objective function is1.44xff+ 0.77xfr+ 0.60x1m+ 0.72xoj== 1.44 · 3.10016 + 0.77 · 3.74417 + 0.60 · 0 + 0.72 · 0.365312 == 7.610259827 == 55 · 0.0270753 + 100 · 0.00386276 + 2000 · 0.00286742 == 55uProt+ 100uVitC+ 2000uEnergyMeaning of the dual variablesIn general, constraints limit the usage of resources or toguarantee a minimum level ofdemand fulfilment.The duals uProt, uVitC, uEnergyare expressed inValueunit of nutrition.◮The higher the dual, the more valuable a resource (ornutrient, in this case) is.◮Depending on the optimal solution, each resource mayhave a different unit worth.◮Changing the problem would indeed possibly change theprimal and dual solution (and the obj. function value).In our case, u⋆Prot≫ u⋆Energy, so we may think that the unit worthof proteins is higher.In general, a dual variable suggests us how important thecorresponding constraint is, i.e., how (and how much) thesolution would change when changing that constraint.TheoremSuppose that the problem (with n variables and m constraints)maxPnj=1cjxjs.t.Pnj=1aijxj≤ bi∀i = 1, 2 . . . mxj≥ 0 ∀j = 1, 2 . . . nhas at least one nondegenerate basic optimal solution x⋆, withvalue z⋆=Pnj=1cjx⋆j. Then there is a positive ǫ such that:For each t ∈ Rmsuch that |ti| ≤ ǫ ∀i ∈ {1, 2 . . . , m}, the problemmaxPnj=1cjxjs.t.Pnj=1aijxj≤ bi+ ti∀i = 1, 2 . . . mxj≥ 0 ∀j = 1, 2 . . . nhas an optimal solution with value z⋆+Pmi=1u⋆iti.z⋆+Pmi=1u⋆itii.e. There exists an ǫ such that we don’t have to re-solve theproblem when changing bito bi+ ti.◮The unitary change in the new obj. function is determinedby the dual of a constraint i:z⋆→ z⋆+ u⋆iti.⇒ If we relax a constraintPnj=1aijxj≤ biby ti, we gain u⋆iti;⇒ If we restrict a constraintPnj=1aijxj≤ biby ti, we lose u⋆iti.⇒ If