运筹学(英)-cha7.ppt

Chapter7IntegerLinearProgramming,TypesofIntegerProgrammingModels-AnLPinwhichallthevariablesarerestrictedtobeintegersiscalledanall-integerlinearprogram(ILP).-Ifonlyasubsetofthevariablesarerestrictedtobeintegers,theproblemiscalledamixed-integerlinearprogram(MILP).-Binaryvariablesarevariableswhosevaluesarerestrictedtobe0or1.Ifallvariablesarerestrictedtobe0or1,theproblemiscalleda0-1orbinaryintegerlinearprogram.,IntegerLinearProgramming,Example:All-IntegerLPConsiderthefollowingall-integerlinearprogram:Maxz=3x1+2x2s.t.3x1+x20andintegerTheLPthatresultsfromdroppingtheintegerrequirementsiscalledtheLPRelaxationoftheILP.Question:CanwefindtheoptimalsolutionfromtheoptimalsolutionoftherelativeLPRelaxation?,IntegerLinearProgramming,Graphicalsolution,LPOptimal(2.5,1.5),Max3x1+2x2,-x1+x21,x1,3x1+x29,1,3,2,5,4,1234567,x1+3x27,x2,IntegerLinearProgramming,GraphicalsolutionRoundingupIfweroundupthefractionalsolution(x1=2.5,x2=1.5)totheLPrelaxationproblem,wegetx1=3andx2=2.Fromthegraphonthenextslide,weseethatthispointliesoutsidethefeasibleregion,makingthissolutioninfeasible.RoundingDownByroundingtheoptimalsolutiondowntox1=2,x2=1,weseethatthissolutionindeedisanintegersolutionwithinthefeasibleregion,andsubstitutingintheobjectivefunction,itgivesz=8.,IntegerLinearProgramming,ILPOptimal(3,0),Max3x1+2x2,-