0-–-1-integer-programmin教學(xué)講解課件

Chapter5IntegerProgrammingIntroductiontoManagementScience8thEditionbyBernardW.TaylorIII1Chapter5-IntegerProgrammingChapter5IntroductiontoManagChapterTopicsIntegerProgramming(IP)ModelsIntegerProgrammingGraphicalSolutionComputerSolutionofIntegerProgrammingProblemsWithExcelandQMforWindows2Chapter5-IntegerProgrammingChapterTopicsIntegerProgrammIntegerProgrammingModelsTypesofModelsTotalIntegerModel:Alldecisionvariablesrequiredtohaveintegersolutionvalues.0-1IntegerModel:Alldecisionvariablesrequiredtohaveintegervaluesofzeroorone.MixedIntegerModel:Someofthedecisionvariables(butnotall)requiredtohaveintegervalues.3Chapter5-IntegerProgrammingIntegerProgrammingModelsTotaATotalIntegerModel(1of2)Machineshopobtainingnewpressesandlathes.Marginalprofitability:eachpress$100/day;eachlathe$150/day.Resourceconstraints:$40,000,200sq.ft.floorspace.Machinepurchasepricesandspacerequirements:4Chapter5-IntegerProgrammingATotalIntegerModel(1of2)ATotalIntegerModel(2of2)IntegerProgrammingModel: MaximizeZ=$100x1+$150x2subjectto: 8,000x1+4,000x2

$40,00015x1+30x2

200ft2x1,x2

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

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: AAMixedIntegerModel(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.8Chapter5-IntegerProgrammingAMixedIntegerModel(1of2)IntegerProgrammingModel:

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-IntegerProgrammingIntegerProgrammingModel: ARoundingnon-integersolutionvaluesuptothenearestintegervaluecanresultinaninfeasiblesolutionAfeasiblesolutionisensuredbyroundingdownnon-integersolutionvaluesbutmayresultinalessthanoptimal(sub-optimal)solution.IntegerProgrammingGraphicalSolution10Chapter5-IntegerProgrammingRoundingnon-integersolutionIntegerProgrammingExampleGraphicalSolutionofMaximizationModelMaximizeZ=$100x1+$150x2subjectto: 8,000x1+4,000x2$40,00015x1+30x2200ft2 x1,x20andintegerOptimalSolution: Z=$1,055.56 x1=2.22presses x2=5.55lathesFigure5.1FeasibleSolutionSpacewithIntegerSolutionPoints11Chapter5-IntegerProgrammingIntegerProgrammingExampleMaxBranchandBoundMethodTraditionalapproachtosolvingintegerprogrammingproblems.Basedonprinciplethattotalsetoffeasiblesolutionscanbepartitionedintosmallersubsetsofsolutions.Smallersubsetsevaluateduntilbestsolutionisfound.Methodisatediousandcomplexmathematicalprocess.ExcelandQMforWindowsusedinthisbook.SeeCD-ROMModuleC–“IntegerProgramming:theBranchandBoundMethod”fordetaileddescriptionofmethod.12Chapter5-IntegerProgrammingBranchandBoundMethodTraditiRecreationalFacilitiesExample: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-IntegerProgrammingRecreationalFacilitiesExamplExhibit5.2ComputerSolutionofIPProblems0–1ModelwithExcel(2of5)14Chapter5-IntegerProgrammingExhibit5.2ComputerSolutionoExhibit5.3ComputerSolutionofIPProblems0–1ModelwithExcel(3of5)15Chapter5-IntegerProgrammingExhibit5.3ComputerSolutionoExhibit5.4ComputerSolutionofIPProblems0–1ModelwithExcel(4of5)16Chapter5-IntegerProgrammingExhibit5.4ComputerSolutionoExhibit5.5ComputerSolutionofIPProblems0–1ModelwithExcel(5of5)17Chapter5-IntegerProgrammingExhibit5.5ComputerSolutionoComputerSolutionofIPProblems0–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-IntegerProgrammingComputerSolutionofIPProbleExhibit5.6ComputerSolutionofIPProblems0–1ModelwithQMforWindows(2of3)19Chapter5-IntegerProgrammingExhibit5.6ComputerSolutiono

Exhibit5.7ComputerSolutionofIPProblems0–1ModelwithQMforWindows(3of3)20Chapter5-IntegerProgramming

ComputerSolutionofIPProblemsTotalIntegerModelwithExcel(1of5)IntegerProgrammingModel: MaximizeZ=$100x1+$150x2 subjectto: 8,000x1+4,000x2$40,000 15x1+30x2200ft2 x1,x20andinteger21Chapter5-IntegerProgrammingComputerSolutionofIPProbleExhibit5.8ComputerSolutionofIPProblemsTotalIntegerModelwithExcel(2of5)22Chapter5-IntegerProgrammingExhibit5.8ComputerSolutionoExhibit5.9ComputerSolutionofIPProblemsTotalIntegerModelwithExcel(3of5)23Chapter5-IntegerProgrammingExhibit5.9ComputerSolutionoExhibit5.10ComputerSolutionofIPProblemsTotalIntegerModelwithExcel(4of5)24Chapter5-IntegerProgrammingExhibit5.10ComputerSolutionExhibit5.11ComputerSolutionofIPProblemsTotalIntegerModelwithExcel(5of5)25Chapter5-IntegerProgrammingExhibit5.11ComputerSolutionIntegerProgrammingModel:

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-IntegerProgrammingIntegerProgrammingModel: CExhibit5.12ComputerSolutionofIPProblemsTotalIntegerModelwithExcel(2of3)27Chapter5-IntegerProgrammingExhibit5.12ComputerSolution

Exhibit5.13ComputerSolutionofIPProblemsSolutionofTotalIntegerModelwithExcel(3of3)28Chapter5-IntegerProgramming

Exhibit5.14ComputerSolutionofIPProblemsMixedIntegerModelwithQMforWindows(1of2)29Chapter5-IntegerProgrammingExhibit5.14ComputerSolutionExhibit5.15ComputerSolutionofIPProblemsMixedIntegerModelwithQMforWindows(2of2)30Chapter5-IntegerProgrammingExhibit5.15ComputerSolutionUniversitybookstoreexpansionproject.Notenoughspaceavailableforbothacomputerdepartmentandaclothingdepartment.Data:0–1IntegerProgrammingModelingExamplesCapitalBudgetingExample(1of4)31Chapter5-IntegerProgrammingUniversitybookstoreexpansionx1=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-IntegerProgrammingx1=selectionofwebsitepro

Exhibit5.160–1IntegerProgrammingModelingExamplesCapitalBudgetingExample(3of4)33Chapter5-IntegerProgramming

Exhibit5.170–1IntegerProgrammingModelingExamplesCapitalBudgetingExample(4of4)34Chapter5-IntegerProgrammingExhibit5.170–1IntegerProg0–1IntegerProgrammingModelingExamplesFixedChargeandFacilityExample(1of4)Whichofsixfarmsshouldbepurchasedthatwillmeetcurrentproductioncapacityatminimumtotalcost,includingannualfixedcostsandshippingcosts?Data:35Chapter5-IntegerProgramming0–1IntegerProgrammingModeyi=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+x1C-11.2y1

<0 x2A+x2B+x2C-10.5y2

<0x3A+x3B+x3C-12.8y3

<0 x4A+x4B+x4C-9.3y4

<0x5A+x5B+x5C-10.8y5

<0 x6A+x6B+X6C-9.6y6

<0x1A+x2A+x3A+x4A+x5A+x6A=12x1B+x2B+x3A+x4B+x5B+x6B=10x1C+x2C+x3C+x4C+x5C+x6C=14xij=0yi=0or10–1IntegerProgrammingModelingExamplesFixedChargeandFacilityExample(2of4)36Chapter5-IntegerProgrammingyi=0iffarmiisnotselectExhibit5.180–1IntegerProgrammingModelingExamplesFixedChargeandFacilityExample(3of4)37Chapter5-IntegerProgrammingExhibit5.180–1IntegerProgExhibit5.190–1IntegerProgrammingModelingExamplesFixedChargeandFacilityExample(4of4)38Chapter5-IntegerProgrammingExhibit5.190–1IntegerProg

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-IntegerProgrammingCitiesxi=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+x9

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-IntegerProgrammingxi=cityi,i=1to12,xi=Exhibit5.200–1IntegerProgrammingModelingExamplesSetCoveringExample(3of4)41Chapter5-IntegerProgrammingExhibit5.200–1IntegerProgExhibit5.210–1IntegerProgrammingModelingExamplesSetCoveringExample(4of4)42Chapter5-IntegerProgrammingExhibit5.210–1IntegerProgTotalIntegerProgrammingModelingExampleProblemStatement(1of3)Textbookcompanydevelopingtwonewregions.Planningtotransfersomeofits10salespeopleintonewregions.Averageannualexpensesforsalesperson:Region1-$10,000/salespersonRegion2-$7,500/salespersonTotalannualexpensebudgetis$72,000.Salesgeneratedeachyear:Region1-$85,000/salespersonRegion2-$60,000/salespersonHowmanysalespeopleshouldbetransferredintoeachregioninordertomaximizeincreasedsales?43Chapter5-IntegerProgrammingTotalIntegerProgrammingModeStep1:FormulatetheIntegerProgrammingModelxi=numberofsalespersonassignedtoregioni,i=1,2. MaximizeZ=$85,000x1+60,000x2 subjectto: x1+x2

10salespeople $10,000x1+7,000x2

$72,000expensebudget x1,x2

0orintegerStep2:SolvetheModelusingQMforWindowsTotalIntegerProgrammingModelingExampleModelFormulation(2of3)44Chapter5-IntegerProgrammingStep1:TotalIntegerProgrammiTotalIntegerProgrammingModelingExampleSolutionwithQMforWindows(3of3)45Chapter5-IntegerProgrammingTotalIntegerProgrammingModeChapter5IntegerProgrammingIntroductiontoManagementScience8thEditionbyBernardW.TaylorIII46Chapter5-IntegerProgrammingChapter5IntroductiontoManagChapterTopicsIntegerProgramming(IP)ModelsIntegerProgrammingGraphicalSolutionComputerSolutionofIntegerProgrammingProblemsWithExcelandQMforWindows47Chapter5-IntegerProgrammingChapterTopicsIntegerProgrammIntegerProgrammingModelsTypesofModelsTotalIntegerModel:Alldecisionvariablesrequiredtohaveintegersolutionvalues.0-1IntegerModel:Alldecisionvariablesrequiredtohaveintegervaluesofzeroorone.MixedIntegerModel:Someofthedecisionvariables(butnotall)requiredtohaveintegervalues.48Chapter5-IntegerProgrammingIntegerProgrammingModelsTotaATotalIntegerModel(1of2)Machineshopobtainingnewpressesandlathes.Marginalprofitability:eachpress$100/day;eachlathe$150/day.Resourceconstraints:$40,000,200sq.ft.floorspace.Machinepurchasepricesandspacerequirements:49Chapter5-IntegerProgrammingATotalIntegerModel(1of2)ATotalIntegerModel(2of2)IntegerProgrammingModel: MaximizeZ=$100x1+$150x2subjectto: 8,000x1+4,000x2

$40,00015x1+30x2

200ft2x1,x2

0andintegerx1=numberofpressesx2=numberoflathes50Chapter5-IntegerProgrammingATotalIntegerModel(2of2)Recreationfacilitiesselectiontomaximizedailyusagebyresidents.Resourceconstraints:$120,000budget;12acresofland.Selectionconstraint:eitherswimmingpoolortenniscenter(notboth).Data:A0-1IntegerModel(1of2)51Chapter5-IntegerProgrammingRecreationfacilitiesselectioIntegerProgrammingModel:

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)52Chapter5-IntegerProgrammingIntegerProgrammingModel: AAMixedIntegerModel(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.53Chapter5-IntegerProgrammingAMixedIntegerModel(1of2)IntegerProgrammingModel:

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)54Chapter5-IntegerProgrammingIntegerProgrammingModel: ARoundingnon-integersolutionvaluesuptothenearestintegervaluecanresultinaninfeasiblesolutionAfeasiblesolutionisensuredbyroundingdownnon-integersolutionvaluesbutmayresultinalessthanoptimal(sub-optimal)solution.IntegerProgrammingGraphicalSolution55Chapter5-IntegerProgrammingRoundingnon-integersolutionIntegerProgrammingExampleGraphicalSolutionofMaximizationModelMaximizeZ=$100x1+$150x2subjectto: 8,000x1+4,000x2$40,00015x1+30x2200ft2 x1,x20andintegerOptimalSolution: Z=$1,055.56 x1=2.22presses x2=5.55lathesFigure5.1FeasibleSolutionSpacewithIntegerSolutionPoints56Chapter5-IntegerProgrammingIntegerProgrammingExampleMaxBranchandBoundMethodTraditionalapproachtosolvingintegerprogrammingproblems.Basedonprinciplethattotalsetoffeasiblesolutionscanbepartitionedintosmallersubsetsofsolutions.Smallersubsetsevaluateduntilbestsolutionisfound.Methodisatediousandcomplexmathematicalprocess.ExcelandQMforWindowsusedinthisbook.SeeCD-ROMModuleC–“IntegerProgramming:theBranchandBoundMethod”fordetaileddescriptionofmethod.57Chapter5-IntegerProgrammingBranchandBoundMethodTraditiRecreationalFacilitiesExample: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)58Chapter5-IntegerProgrammingRecreationalFacilitiesExamplExhibit5.2ComputerSolutionofIPProblems0–1ModelwithExcel(2of5)59Chapter5-IntegerProgrammingExhibit5.2ComputerSolutionoExhibit5.3ComputerSolutionofIPProblems0–1ModelwithExcel(3of5)60Chapter5-IntegerProgrammingExhibit5.3ComputerSolutionoExhibit5.4ComputerSolutionofIPProblems0–1ModelwithExcel(4of5)61Chapter5-IntegerProgrammingExhibit5.4ComputerSolutionoExhibit5.5ComputerSolutionofIPProblems0–1ModelwithExcel(5of5)62Chapter5-IntegerProgrammingExhibit5.5ComputerSolutionoComputerSolutionofIPProblems0–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=0or163Chapter5-IntegerProgrammingComputerSolutionofIPProbleExhibit5.6ComputerSolutionofIPProblems0–1ModelwithQMforWindows(2of3)64Chapter5-IntegerProgrammingExhibit5.6ComputerSolutiono

Exhibit5.7ComputerSolutionofIPProblems0–1ModelwithQMforWindows(3of3)65Chapter5-IntegerProgramming

ComputerSolutionofIPProblemsTotalIntegerModelwithExcel(1of5)IntegerProgrammingModel: MaximizeZ=$100x1+$150x2 subjectto: 8,000x1+4,000x2$40,000 15x1+30x2200ft2 x1,x20andinteger66Chapter5-IntegerProgrammingComputerSolutionofIPProbleExhibit5.8ComputerSolutionofIPProblemsTotalIntegerModelwithExcel(2of5)67Chapter5-IntegerProgrammingExhibit5.8ComputerSolutionoExhibit5.9ComputerSolutionofIPProblemsTotalIntegerModelwithExcel(3of5)68Chapter5-IntegerProgrammingExhibit5.9ComputerSolutionoExhibit5.10ComputerSolutionofIPProblemsTotalIntegerModelwithExcel(4of5)69Chapter5-IntegerProgrammingExhibit5.10ComputerSolutionExhibit5.11ComputerSolutionofIPProblemsTotalIntegerModelwithExcel(5of5)70Chapter5-IntegerProgrammingExhibit5.11ComputerSolutionIntegerProgrammingModel:

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)71Chapter5-IntegerProgrammingIntegerProgrammingModel: CExhibit5.12ComputerSolutionofIPProblemsTotalIntegerModelwithExcel(2of3)72Chapter5-IntegerProgrammingExhibit5.12ComputerSolution

Exhibit5.13ComputerSolutionofIPProblemsSolutionofTotalIntegerModelwithExcel(3of3)73Chapter5-IntegerProgramming

Exhibit5.14ComputerSolutionofIPProblemsMixedIntegerModelwithQMforWindows(1of2)74Chapter5-IntegerProgrammingExhibit5.14ComputerSolutionExhibit5.15ComputerSolutionofIPProblemsMixedIntegerModelwithQMforWindows(2of2)75Chapter5-IntegerProgrammingExhibit5.15ComputerSolutionUniversitybookstoreexpansionproject.Notenoughspaceavailableforbothacomputerdepartmentandaclothingdepartment.Data:0–1IntegerProgrammingModelingExamplesCapitalBudgetingExample(1of4)76Chapter5-IntegerProgrammingUniversitybookstoreexpansionx1=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)77Chapter5-IntegerProgrammingx1=selectionofwebsitepro

Exhibit5.160–1IntegerProgrammingModelingExamplesCapitalBudgetingExample(3of4)78Chapter5-IntegerProgramming

Exhibit5.170–1IntegerProgrammingModelingExamplesCapitalBudgetingExample(4of4)79Chapter5-IntegerProgrammingExhibit5.170–1IntegerProg0–1IntegerProgrammingModelingExamplesFixedChargeandFacilityExample(1of4)Whichofsixfarmsshouldbepurchasedthatwillmeetcurrentproductioncapacityatminimumtotalcost,includingannualfixedcostsandshippingcosts?Data:80Chapter5-IntegerProgramming0–1IntegerProgrammingModeyi=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+x1C-11.2y1

<0 x2A+x2B+x2C-10.5y2

<0x3A+x3B+x3C-12.8y3

<0 x4A+x4B+x4C-9.3y4

<0x5A+x5B+x5C-10.8y5

<0 x6A+x6B+X6C-9.6y6

<0x1A+x2A+x3A+x4A+x5A+x6A=12x1B+x2B+x3A+x4B+x5B+x6B=10x1C+x2C+x3C+x4C+x5C+x6C=14xij=0yi=0or10–1IntegerProgrammingModelingExamplesFixedChargeandFacilityExample(2of4)81Chapter5-IntegerProgrammingyi=0iffarmiisnotselectExhibit5.180–1IntegerProgrammingModelingExamplesFixedChargeandFacilityExample(3of4)82Chapter5-IntegerProgrammingExhibit5.180–1IntegerProgExhibit5.190–1IntegerProgrammingModelingExamplesFixedChargeandFacilityExample(4of4)83Chap