第四章 规划问题

1、第四章第四章 整数规划整数规划(integer programming, ip) 整数规划整数规划（integer programming）主要是指整数线）主要是指整数线性规划。一个线性规划问题，如果要求部分决策变量性规划。一个线性规划问题，如果要求部分决策变量为整数，则构成一个整数规划问题。为整数，则构成一个整数规划问题。 所有变量都要求为整数的称为所有变量都要求为整数的称为纯整数规划纯整数规划（pure integer programming）或称）或称全整数规划全整数规划（all integer programming）；）； 仅有一部分变量要求为整数的称为仅有一部分变量要求为整数的称为

2、混合整数规划混合整数规划（mixed integer programming）；）； 有的变量限制其取值只能为有的变量限制其取值只能为0或或1，这类特殊的整数规，这类特殊的整数规划称为划称为01规划规划(0-1 integer programming )。整数规划的有关概念整数规划的有关概念一、整数规划问题一、整数规划问题 例例4.1 某工厂生产甲、乙两种设备，已知生产这两种设某工厂生产甲、乙两种设备，已知生产这两种设备需要消耗材料备需要消耗材料a、材料、材料b，有关数据如下，问这两种，有关数据如下，问这两种设备各生产多少使工厂利润最大？设备各生产多少使工厂利润最大？设备设备材材 料料甲甲乙乙

3、资源限量资源限量材料材料a（kg）2314材料材料b（kg）10.54.5利润（元利润（元/件）件）32第一节第一节 整数规划问题及其数学模型整数规划问题及其数学模型解：解：设生产甲、乙这两种设备的数量分别为设生产甲、乙这两种设备的数量分别为x1、x2，由于是设备台数，则其变量都要求为整数，建立模由于是设备台数，则其变量都要求为整数，建立模型如下：型如下：maxz=3x1+2x22x1+3x214x1+0.5x24.5x1、x20, 且为整数且为整数要求该模型的解，不考虑整数约束条件，用单纯形法要求该模型的解，不考虑整数约束条件，用单纯形法对相应线性规划求解，其最优解为：对相应线性规划求解，其

4、最优解为： x13.25 x22.5 max z14.75凑整得到的凑整得到的（4，2）不在可行域范围内。不在可行域范围内。（3，2）点尽管在可行域内，但没有使目标达到极大化。点尽管在可行域内，但没有使目标达到极大化。（4，1）使目标函数达到最大，即使目标函数达到最大，即z14。二、整数规划数学模型的一般形式二、整数规划数学模型的一般形式由上述例子可得出整数规划数由上述例子可得出整数规划数学模型的一般形式：学模型的一般形式： max z =cx ax=b x0, 且为整数或部分且为整数或部分为整数为整数若称该整数规划问题为若称该整数规划问题为原问题原问题，则线性规划问题：则线性规划问题： ma

5、x z =cx ax=b x0为原问题对应的为原问题对应的松驰问题松驰问题（lp relaxation)。显然，原问题与松弛问显然，原问题与松弛问题有如下关系：题有如下关系：1)松弛问题可行域包含原松弛问题可行域包含原问题可行域；问题可行域；2)若两者都有最优解，则若两者都有最优解，则松弛问题最优解大于原松弛问题最优解大于原问题最优解；问题最优解；3)若松弛问题最优解为整若松弛问题最优解为整数解，则该最优解就是数解，则该最优解就是原问题最优解。原问题最优解。 整数规划常用的解法有分枝定界法和割平面法，它整数规划常用的解法有分枝定界法和割平面法，它们适用于解纯整数规划问题和混合整数规划问题。们适

6、用于解纯整数规划问题和混合整数规划问题。 一、分枝定界法一、分枝定界法 基本思想基本思想二、割平面法二、割平面法 基本思想基本思想三、整数规划的计算机解法三、整数规划的计算机解法 计算机求解举例计算机求解举例第二节第二节 整数规划的解法整数规划的解法第三节第三节 0 01 1整数规划整数规划 一、一、0 01 1整数规划模型整数规划模型 01整数规划在实际中应用较多。因为实际问题中经整数规划在实际中应用较多。因为实际问题中经常碰到大量的决策问题，要求回答常碰到大量的决策问题，要求回答“是否是否”或或“有有无无”问题，这类问题可以借助整数规划中的问题，这类问题可以借助整数规划中的01整整数变量，

7、使许多复杂的、困难的问题相对变得简单。数变量，使许多复杂的、困难的问题相对变得简单。 01变量一般可表示为：变量一般可表示为：为为无j jj jj j1 1x xx x= =0 0 x x是是 或或 有有否否 或或 01整数规划的数学模型可表示为：整数规划的数学模型可表示为：或njjj=1nijjij=1jmaxz =c xa x =b(i =1,2,m)s.tx = 01(j =1,2,n)第三节第三节 0 01 1整数规划整数规划二、二、0 01 1整数规划求解整数规划求解 01整数规划的求解方法有穷举法、隐枚举法和分枝整数规划的求解方法有穷举法、隐枚举法和分枝定界法定界法. 隐枚举法求解

8、举例隐枚举法求解举例或12312312323123m a x z = 4 x+ 3 x+ 2 x2 x- 5 x+ 3 x = 3s .tx+ x = 1x , x, x= 01 解：解：（1）先用试探的方法找出一个初始可行解）先用试探的方法找出一个初始可行解，如，如x1x20，x31。满足约束条件，选其作为初始可行。满足约束条件，选其作为初始可行解，目标函数解，目标函数z02。（2）附加过滤条件）附加过滤条件 以目标函数作为过滤约束：以目标函数作为过滤约束： 4x13x22x3 = 2 原模型变为：原模型变为：或123 12312323123123m a x z = 4 x+ 3 x+ 2

9、x2 x- 5 x+ 3 x = 3(2 )x+ x = 1(3 )4 x+ 3 x+ 2 x = 2(4 )x , x, x= 01（3 3）求解）求解 求解过程如表求解过程如表4 46 6所示。所示。点点过滤条件过滤条件约束约束z值值 4x13x22x32 （0，0，0）t （0，0，1）t 2（0，1，0）t （0，1，1）t 5 4x13x22x35 （1，0，0）t （1，0，1）t （1，1，0）t 7 4x13x22x37 （1，1，1）t 9一、相互排斥的计划一、相互排斥的计划(mutually exclusive planning)例例4.6 某公司拟在市东、西、南三区中建立

10、门市部，某公司拟在市东、西、南三区中建立门市部，有例有例7个个点点ai（i1，2，7）可供选择，要求满）可供选择，要求满足以下条件：足以下条件： 1) 在东区，在在东区，在a1，a2，a3三个点中至多选两个；三个点中至多选两个； 2) 在西区在西区，a4，a5两个点中至少选一个；两个点中至少选一个； 3) 在南区，在南区，a6，a7两个点为互斥点。两个点为互斥点。 4) 选选a2点必选点必选a5点。点。若若ai点投资点投资为为bi万元，每年可获利润万元，每年可获利润为为ci万元，投资万元，投资总额为总额为b万元，试建立利润最大化的万元，试建立利润最大化的01规划模型。规划模型。第四节 01整数

11、规划应用(applications)解：设决策变量为解：设决策变量为当点选当点选被被用用未未被被用用iii1,ax =i=1,2,.,70,a112277maxz =c x +c x +c x，或7iii=1123456725ib x =bx +x +x =1s.tx +x =1x - x = 0 x = 01, i =1,2,.,7建立建立01规划模型如下：规划模型如下： 例例4.7 某产品有某产品有a1和和a2两种型号，需要经过两种型号，需要经过b1、b2、b3三道工序，单位工时和利润、各工序每周工时限制见表三道工序，单位工时和利润、各工序每周工时限制见表所示，问工厂如何安排生产，才能使总

12、利润最大？（所示，问工厂如何安排生产，才能使总利润最大？（b3工序有两种加工方式工序有两种加工方式b31和和b32，产品为整数）。，产品为整数）。二、互排斥的约束条件二、互排斥的约束条件(mutually exclusive constraints) 工序工序型号型号b1b2b3利润利润（元（元/件）件）b31b32a1a20.30.70.20.10.30.50.20.42540每周工时每周工时(小时小时/月月)250100150120 解：设解：设a1、a2产品的生产数量分别为产品的生产数量分别为x1、x2件，在不件，在不考虑考虑b31和和b32相互排斥的情况下，问题的数学模型为相互排斥的情

13、况下，问题的数学模型为且为整数121212121212 maxz = 25x + 40 x0.3x +0.7x= 2500.2x +0.1x= 100s.t. 0.3x +0.5x= 150(1)0.2x +0.4x= 0, 工序工序b3只能从两种加工方式中选择一种，那么约束条件只能从两种加工方式中选择一种，那么约束条件（1）和（）和（2）就成为相互排斥的约束条件。为了统一在一）就成为相互排斥的约束条件。为了统一在一个问题中，引入个问题中，引入0-1变量变量采采用用加加工工方方式式不不采采用用加加工工方方式式33ii33i1,bby =i=1,20,bb且 为 整 数或121212121122

14、121212m axz = 25x+ 40 x0.3x+ 0.7x= 2500.2x+ 0.1x= 1000.3x+ 0.5x= 150 + m (1- y )s.t.0.2x+ 0.4x= 0,y , y= 01则数学模型为则数学模型为 一般地，在建立数学模型时，若需从一般地，在建立数学模型时，若需从p个约束条件个约束条件中选择中选择q个约束条件，则可以引入个约束条件，则可以引入p个个0-1变量变量选择个约选择个约若若第第束束若若不不第第束束i1,iy =i=1,.,p0,iijjiiij=1pii=1a x= b + m (1 - y )y= q那么约束条件组那么约束条件组 例例4.8 某

15、公司制造小、中、大三种尺寸的容器，所需某公司制造小、中、大三种尺寸的容器，所需资源为金属板、劳动力和机器设备，制造一个容器所资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如下表所示：不考虑固定费用，需的各种资源的数量如下表所示：不考虑固定费用，小、中、大号容器每售出一个其利润分别为小、中、大号容器每售出一个其利润分别为4万元、万元、5万元、万元、6万元，可使用的金属板有万元，可使用的金属板有500吨，劳动力有吨，劳动力有300人人/月，机器有月，机器有100台台/月，另外若生产，不管每种月，另外若生产，不管每种容器生产多少，都需要支付一笔固定费用：小号为容器生产多少，都需要支

16、付一笔固定费用：小号为100万元，中号为万元，中号为150万元，大号为万元，大号为200万元。问如何制定万元。问如何制定生产计划使获得的利润对大？生产计划使获得的利润对大？三、固定成本问题三、固定成本问题 (fixed cost problem)解解：设设x1、x2、x3分别为小号容器、中号容器、大号容器分别为小号容器、中号容器、大号容器的生产数量。不考虑固定费用，则问题的数学模型为的生产数量。不考虑固定费用，则问题的数学模型为123123123123123maxz = 4x +5x +6x2x + 4x +8x= 5002x +3x + 4x= 300s.t.x +2x +3x= 0资源资源

17、小号容器小号容器中号容器中号容器大号容器大号容器金属板（吨）金属板（吨）248劳动力（人劳动力（人/月）月）234机器设备（台机器设备（台/月）月）123若考虑固定费用就必须引入若考虑固定费用就必须引入01变量：变量：当产时当产时生生第第 种种容容器器即即不不生生第第 种种容容器器即即iii1,ix 0y =i=1,2,30,ix =0123123123123123112233123123m axz = 4x + 5x+ 6x- 100y - 150y- 200y2x + 4x+ 8x= 5002x + 3x+ 4x= 300 x + 2x+ 3x= 100 x - my= 0s.t.x- m

18、y= 0 x- my= 0y , y , y= 0or1则该问题的数学模型为则该问题的数学模型为 例例4.9 某城市消防队布点问题。该城市共有某城市消防队布点问题。该城市共有6个区，每个区都可以建消个区，每个区都可以建消防站，市政府希望设置的消防站最少，但必须满足在城市任何地区发防站，市政府希望设置的消防站最少，但必须满足在城市任何地区发生火警时，消防车要在生火警时，消防车要在15 分钟内赶到现场。据实地测定，各区之间消分钟内赶到现场。据实地测定，各区之间消防车行驶的时间见表防车行驶的时间见表49，请帮助该市制定一个布点最少的计划。，请帮助该市制定一个布点最少的计划。 地区地区1地区地区2地区

19、地区3地区地区4地区地区5地区地区6地区地区101016282720地区地区210024321710地区地区316240122721地区地区428321201525地区地区527172715014地区地区620102125140四、布点问题四、布点问题 (location problem)表表49 消防车在各区间行驶时间表消防车在各区间行驶时间表 单位：单位：min 本问题的约束方程是要保证每个地区都有一个消防站本问题的约束方程是要保证每个地区都有一个消防站在在15分钟行程内。如地区分钟行程内。如地区1，由表，由表49可知，在地区可知，在地区1及地区及地区2内设消防站都能达到此要求，即内设消防

20、站都能达到此要求，即x1x21 因此本问题的数学模型为：因此本问题的数学模型为： min zx1x2x3x4x5x6 x1x2 1 x1x2 x6 1 x3x4 1 x3x4x5 1 x4x5x6 1 x2 x5x6 1 xi1或或0 （i1，6）区 设区设表表示示在在地地消消防防站站表表示示在在地地不不消消防防站站i1,ix =i=1,2,.,60,i解：引入解：引入01变量变量xi作决策变量，令作决策变量，令资金预算（资金预算（capital budgeting problem） 冰冷电冰箱公司正在考虑冰冷电冰箱公司正在考虑4种投资方案，有关数据如下表。种投资方案，有关数据如下表。 问题：

21、问题：选择投资项目使总现值最大选择投资项目使总现值最大。五、其他案例五、其他案例冰冷电冰箱公司各投资项目冰冷电冰箱公司各投资项目现值估算、资金需求和现值估算、资金需求和4年内的资产（单位：千美元）年内的资产（单位：千美元）项目项目工厂工厂扩张扩张仓库仓库扩张扩张新机器新机器新产品新产品研究研究总可用总可用资金资金现值现值第第1年资金年资金第第2年资金年资金第第3年资金年资金第第4年资金年资金901520201540101520510104371510101040504035引入引入4个个0-1变量：变量： p=1，工厂扩建通过；，工厂扩建通过；p=0，则不选工厂扩建；，则不选工厂扩建； w=1

22、，仓库扩建通过；，仓库扩建通过；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固定成本固定成本（fixed cost problem） 生产三种产品需要用三种原料，生产这

23、些产品需要配生产三种产品需要用三种原料，生产这些产品需要配置成本，若不需要，则无配置成本。有关数据如下表。置成本，若不需要，则无配置成本。有关数据如下表。问题：问题：各产品应生产多少总利润最大各产品应生产多少总利润最大。 生生 产产 数数 据据 表表添加剂添加剂溶剂溶剂清洁剂清洁剂原料数量原料数量原料原料1原料原料2原料原料30.40.60.50.20.30.60.10.320521单位利润单位利润($)403050配置费用配置费用($)20050400最大产量最大产量(t)502540设：设：f=添加剂生产量；添加剂生产量；s=溶剂生产量；溶剂生产量；c=清洁剂生产量；清洁剂生产量；引入引入

24、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分销系统设计分销系统设计(distribution system d

25、esign problem) 马丁贝克公司在圣路易斯经营一家生产量为马丁贝克公司在圣路易斯经营一家生产量为30000件产品的工厂。件产品的工厂。产品被运输到位于波士顿、亚特兰大和休斯敦的地区分销中心。由产品被运输到位于波士顿、亚特兰大和休斯敦的地区分销中心。由于预期将有需求增长于预期将有需求增长,公司计划在底特律、托来多、丹佛和堪萨斯中公司计划在底特律、托来多、丹佛和堪萨斯中一个或多个城市建立新工厂以增加生产力。有关数据如下表。一个或多个城市建立新工厂以增加生产力。有关数据如下表。 问题：问题：各选择哪个或哪些工厂使总成本最小。各选择哪个或哪些工厂使总成本最小。 生生 产产 数数 据据 表表

26、分销中心分销中心生产地生产地1波士顿波士顿2亚特兰大亚特兰大3休斯敦休斯敦生产能力生产能力（千件）（千件）年固定成年固定成本本(千千$)1 底特律底特律2 托来多托来多3 丹丹 佛佛4 堪萨斯堪萨斯5 圣路易斯圣路易斯54910823744345231020304030175300375500需求量需求量(千件千件)302020 在不考虑固定成本和生产地选择的情况下，此问题是一个在不考虑固定成本和生产地选择的情况下，此问题是一个运输问题运输问题.若用若用xij表示从产地表示从产地i到分销中心到分销中心j的运量的运量,则其数学模型为：则其数学模型为：minf=5x11+2x12+3x13+4x2

27、1+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; 若

28、在丹佛建立工厂若在丹佛建立工厂, 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+x

29、22+x32+x42+x52 =20 x13+x23+x33+x43+x53 =20 xij0,所有所有i,j; y1,y2,y3,y4=0,1银行选址（银行选址（location problem）俄亥俄州信托投资公司的远期计划正在考虑在俄亥俄州东北部俄亥俄州信托投资公司的远期计划正在考虑在俄亥俄州东北部20个郡的地区开展业务个郡的地区开展业务.该投资公司目前在这该投资公司目前在这20个郡还没有主营业处个郡还没有主营业处.根据该州法律根据该州法律:如果一个银行在任一个郡建立主营业处如果一个银行在任一个郡建立主营业处,即可在该即可在该郡及所有毗邻郡建设分行郡及所有毗邻郡建设分行. 该计划的第一步

30、是：投资公司需要确该计划的第一步是：投资公司需要确定为了在这定为了在这20个郡完全营业一共要建立的主营业处的最小数目个郡完全营业一共要建立的主营业处的最小数目.2019181787645911101314315122161 若在第若在第i郡建立主营业处郡建立主营业处, 则则xi=1, 否则否则 xi=0 这样这样, 目标函数为目标函数为: min z = x1+x2+ +x20 每个郡要满足一个约束条件每个郡要满足一个约束条件:该郡或与该郡相毗邻的郡中至少有该郡或与该郡相毗邻的郡中至少有一个需要建立主营业处一个需要建立主营业处. 例如第例如第10个郡有个郡有: x3+x9+x8+x11x10+

31、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产品设计和市场份额的优化（产品设计和市场份额的优化（ product design and market share optimization problem）顾顾客客面包皮

32、面包皮奶酪奶酪调味品调味品香肠口味香肠口味顾客对现有品顾客对现有品牌的效用牌的效用薄薄厚厚意意大大利利混混合合细细滑滑橙块橙块果酱果酱清清谈谈中中等等辣辣安东安东尼奥尼奥国王国王123456781111713212952752081719961582061112471714171191614316161730216231726714203025162614292515223016271162951223308101910122019352493683397079594758567258457158决策变量决策变量: xij=1, 表示赛伦表示赛伦pizza 在属性在属性j上选择上选择i, 否则

33、否则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+2

34、6x14+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+ 5x2

35、1+ 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