数据、模型与决策（第12版）课件 第5章整数规划

IntegerProgrammingChapter5Copyright©2016PearsonEducation,Inc.ChapterTopicsIntegerProgramming(IP)ModelsIntegerProgrammingGraphicalSolutionComputerSolutionofIntegerProgrammingProblemsWithExcelandQMforWindows0-1IntegerProgrammingModelingExamplesCopyright©2016PearsonEducation,Inc.IntegerProgrammingModelsTypesofModelsTotalIntegerModel:Alldecisionvariablesrequiredtohaveintegersolutionvalues.0-1IntegerModel:Alldecisionvariablesrequiredtohaveintegervaluesofzeroorone.MixedIntegerModel:Someofthedecisionvariables(butnotall)requiredtohaveintegervalues.Copyright©2016PearsonEducation,Inc.ATotalIntegerModel(1of2)Machineshopobtainingnewpressesandlathes.Marginalprofitability:eachpress$100/day;eachlathe$150/day.Resourceconstraints:$40,000budget,200sq.ft.floorspace.Machinepurchasepricesandspacerequirements:Copyright©2016PearsonEducation,Inc.ATotalIntegerModel(2of2)IntegerProgrammingModel: MaximizeZ=$100x1+$150x2subjectto: $8,000x1+4,000x2

$40,00015x1+30x2

200ft2x1,x2

0andintegerx1=numberofpressesx2=numberoflathesCopyright©2016PearsonEducation,Inc.Recreationfacilitiesselectiontomaximizedailyusagebyresidents.Resourceconstraints:$120,000budget;12acresofland.Selectionconstraint:eitherswimmingpoolortenniscenter(notboth).A0-1IntegerModel(1of2)Copyright©2016PearsonEducation,Inc.IntegerProgrammingModel:

MaximizeZ=300x1+90x2+400x3+150x4subjectto: $35,000x1+10,000x2+25,000x3+90,000x4

$120,0004x1+2x2+7x3+3x4

12acresx1+x2

1facilityx1,x2,x3,x4=0or1 x1=constructionofaswimmingpoolx2=constructionofatenniscenterx3=constructionofanathleticfieldx4=constructionofagymnasiumA0-1IntegerModel(2of2)Copyright©2016PearsonEducation,Inc.AMixedIntegerModel(1of2)$250,000availableforinvestmentsprovidinggreatestreturnafteroneyear.Data:Condominiumcost$50,000/unit;$9,000profitifsoldafteroneyear.Landcost$12,000/acre;$1,500profitifsoldafteroneyear.Municipalbondcost$8,000/bond;$1,000profitifsoldafteroneyear.Only4condominiums,15acresofland,and20municipalbondsavailable.Copyright©2016PearsonEducation,Inc.IntegerProgrammingModel:

MaximizeZ=$9,000x1+1,500x2+1,000x3 subjectto: 50,000x1+12,000x2+8,000x3

$250,000 x1

4condominiums x2

15acres x3

20bonds x2

0 x1,x3

0andinteger x1=condominiumspurchased x2=acresoflandpurchased x3=bondspurchasedAMixedIntegerModel(2of2)Copyright©2016PearsonEducation,Inc.Roundingnon-integersolutionvaluesuptothenearestintegervaluecanresultinaninfeasiblesolution.Afeasiblesolutionisensuredbyroundingdownnon-integersolutionvaluesbutmayresultinalessthanoptimal(sub-optimal)solution.IntegerProgrammingGraphicalSolutionCopyright©2016PearsonEducation,Inc.IntegerProgrammingExampleGraphicalSolutionofMachineShopModelMaximizeZ=$100x1+$150x2subjectto: 8,000x1+4,000x2

$40,00015x1+30x2

200ft2 x1,x2

0andintegerOptimalSolution: Z=$1,055.56 x1=2.22presses x2=5.55lathesFigure5.1FeasiblesolutionspacewithintegersolutionpointsCopyright©2016PearsonEducation,Inc.BranchandBoundMethodTraditionalapproachtosolvingintegerprogrammingproblems.FeasiblesolutionscanbepartitionedintosmallersubsetsSmallersubsetsevaluateduntilbestsolutionisfound.Methodisatediousandcomplexmathematicalprocess.ExcelandQMforWindowsusedinthisbook.Seebook’swebsiteModuleC–“IntegerProgramming:theBranchandBoundMethod”fordetaileddescriptionofthismethod.Copyright©2016PearsonEducation,Inc.RecreationalFacilitiesExample:MaximizeZ=300x1+90x2+400x3+150x4subjectto: $35,000x1+10,000x2+25,000x3+90,000x4

$120,0004x1+2x2+7x3+3x4

12acresx1+x2

1facilityx1,x2,x3,x4=0or1ComputerSolutionofIPProblems0–1ModelwithExcel(1of5)Copyright©2016PearsonEducation,Inc.Exhibit5.2ComputerSolutionofIPProblems0–1ModelwithExcel(2of5)=C7*C12+D7*C13+E7*C14+F7*C15Decisionvariables—C12:C15Copyright©2016PearsonEducation,Inc.Exhibit5.3ComputerSolutionofIPProblems0–1ModelwithExcel(3of5)Restrictsvariables,C12:C15,tointegerand0-1valuesCopyright©2016PearsonEducation,Inc.Exhibit5.4ComputerSolutionofIPProblems0–1ModelwithExcel(4of5)Clickon“bin”for0-1.Copyright©2016PearsonEducation,Inc.Exhibit5.5ComputerSolutionofIPProblems0–1ModelwithExcel(5of5)DeactivateReturntosolverwindowCopyright©2016PearsonEducation,Inc.ComputerSolutionofIPProblems0–1ModelwithQMforWindows(1of3)RecreationalFacilitiesExample:MaximizeZ=300x1+90x2+400x3+150x4subjectto: $35,000x1+10,000x2+25,000x3+90,000x4

$120,0004x1+2x2+7x3+3x4

12acresx1+x2

1facilityx1,x2,x3,x4=0or1Copyright©2016PearsonEducation,Inc.Exhibit5.6ComputerSolutionofIPProblems0–1ModelwithQMforWindows(2of3)Copyright©2016PearsonEducation,Inc.Exhibit5.7ComputerSolutionofIPProblems0–1ModelwithQMforWindows(3of3)Clicktosolve.VariabletypeClickon“0/1”tomakevariables0or1.Copyright©2016PearsonEducation,Inc.ComputerSolutionofIPProblemsTotalIntegerModelwithExcel(1of6)IntegerProgrammingModelofMachineShop: MaximizeZ=$100x1+$150x2 subjectto: 8,000x1+4,000x2

$40,000 15x1+30x2

200ft2 x1,x2

0andintegerCopyright©2016PearsonEducation,Inc.Exhibit5.8ComputerSolutionofIPProblemsTotalIntegerModelwithExcel(2of6)Solution:X1=1swimmingpoolX2=0tenniscenterX3=1athleticfieldX4=0gymnasiumZ=700peopleperdayusageCopyright©2016PearsonEducation,Inc.Exhibit5.9ComputerSolutionofIPProblemsTotalIntegerModelwithExcel(3of6)ObjectivefunctionSlack,=G6-E6=C6*B10+D6*B11Decisionvariables—B10:B11Copyright©2016PearsonEducation,Inc.Exhibit5.10ComputerSolutionofIPProblemsTotalIntegerModelwithExcel(4of6)IntegervariablesCopyright©2016PearsonEducation,Inc.Exhibit5.11ComputerSolutionofIPProblemsTotalIntegerModelwithExcel(5of6)Clickon“int”Copyright©2016PearsonEducation,Inc.Exhibit5.12ComputerSolutionofIPProblemsTotalIntegerModelwithExcel(6of6)IntegerSolutionCopyright©2016PearsonEducation,Inc.IntegerProgrammingModelforInvestmentsProblem:

MaximizeZ=$9,000x1+1,500x2+1,000x3 subjectto: 50,000x1+12,000x2+8,000x3

$250,000 x1

4condominiums x2

15acres x3

20bonds x2

0 x1,x3

0andinteger ComputerSolutionofIPProblemsMixedIntegerModelwithExcel(1of3)Copyright©2016PearsonEducation,Inc.Exhibit5.13ComputerSolutionofIPProblemsTotalIntegerModelwithExcel(2of3)Availabletoinvest=C4*B8+D4*B9+E4*B10Copyright©2016PearsonEducation,Inc.

Exhibit5.14ComputerSolutionofIPProblemsSolutionofTotalIntegerModelwithExcel(3of3)Integerrequirementforcondos(x1)andbonds(x3)Constraintsforacres,condos,andbondsCopyright©2016PearsonEducation,Inc.Exhibit5.15ComputerSolutionofIPProblemsMixedIntegerModelwithQMforWindows(1of2)Clickon“Real”Copyright©2016PearsonEducation,Inc.Exhibit5.16ComputerSolutionofIPProblemsMixedIntegerModelwithQMforWindows(2of2)Copyright©2016PearsonEducation,Inc.Universitybookstoreexpansionproject.Notenoughspaceavailableforbothacomputerdepartmentandaclothingdepartment.0–1IntegerProgrammingModelingExamplesCapitalBudgetingExample(1of4)Copyright©2016PearsonEducation,Inc.x1=selectionofwebsiteprojectx2=selectionofwarehouseprojectx3=selectionclothingdepartmentprojectx4=selectionofcomputerdepartmentprojectx5=selectionofATMprojectxi=1ifproject“i”isselected,0ifproject“i”isnotselectedMaximizeZ=$120x1+$85x2+$105x3+$140x4+$70x5subjectto:55x1+45x2+60x3+50x4+30x5

15040x1+35x2+25x3+35x4+30x5

11025x1+20x2+30x4

60x3+x4

1xi=0or1

0–1IntegerProgrammingModelingExamplesCapitalBudgetingExample(2of4)Copyright©2016PearsonEducation,Inc.Exhibit5.170–1IntegerProgrammingModelingExamplesCapitalBudgetingExample(3of4)=SUMPRODUCT(C7:C11,E7:E11)=C9+C10Copyright©2016PearsonEducation,Inc.Exhibit5.180–1IntegerProgrammingModelingExamplesCapitalBudgetingExample(4of4)0-1integerrestrictionMutuallyexclusiveconstraintCopyright©2016PearsonEducation,Inc.0–1IntegerProgrammingModelingExamplesFixedChargeandFacilityExample(1of4) Whichofsixfarmsshouldbepurchasedthatwillmeetcurrentproductioncapacityatminimumtotalcost,includingannualfixedcostsandshippingcosts?Copyright©2016PearsonEducation,Inc.yi=0iffarmiisnotselected,and1iffarmiisselected; i=1,2,3,4,5,6xij=potatoes(1000tons)shippedfromfarmItoplantj; j=A,B,C.MinimizeZ= 18x1A+15x1B+12x1C+13x2A+10x2B+17x2C+16x3+14x3B

+18x3C+19x4A+15x4b+16x4C+17x5A+19x5B+12x5C+14x6A

+16x6B+12x6C+405y1+390y2+450y3+368y4+520y5+465y6subjectto:x1A+x1B+x1B-11.2y1≤0 x2A+x2B+x2C-10.5y2

≤0x3A+x3A+x3C-12.8y3

≤0 x4A+x4b+x4C-9.3y4

≤0x5A+x5B+x5B-10.8y5

≤0 x6A+x6B+X6C-9.6y6

≤0x1A+x2A+x3A+x4A+x5A+x6A=12x1B+x2B+x3B+x4B+x5B+x6B=10x1C+x2C+x3C+x4C+x5C+x6C=14xij≥0yi=0or10–1IntegerProgrammingModelingExamplesFixedChargeandFacilityExample(2of4)Copyright©2016PearsonEducation,Inc.Exhibit5.190–1IntegerProgrammingModelingExamplesFixedChargeandFacilityExample(3of4)Objectivefunction=SUM(C5:C10)=C10+D10+E10=G10-C22*F10Copyright©2016PearsonEducation,Inc.Exhibit5.200–1IntegerProgrammingModelingExamplesFixedChargeandFacilityExample(4of4)0-1integerrestrictionPlantcapacityconstraintsHarvestconstraintsCopyright©2016PearsonEducation,Inc.

Cities

Citieswithin300miles1.Atlanta Atlanta,Charlotte,Nashville2.Boston Boston,NewYork3.Charlotte Atlanta,Charlotte,Richmond4.Cincinnati Cincinnati,Detroit,Indianapolis,Nashville,Pittsburgh5.Detroit Cincinnati,Detroit,Indianapolis,Milwaukee,Pittsburgh6.Indianapolis Cincinnati,Detroit,Indianapolis,Milwaukee,Nashville,St.Louis7.Milwaukee Detroit,Indianapolis,Milwaukee8.Nashville Atlanta,Cincinnati,Indianapolis,Nashville,St.Louis9.NewYork Boston,NewYork,Richmond10.Pittsburgh Cincinnati,Detroit,Pittsburgh,Richmond11.Richmond Charlotte,NewYork,Pittsburgh,Richmond12.St.Louis Indianapolis,Nashville,St.Louis APSwantstoconstructtheminimumsetofnewhubsinthesetwelvecitiessuchthatthereisahubwithin300milesofeverycity:0–1IntegerProgrammingModelingExamplesSetCoveringExample(1of4)Copyright©2016PearsonEducation,Inc.xi=cityi,i=1to12;xi=0ifcityisnotselectedasahubandxi=1ifitis.MinimizeZ=x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12subjectto: Atlanta: x1+x3+x8

1 Boston: x2+x10

1 Charlotte: x1+x3+x11

1 Cincinnati: x4+x5+x6+x8+x10

1 Detroit: x4+x5+x6+x7+x10

1 Indianapolis: x4+x5+x6+x7+x8+x12

1 Milwaukee: x5+x6+x7

1 Nashville: x1+x4+x6+x8+x12

1 NewYork: x2+x9+x11

1 Pittsburgh: x4+x5+x10+x11

1 Richmond: x3+x9+x10+x11

1 StLouis: x6+x8+x12

1xij=0or10–1IntegerProgrammingModelingExamplesSetCoveringExample(2of4)0–1IntegerProgrammingModelingExamplesSetCoveringExampleinExcel(3of4)Exhibit5.21ObjectivefunctionDecisionvariablesinrow20=SUMPRODUCT(B18:M18,B20:M20)Copyright©2016PearsonEducation,Inc.Exhibit5.220–1IntegerPr