管理科学整数规划 精选文档.ppt
( 4.5 )《管理科学整数规划 精选文档.ppt》由会员分享，可在线阅读，更多相关《管理科学整数规划 精选文档.ppt（45页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、管理科学整数规划 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 Program
2、ming 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.本讲稿第三页，
3、共四十五页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
4、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 dai
5、ly 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,00
6、0 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 Pr
7、ogramming 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 a
8、fter 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 i
9、nteger 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
10、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,0
11、00 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 pr
12、inciple 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
13、 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 Solu
14、tion 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
15、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 wi
16、th 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 Proble
17、ms0 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
18、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 S
19、olution 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 wi
- 配套讲稿：
如PPT文件的首页显示word图标，表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制：
部分文档作品中含有的国旗、国徽等图片，仅作为作品整体效果示例展示，禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词：
- 管理科学整数规划 精选文档 管理科学 整数 规划 精选 文档
淘文阁 - 分享文档赚钱的网站所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
限制150内