管理科学整数规划 精选文档.ppt

管理科学整数规划 Chapter 5-Integer Programming1本讲稿第一页，共四十五页Chapter 5-Integer Programming 2Chapter TopicsInteger Programming(IP)ModelsInteger Programming Graphical SolutionComputer Solution of Integer Programming Problems With Excel and QM for Windows本讲稿第二页，共四十五页Chapter 5-Integer Programming 3Integer Programming ModelsTypes of ModelsTotal Integer Model:All decision variables required to have integer solution values.0-1 Integer Model:All decision variables required to have integer values of zero or one.Mixed Integer Model:Some of the decision variables(but not all)required to have integer values.本讲稿第三页，共四十五页Chapter 5-Integer Programming 4A Total Integer Model(1 of 2)Machine shop obtaining new presses and lathes.Marginal profitability:each press$100/day;each lathe$150/day.Resource constraints:$40,000,200 sq.ft.floor space.Machine purchase prices and space requirements:本讲稿第四页，共四十五页Chapter 5-Integer Programming 5A Total Integer Model(2 of 2)Integer Programming Model:Maximize Z=$100 x1+$150 x2 subject to:8,000 x1+4,000 x2$40,000 15x1+30 x2 200 ft2 x1,x2 0 and integer x1=number of presses x2=number of lathes本讲稿第五页，共四十五页Chapter 5-Integer Programming 6Recreation facilities selection to maximize daily usage by residents.Resource constraints:$120,000 budget;12 acres of land.Selection constraint:either swimming pool or tennis center(not both).Data:A 0-1 Integer Model(1 of 2)本讲稿第六页，共四十五页Chapter 5-Integer Programming 7Integer Programming Model:Maximize Z=300 x1+90 x2+400 x3+150 x subject to:$35,000 x1+10,000 x2+25,000 x3+90,000 x4$120,000 4x1+2x2+7x3+3x3 12 acres x1+x2 1 facility x1,x2,x3,x4=0 or 1 x1=construction of a swimming pool x2=construction of a tennis center x3=construction of an athletic field x4=construction of a gymnasiumA 0-1 Integer Model(2 of 2)本讲稿第七页，共四十五页Chapter 5-Integer Programming 8A Mixed Integer Model(1 of 2)$250,000 available for investments providing greatest return after one year.Data:Condominium cost$50,000/unit,$9,000 profit if sold after one year.Land cost$12,000/acre,$1,500 profit if sold after one year.Municipal bond cost$8,000/bond,$1,000 profit if sold after one year.Only 4 condominiums,15 acres of land,and 20 municipal bonds available.本讲稿第八页，共四十五页Chapter 5-Integer Programming 9Integer Programming Model:Maximize Z=$9,000 x1+1,500 x2+1,000 x3subject to:50,000 x1+12,000 x2 +8,000 x3$250,000 x1 4 condominiums x2 15 acres x3 20 bonds x2 0 x1,x3 0 and integer x1=condominiums purchased x2 =acres of land purchased x3=bonds purchasedA Mixed Integer Model(2 of 2)本讲稿第九页，共四十五页Chapter 5-Integer Programming 10Rounding non-integer solution values up to the nearest integer value can result in an infeasible solutionA feasible solution is ensured by rounding down non-integer solution values but may result in a less than optimal(sub-optimal)solution.Integer Programming Graphical Solution本讲稿第十页，共四十五页Chapter 5-Integer Programming 11Integer Programming ExampleGraphical Solution of Maximization ModelMaximize Z=$100 x1+$150 x2subject to:8,000 x1+4,000 x2$40,000 15x1+30 x2 200 ft2 x1,x2 0 and integerOptimal Solution:Z=$1,055.56x1=2.22 pressesx2=5.55 lathesFigure 5.1Feasible Solution Space with Integer Solution Points本讲稿第十一页，共四十五页Chapter 5-Integer Programming 12Branch and Bound MethodTraditional approach to solving integer programming problems.Based on principle that total set of feasible solutions can be partitioned into smaller subsets of solutions.Smaller subsets evaluated until best solution is found.Method is a tedious and complex mathematical process.Excel and QM for Windows used in this book.See CD-ROM Module C “Integer Programming:the Branch and Bound Method”for detailed description of method.本讲稿第十二页，共四十五页Chapter 5-Integer Programming 13Recreational Facilities Example:Maximize Z=300 x1+90 x2+400 x3+150 x4subject to:$35,000 x1+10,000 x2+25,000 x3+90,000 x4$120,000 4x1+2x2+7x3+3x3 12 acres x1+x2 1 facility x1,x2,x3,x4=0 or 1Computer Solution of IP Problems0 1 Model with Excel(1 of 5)本讲稿第十三页，共四十五页Chapter 5-Integer Programming 14Exhibit 5.2Computer Solution of IP Problems0 1 Model with Excel(2 of 5)本讲稿第十四页，共四十五页Chapter 5-Integer Programming 15Exhibit 5.3Computer Solution of IP Problems0 1 Model with Excel(3 of 5)本讲稿第十五页，共四十五页Chapter 5-Integer Programming 16Exhibit 5.4Computer Solution of IP Problems0 1 Model with Excel(4 of 5)本讲稿第十六页，共四十五页Chapter 5-Integer Programming 17Exhibit 5.5Computer Solution of IP Problems0 1 Model with Excel(5 of 5)本讲稿第十七页，共四十五页Chapter 5-Integer Programming 18Computer Solution of IP Problems0 1 Model with QM for Windows(1 of 3)Recreational Facilities Example:Maximize Z=300 x1+90 x2+400 x3+150 x4subject to:$35,000 x1+10,000 x2+25,000 x3+90,000 x4$120,000 4x1+2x2+7x3+3x3 12 acres x1+x2 1 facility x1,x2,x3,x4=0 or 1本讲稿第十八页，共四十五页Chapter 5-Integer Programming 19Exhibit 5.6Computer Solution of IP Problems0 1 Model with QM for Windows(2 of 3)本讲稿第十九页，共四十五页Chapter 5-Integer Programming 20 Exhibit 5.7Computer Solution of IP Problems0 1 Model with QM for Windows(3 of 3)本讲稿第二十页，共四十五页Chapter 5-Integer Programming 21Computer Solution of IP ProblemsTotal Integer Model with Excel(1 of 5)Integer Programming Model:Maximize Z=$100 x1+$150 x2subject to:8,000 x1+4,000 x2$40,000 15x1+30 x2 200 ft2 x1,x2 0 and integer本讲稿第二十一页，共四十五页Chapter 5-Integer Programming 22Exhibit 5.8Computer Solution of IP ProblemsTotal Integer Model with Excel(2 of 5)本讲稿第二十二页，共四十五页Chapter 5-Integer Programming 23Exhibit 5.9Computer Solution of IP ProblemsTotal Integer Model with Excel(3 of 5)本讲稿第二十三页，共四十五页Chapter 5-Integer Programming 24Exhibit 5.10Computer Solution of IP ProblemsTotal Integer Model with Excel(4 of 5)本讲稿第二十四页，共四十五页Chapter 5-Integer Programming 25Exhibit 5.11Computer Solution of IP ProblemsTotal Integer Model with Excel(5 of 5)本讲稿第二十五页，共四十五页Chapter 5-Integer Programming 26Integer Programming Model:Maximize Z=$9,000 x1+1,500 x2+1,000 x3subject to:50,000 x1+12,000 x2 +8,000 x3$250,000 x1 4 condominiums x2 15 acres x3 20 bonds x2 0 x1,x3 0 and integerComputer Solution of IP ProblemsMixed Integer Model with Excel(1 of 3)本讲稿第二十六页，共四十五页Chapter 5-Integer Programming 27Exhibit 5.12Computer Solution of IP ProblemsTotal Integer Model with Excel(2 of 3)本讲稿第二十七页，共四十五页Chapter 5-Integer Programming 28 Exhibit 5.13Computer Solution of IP ProblemsSolution of Total Integer Model with Excel(3 of 3)本讲稿第二十八页，共四十五页Chapter 5-Integer Programming 29Exhibit 5.14Computer Solution of IP ProblemsMixed Integer Model with QM for Windows(1 of 2)本讲稿第二十九页，共四十五页Chapter 5-Integer Programming 30Exhibit 5.15Computer Solution of IP ProblemsMixed Integer Model with QM for Windows(2 of 2)本讲稿第三十页，共四十五页Chapter 5-Integer Programming 31University bookstore expansion project.Not enough space available for both a computer department and a clothing department.Data:0 1 Integer Programming Modeling ExamplesCapital Budgeting Example(1 of 4)本讲稿第三十一页，共四十五页Chapter 5-Integer Programming 32x1=selection of web site projectx2=selection of warehouse projectx3=selection clothing department projectx4=selection of computer department projectx5=selection of ATM projectxi =1 if project“i”is selected,0 if project“i”is not selectedMaximize Z=$120 x1+$85x2+$105x3+$140 x4+$70 x5subject to:55x1+45x2+60 x3+50 x4+30 x5 150 40 x1+35x2+25x3+35x4+30 x5 110 25x1+20 x2+30 x4 60 x3+x4 1 xi=0 or 1 0 1 Integer Programming Modeling ExamplesCapital Budgeting Example(2 of 4)本讲稿第三十二页，共四十五页Chapter 5-Integer Programming 33 Exhibit 5.160 1 Integer Programming Modeling ExamplesCapital Budgeting Example(3 of 4)本讲稿第三十三页，共四十五页Chapter 5-Integer Programming 34Exhibit 5.170 1 Integer Programming Modeling ExamplesCapital Budgeting Example(4 of 4)本讲稿第三十四页，共四十五页Chapter 5-Integer Programming 350 1 Integer Programming Modeling ExamplesFixed Charge and Facility Example(1 of 4)Which of six farms should be purchased that will meet current production capacity at minimum total cost,including annual fixed costs and shipping costs?Data:本讲稿第三十五页，共四十五页Chapter 5-Integer Programming 36yi=0 if farm i is not selected,and 1 if farm i is selected,i=1,2,3,4,5,6xij=potatoes(tons,1000s)shipped from farm i,i=1,2,3,4,5,6 to plant j,j=A,B,C.Minimize Z=18x1A+15x1B+12x1C+13x2A+10 x2B+17x2C+16x3A+14x3B+18x3C+19x4A+15x4b+16x4C+17x5A+19x5B+12x5C+14x6A+16x6B+12x6C+405y1+390y2+450y3+368y4+520y5+465y6subject to:x1A+x1B+x1B-11.2y1=0 x2A+x2B+x2C-10.5y2=0 x3A+x3A+x3C-12.8y3=0 x4A+x4b+x4C-9.3y4=0 x5A+x5B+x5B-10.8y5=0 x6A+x6B+X6C-9.6y6=0 x1A+x2A+x3A+x4A+x5A+x6A=12 x1B+x2B+x3A+x4b+x5B+x6B =10 x1B+x2C+x3C+x4C+x5B+x6C=14 xij=0 yi=0 or 10 1 Integer Programming Modeling ExamplesFixed Charge and Facility Example(2 of 4)本讲稿第三十六页，共四十五页Chapter 5-Integer Programming 37Exhibit 5.180 1 Integer Programming Modeling ExamplesFixed Charge and Facility Example(3 of 4)本讲稿第三十七页，共四十五页Chapter 5-Integer Programming 38Exhibit 5.190 1 Integer Programming Modeling ExamplesFixed Charge and Facility Example(4 of 4)本讲稿第三十八页，共四十五页Chapter 5-Integer Programming 39 Cities Cities within 300 miles 1.AtlantaAtlanta,Charlotte,Nashville 2.BostonBoston,New York 3.CharlotteAtlanta,Charlotte,Richmond 4.CincinnatiCincinnati,Detroit,Nashville,Pittsburgh 5.DetroitCincinnati,Detroit,Indianapolis,Milwaukee,Pittsburgh 6.IndianapolisCincinnati,Detroit,Indianapolis,Milwaukee,Nashville,St.Louis 7.MilwaukeeDetroit,Indianapolis,Milwaukee 8.NashvilleAtlanta,Cincinnati,Indianapolis,Nashville,St.Louis 9.New YorkBoston,New York,Richmond10.PittsburghCincinnati,Detroit,Pittsburgh,Richmond11.RichmondCharlotte,New York,Pittsburgh,Richmond12.St.Louis Indianapolis,Nashville,St.LouisAPS wants to construct the minimum set of new hubs in the following twelve cities such that there is a hub within 300 miles of every city:0 1 Integer Programming Modeling ExamplesSet Covering Example(1 of 4)本讲稿第三十九页，共四十五页Chapter 5-Integer Programming 40 xi=city i,i=1 to 12,xi=0 if city is not selected as a hub and xi=1if it is.Minimize Z=x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12subject to:Atlanta:x1+x3+x8 1Boston:x2 +x10 1Charlotte:x1+x3+x11 1Cincinnati:x4+x5+x8+x10 1Detroit:x4+x5+x6+x7+x10 1Indianapolis:x4+x5+x6+x7+x8+x12 1Milwaukee:x5+x6+x7 1Nashville:x1+x4+x6+x8+x12 1New York:x2 +x9+x11 1Pittsburgh:x4+x5+x10+x11 1Richmond:x3+x9+x10+x11 1St Louis:x6+x8+x12 1 xij=0 or 1 0 1 Integer Programming Modeling ExamplesSet Covering Example(2 of 4)本讲稿第四十页，共四十五页Chapter 5-Integer Programming 41Exhibit 5.200 1 Integer Programming Modeling ExamplesSet Covering Example(3 of 4)本讲稿第四十一页，共四十五页Chapter 5-Integer Programming 42Exhibit 5.210 1 Integer Programming Modeling ExamplesSet Covering Example(4 of 4)本讲稿第四十二页，共四十五页Chapter 5-Integer Programming 43Total Integer Programming Modeling ExampleProblem Statement(1 of 3)Textbook company developing two new regions.Planning to transfer some of its 10 salespeople into new regions.Average annual expenses for sales person:Region 1-$10,000/salespersonRegion 2-$7,500/salespersonTotal annual expense budget is$72,000.Sales generated each year:Region 1-$85,000/salespersonRegion 2-$60,000/salesperson How many salespeople should be transferred into each region in order to maximize increased sales?本讲稿第四十三页，共四十五页Chapter 5-Integer Programming 44Step 1:Formulate the Integer Programming ModelMaximize Z=$85,000 x1+60,000 x2subject to:x1+x2 10 salespeople$10,000 x1+7,000 x2$72,000 expense budget x1,x2 0 or integerStep 2:Solve the Model using QM for WindowsTotal Integer Programming Modeling ExampleModel Formulation(2 of 3)本讲稿第四十四页，共四十五页Chapter 5-Integer Programming 45Total Integer Programming Modeling ExampleSolution with QM for Windows(3 of 3)本讲稿第四十五页，共四十五页