管理科学05-整数规划课件

Chapter5IntegerProgrammingIntroductiontoManagementScience8thEditionbyBernardW.TaylorIII1Chapter5-IntegerProgrammingChapterTopicsIntegerProgramming(IP)ModelsIntegerProgrammingGraphicalSolutionComputerSolutionofIntegerProgrammingProblemsWithExcelandQMforWindows2Chapter5-IntegerProgrammingIntegerProgrammingModelsTypesofModelsTotalIntegerModel:Alldecisionvariablesrequiredtohaveintegersolutionvalues.0-1IntegerModel:Alldecisionvariablesrequiredtohaveintegervaluesofzeroorone.MixedIntegerModel:Someofthedecisionvariables(butnotall)requiredtohaveintegervalues.3Chapter5-IntegerProgrammingATotalIntegerModel(2of2)IntegerProgrammingModel: MaximizeZ=$100x1+$150x2subjectto: 8,000x1+4,000x2

$40,00015x1+30x2

200ft2x1,x2

0andintegerx1=numberofpressesx2=numberoflathes5Chapter5-IntegerProgrammingRecreationfacilitiesselectiontomaximizedailyusagebyresidents.Resourceconstraints:$120,000budget;12acresofland.Selectionconstraint:eitherswimmingpoolortenniscenter(notboth).Data:A0-1IntegerModel(1of2)6Chapter5-IntegerProgrammingIntegerProgrammingModel:

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

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

12acresx1+x2

1facilityx1,x2,x3,x4=0or1 x1=constructionofaswimmingpoolx2=constructionofatenniscenterx3=constructionofanathleticfieldx4=constructionofagymnasiumA0-1IntegerModel(2of2)7Chapter5-IntegerProgrammingIntegerProgrammingModel:

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

$250,000 x1

4condominiums x215acres x3

20bonds x20 x1,x3

0andinteger x1=condominiumspurchased x2=acresoflandpurchased x3=bondspurchasedAMixedIntegerModel(2of2)9Chapter5-IntegerProgrammingRoundingnon-integersolutionvaluesuptothenearestintegervaluecanresultinaninfeasiblesolutionAfeasiblesolutionisensuredbyroundingdownnon-integersolutionvaluesbutmayresultinalessthanoptimal(sub-optimal)solution.IntegerProgrammingGraphicalSolution10Chapter5-IntegerProgrammingIntegerProgrammingExampleGraphicalSolutionofMaximizationModelMaximizeZ=$100x1+$150x2subjectto: 8,000x1+4,000x2$40,00015x1+30x2200ft2 x1,x20andintegerOptimalSolution: Z=$1,055.56 x1=2.22presses x2=5.55lathesFigure5.1FeasibleSolutionSpacewithIntegerSolutionPoints11Chapter5-IntegerProgrammingRecreationalFacilitiesExample:MaximizeZ=300x1+90x2+400x3+150x4subjectto: $35,000x1+10,000x2+25,000x3+90,000x4

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

12acresx1+x2

1facilityx1,x2,x3,x4=0or1ComputerSolutionofIPProblems0–1ModelwithExcel(1of5)13Chapter5-IntegerProgrammingExhibit5.2ComputerSolutionofIPProblems0–1ModelwithExcel(2of5)14Chapter5-IntegerProgrammingExhibit5.3ComputerSolutionofIPProblems0–1ModelwithExcel(3of5)15Chapter5-IntegerProgrammingExhibit5.5ComputerSolutionofIPProblems0–1ModelwithExcel(5of5)17Chapter5-IntegerProgrammingComputerSolutionofIPProblems0–1ModelwithQMforWindows(1of3)RecreationalFacilitiesExample:MaximizeZ=300x1+90x2+400x3+150x4subjectto: $35,000x1+10,000x2+25,000x3+90,000x4

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

12acresx1+x2

1facilityx1,x2,x3,x4=0or118Chapter5-IntegerProgrammingExhibit5.6ComputerSolutionofIPProblems0–1ModelwithQMforWindows(2of3)19Chapter5-IntegerProgrammingComputerSolutionofIPProblemsTotalIntegerModelwithExcel(1of5)IntegerProgrammingModel: MaximizeZ=$100x1+$150x2 subjectto: 8,000x1+4,000x2$40,000 15x1+30x2200ft2 x1,x20andinteger21Chapter5-IntegerProgrammingExhibit5.8ComputerSolutionofIPProblemsTotalIntegerModelwithExcel(2of5)22Chapter5-IntegerProgrammingExhibit5.9ComputerSolutionofIPProblemsTotalIntegerModelwithExcel(3of5)23Chapter5-IntegerProgrammingExhibit5.11ComputerSolutionofIPProblemsTotalIntegerModelwithExcel(5of5)25Chapter5-IntegerProgrammingIntegerProgrammingModel:

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

$250,000 x1

4condominiums x215acres x3

20bonds x20 x1,x3

0andinteger ComputerSolutionofIPProblemsMixedIntegerModelwithExcel(1of3)26Chapter5-IntegerProgrammingExhibit5.14ComputerSolutionofIPProblemsMixedIntegerModelwithQMforWindows(1of2)29Chapter5-IntegerProgrammingExhibit5.15ComputerSolutionofIPProblemsMixedIntegerModelwithQMforWindows(2of2)30Chapter5-IntegerProgrammingUniversitybookstoreexpansionproject.Notenoughspaceavailableforbothacomputerdepartmentandaclothingdepartment.Data:0–1IntegerProgrammingModelingExamplesCapitalBudgetingExample(1of4)31Chapter5-IntegerProgrammingx1=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)32Chapter5-IntegerProgramming

Exhibit5.160–1IntegerProgrammingModelingExamplesCapitalBudgetingExample(3of4)33Chapter5-IntegerProgrammingExhibit5.170–1IntegerProgrammingModelingExamplesCapitalBudgetingExample(4of4)34Chapter5-IntegerProgramming0–1IntegerProgrammingModelingExamplesFixedChargeandFacilityExample(1of4)Whichofsixfarmsshouldbepurchasedthatwillmeetcurrentproductioncapacityatminimumtotalcost,includingannualfixedcostsandshippingcosts?Data:35Chapter5-IntegerProgrammingyi=0iffarmiisnotselected,and1iffarmiisselected,i=1,2,3,4,5,6xij=potatoes(tons,1000s)shippedfromfarmi,i=1,2,3,4,5,6toplantj,j=A,B,C.MinimizeZ=18x1A+15x1B+12x1C+13x2A+10x2B+17x2C+16x3A+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+x3A+x4b+x5B+x6B=10x1B+x2C+x3C+x4C+x5B+x6C=14xij=0yi=0or10–1IntegerProgrammingModelingExamplesFixedChargeandFacilityExample(2of4)36Chapter5-IntegerProgrammingExhibit5.180–1IntegerProgrammingModelingExamplesFixedChargeandFacilityExample(3of4)37Chapter5-IntegerProgrammingExhibit5.190–1IntegerProgrammingModelingExamplesFixedChargeandFacilityExample(4of4)38Chapter5-IntegerProgramming

Cities

Citieswithin300miles1.Atlanta Atlanta,Charlotte,Nashville2.Boston Boston,NewYork3.Charlotte Atlanta,Charlotte,Richmond4.Cincinnati Cincinnati,Detroit,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.LouisAPSwantstoconstructtheminimumsetofnewhubsinthefollowingtwelvecitiessuchthatthereisahubwithin300milesofeverycity:0–1IntegerProgrammingModelingExamplesSetCoveringExample(1of4)39Chapter5-IntegerProgrammingxi=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+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=0or1

0–1IntegerProgrammingModelingExamplesSetCoveringExample(2of4)40Chapter5-IntegerProgrammingExhibit5.200–1IntegerProgrammingModelingExamplesSetCoveringExample(3of4)41Chapter5-IntegerProgrammingExhibit