运筹学课件 Duality and Post-Optimal Analysis

《运筹学课件 Duality and Post-Optimal Analysis》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、OperationsResearchCh4DualityandPost-OptimalAnalysis1'$4.1De¯nitionofTheDualProblem²Adualvariableisde¯nedforeachprimalconstraint.²Adualconstraintisde¯nedforeachprimalvariable.²Aconstraintcoe±cientsofaprimalvariablede¯netheLHScoe±cientsofthedualconstraintanditsobjectivecoe±cientde¯ne

2、theRHS.²Theobjectivecoe±cientsofthedualequaltheRHSoftheprimalconstraints.&%OperationsResearchCh4DualityandPost-OptimalAnalysis2'$Thesenseofoptimizationinthedualisalwaysoppositetothatoftheprimal.Assumethattheproblemisinstandardform.Ifthedualobjectiveisminimization,thentheconstraints

3、arealltype¸.Theoppositeistruewhenthedualobjectiveismax.Example4.1-1Writedownthedualofthefollowing,max=5x1+12x2+4x3x1+2x2+x3·102x1¡x2+3x3=8x1;x2;x3¸0&%OperationsResearchCh4DualityandPost-OptimalAnalysis3'$maxx0=5x1+12x2+4x3miny0=10y1+8y2x1+2x2+x3+x4=10y1+2y2¸52x1¡x2+3x3+0x4=8)2y1¡y2

4、¸12x1;x2;x3;x4¸0y1+3y2¸4y1¸0(y1)y2freeExample4.1-3maxx0=5x1+6x2x1+2x2=5¡x1+5x2¸34x1+7x2·8x1unrestricted;x2¸0&%OperationsResearchCh4DualityandPost-OptimalAnalysis4'$+¡maxx0=5x1¡5x1+6x2+¡x1¡x1+2x2=5+¡¡x1+x1+5x2¡x3=3+¡4x1¡4x1+7x2+x4=8§x1;x2;x3;x4¸0Onecangetthatthedualproblemisminy0=5y

5、1+3y2+8y3y1¡y2+4y3=52y1+5y2+7y3¸6y1unrestricted,y2·0;y3¸0&%OperationsResearchCh4DualityandPost-OptimalAnalysis5'$wesummarizetheformulationinthefollowingtable:MinimizationMaximization¸0$·variable·0$¸constraintunrestricted$=¸$¸0constraint·$·0variable=$unrestricted&%OperationsResearch

6、Ch4DualityandPost-OptimalAnalysis6'$4.3.1EconomicInterpretationofDualExample4.3-1ConsidertheReddyMikksmodel.Theprimalproblemrepresentsaresourceallocationproblem.Thedualvariableyj¸0representstheworthperunitoftheresource.Supposethatthecompanywantstoestimatetheleast(min)valueofitsreso

7、urces.Thiswillinducetheproblemminy0=24y1+6y2+y3+2y4.Noticethattheworthoftheresourcescannotbelessthanproducingthepaints,thus6y1+y2¡y3¸5;4y1+2y2+y3+y4¸4:Thisisthedualproblem.&%OperationsResearchCh4DualityandPost-OptimalAnalysis7'$4.4.1DualSimplexAlgorithmTostartthealgorithm,tworequir

8、ementsmustbemet:1.Theobjec