第四章规划问题

第四章第四章规划问题规划问题整数规划整数规划（IntegerProgramming）主要是指整数线）主要是指整数线性规划。一个线性规划问题，如果要求部分决策变量性规划。一个线性规划问题，如果要求部分决策变量为整数，则构成一个整数规划问题。为整数，则构成一个整数规划问题。所有变量都要求为整数的称为所有变量都要求为整数的称为纯整数规划纯整数规划（PureIntegerProgramming）或称）或称全整数规划全整数规划（AllintegerProgramming）；）；仅有一部分变量要求为整数的称为仅有一部分变量要求为整数的称为混合整数规划混合整数规划（MixedIntegerProgramming）；）；有的变量限制其取值只能为有的变量限制其取值只能为0或或1，这类特殊的整数规，这类特殊的整数规划称为划称为01规划规划(0-1IntegerProgramming)。整数规划的有关概念整数规划的有关概念一、整数规划问题一、整数规划问题例例4.1某工厂生产甲、乙两种设备，已知生产这两种设某工厂生产甲、乙两种设备，已知生产这两种设备需要消耗材料备需要消耗材料A、材料、材料B，有关数据如下，问这两种，有关数据如下，问这两种设备各生产多少使工厂利润最大？设备各生产多少使工厂利润最大？设备设备材材料料甲甲乙乙资源限量资源限量材料材料A（kg）2314材料材料B（kg）10.54.5利润（元利润（元/件）件）32第一节第一节 整数规划问题及其数学模型整数规划问题及其数学模型解：解：设生产甲、乙这两种设备的数量分别为设生产甲、乙这两种设备的数量分别为x1、x2，由于是设备台数，则其变量都要求为整数，建立模由于是设备台数，则其变量都要求为整数，建立模型如下：型如下：Maxz=3x1+2x22x1+3x214x1+0.5x24.5x1、x20,且为整数且为整数要求该模型的解，不考虑整数约束条件，用单纯形法要求该模型的解，不考虑整数约束条件，用单纯形法对相应线性规划求解，其最优解为：对相应线性规划求解，其最优解为：x13.25x22.5maxz14.75凑整得到的凑整得到的（4，2）不在可行域范围内。不在可行域范围内。（3，2）点尽管在可行域内，但没有使目标达到极大化。点尽管在可行域内，但没有使目标达到极大化。（4，1）使目标函数达到最大，即使目标函数达到最大，即z14。二、整数规划数学模型的一般形式二、整数规划数学模型的一般形式由上述例子可得出整数规划数由上述例子可得出整数规划数学模型的一般形式：学模型的一般形式：Maxz=CXAX=bX0,且为整数或部分且为整数或部分为整数为整数若称该整数规划问题为若称该整数规划问题为原问题原问题，则线性规划问题：则线性规划问题：Maxz=CXAX=bX0为原问题对应的为原问题对应的松驰问题松驰问题（LPRelaxation)。显然，原问题与松弛问显然，原问题与松弛问题有如下关系：题有如下关系：1)松弛问题可行域包含原松弛问题可行域包含原问题可行域；问题可行域；2)若两者都有最优解，则若两者都有最优解，则松弛问题最优解大于原松弛问题最优解大于原问题最优解；问题最优解；3)若松弛问题最优解为整若松弛问题最优解为整数解，则该最优解就是数解，则该最优解就是原问题最优解。原问题最优解。整数规划常用的解法有分枝定界法和割平面法，它整数规划常用的解法有分枝定界法和割平面法，它们适用于解纯整数规划问题和混合整数规划问题。们适用于解纯整数规划问题和混合整数规划问题。一、分枝定界法一、分枝定界法 基本思想基本思想二、割平面法二、割平面法 基本思想基本思想三、整数规划的计算机解法三、整数规划的计算机解法 计算机求解举例计算机求解举例第二节第二节 整数规划的解法整数规划的解法第三节第三节 0 01 1整数规划整数规划一、一、0 01 1整数规划模型整数规划模型01整数规划在实际中应用较多。因为实际问题中经整数规划在实际中应用较多。因为实际问题中经常碰到大量的决策问题，要求回答常碰到大量的决策问题，要求回答“是否是否”或或“有无有无”问题，这类问题可以借助整数规划中的问题，这类问题可以借助整数规划中的01整数变量，整数变量，使许多复杂的、困难的问题相对变得简单。使许多复杂的、困难的问题相对变得简单。01变量一般可表示为：变量一般可表示为：01整数规划的数学模型可表示为：整数规划的数学模型可表示为：第三节第三节 0 01 1整数规划整数规划二、二、0 01 1整数规划求解整数规划求解01整数规划的求解方法有穷举法、隐枚举法和分枝整数规划的求解方法有穷举法、隐枚举法和分枝定界法定界法.隐枚举法求解举例隐枚举法求解举例解：解：（1）先用试探的方法找出一个初始可行解，如）先用试探的方法找出一个初始可行解，如x1x20，x31。满足约束条件，选其作为初始可行。满足约束条件，选其作为初始可行解，目标函数解，目标函数z02。（2）附加过滤条件）附加过滤条件以目标函数作为过滤约束：以目标函数作为过滤约束：4x13x22x3=2原模型变为：原模型变为：（3 3）求解）求解 求解过程如表求解过程如表4 46 6所示。所示。点点过滤条件过滤条件约束约束z值值4x13x22x32（0，0，0）T（0，0，1）T2（0，1，0）T（0，1，1）T54x13x22x35（1，0，0）T（1，0，1）T（1，1，0）T74x13x22x37（1，1，1）T9一、相互排斥的计划一、相互排斥的计划(Mutuallyexclusiveplanning)例例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，产品为整数）。，产品为整数）。二、互排斥的约束条件二、互排斥的约束条件(Mutuallyexclusiveconstraints)工序工序型号型号B1B2B3利润利润（元（元/件）件）B31B32A1A20.30.70.20.10.30.50.20.42540每周工时每周工时(小时小时/月月)250100150120解：设解：设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万元。问如何制定生产计万元。问如何制定生产计划使获得的利润对大？划使获得的利润对大？三、固定成本问题三、固定成本问题(Fixedcostproblem)解解：设：设x1、x2、x3分别为小号容器、中号容器、大号容器分别为小号容器、中号容器、大号容器的生产数量。不考虑固定费用，则问题的数学模型为的生产数量。不考虑固定费用，则问题的数学模型为资源资源小号容器小号容器中号容器中号容器大号容器大号容器金属板（吨）金属板（吨）248劳动力（人劳动力（人/月）月）234机器设备（台机器设备（台/月）月）123若考虑固定费用就必须引入若考虑固定费用就必须引入01变量：变量：则该问题的数学模型为则该问题的数学模型为例例4.9某城市消防队布点问题。该城市共有某城市消防队布点问题。该城市共有6个区，每个区都可以建消个区，每个区都可以建消防站，市政府希望设置的消防站最少，但必须满足在城市任何地区发防站，市政府希望设置的消防站最少，但必须满足在城市任何地区发生火警时，消防车要在生火警时，消防车要在15分钟内赶到现场。据实地测定，各区之间消分钟内赶到现场。据实地测定，各区之间消防车行驶的时间见表防车行驶的时间见表49，请帮助该市制定一个布点最少的计划。，请帮助该市制定一个布点最少的计划。地区地区1地区地区2地区地区3地区地区4地区地区5地区地区6地区地区101016282720地区地区210024321710地区地区316240122721地区地区428321201525地区地区527172715014地区地区620102125140四、布点问题四、布点问题 (LocationProblem)表表49 消防车在各区间行驶时间表消防车在各区间行驶时间表 单位：单位：min本问题的约束方程是要保证每个地区都有一个消防站本问题的约束方程是要保证每个地区都有一个消防站在在15分钟行程内。如地区分钟行程内。如地区1，由表，由表49可知，在地区可知，在地区1及地区及地区2内设消防站都能达到此要求，即内设消防站都能达到此要求，即x1x21因此本问题的数学模型为：因此本问题的数学模型为：minzx1x2x3x4x5x6x1x21x1x2x61x3x41x3x4x51x4x5x61x2x5x61xi1或或0（i1，6）解：引入解：引入01变量变量xi作决策变量，令作决策变量，令资金预算（资金预算（Capitalbudgetingproblem）冰冷电冰箱公司正在考虑冰冷电冰箱公司正在考虑4种投资方案，有关数据如下表。种投资方案，有关数据如下表。问题：问题：选择投资项目使总现值最大选择投资项目使总现值最大。五、其他案例五、其他案例冰冷电冰箱公司各投资项目冰冷电冰箱公司各投资项目现值估算、资金需求和现值估算、资金需求和4年内的资产（单位：千美元）年内的资产（单位：千美元）项目项目工厂工厂扩张扩张仓库仓库扩张扩张新机器新机器新产品新产品研究研究总可用总可用资金资金现值现值第第1年资金年资金第第2年资金年资金第第3年资金年资金第第4年资金年资金901520201540101520510104371510101040504035引入引入4个个0-1变量：变量：P=1，工厂扩建通过；，工厂扩建通过；P=0，则不选工厂扩建；，则不选工厂扩建；W=1，仓库扩建通过；，仓库扩建通过；P=0，则不选仓库扩建；，则不选仓库扩建；M=1，机器更新通过；，机器更新通过；P=0，则不选机器更新；，则不选机器更新；R=1，新产品研究通过；，新产品研究通过；P=0，则不选新产品研究；，则不选新产品研究；则问题的则问题的0-1规划数学模型为：规划数学模型为：MaxZ=90P+40W+10M+37R15P+10W+10M+15R4020P+15W+10R5020P+20W+10R4015P+5W+4M+10R50P，W，M，R=0，1固定成本（固定成本（Fixedcostproblem）生产三种产品需要用三种原料，生产这些产品需要配置生产三种产品需要用三种原料，生产这些产品需要配置成本，若不需要，则无配置成本。有关数据如下表。成本，若不需要，则无配置成本。有关数据如下表。问题：问题：各产品应生产多少总利润最大各产品应生产多少总利润最大。生生产产数数据据表表添加剂添加剂溶剂溶剂清洁剂清洁剂原料数量原料数量原料原料1原料原料2原料原料30.40.60.50.20.30.60.10.320521单位利润单位利润($)403050配置费用配置费用($)20050400最大产量最大产量(t)502540设：设：F=添加剂生产量；添加剂生产量；S=溶剂生产量；溶剂生产量；C=清洁剂生产量；清洁剂生产量；引入引入3个个0-1变量：变量：若生产添加剂，若生产添加剂，SF=1，否则，否则SF=0；若生产溶剂，若生产溶剂，SS=1，否则，否则SS=0；若生产清洁剂，若生产清洁剂，SC=1，否则，否则SC=0；则问题的则问题的0-1规划数学模型为：规划数学模型为：MaxZ=40F+30S+50C200SF50SS400SC0.4F+0.5S+0.6C200.2S+0.1C50.6F+0.3S+0.3C21F-50SF0S-25SS0C-40SC0F,S,C0,SF,SS,SC=0,1分销系统设计分销系统设计(Distributionsystemdesignproblem)马丁贝克公司在圣路易斯经营一家生产量为马丁贝克公司在圣路易斯经营一家生产量为30000件产品的工厂。件产品的工厂。产品被运输到位于波士顿、亚特兰大和休斯敦的地区分销中心。由于产品被运输到位于波士顿、亚特兰大和休斯敦的地区分销中心。由于预期将有需求增长预期将有需求增长,公司计划在底特律、托来多、丹佛和堪萨斯中一公司计划在底特律、托来多、丹佛和堪萨斯中一个或多个城市建立新工厂以增加生产力。有关数据如下表。个或多个城市建立新工厂以增加生产力。有关数据如下表。问题：问题：各选择哪个或哪些工厂使总成本最小。各选择哪个或哪些工厂使总成本最小。生生产产数数据据表表分销中心分销中心生产地生产地1波士顿波士顿2亚特兰大亚特兰大3休斯敦休斯敦生产能力生产能力（千件）（千件）年固定成年固定成本本(千千$)1底特律底特律2托来多托来多3丹丹佛佛4堪萨斯堪萨斯5圣路易斯圣路易斯54910823744345231020304030175300375500需求量需求量(千件千件)302020在不考虑固定成本和生产地选择的情况下，此问题是一个在不考虑固定成本和生产地选择的情况下，此问题是一个运输问题运输问题.若用若用xij表示从产地表示从产地i到分销中心到分销中心j的运量的运量,则其数学模型为：则其数学模型为：Minf=5x11+2x12+3x13+4x21+3x22+4x23+4x52+3x53x11+x12+x1310 x21+x22+x2320 x31+x32+x3330 x41+x42+x4340 x51+x52+x5330 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+500y4x11+x12+x13-10y10 x21+x22+x23-20y20 x31+x32+x33-30y30 x41+x42+x43-40y40 x51+x52+x5330 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银行选址（银行选址（Locationproblem）俄亥俄州信托投资公司的远期计划正在考虑在俄亥俄州东北部俄亥俄州信托投资公司的远期计划正在考虑在俄亥俄州东北部20个郡的地区开展业务个郡的地区开展业务.该投资公司目前在这该投资公司目前在这20个郡还没有主营业处个郡还没有主营业处.根据该州法律根据该州法律:如果一个银行在任一个郡建立主营业处如果一个银行在任一个郡建立主营业处,即可在该即可在该郡及所有毗邻郡建设分行郡及所有毗邻郡建设分行.该计划的第一步是：投资公司需要确该计划的第一步是：投资公司需要确定为了在这定为了在这20个郡完全营业一共要建立的主营业处的最小数目个郡完全营业一共要建立的主营业处的最小数目.2019181787645911101314315122161若在第若在第i郡建立主营业处郡建立主营业处,则则xi=1,否则否则xi=0这样这样,目标函数为目标函数为:minz=x1+x2+x20每个郡要满足一个约束条件每个郡要满足一个约束条件:该郡或与该郡相毗邻的郡中至少有该郡或与该郡相毗邻的郡中至少有一个需要建立主营业处一个需要建立主营业处.例如第例如第10个郡有个郡有:x3+x9+x8+x11x10+x12+x131因此因此,该问题的数学模型为该问题的数学模型为:minz=x1+x2+x20 x1+x2+x12+x161(第第1个郡个郡)x1+x2+x3+x12+x161(第第2个郡个郡)x2+x3+x4+x9+x10+x12+x131(第第3个郡个郡).x11+x14+x19+x201(第第20个郡个郡)xi=0,1I=1,2,20产品设计和市场份额的优化（产品设计和市场份额的优化（Productdesignandmarketshareoptimizationproblem）顾顾客客面包皮面包皮奶酪奶酪调味品调味品香肠口味香肠口味顾客对现有品顾客对现有品牌的效用牌的效用薄薄厚厚意意大大利利混混合合细细滑滑橙块橙块果酱果酱清清谈谈中中等等辣辣安东安东尼奥尼奥国王国王123456781111713212952752081719961582061112471714171191614316161730216231726714203025162614292515223016271162951223308101910122019352493683397079594758567258457158决策变量决策变量:xij=1,表示赛伦表示赛伦pizza在属性在属性j上选择上选择i,否则否则xij=0yk=1,顾客顾客i选择赛伦选择赛伦pizza,否则否则yk=0这样这样,目标函数为目标函数为:选择赛伦选择赛伦pizza的顾客数最大的顾客数最大,即即maxz=y1+y2+y3+y4+y5+y6+y7+y8约束条件约束条件:(1)若果顾客若果顾客i选择赛伦选择赛伦,则他认为赛伦的效用比他目前中意的品牌则他认为赛伦的效用比他目前中意的品牌的效用还要大的效用还要大.例如第例如第1个顾客个顾客,目前中意的目前中意的pizza是安东尼奥是安东尼奥,效效用为用为52,因此因此:11x11+2x21+6x12+7x22+3x13+17x23+26x14+27x24+8x341+52y1(2)赛伦在每中属性中只能选择一种赛伦在每中属性中只能选择一种,即即x11+x21=1x12+x22=1x13+x23=1x14+x24+x34=1因此因此,该问题的数学模型为：该问题的数学模型为：maxz=y1+y2+y3+y4+y5+y6+y7+y811x11+2x21+6x12+7x22+3x13+17x23+26x14+27x24+8x341+52y111x11+7x21+15x12+17x22+16x13+26x23+14x14+1x24+10 x341+58y27x11+5x21+8x12+14x22+16x13+7x23+29x14+16x24+19x341+56y313x11+20 x21+20 x12+17x22+17x13+14x23+25x14+29x24+10 x341+83y42x11+8x21+6x12+11x22+30 x13+20 x23+15x14+5x24+12x341+58y512x11+17x21+11x12+9x22+2x13+30 x23+22x14+12x24+20 x341+70y69x11+19x21+12x12+16x22+16x13+25x23+30 x14+23x24+19x341+79y75x11+9x21+4x12+14x22+23x13+16x23+16x14+30 x24+3x341+59y8x11+x21=1x12+x22=1x13+x23=1x14+x24+x34=1xij，yk=0，1对于所有对于所有i，j，k求解结果：求解结果：x11=x22=x23=x14=1，y1=y2=y3=y6=y7=1五、指派问题（五、指派问题（Assignmentproblem）指派问题是一种特殊的整数规划问题。在实践中经常会遇到一种指派问题是一种特殊的整数规划问题。在实践中经常会遇到一种问题：某单位有问题：某单位有m项任务要项任务要m个人去完成（每人只完成一项工作）个人去完成（每人只完成一项工作），在分配过程中要充分考虑各人的知识、能力、经验等，应如何，在分配过程中要充分考虑各人的知识、能力、经验等，应如何分配才能使工作效率最高或消耗的资源最少？这类问题就属于指分配才能使工作效率最高或消耗的资源最少？这类问题就属于指派问题。引入派问题。引入01变量变量xij案例：福尔市场营销调查指派问题案例：福尔市场营销调查指派问题福尔市场营销调查公司有福尔市场营销调查公司有3个新客户需要进行市场调查，个新客户需要进行市场调查，目前正好有目前正好有3个人没有其他工作，由于他们的对不同市场个人没有其他工作，由于他们的对不同市场的经验和能力不同，估计他们完成不同任务所需时间如的经验和能力不同，估计他们完成不同任务所需时间如下表。公司面临的问题是如何给每个客户指派一个项目下表。公司面临的问题是如何给每个客户指派一个项目主管（代理商），使他们完成市场调查的时间最短主管（代理商），使他们完成市场调查的时间最短。预计完成时间预计完成时间客户客户项目主管项目主管1231231096151814953设设xij=1表示指派主管表示指派主管i完成第完成第j项市场调查，项市场调查，否则否则xij=0则问题的数学模型为：则问题的数学模型为：minf=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=1xij0，i=1，2，3；j=1，2，3 1.整数规划的提出是解决实际的需要整数规划的提出是解决实际的需要;2.0-1 变量的引入使得整数规划的应用非常广泛变量的引入使得整数规划的应用非常广泛;3.整数规划的求解对计算机软件要求较高整数规划的求解对计算机软件要求较高.整数规划小结整数规划小结:第四章第四章 结束结束