运筹学Lect-4-Duality-updated

DualitySchoolofManagementOutlineOriginofDualProblemPrimal–DualRelationshipHowtowritethedualproblemObjectiveFunctionComplementarySlacknessEconomicImplicationDualSimplexMethodDUALEconomicInterpretation:Example1ThereisasmallcompanyinMelbournewhichhasrecentlybecomeengagedintheproductionofofficefurniture.Thecompanymanufacturestables,desksandchairs.Theproductionofatablerequires8kgsofwoodand5kgsofmetalandissoldfor$80;adeskuses6kgsofwoodand4kgsofmetalandissoldfor$60;andachairrequires4kgsofbothmetalandwoodandissoldfor$50.Wewouldliketodeterminetherevenuemaximizingstrategyforthiscompany,giventhattheirresourcesarelimitedto100kgsofwoodand60kgsofmetal.ProblemP1maxxZxxx806050123864100544600123123123xxxxxxxxx,,NowconsiderthatthereisamuchbiggercompanyinMelbournewhichhasbeentheloneproducerofthistypeoffurnitureformanyyears.Theydon'tappreciatethecompetitionfromthisnewcompany;sotheyhavedecidedtotenderanoffertobuyalloftheircompetitor'sresourcesandthereforeputthemoutofbusiness.Thechallengeforthislargecompanythenistodevelopalinearprogramwhichwilldeterminetheappropriateamountofmoneythatshouldbeofferedforaunitofeachtypeofresource,suchthattheofferwillbeacceptabletothesmallercompanywhileminimizingtheexpendituresofthelargercompany.ProblemD1858064604450012121212yyyyyyyy,minywyy1006012Anindividualhasachoiceoftwotypesoffoodtoeat,meatandpotatoes,eachofferingvaryingdegreesofnutritionalbenefit.Hehasbeenwarnedbyhisdoctorthathemustreceiveatleast400unitsofprotein,200unitsofcarbohydratesand100unitsoffatfromhisdailydiet.Giventhatakgofsteakcosts$10andprovides80unitsofprotein,20unitsofcarbohydratesand30unitsoffat,andthatakgofpotatoescosts$2andprovides40unitsofprotein,50unitsofcarbohydratesand20unitsoffat,hewouldliketofindtheminimumcostdietwhichsatisfieshisnutritionalrequirementsEconomicInterpretation:Example2ProblemP2804040020502003020100012121212xxxxxxxx,minxZxx10212Nowconsiderachemicalcompanywhichhopestoattractthisindividualawayfromhispresentdietbyofferinghimsyntheticnutrientsintheformofpills.Thiscompanywouldlikedeterminepricesperunitfortheirsyntheticnutrientswhichwillbringthemthehighestpossiblerevenuewhilestillprovidinganacceptabledietaryalternativetotheindividual.ProblemD2maxywyyy40020010012380203010123yyy4050202123yyyyyy1230,,CommentsEachofthetwoexamplesdescribessomekindofcompetitionbetweentwodecisionmakers.Youwillinvestigatethenotionof“competition”moreformallyin“GameTheory”.Youwillinvestigatetheeconomicinterpretationoftheprimal/dualrelationshiplaterinthisclass.DefinitionofDualPrimalProblemminz=cTxs.t.Ax≥bx≥0DualProblemmaxy=bTws.t.ATw≤cw≥0≥minbAcTcATbT≤maxmnmnMathematicalInterpretationTheOriginofDualThemaximizationproblemmaximizesubjecttoZ=3x1x1+5x2≤43x12x2+2x2≤12≤18x1,x2≥0Question:Canwefindanupperbound(UB)for1235zxxTheOriginofDualThemaximizationproblemmaximizesubjecttoZ=3x1x1+5x2≤43x12x2+2x2≤12≤18x1,x2≥0Firsttry:1233125()4(2530212)2xx123542xxCantheupperbound(UB)bebetter？TheOriginofDualThemaximizationproblemmaximizesubjecttoZ=3x1x1+5x2≤43x12x2+2x2≤12≤18x1,x2≥0Thesecondtry:212332218(2)12+2183xxx123536xxCanwedoevenbetter?TheOriginofDualThemaximizationproblemInordertogettheaboveinequality,wemusthavey1,y2,y3≥0Doyouunderstandwhatwearedoinghere?112233132121212121312maximize35subjectto()4(2)12(32)18,0()(224)31zxxxxxxyyyyyyyxxxyyyxy23218yySumLHS&RHSTheOriginofDual112233132121212121312maximize35subjectto()4(2)12(32)18,0()(224)31zxxxxxxyyyyyyyxxxyyyxy23218yySumLHS&RHSTheOriginofDualThemaximizationproblemMoreformally,tohaveanupperbound(UB)forWemusthave121112223123121312321maximize35subjectto()4(2)12(32)18,0(3)(22)41zxxyxyyxyyxxyxxyyxyyxy23218yy1235zxx131232121323(3)(22)3533225yyxyyxxxyyyyTheOriginofDualThemaximizationproblemTheUBofZisminimizediftheabovevalueisminimized112233132121212121312maximize35subjectto()4(2)12(32)18,0()()2234zxxxyyyyyyyyyyyxxxxxxx231218yy132333225yyyyTheOriginofDualThemaximizationproblemFinally,wegetthefollowingminimizationproblemThisisDualofthePrimal!3323121312183,minimizew412subjectto+32+25,0yyyyyyyyyyPrimalandDualProblemsPrimalproblemminz=2x1+3x2-x3s.t.x1+2x2+x3≥62x1-3x2+2x3≥9x1,x2,x3≥0Dualproblemmaxy=6w1+9w2s.t.w1+2w2≤22w1-3w2≤3w1+2w2≤-1w1,w2≥0MinimumproblemConstraintsareall≥3variablesand2constraintsVariablesarenon-negativeMaximumproblemConstraintsareall≤2variablesand3constraintsVariablesarenon-negativeNumberofvariables(3)inprimalproblemequalsthatofconstraints(3)indualproblem.Numberofconstraints(2)inprimalproblemequalsthatofvariables(2)indualproblem.Exerciseminz=2x1+x2-3x3s.t.x1-3x2+2x3-5x4≥64x1+x2-5x3+2x4≥9-x1+2x2+x4≥12x1,x2,x3,x4≥04variablesand3constraintsinprimalproblem3variablesand4constraintsindualproblemw1w2w3maxy=6w1+9w2+12w3s.t.w1+4w2-w3≤2-3w1+w2+2w3≤12w1-5w2≤-3-5w1+2w2+w3≤0w1,w2,w3≥0x1x2x3x4DualProblemofDualProblemmaxy=6w1+9w2s.t.w1+2w2≤22w1-3w2≤3w1+2w2≤-1w1,w2≥0miny’=-6w1-9w2s.t.-w1-2w2≥-2-2w1+3w2≥-3-w1-2w2≥1w1,w2≥0maxz’=-2x1-3x2+x3s.t.–x1-2x2-x3≤-6-2x1+3x2-2x3≤-9x1,x2,