运筹学导论之整数线性规划

第6章整数线性规划整数线性规划问的提出对于某些具体问题，决策变量必须是整数的情形(称为整数解)。例如，机器台数、人数、装货车数等，含小数的解不合要求。为满足整数解要求，能否把已得到的含有分数的解“圆整”？下例说明单纯形法求得的解不能保证是整数最优解。例1COSCO公司拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如下表所示。问两种货物各托运多少箱，可使获得利润为最大? 货物 体积(m3/箱) 重量(100kg/箱) 利润(100元/箱) 甲乙 54 25 2010 托运限制 24m3 1300kg 现在我们解这个问题，设x1，x2分别为甲、乙两种货物的托运箱数(当然都是非负整数)。这是一个(纯)整数线性规划问题，用数学式可表示为：maxz=20x1+10x2①5x1+4x2≤24②2x1+5x2≤13③x1，x2≥0④x1，x2整数⑤它和线性规划问题的区别仅在于最后的条件⑤。现在我们暂不考虑这一条件，即解①～④(以后我们称这样的问题为与原问题相应的线性规划问题)，很容易求得最优解为：x1=4.8，x2=0，maxz=96但x1是托运甲种货物的箱数，现在它不是整数，所以不合条件⑤的要求。是否可以把所得的非整数的最优解经过“化整”就可得到合于条件⑤的整数最优解呢?如将(x1=4.8，x2=0)凑整为(x1=5，x2=0)，这样就破坏了条件②(关于体积的限制)，因而它不是可行解；如将(x1=4.8，x2=0)舍去尾数0.8，变为(x1=4，x2=0)，这当然满足各约束条件，因而是可行解，但不是最优解，因为当x1=4，x2=0,时z=80.非整数的最优解在C(4.8，0)点达到。但当x1=4，x2=1(这也是可行解)时，z=90。本例还可以用图解法来说明 图中(+)表示可行整数解。 凑整的(5，0)不在可行域内，而C点又不合于条件⑤。目标函数z的等值线必须向原点平行移动，直到首次遇到带“+”号B点(x1=4，x2=1)为止。此时，z值就由z=96变到z=90，Δz=96-90=6表示利润的降低，这是由于变量的不可分性(装箱)所引起的。将其相应的线性规划的最优解“化整”来解原整数线性规划，虽是最容易想到的，但往往不可行。化整后不见得是可行解；或虽是可行解，但不一定是最优解。因此有必要对整数线性规划的解法进行专门研究。由上例看出，此类问题为整数线性规划(IntegerLinearProgramming，ILP)，整数线性规划是最近几十年来发展起来的规划论中的一个分支。整数线性规划中如果所有的变量都限制为(非负)整数，就称为纯整数线性规划(pureintegerlinearprogramming)或称为全整数线性规划(allintegerlinearprogramming)；如果仅一部分变量限制为整数，则称为混合整数规划(mixedintegerlinearprogramming)。整数线性规划的一种特殊情形是0-1规划，它的变量取值仅限于0或1。指派问题就是一个0-1规划问题。8.1应用实例介绍1.资本预算在个人项目中投资中，既要考虑这些在个人项目中投资的收益，又要考虑有限的总预算。例在一个3年的规划周期内，有5个项目可供选择。下表给出了每一项目可以带来的期望收益以及相应每年的支出(单位：100万没有)，那么这个3年规划周期应该选择哪些项目？ 项目 每年支出 收益 1 2 3 1 5 1 8 20 2 4 7 10 40 3 3 9 2 20 4 7 4 1 15 5 8 6 10 30 可用资金 25 25 25问题可以化为一个对于每个项目的选择为“是-否”的决策，引入二元变量xj那么整数线性规划模型是最优的整数解是x1=x2=x3=x4=1，x5=0，对应的最优值z=95. 若采用连续的线性规划问题求解，将xj=(0,1),替换为0≤xj≤1，那么最优解为x1=0.5789,x2=x3=x4=1,x5=0.7368. 有部分变量取小数，这不符合实际，若采用舍入，则x1=x5=1，这意味着5个项目都要选择，显然是不可行解， 对于采用“是否”决策问题，舍入法不可行。习题某唱片公司与一位新的歌手签约录制8首歌曲，这8首歌曲的时间长度分别为8,3,5,5,9,6,7,12分钟，公司希望将所有的歌曲分配在磁带的两面，使得两面的歌曲时间长度尽量相同。请建立整数规划模型，求出最优解。2.集合覆盖问题在这一类问题中，会有许多的服务装置为一些设备提供互相重叠的服务，目标就是要确定安装数目最少的装置来覆盖每一个设备（满足服务需求）。例如，几个污水处理工厂可以选择建造在几个不同的位置，在不同的位置可以服务不同的几个城市，但一个城市可以得到几个不同工厂服务的时候就是重叠服务。16274583街道G街道E街道A街道B街道C街道D街道H街道I街道K街道J例为了提高城市校园的安全性，A大学的保安部门希望在校园的每条主要街道上都至少有一部电话的情况下，使得安装的电话总数最少，下图给出了校园的主要街道图将电话安装在街道的交叉口处是比较合理的，因为这样可以至少为两条街道提供服务。按照图中街道的可以看出，最多需要8部电话。 定义问题是求每一条街道都至少安装1部电话，则模型可写为：这个问题的最优解需要安装4部电话，分别在交叉口1，2，5，7覆盖问题有以下几个重要的性质：(1)变量xj,j=1,2,…,n,都是二元变量；(2)约束左端项的系数是0或者1；(3)每一个约束右端项的形式都是(≥1);(4)目标函数是最小化上例中，对所有的j，cj=1.如果cj表示位置j安装电话的费用，那么这些系数就是这些费用值而不再是1.习题MobileCo公司拿出1500万美元，最多建造7个发射台来覆盖15个相邻社区中尽可能多的人口。下表给出了每个发射台可以覆盖的社区以及建造这个发射台的费用以及社区人口。确定出需要建设哪几个发射台。各个社区人口数目 发射台 覆盖社区 建造费用(百万) 1 1，2 3.6 2 2，3，5 2.3 3 1，7，9，10 4.1 4 4，6，8，9 3.15 5 6，7，9，11 2.8 6 5，7，10，12，14 2.65 7 12，13，14，15 3.1 社区 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 人口(千人) 4 3 10 14 6 7 9 10 13 11 6 12 7 5 163.固定费用问题在这一类问题是处理一类同时包含两种费用形式的经济活动：一种费用称作“固定费”,只要启动这种活动就会有一个费用值；另一类费用是可变费用，正比于使用这种活动的程度。例如，在生产某种产品之前，需要购买一台机器，这台及其的费用是固定费，它与生产多少产品无关；一旦买进了机器，那么劳动力和原材料的消耗费用就正比于产品的数量。假定F是固定费用，c是变量的单位费用，x是产品的数量，那么总费用函数可以表示为例在美国有3家电话服务公司找我推销长途电话业务。MaBell公司收取固定费用16美元然后每分钟0.25美元；PaBell公司每月收取固定费25美元，但每分钟费用为0.21美元；BabyBell公司的每月固定费用为18美元，每分钟0.22美元。一般情况下，我平均每月使用的长途电话时间是200分钟。假设只有在我拨打电话以后公司才收取固定费。当然每月也可以使用多家电话公司，那么我该如何选择这3家电话公司，使得每月的电话费用最少？定义 x1=每个月使用MaBell公司的长途电话时间(分钟) x2=每个月使用PaBell公司的长途电话时间(分钟) x3=每个月使用BabyBell公司的长途电话时间(分钟)可以使用下面的约束来保证xj取正数时yj等于1.其中M是一个取足够大的数，使得不会限制变量xj的取值.由于我每个月的长途电话使用时间大约为200分钟，所以对所有的j，有xj≤200，因此取M=200即可.完整的模型是minz=0.25x1+0.21x2+0.22x3+16y1+25y2+18y3s.t.x1+x2+x3=200x1≤200y1x2≤200y2x3≤200y3y1,y2,y3=(1,0)从上面的式子，只有但yi=1的时候，也就是当xj>0的时候，第j个电话公司的固定费用才会在目标函数中起作用(根据模型的最后3个约束).如果在最优解中xj=0,那么由于目标函数z是最小化，又因为相应yi的系数是严格的正数，以及yi≥0,所以一定有yj=0才能达到最小.最优解x3=200,y3=1,其他变量取值为0，采用BabyBell公司拨打全部长途电话最合适。引入yi的目的是为了计算每个月的固定费.习题JOBCO在3台机器上生产至少2000个小零件。任何一台机器上至少生产500个。下表给出了这个问题的相关数据。根据这个问题，建立整数线性规划模型，并给出最优解. 机器 固定费用 每件产品的生产费用 生产能力 1 300 2 600 2 100 10 800 3 200 5 1200xj表示机器j生产的零件数目，j=1,2,3.如果使用机器j，那么yj=1；否则yj=04.“或者-或者”和“如果-那么”约束在固定费用问题中，我们引入二元变量来处理不连续的目标函数。本节，我们仍然利用二元变量来处理模型中约束不满足同时性(“或者-或者”)或者依赖性(“如果-那么”)的情形.采用的变换不会改变约束的“或者”或“依赖”关系，我们只是利用数学上的技巧方法将这样的约束转化为“并且”的关系.例JOBCO公司需要在一台机器上处理3项工作。下表给出了每项工作的处理时间及交货日期。假定第一项工作处理时的日期为0，应交工期从0算起.求使得延期处罚最少的工序处理. 工作 处理时间(天) 交货日期(天) 延期处罚(美元/天) 1 5 25 19 2 20 22 12 3 15 35 34定义xj=工作j的开始加工日期(按天计算，从0开始计算)这个问题有两个约束条件：互不干扰约束(保证两项工作不能同时处理)，应交货日期约束.首先考虑互不干扰约束.假设工作i和工作j的处理时间分别为pi和pj，为了保证这两项工作不同时处理，那么必须满足xi≥xj+pj,或者xj≥xi+pi,取决于工作j是在工作i之前处理还是在其后处理.因为所有的数学规划都是仅仅处理并的约束，所以我们通过引入下面的二元变量来将“或者-或者”约束转化为“并的”约束：对于足够大的数M，或者-或者约束可以用下面两个并的约束代替Myij+(xi-xj)≥pj和M(1-yij)+(xj-xi)≥pi这样的转化可以保证在任何时候这两个约束只有1个是起作用的.如果yij=0，那么第1个约束是起作用的，而第2个约束是多余的(因为左端项包含充分大的数M，所以一定会大于pi)；如果yij=1,那么第1个约束是多余的，第2个约束是起作用的。下面再考虑应交工日期约束。给定工件j的应交工日期是dj，令sj是一个无限制的变量，那么相关的约束是xj+pj+sj=dj如果sj≥0，那么应交工日期的约束可以满足；如果sj≤0则会有一个延期的处罚。引用代换那么约束变为延期处罚的费用正比例于这个问题的模型可以写为见3.1.2节，p.78引入整数变量y12,y13,y23是为了将“或者-或者”转化为“并的”约束.构造的模型是一个混合整数线性规划模型。为了求解这个模型，取M=100，这比3项工作处理时间总和还要大。最优解是x1=20,x2=0,x3=25.说明工作2在0时刻开始，工作1在第20天开始，工作3在第25天开始，最优的处理顺序是2→1→3.同时这个解还表明工作2在第0+20=20天完成，工作1在第20+5天完成，工作3在第25+15=40天完成，所以工作3延误了40-35=5天，罚款费用为5×34=170美元。8.2整数规划算法 在求解整数线性规划时，如果可行域是有界的，首先容易想到的方法就是穷举变量的所有可行的整数组合，就像在例1的图中给出所有“+”号的点那样，然后比较它们的目标函数值以定出最优解。 对于小型的问题，变量数很少，可行的整数组合数也是很小时，这个方法是可行的，也是有效的。 根据例1，如果决策变量数很少，穷举法还是勉强可用的。例如，例1的组合(不都是可行的)数是3×5=15个。 对于大型的问题，可行的整数组合数是很大的。例如在指派问题中，将n项任务指派n个人去完成，不同的指派方案共有n!种，当n=10，这个数就超过300万；当n=20，这个数就超过2×1018，如果一一计算，就是用每秒百万次的计算机，也要几万年。显然对于大型问题，穷举法不可行。 所以我们的方法一般应是仅检查可行的整数组合的一部分，就能定出最优的整数解。分支定界解法(branchandboundmethod)就是其中的一个。设有最大化的整数线性规划问题A，与它相应的线性规划为问题B，从解问题B开始，若其最优解不符合A的整数条件，那么B的最优目标函数必是A的最优目标函数z*的上界，记作；而A的任意可行解的目标函数值将是z*的一个下界。分支定界法就是将B的可行域分成子区域(称为分支)的方法，逐步减小和增大，最终求到z*。分支定界法可用于解纯整数或混合的整数线性规划问题。在20世纪60年代初由LandDoig和Dakin等人提出。由于这方法灵活且便于用计算机求解，所以现在它已是解整数线性规划的重要方法。8.2.1分支定界算法例1maxz=5x1+4x2x1+x2≤510x1+6x2≤45x1，x2非负整数最优解x1=3.75,x2=1.25z=23.75LP1LP2LP3LP1x1=3.75，x2=1.25，z=23.75LP2x1=3，x2=2，z=23下界(最优解)LP3x1=4，x2=0.83，z=23.33LP4x1=4.5，x2=0，z=22.5LP5无可行解LP6x1=4，x2=0，z=20下界LP5无可行解x1≤3x1≥4x2≤0x2≥1x1≤4x1≥51724365例2 求解maxz=40x1+90x2①9x1+7x2≤56②7x1+20x2≤70③x1，x2≥0④x1，x2整数⑤先不考虑条件⑤，即解相应的线性规划B,①～④，得最优解x1=4.81，x2=1.82，z0=356 可见它不符合整数条件⑤。这时z0是问题A的最优目标函数值z*的上界，记作z0=。而在x1=0，x2=0时，显然是问题A的一个整数可行解，这时z=0，是z*的一个下界，记作=0，即0≤z*≤356分支定界法的解法 首先注意其中一个非整数变量的解，如x1，在问题B的解中x1=4.81。于是对原问题增加两个约束条件x1≤4，x1≥5 可将原问题分解为两个子问题B1和B2(即两支)，给每支增加一个约束条件，如下图。x1≤4，x1≥5 这并不影响问题A的可行域，不考虑整数条件解问题B1和B2，称此为第一次迭代。得到最优解为： 显然没有得到全部变量是整数的解。因z1＞z2，故将改为349，那么必存在最优整数解，得到z*，并且0≤z*≤349继续对问题B1和B2进行分解继续对问题B2进行分解因z1＞z2，故先分解B1为两支。增加条件x2≤2者，称为问题B3；增加条件x2≥3者称为问题B4。在下图中再舍去x2＞2与x2＜3之间的可行域，再进行第二次迭代。从以上解题过程可得到，用分支定界法求解整数线性规划(最大化)问题的步骤为： 将要求解的整数线性规划问题称为问题A， 将与它相应的线性规划问题称为问题B。(1)解问题B，可能得到以下情况之一。①B没有可行解，这时A也没有可行解，则停止。②B有最优解，并符合问题A的整数条件，B的最优解即为A的最优解，则停止。③B有最优解，但不符合问题A的整数条件，记它的目标函数值为(2)用观察法找问题A的一个整数可行解，一般可取xj=0，j=1，…，n，试探，求得其目标函数值，并记作。以z*表示问题A的最优目标函数值；这时有 在B的最优解中任选一个不符合整数条件的变量xj，其值为bj，以［bj］表示小于bj的最大整数。构造两个约束条件xj≤［bj］和xj≥［bj］+1将这两个约束条件，分别加入问题B，求两个后继规划问题B1和B2。不考虑整数条件求解这两个后继问题。 定界，以每个后继问题为一分支标明求解的结果，与其他问题的解的结果中，找出最优目标函数值最大者作为新的上界。从已符合整数条件的各分支中，找出目标函数值为最大者作为新的下界，若无可行解，第一步：分支第二步：比较与剪支 各分支的最优目标函数中若有小于者，则剪掉这支(用×表示)，即以后不再考虑了。若大于，且不符合整数条件，则重复第一步骤。一直到最后得到z*为止，得最优整数解xj*，j=1，…，n。 用分支定界法可解纯整数线性规划问题和混合整数线性规划问题。它比穷举法优越。因为它仅在一部分可行解的整数解中寻求最优解，计算量比穷举法小。若变量数目很大，其计算工作量也是相当可观的。例maxz=5x1+8x2stx1+x2≤610x1+6x2≤45x1和x2均为非负整数解：（1）首先不考虑整数性约束，得原问题的松弛问题(B)maxz=5x1+8x2stx1+x2≤610x1+6x2≤45x1≥0，x2≥0利用单纯形法求得最优解为x1=2.25，x2=3.75，maxz=41.25令（2）在不满足约束条件的两个变量中任选一个，不妨选择x1，对原问题分别增加约束条件x1≤2和x1≥3，将原问题分支为两个子问题，该子问题对应的松弛问题是(B1)和(B2)，即(B1)maxz=5x1+8x2stx1+x2≤610x1+6x2≤45x1≤2x1≥0，x2≥0(B2)maxz=5x1+8x2stx1+x2≤610x1+6x2≤45x1≥3x1≥0，x2≥0（3）先求解问题(B1).利用单纯形法得到(B1)的最优解,x1=2,x2=3.89，maxz=41.1。因为x2还不是整数，且maxz=41.1>所以还要对问题(B1).进行分支。分别增加新的约束条件x2≤3和x2≥4，将问题(B1)分支为两个子问题(B11)和(B12)，其对应的松弛问题为(B11)maxz=5x1+8x2stx1+x2≤6 10x1+6x2≤45x1≤2x2≤3x1≥0，x2≥0(B12)maxz=5x1+8x2stx1+x2≤6 10x1+6x2≤45 x1≥3 x2≥4 x1≥0，x2≥0（4）利用单纯形法得到(B2)的最优解,x1=3,x2=3，maxz=39。已经是整数解，同时修改原问题的下界，即（5）再求解问题(B11)，利用单纯形法求得最优解为x1=2,x2=3,maxz=34,由于最优解满足整数性要求，故不再分支。（6）对问题(B12)进行求解，得最优解,x1=1.8,x2=4,maxz=41。还没有得到整数解，且目标函数大于下界maxz=41>39,因此还需要继续分支。由于x1又不满足整数性约束，加入约束条件x1≤1和x1≥2进行分支，其对应的松弛问题为问题(B121)和(B122)，即(B121)maxz=5x1+8x2stx1+x2≤610x1+6x2≤45x1≤2x2≥4x1≤1x1≥0，x2≥0(B122)maxz=5x1+8x2stx1+x2≤610x1+6x2≤45x1≤2 x2≥4x1≥2x1≥0，x2≥0（7）对问题(B121)进行求解，得最优解,x1=1,x2=4.44,maxz=40.6>，还需要继续分支。而问题(B122)已无可行解。（8）对问题(B121)加入约束条件x2≤4和x2≥5继续分支，得到其对应的松弛问题为问题(B1211)和(B1212)，如下问题(B1211)的最优解为x1=1,x2=4,maxz=37，问题(B1212)的最优解为x1=0,x2=5,maxz=40.由此所有的分支全部求解完毕。原问题的最优解为x1=0,x2=5,maxz=40.(B121)maxz=5x1+8xstx1+x2≤610x1+6x2≤45x1≤2x2≥4x1≤1x2≤4x1≥0，x2≥0(B122)maxz=5x1+8x2stx1+x2≤610x1+6x2≤45x1≤2x2≥4x1≤1x2≥5x1≥0，x2≥0分支定界算法的原则：(1)每个松弛问题的最优值均是相应整数规划问题最优值的上界。(2)在求解子问题的松弛问题时：①若松弛问题无可行解，则相应的子问题也无可行解，舍弃不再分支。②若松弛问题的解满足整数性约束，则此解为相应子问题的最优解，此时不再分支。如果目标函数值大于目前的下界值，则修改下界值。③如果松弛问题的解不满足整数性约束，但目标函数值不大于目前的下界值，则不再分支。④若松弛问题的解不满足整数性约束，但目标函数值大于目前的下界值，则对应的子问题需要进一步分支。maxz=3x1+x2+3x3st-x1+2x2+x3≤4-4x2-3x3≤2x1-3x2+2x3≤3x1,x2,x3≥0且x1和x3为整数习题maxz=3x1+2x2st2x1+5x2≤94x1+2x2≤9x1和x2均为非负整数8.2.20-1型整数线性规划算法 0-1型整数线性规划是整数线性规划中的特殊情形，它的变量xi仅取值0或1。这时xi称为0-1变量，或称二进制变量.xi仅取值0或1这个条件可由下述约束条件所代替。xi≤1,xi≥0，整数 它和一般整数线性规划的约束条件形式是一致的。在实际问题中，如果引入0-1变量，就可以把有各种情况需要分别讨论的线性规划问题统一在一个问题中讨论了。在本节我们先介绍引入0-1变量的实际问题，再研究解法。解0-1型整数线性规划最容易想到的方法，和一般整数线性规划的情形一样，就是穷举法，即检查变量取值为0或1的每一种组合，比较目标函数值以求得最优解，这就需要检查变量取值的2n个组合。对于变量个数n较大(例如n＞10)，这几乎是不可能的。因此常设计一些方法，只检查变量取值的组合的一部分，就能求到问题的最优解。这样的方法称为隐枚举法(implicitenumeration)，分枝定界法也是一种隐枚举法。当然，对有些问题隐枚举法并不适用，所以有时穷举法还是必要的。下面举例说明一种解0-1型整数线性规划的隐枚举法例6目标函数maxz=3x1-2x2+3x5约束条件： x1+2x2-x3≤2① x1+4x2+x3≤4② x1+x2≤3③ 4x1+x3≤6④ x1，x2，x3=0或1⑤解题时先通过试探的方法找一个可行解，容易看出(x1，x2，x3)=(1，0，0)就是合于①～④条件的，算出相应的目标函数值z=3。 对于求解极大化最优解，当然希望z≥3，故增加约束条件：3x1-2x2+5x3≥3◎ 后加的条件称为过滤的条件(filteringconstraint)。这样，原问题的线性约束条件就变成5个。用全部枚举的方法，3个变量共有23=8个解，原来4个约束条件，共需32次运算。现在增加了过滤条件◎，如按下述方法进行，就可减少运算次数。将5个约束条件按◎～④顺序排好。 对每个解，依次代入约束条件左侧，求出数值，看是否适合不等式条件，如某一条件不适合，同行以下各条件就不必再检查，因而就减少了运算次数。 本例计算过程如表5-5，实际只作24次运算。 于是求得最优解(x1，x2，x3)=(1，0，1),maxz=8 在计算过程中，若遇到z值已超过条件◎右边的值，应改变条件◎，使右边为迄今为止最大者，然后继续作。例如，当检查点(0，0，1)时因z=5(＞3)，所以应将条件◎换成 3x1-2x2+5x3≥5◎ 这种对过滤条件的改进，更可以减少计算量。注意：一般常重新排列xi的顺序使目标函数中xi的系数是递增(不减)的，在上例中，改写z=3x1-2x2+5x3=-2x2+3x1+5x3 因为-2，3，5是递增的序，变量(x2，x1，x3)也按下述顺序取值：(0，0，0)，(0，0，1)，(0，1，0)，(0，1，1)，…， 这样，最优解容易比较早的发现。再结合过滤条件的改进，更可使计算简化 在上例中maxz=-2x2+3x1+5x3-2x2+3x1+5x3≥3◎2x2+x1-x3≤2①4x2+x1+x3≤4②x2+x1≤3③4x2+x3≤6④ 解题时按下述步骤进行，见下表：改进过滤条件，用 -2x2+3x1+5x3≥5◎′代替◎，继续进行。条件点(x2,x1,x3)◎①②③④满足条件?是(√)否(×)z值(0,0,0)(0,0,1)05-1101×√5条件点(x2,x1,x3)◎’①②③④满足条件?是(√)否(×)z值(0,1,0)(0,1,1)380211×√8再改进过滤条件，用2x2+3x1+5x3≥8◎″代替◎′，再继续进行。至此，z值已不能改进，即得到最优解，解答如前，但计算已简化。条件Ä点(x2,x1,x3)◎″①②③④满足条件?是(√)否(×)z值(0,0,0)(0,0,1)(1,1,0)(1,1,1)2316××××