chapter 3 IP(1).ppt

第3讲 整数规划(Integer Programming,IP),整数规划（Integer Programming）主要是指整数线性规划。一个线性规划问题，如果要求部分决策变量为整数，则构成一个整数规划问题。所有变量都要求为整数的称为纯整数规划（Pure Integer Programming）或称全整数规划（All integer Programming）；仅有一部分变量要求为整数的称为混合整数规划（Mixed Integer Programming）；有的变量限制其取值只能为0或1，这类特殊的整数规划称为01规划(0-1 Integer Programming)。,整数规划的有关概念,一、整数规划问题 例4.1 某工厂生产甲、乙两种设备，已知生产这两种设备需要消耗材料A、材料B，有关数据如下，问这两种设备各生产多少使工厂利润最大？,第一节 整数规划问题及其数学模型,解：设生产甲、乙这两种设备的数量分别为x1、x2，由于是设备台数，则其变量都要求为整数，建立模型如下：,Maxz=3x1+2x22x1+3x214x1+0.5x24.5x1、x20,且为整数,要求该模型的解，不考虑整数约束条件，用单纯形法对相应线性规划求解，其最优解为：x13.25 x22.5 max z14.75,凑整得到的（4，2）不在可行域范围内。（3，2）点尽管在可行域内，但没有使目标达到极大化。（4，1）使目标函数达到最大，即z14。,二、整数规划数学模型的一般形式,由上述例子可得出整数规划数学模型的一般形式：Max z=CX AX=b X0,且为整数或部分为整数若称该整数规划问题为原问题，则线性规划问题：Max z=CX AX=b X0为原问题对应的松驰问题（LP Relaxation)。,显然，原问题与松弛问题有如下关系：松弛问题可行域包含原问题可行域；若两者都有最优解，则松弛问题最优解大于原问题最优解；若松弛问题最优解为整数解，则该最优解就是原问题最优解。,整数规划常用的解法有分枝定界法和割平面法，它们适用于解纯整数规划问题和混合整数规划问题。一、分枝定界法 基本思想二、割平面法 基本思想三、整数规划的计算机解法 计算机求解举例,第二节 整数规划的解法,第三节 01整数规划,一、01整数规划模型01整数规划在实际中应用较多。因为实际问题中经常碰到大量的决策问题，要求回答“是否”或“有无”问题，这类问题可以借助整数规划中的01整数变量，使许多复杂的、困难的问题相对变得简单。01变量一般可表示为：,01整数规划的数学模型可表示为：,第三节 01整数规划,二、01整数规划求解01整数规划的求解方法有穷举法、隐枚举法和分枝定界法.隐枚举法求解举例,解：（1）先用试探的方法找出一个初始可行解，如x1x20，x31。满足约束条件，选其作为初始可行解，目标函数z02。（2）附加过滤条件 以目标函数作为过滤约束：4x13x22x3=2原模型变为：,（3）求解 求解过程如表46所示。,一、相互排斥的计划(Mutually exclusive planning)例4.6 某公司拟在市东、西、南三区中建立门市部，有例7个点Ai（i1，2，7）可供选择，要求满足以下条件：1)在东区，在A1，A2，A3三个点中至多选两个；2)在西区，A4，A5两个点中至少选一个；3)在南区，A6，A7两个点为互斥点。4)选A2点必选A5点。若Ai点投资为bi万元，每年可获利润为ci万元，投资总额为B万元，试建立利润最大化的01规划模型。,第四节 01整数规划应用(Applications),解：设决策变量为,建立01规划模型如下：,例4.7 某产品有A1和A2两种型号，需要经过B1、B2、B3三道工序，单位工时和利润、各工序每周工时限制见表所示，问工厂如何安排生产，才能使总利润最大？（B3工序有两种加工方式B31和B32，产品为整数）。,二、互排斥的约束条件(Mutually exclusive constraints),解：设A1、A2产品的生产数量分别为x1、x2件，在不考虑B31和B32相互排斥的情况下，问题的数学模型为,工序B3只能从两种加工方式中选择一种，那么约束条件（1）和（2）就成为相互排斥的约束条件。为了统一在一个问题中，引入0-1变量,则数学模型为,一般地，在建立数学模型时，若需从p个约束条件中选择q个约束条件，则可以引入p个0-1变量,那么约束条件组,例4.8 某公司制造小、中、大三种尺寸的容器，所需资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如下表所示：不考虑固定费用，小、中、大号容器每售出一个其利润分别为4万元、5万元、6万元，可使用的金属板有500吨，劳动力有300人/月，机器有100台/月，另外若生产，不管每种容器生产多少，都需要支付一笔固定费用：小号为100万元，中号为150万元，大号为200万元。问如何制定生产计划使获得的利润对大？,三、固定成本问题(Fixed cost problem),解：设x1、x2、x3分别为小号容器、中号容器、大号容器的生产数量。不考虑固定费用，则问题的数学模型为,若考虑固定费用就必须引入01变量：,则该问题的数学模型为,例4.9 某城市消防队布点问题。该城市共有6个区，每个区都可以建消防站，市政府希望设置的消防站最少，但必须满足在城市任何地区发生火警时，消防车要在15 分钟内赶到现场。据实地测定，各区之间消防车行驶的时间见表49，请帮助该市制定一个布点最少的计划。,四、布点问题(Location Problem),表49 消防车在各区间行驶时间表 单位：min,本问题的约束方程是要保证每个地区都有一个消防站在15分钟行程内。如地区1，由表49可知，在地区1及地区2内设消防站都能达到此要求，即x1x21因此本问题的数学模型为：min zx1x2x3x4x5x6 x1x2 1 x1x2 x6 1 x3x4 1 x3x4x5 1 x4x5x6 1 x2 x5x6 1 xi1或0（i1，6）,解：引入01变量xi作决策变量，令,案例8.3.1（P275）资金预算（Capital budgeting problem）冰冷电冰箱公司正在考虑4种投资方案，有关数据如下表。问题：选择投资项目使总现值最大。,五、其他案例（数据、模型与决策）,引入4个0-1变量：P=1，工厂扩建通过；P=0，则不选工厂扩建；W=1，仓库扩建通过；P=0，则不选仓库扩建；M=1，机器更新通过；P=0，则不选机器更新；R=1，新产品研究通过；P=0，则不选新产品研究；则问题的0-1规划数学模型为：Max Z=90P+40W+10M+37R 15P+10W+10M+15R 40 20P+15W+10R 50 20P+20W+10R 40 15P+5W+4M+10R 50 P，W，M，R=0，1,案例8.3.2（P276）固定成本（Fixed cost problem）生产三种产品需要用三种原料，生产这些产品需要配置成本，若不需要，则无配置成本。有关数据如下表。问题：各产品应生产多少总利润最大。,设：F=添加剂生产量；S=溶剂生产量；C=清洁剂生产量；引入3个0-1变量：若生产添加剂，SF=1，否则SF=0；若生产溶剂，SS=1，否则SS=0；若生产清洁剂，SC=1，否则SC=0；则问题的0-1规划数学模型为：Max Z=40F+30S+50C 200SF 50SS 400SC 0.4F+0.5S+0.6C 20 0.2S+0.1C 5 0.6F+0.3S+0.3C 21 F-50SF 0 S-25SS 0 C-40SC 0 F,S,C 0,SF,SS,SC=0,1,案例8.3.3(P277)分销系统设计(Distribution system design problem)马丁贝克公司在圣路易斯经营一家生产量为30000件产品的工厂。产品被运输到位于波士顿、亚特兰大和休斯敦的地区分销中心。由于预期将有需求增长,公司计划在底特律、托来多、丹佛和堪萨斯中一个或多个城市建立新工厂以增加生产力。有关数据如下表。问题：各选择哪个或哪些工厂使总成本最小。,在不考虑固定成本和生产地选择的情况下，此问题是一个运输问题.若用xij表示从产地i到分销中心j的运量,则其数学模型为：Minf=5x11+2x12+3x13+4x21+3x22+4x23+4x52+3x53 x11+x12+x13 10 x21+x22+x23 20 x31+x32+x33 30 x41+x42+x43 40 x51+x52+x53 30 x11+x21+x31+x41+x51=30 x12+x22+x32+x42+x52=20 x13+x23+x33+x43+x53=20 xij0,所有i,j,若考虑固定成本和生产地的选择需要引入0-1变量.若在底特律建立工厂,y1=1,否则 y1=0;若在托来多建立工厂,y2=1,否则 y2=0;若在丹佛建立工厂,y3=1,否则 y3=0;若在堪萨斯建立工厂,y4=1,否则 y4=0;若用xij表示从产地i到分销中心j的运量,则其数学模型为：minf=5x11+2x12+3x13+4x52+3x53+175y1+300y2+375y3+500y4 x11+x12+x13-10y1 0 x21+x22+x23-20y2 0 x31+x32+x33-30y3 0 x41+x42+x43-40y4 0 x51+x52+x53 30 x11+x21+x31+x41+x51=30 x12+x22+x32+x42+x52=20 x13+x23+x33+x43+x53=20 xij0,所有i,j;y1,y2,y3,y4=0,1,案例8.3.4（P281）银行选址（Location problem）俄亥俄州信托投资公司的远期计划正在考虑在俄亥俄州东北部20个郡的地区开展业务.该投资公司目前在这20个郡还没有主营业处.根据该州法律:如果一个银行在任一个郡建立主营业处,即可在该郡及所有毗邻郡建设分行.该计划的第一步是：投资公司需要确定为了在这20个郡完全营业一共要建立的主营业处的最小数目.,若在第i郡建立主营业处,则xi=1,否则 xi=0 这样,目标函数为:min z=x1+x2+x20 每个郡要满足一个约束条件:该郡或与该郡相毗邻的郡中至少有一个需要建立主营业处.例如第10个郡有:x3+x9+x8+x11x10+x12+x13 1因此,该问题的数学模型为:min z=x1+x2+x20 x1+x2+x12+x16 1(第1个郡)x1+x2+x3+x12+x16 1(第2个郡)x2+x3+x4+x9+x10+x12+x13 1(第3个郡).x11+x14+x19+x20 1(第20个郡)xi=0,1 I=1,2,20,案例8.3.5（P283）产品设计和市场份额的优化（Product design and market share optimization problem）,决策变量:xij=1,表示赛伦pizza 在属性j上选择i,否则xij=0 yk=1,顾客i选择赛伦pizza,否则yk=0这样,目标函数为:选择赛伦pizza的顾客数最大,即 max z=y1+y2+y3+y4+y5+y6+y7+y8约束条件:(1)若果顾客i选择赛伦,则他认为赛伦的效用比他目前中意的品牌的效用还要大.例如第1个顾客,目前中意的pizza是安东尼奥,效用为52,因此:11x11+2x21+6x12+7x22+3x13+17x23+26x14+27x24+8x34 1+52y1(2)赛伦在每中属性中只能选择一种,即 x11+x21=1 x12+x22=1 x13+x23=1 x14+x24+x34=1,因此,该问题的数学模型为：max z=y1+y2+y3+y4+y5+y6+y7+y8 11x11+2x21+6x12+7x22+3x13+17x23+26x14+27x24+8x34 1+52y1 11x11+7x21+15x12+17x22+16x13+26x23+14x14+1x24+10 x34 1+58y2 7x11+5x21+8x12+14x22+16x13+7x23+29x14+16x24+19x34 1+56y3 13x11+20 x21+20 x12+17x22+17x13+14x23+25x14+29x24+10 x34 1+83y4 2x11+8x21+6x12+11x22+30 x13+20 x23+15x14+5x24+12x34 1+58y5 12x11+17x21+11x12+9x22+2x13+30 x23+22x14+12x24+20 x34 1+70y6 9x11+19x21+12x12+16x22+16x13+25x23+30 x14+23x24+19x34 1+79y7 5x11+9x21+4x12+14x22+23x13+16x23+16x14+30 x24+3x34 1+59y8 x11+x21=1 x12+x22=1 x13+x23=1 x14+x24+x34=1 xij，yk=0，1 对于所有i，j，k求解结果：x11=x22=x23=x14=1，y1=y2=y3=y6=y7=1,五、指派问题（Assignment problem）（P223）指派问题是一种特殊的整数规划问题。在实践中经常会遇到一种问题：某单位有m项任务要m个人去完成（每人只完成一项工作），在分配过程中要充分考虑各人的知识、能力、经验等，应如何分配才能使工作效率最高或消耗的资源最少？这类问题就属于指派问题。引入01变量xij,案例：福尔市场营销调查指派问题（P223）福尔市场营销调查公司有3个新客户需要进行市场调查，目前正好有3个人没有其他工作，由于他们的对不同市场的经验和能力不同，估计他们完成不同任务所需时间如下表。公司面临的问题是如何给每个客户指派一个项目主管（代理商），使他们完成市场调查的时间最短。,设 xij=1表示指派主管i完成第j项市场调查，否则 xij=0则问题的数学模型为：min f=10 x11+15x12+9x13+9x21+18x22+5x23+6x31+14x32+3x33 x11+x12+x13=1 x21+x22+x23=1 x31+x32+x33=1 x11+x21+x31=1 x12+x22+x32=1 x13+x23+x33=1 xij0，i=1，2，3；j=1，2，3,1.整数规划的提出是解决实际的需要;2.0-1 变量的引入使得整数规划的应用非常广泛;3.整数规划的求解对计算机软件要求较篙.,整数规划小结:,第四章 结束,