运筹与决策之4整数规划bgtc.pptx

《运筹与决策之4整数规划bgtc.pptx》由会员分享，可在线阅读，更多相关《运筹与决策之4整数规划bgtc.pptx（46页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、1 11绪论绪论Introduction2线性规划线性规划LinearProgramming3运输与指派问题运输与指派问题TransportationModels4整数规划整数规划IntegerProgramming5网络模型网络模型NetworkModels6项目计划项目计划PERT&CPM7排队论排队论QueueingModels8模拟模拟Simulation9决策分析决策分析DecisionTheory10多目标决策多目标决策Multi-objectiveDecision管理数量方法管理数量方法 目录目录2 2授课内容授课内容Case:分销系统设计分销系统设计（P192）整数规划整数规划

2、1.1.图解法及分枝定界法图解法及分枝定界法2.2.MS6.0软件求解软件求解3.3.整数规划应用举例整数规划应用举例银行选址银行选址 P209（讲义：消防站选址讲义：消防站选址）案例讨论：课本出版案例讨论：课本出版P2223 3Questions 1.整整数数规规划划IP与与线线性性规规划划LP有有何何不同不同？整数规划的分类？整数规划的分类？2.整数规划的求解方法？整数规划的求解方法？3.分枝定界法的基本思路？分枝定界法的基本思路？4.分枝问题解可能出现的情况？分枝问题解可能出现的情况？4 4Q1Q1：整数规划与线性规划整数规划与线性规划LPLP 区别：区别：（要求所有（要求所有 xj x

3、j 的解为整数，或者要求部的解为整数，或者要求部分分 xj xj 的解为整数）的解为整数）1）一般整数规划。要求所有）一般整数规划。要求所有xj 的解为整数，的解为整数，称为纯整数规划；或者要求部分称为纯整数规划；或者要求部分xj的解为整的解为整数，称为混合整数规划。数，称为混合整数规划。2）0-1整数规划。它规定整数变量只能有两个整数规划。它规定整数变量只能有两个值，值，0或或1。5 5Q2Q2：整数规划的解法整数规划的解法v图解法图解法v穷举法穷举法v分枝定界法分枝定界法(Branch and Method)v割平面法割平面法6Q3Q3：分枝定界法的基本思路分枝定界法的基本思路maxZ=C

4、XAX=bX 0(A)maxZ=CXAX=bX 0X为整数为整数(B)(B)为为(A)的的线性规划线性规划松弛问题。松弛问题。7(C)(D)(B)Xj i+1(B)Xj iX*最优解最优解Xj*i+1i(C)(D)X*最优解为非整数解，最优解为非整数解，则对则对(B)每次分两枝每次分两枝,每枝多一个约束条件每枝多一个约束条件8 8Q4：分枝问题解可能出现的情况分枝问题解可能出现的情况如何回答？如何回答？9 9表表 分枝问题解可能出现的情况分枝问题解可能出现的情况情况情况2,4,5找到最优解找到最优解情况情况3在缩减的域上继续分枝定界法在缩减的域上继续分枝定界法情况情况6问题问题1的整数解作为的

5、整数解作为界界被保留，用于以后与问被保留，用于以后与问题题2的后续分枝的整数解进行比较，结论如情况的后续分枝的整数解进行比较，结论如情况4。结果结果10101绪论绪论Introduction2线性规划线性规划LinearProgramming3运输问题运输问题 TransportationModels4整数规划整数规划IntegerProgramming5网络模型网络模型NetworkModels6项目计划项目计划PERT&CPM7排队论排队论QueueingModels8模拟模拟Simulation9决策分析决策分析DecisionTheory10多目标决策多目标决策Multi-object

6、iveDecision管理数量方法管理数量方法 目录目录1111授课内容授课内容整数规划整数规划1.1.图解法及分枝定界法图解法及分枝定界法2.2.MS6.0软件求解软件求解3.3.整数规划应用举例整数规划应用举例银行选址银行选址 P230（讲义：消防站选址讲义：消防站选址）案例讨论：课本出版案例讨论：课本出版P2421212整数规划整数规划 举例举例产品产品桌桌椅椅备用资源备用资源木工木工1230油漆工油漆工3260搬运工搬运工0224利润利润4050例例1、家具厂生产计划问题、家具厂生产计划问题桌桌，椅各生产多少椅各生产多少,可获最大利润可获最大利润?13图解法求最优解图解法求最优解解：解

7、：X*=(15,7.5)Zmax=975该解是否符合实际该解是否符合实际要求？要求？0203010102030X1X2DABCDABCC点：点：X1+2X2=303X1+2X2=60如何求解整数解如何求解整数解？14144 整数规划整数规划整数规划的难度远大于一般线性规划整数规划的难度远大于一般线性规划1515整数规划简介整数规划简介要求所有要求所有xj 的解为整数，称为纯整数规划的解为整数，称为纯整数规划要求部分要求部分xj 的解为整数，称为混合整数规划的解为整数，称为混合整数规划对应没有整数解要求的线性规划称之为松弛问题对应没有整数解要求的线性规划称之为松弛问题整数规划的解是可数个的，最优

8、解不一定发生在极点整数规划的解是可数个的，最优解不一定发生在极点整数规划的最优解不会优于其松弛问题的最优解整数规划的最优解不会优于其松弛问题的最优解1616整数规划的解法整数规划的解法v图解法图解法v穷举法穷举法v分枝定界法分枝定界法v割平面法割平面法174.1整数规划的整数规划的穷举法穷举法穷举法：可以通过计算和比较所有整穷举法：可以通过计算和比较所有整数格点的值来求解。数格点的值来求解。18例：例：maxZ=40 x1+60 x2+70 x3+160 x416x1+35x2+45x3+85x4 100 x1,x2,x3,x4为为 0,1 X1=1X1=0111 01 01 01X2=0X3

9、=00解法解法1：枚举法：枚举法：x1=1,x2=1,x3=1,x4=0。枚举法？枚举法？1919v2100个整数解，用最现代化的计算机也要算个整数解，用最现代化的计算机也要算上几亿亿年。上几亿亿年。v穷举法是无法用来求解实际问题。穷举法是无法用来求解实际问题。v最优解经过四舍五入的方法是否可以？最优解经过四舍五入的方法是否可以？若若该该整整数数规规划划问问题题有有100个个01整整数数变量，那么整数解有多少个？变量，那么整数解有多少个？如何回答？如何回答？204.2分枝定界法的基本思路分枝定界法的基本思路maxZ=CXAX=bX 0(A)maxZ=CXAX=bX 0X为整数为整数(B)(B)

10、为为(A)的的线性规划线性规划松弛问题。松弛问题。21(C)(D)(B)Xj i+1(B)Xj iX*最优解最优解Xj*i+1i(C)(D)X*最优解为非整数解，最优解为非整数解，则对则对(B)每次分两枝每次分两枝,每枝多一个约束条件每枝多一个约束条件2222分枝定界法的步骤分枝定界法的步骤v思路思路:暂不考虑整数条件暂不考虑整数条件,用单纯形法求解用单纯形法求解,得整得整数解数解,停停;不是整数解不是整数解,分枝。分枝。v分枝分枝:每次分两枝每次分两枝,每枝多一个约束条件，每枝多一个约束条件，（每个（每个节点代表一个子问题）节点代表一个子问题）。v停止分枝条件停止分枝条件:1）子问题无可行解

11、子问题无可行解.2）子问题）子问题得整数解得整数解.3）子问题的目标值比下界差。）子问题的目标值比下界差。vmaxZ定界定界:v1）初始整数规划的松弛问题的最优值是上界）初始整数规划的松弛问题的最优值是上界.v2）子问题得整数解的最优值是一个下界。）子问题得整数解的最优值是一个下界。2323分枝问题解可能出现的情况分枝问题解可能出现的情况如何回答？如何回答？2424表表 分枝问题解可能出现的情况分枝问题解可能出现的情况情况情况2,4,5找到最优解找到最优解情况情况3在缩减的域上继续分枝定界法在缩减的域上继续分枝定界法情况情况6问题问题1的整数解作为的整数解作为界界被保留，用于以后与问被保留，用

12、于以后与问题题2的后续分枝的整数解进行比较，结论如情况的后续分枝的整数解进行比较，结论如情况4。结果结果25举例举例例：例：max Z=x1+x2 6x1+2x2 175x1+9x2 44x1,x2 为为 整数整数 如何回答？如何回答？26 松弛问题松弛问题Z0=5.545X1=1.477X2=4.068子问题子问题1Z1=5.333X1=1X2=4.333子问题子问题2Z2=4.5X1=2X2=2.5子问题子问题3Z3=5X1=1X2=4子问题子问题4无可行解无可行解x12x11x24x25分枝定界法分枝定界法求解过程求解过程最优整数解最优整数解X1=1X2=4最优目标函数值最优目标函数值Z

13、=527270-1 Programming(Binary IP)0-1整数规划整数规划v决策变量取值决策变量取值0或或1，称，称0-1或二进制变量或二进制变量。v0-1变量可数量化地描述诸如开与关、取与变量可数量化地描述诸如开与关、取与弃、有与无等现象所反映的离散变量间的弃、有与无等现象所反映的离散变量间的逻辑关系、顺序关系以及互斥的约束条件逻辑关系、顺序关系以及互斥的约束条件v0-1规划应用：如规划应用：如工厂选址工厂选址、生产计划安排、生产计划安排、旅行购物、背包问题、人员安排旅行购物、背包问题、人员安排、代码选、代码选取、线路设计取、线路设计、可靠性等、可靠性等28284.3整数规划建模

14、应用举例：整数规划建模应用举例：0-1变量的作用变量的作用1.Xj=3.从从N个方案中最多选中个方案中最多选中3个个:2.从从N个方案中必须选中一个个方案中必须选中一个:2929特殊约束的处理特殊约束的处理1.只有方案只有方案J选中时，方案选中时，方案I才可能被选才可能被选中中:如何表示？如何表示？xixj2.方案方案I与方案与方案J是否选中是同时的是否选中是同时的:xi=xj3.矛盾约束矛盾约束:f(x)-50与与f(x)0-f(x)+5M(1-y)与与f(x)MyM表示很大的数表示很大的数，y为为01变量。变量。如何回答？如何回答？3030特殊约束的处理特殊约束的处理4.多个选一多个选一:

15、fi(x)0,I=1,2,n.如何表示？如何表示？5.逻辑关系约束：逻辑关系约束：若若f(x)无限制无限制,则则g(x)0;若若f(x)0不成立不成立,则则g(x)无限制无限制.如何表示？如何表示？fi(x)M(1-yi)I=1,2,n.y1+y2+yn=1f(x)-M(1-y),g(x)My，M表示很大的数表示很大的数，y为为01变量。变量。31310-1整数规划模型及其应用整数规划模型及其应用8.3.1 资金预算（投资决策）问题资金预算（投资决策）问题8.3.2 固定成本问题固定成本问题8.3.3 配送系统设计配送系统设计8.3.4 银行选址（覆盖问题）银行选址（覆盖问题）8.3.5 产品

16、设计与市场份额优化产品设计与市场份额优化3232整数规划应用举例整数规划应用举例例例华华美美公公司司有有5个个项项目目被被列列入入投投资资计计划划，各各项项目目的的投投资资额额和和期期望望的的投投资资收收益益见见下下表表：该该公公司司只只有有600万万元元资资金金可可用用于于投投资资，由由于于技技术术上上的的原原因，投资受到以下约束：因，投资受到以下约束：1.在项目在项目1、2和和3中必须（只）有一项被选中；中必须（只）有一项被选中；2.项目项目3和和4只能选中一项；（必须选一项）只能选中一项；（必须选一项）3.项目项目5被选中的前提是项目被选中的前提是项目1必须被选中。必须被选中。如如何何在

17、在上上述述条条件件下下选选择择一一个个最最好好的的投投资资方方案，使投资收益最大。案，使投资收益最大。3333 项目投资收益表项目投资收益表 项目项目投资额（万元）投资额（万元）投资收益（万元）投资收益（万元）121015023002103100604130805260180Xj=1表表项项目目j选选中中,Xj=0表表项项目目j未未选选中中.j=1,2,3,4,5.约束条件如何表示？约束条件如何表示？3434计算过程计算过程解解:Xj=1表项目表项目j选中选中,Xj=0表项目表项目j未选中未选中.j=1,2,3,4,5.Z表示总收益表示总收益.则模型如下则模型如下:MaxZ=150X1+210

18、X2+60X3+80X4+180X5s.t:210X1+300X2+100X3+130X4+260X5600X1+X2+X3=1X3+X4=1X5X1Xj=0或1;j=1,2,3,4,5.3535 例例 解决某市解决某市消防站的布点问题消防站的布点问题。该城市共有该城市共有6个区，个区，每个都可以建消防站。每个都可以建消防站。市政府希望建设的消防站最市政府希望建设的消防站最少，但必须满足在城市任何地区发生火警时，消防少，但必须满足在城市任何地区发生火警时，消防车要在车要在15分钟内赶到现场。据实地测定，各区之间分钟内赶到现场。据实地测定，各区之间消防车行驶的时间见下表：请帮助该市制定一个最消防

19、车行驶的时间见下表：请帮助该市制定一个最节省的计划。节省的计划。消防车在各区行驶距离表消防车在各区行驶距离表地区地区1地区地区2地区地区3地区地区4地区地区5地区地区6地区地区1地区地区2地区地区3地区地区4地区地区5地区地区6010162827201002432171016240122721283212015252717271501420102125140Howtosolve？3636计算过程计算过程解解:Xj=1表地区设消防站表地区设消防站,Xj=0表地区不设消防站表地区不设消防站.Z=消防站总数消防站总数,则模型如下则模型如下:MinZ=X1+X2+X3+X4+X5+X6s.t.X1+X

20、21X1+X2+X61X3+X41X3+X4+X51X4+X5+X61X2+X5+X61Xj=0或或1；j=1,2,3,4,5,6.3737银行选址银行选址P209l俄亥俄信托公司（俄亥俄信托公司（OhioTrustCompany）希望）希望在俄亥俄西北部在俄亥俄西北部20个县进行选址，该地区还没个县进行选址，该地区还没有首席业务处（有首席业务处（PrincipalPlaceofbusinessPPB）。根据俄亥俄州的银行法，如果金融企）。根据俄亥俄州的银行法，如果金融企业在任何一个县设立业在任何一个县设立PPB，就可以在该县及其，就可以在该县及其比邻的县设立分支机构。比邻的县设立分支机构。俄

21、亥俄信托公司想知俄亥俄信托公司想知道在那些县设立道在那些县设立PPB会使其数量最少？会使其数量最少？3838表表表表 俄亥俄信托公司考虑的各县邻居俄亥俄信托公司考虑的各县邻居俄亥俄信托公司考虑的各县邻居俄亥俄信托公司考虑的各县邻居 考考虑虑的的县县邻县邻县的数字代号的数字代号考考虑虑的的县县邻县邻县的数字代号的数字代号12，12，16118，10，13，14，15，18，19，2021，3，12121，2，3，10，13，1632，4，9，10，12，13133，10，11，12，15，1643，5，7，91411，15，2054，6，71511，13，14，1665，7，17161，12，1

22、3，1574，5，6，8，9，17，18176，7，1887，9，10，11，18187，8，11，17，1993，4，7，8，101911，18，20103，8，9，11，12，132011，14，193939整数规划选址模型整数规划选址模型使用使用OR软件对该问题进行求解，我们得出软件对该问题进行求解，我们得出需要需要3个个PPB，他们应分别选址在，他们应分别选址在7、11、12。4040例例 红光服装厂可生产三种服装：西服、衬衫和红光服装厂可生产三种服装：西服、衬衫和羽绒服。生产不同种类的服装要使用不同的设备，羽绒服。生产不同种类的服装要使用不同的设备，红光服装厂可从专业租赁公司租用这些

23、设备。设红光服装厂可从专业租赁公司租用这些设备。设备租金和其他经济参数见下表：假定市场需求不备租金和其他经济参数见下表：假定市场需求不成问题，服装厂每月可用工人工时为成问题，服装厂每月可用工人工时为2000小时，小时，该厂如何安排生产可使每月的利润最大？该厂如何安排生产可使每月的利润最大？4141表表 产品经济参数产品经济参数 序序号号服装服装种类种类设备设备租金租金元元生生产产成本成本元元/件件销销售售价格价格元元/件件人人工工工工时时小小 时时/件件设设备备工工时时小小 时时/件件设设 备备可可 用用工时工时123西服西服衬衫衬衫羽羽 绒绒服服50002000300028030200400

24、4030051430523003003004242解解:1.目标函数是什么目标函数是什么?每月的利润最大，每月的利润最大，=收入收入-租金租金-生产成本。生产成本。2.决策变量是什么决策变量是什么?租用与不租租用与不租用设备用设备?与租用后产品生产量是多少与租用后产品生产量是多少?3.约束条件是什么约束条件是什么?).人工工时只有人工工时只有2000小时小时.).设备工时约束设备工时约束.43Yj=租用第租用第j种设备种设备;Xj=第种产品生产量。第种产品生产量。MaxZ=400X1+40X2+300X3-280X1-30X2-200X3-5000Y1-2000Y2-3000Y3s.t.5X1

25、+X2+4X320003X1300Y10.5X2300y22X3300Y3Xj0,且为整数且为整数,j=1,2,3.Yj=0或或1,j=1,2,34444案例案例1 课本出版课本出版P222整数规划模型整数规划模型4545课本出版计算结果课本出版计算结果l现状优化结果 x2=x5=x6=1，预期销售量 73,000 copies.l1）Susan：优化结果 x2=x8=1，预期销售量 80,000 copies.l 2）Monica：优化结果 x2=x5=x8=1，预期销售量 105,000 copies.l3）由于上述结果均为出版修订本教材，长期看对公司发展不利，故可增加约束至少出版1本新书。4646下次课内容下次课内容 P17 整数规划作业整数规划作业 4.44.6建模，并用建模，并用MS6.0计算计算第九章第九章网络模型网络模型哥尼斯堡七桥问题哥尼斯堡七桥问题最小树问题最小树问题最短路问题最短路问题最大流问题最大流问题