《管理科学05-整数规划.ppt》由会员分享，可在线阅读，更多相关《管理科学05-整数规划.ppt（45页珍藏版）》请在三一办公上搜索。
1、Chapter 5-Integer Programming,1,Chapter 5Integer Programming,Introduction to Management Science8th EditionbyBernard W.Taylor III,Chapter 5-Integer Programming,2,Chapter Topics,Integer Programming(IP)ModelsInteger Programming Graphical SolutionComputer Solution of Integer Programming Problems With Ex
2、cel and QM for Windows,Chapter 5-Integer Programming,3,Integer Programming ModelsTypes of Models,Total 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
3、 decision variables(but not all)required to have integer values.,Chapter 5-Integer Programming,4,A 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 purchas
4、e prices and space requirements:,Chapter 5-Integer Programming,5,A 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,6,Recr
5、eation 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,7,Integer Programming Model:Maximize Z=300 x1+90
6、 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 gymnasium,A 0-1 Integer Model(2 of
7、 2),Chapter 5-Integer Programming,8,A 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/bo
8、nd,$1,000 profit if sold after one year.Only 4 condominiums,15 acres of land,and 20 municipal bonds available.,Chapter 5-Integer Programming,9,Integer 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
9、0 x1,x3 0 and integer x1=condominiums purchased x2=acres of land purchased x3=bonds purchased,A Mixed Integer Model(2 of 2),Chapter 5-Integer Programming,10,Rounding non-integer solution values up to the nearest integer value can result in an infeasible solutionA feasible solution is ensured by roun
10、ding down non-integer solution values but may result in a less than optimal(sub-optimal)solution.,Integer Programming Graphical Solution,Chapter 5-Integer Programming,11,Integer Programming ExampleGraphical Solution of Maximization Model,Maximize Z=$100 x1+$150 x2subject to:8,000 x1+4,000 x2$40,000
11、15x1+30 x2 200 ft2 x1,x2 0 and integerOptimal Solution:Z=$1,055.56x1=2.22 pressesx2=5.55 lathes,Figure 5.1Feasible Solution Space with Integer Solution Points,Chapter 5-Integer Programming,12,Branch and Bound Method,Traditional approach to solving integer programming problems.Based on principle that
12、 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 Me
13、thod”for detailed description of method.,Chapter 5-Integer Programming,13,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,Computer Solution of IP Problems0 1
14、Model with Excel(1 of 5),Chapter 5-Integer Programming,14,Exhibit 5.2,Computer Solution of IP Problems0 1 Model with Excel(2 of 5),Chapter 5-Integer Programming,15,Exhibit 5.3,Computer Solution of IP Problems0 1 Model with Excel(3 of 5),Chapter 5-Integer Programming,16,Exhibit 5.4,Computer Solution
15、of IP Problems0 1 Model with Excel(4 of 5),Chapter 5-Integer Programming,17,Exhibit 5.5,Computer Solution of IP Problems0 1 Model with Excel(5 of 5),Chapter 5-Integer Programming,18,Computer Solution of IP Problems0 1 Model with QM for Windows(1 of 3),Recreational Facilities Example:Maximize Z=300 x
16、1+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,19,Exhibit 5.6,Computer Solution of IP Problems0 1 Model with QM for Windows(2 of 3),Chapter 5-Integer Programming,20,Exhibit 5.
17、7,Computer Solution of IP Problems0 1 Model with QM for Windows(3 of 3),Chapter 5-Integer Programming,21,Computer 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 integ
18、er,Chapter 5-Integer Programming,22,Exhibit 5.8,Computer Solution of IP ProblemsTotal Integer Model with Excel(2 of 5),Chapter 5-Integer Programming,23,Exhibit 5.9,Computer Solution of IP ProblemsTotal Integer Model with Excel(3 of 5),Chapter 5-Integer Programming,24,Exhibit 5.10,Computer Solution o
19、f IP ProblemsTotal Integer Model with Excel(4 of 5),Chapter 5-Integer Programming,25,Exhibit 5.11,Computer Solution of IP ProblemsTotal Integer Model with Excel(5 of 5),Chapter 5-Integer Programming,26,Integer Programming Model:Maximize Z=$9,000 x1+1,500 x2+1,000 x3subject to:50,000 x1+12,000 x2+8,0
20、00 x3$250,000 x1 4 condominiums x2 15 acres x3 20 bonds x2 0 x1,x3 0 and integer,Computer Solution of IP ProblemsMixed Integer Model with Excel(1 of 3),Chapter 5-Integer Programming,27,Exhibit 5.12,Computer Solution of IP ProblemsTotal Integer Model with Excel(2 of 3),Chapter 5-Integer Programming,2
21、8,Exhibit 5.13,Computer Solution of IP ProblemsSolution of Total Integer Model with Excel(3 of 3),Chapter 5-Integer Programming,29,Exhibit 5.14,Computer Solution of IP ProblemsMixed Integer Model with QM for Windows(1 of 2),Chapter 5-Integer Programming,30,Exhibit 5.15,Computer Solution of IP Proble
22、msMixed Integer Model with QM for Windows(2 of 2),Chapter 5-Integer Programming,31,University 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-Int
23、eger Programming,32,x1=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 x
24、5subject 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.16,0 1 Integer Programming Modeling ExamplesCapital Budgeting Example
25、(3 of 4),Chapter 5-Integer Programming,34,Exhibit 5.17,0 1 Integer Programming Modeling ExamplesCapital Budgeting Example(4 of 4),Chapter 5-Integer Programming,35,0 1 Integer Programming Modeling ExamplesFixed Charge and Facility Example(1 of 4),Which of six farms should be purchased that will meet
26、current production capacity at minimum total cost,including annual fixed costs and shipping costs?Data:,Chapter 5-Integer Programming,36,yi=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=18x
27、1A+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=
28、12 x1B+x2B+x3A+x4b+x5B+x6B=10 x1B+x2C+x3C+x4C+x5B+x6C=14 xij=0 yi=0 or 1,0 1 Integer Programming Modeling ExamplesFixed Charge and Facility Example(2 of 4),Chapter 5-Integer Programming,37,Exhibit 5.18,0 1 Integer Programming Modeling ExamplesFixed Charge and Facility Example(3 of 4),Chapter 5-Integ
29、er Programming,38,Exhibit 5.19,0 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,
30、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,Rich
31、mond10.PittsburghCincinnati,Detroit,Pittsburgh,Richmond11.RichmondCharlotte,New York,Pittsburgh,Richmond12.St.Louis Indianapolis,Nashville,St.Louis,APS 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 P
32、rogramming 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+x
33、10 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 P
34、rogramming,41,Exhibit 5.20,0 1 Integer Programming Modeling ExamplesSet Covering Example(3 of 4),Chapter 5-Integer Programming,42,Exhibit 5.21,0 1 Integer Programming Modeling ExamplesSet Covering Example(4 of 4),Chapter 5-Integer Programming,43,Total Integer Programming Modeling ExampleProblem Stat
35、ement(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/
36、salespersonRegion 2-$60,000/salesperson How many salespeople should be transferred into each region in order to maximize increased sales?,Chapter 5-Integer Programming,44,Step 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 Windows,Total Integer Programming Modeling ExampleModel Formulation(2 of 3),Chapter 5-Integer Programming,45,Total Integer Programming Modeling ExampleSolution with QM for Windows(3 of 3),
