搜索
1第6章整数线性规划2整数线性规划问题的提出对于某些具体问题，决策变量必须是整数的情形(称为整数解)。例如，机器台数、人数、装货车数等，含小数的解不合要求。为满足整数解要求，能否把已得到的含有分数的解“圆整”？3下例说明单纯形法求得的解不能保证是整数最优解。例1COSCO公司拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如下表所示。问两种货物各托运多少箱，可使获得利润为最大?货物体积(m3/箱)重量(100kg/箱)利润(100元/箱)甲乙54252010托运限制24m31300kg4现在我们解这个问题，设x1，x2分别为甲、乙两种货物的托运箱数(当然都是非负整数)。这是一个(纯)整数线性规划问题，用数学式可表示为：maxz=20x1+10x2①5x1+4x2≤24②2x1+5x2≤13③x1，x2≥0④x1，x2整数⑤5它和线性规划问题的区别仅在于最后的条件⑤。现在我们暂不考虑这一条件，即解①～④(以后我们称这样的问题为与原问题相应的线性规划问题)，很容易求得最优解为：x1=4.8，x2=0，maxz=966但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)点达到。7但当x1=4，x2=1(这也是可行解)时，z=90。本例还可以用图解法来说明图中(+)表示可行整数解。凑整的(5，0)不在可行域内，而C点又不合于条件⑤。目标函数z的等值线必须向原点平行移动，直到首次遇到带“+”号B点(x1=4，x2=1)为止。此时，z值就由z=96变到z=90，Δz=96-90=6表示利润的降低，这是由于变量的不可分性(装箱)所引起的。8将其相应的线性规划的最优解“化整”来解原整数线性规划，虽是最容易想到的，但往往不可行。化整后不见得是可行解；或虽是可行解，但不一定是最优解。因此有必要对整数线性规划的解法进行专门研究。由上例看出，9此类问题为整数线性规划(IntegerLinearProgramming，ILP)，整数线性规划是最近几十年来发展起来的规划论中的一个分支。整数线性规划中如果所有的变量都限制为(非负)整数，就称为纯整数线性规划(pureintegerlinearprogramming)或称为全整数线性规划(allintegerlinearprogramming)；如果仅一部分变量限制为整数，则称为混合整数规划(mixedintegerlinearprogramming)。整数线性规划的一种特殊情形是0-1规划，它的变量取值仅限于0或1。指派问题就是一个0-1规划问题。108.1应用实例介绍1.资本预算在个人项目中投资中，既要考虑这些在个人项目中投资的收益，又要考虑有限的总预算。例在一个3年的规划周期内，有5个项目可供选择。下表给出了每一项目可以带来的期望收益以及相应每年的支出(单位：100万没有)，那么这个3年规划周期应该选择哪些项目？项目每年支出收益12315182024710403392204741155861030可用资金25252511问题可以化为一个对于每个项目的选择为“是-否”的决策，引入二元变量xj1,0jjxj如果选择项目，如果不选择项目那么整数线性规划模型是1234512345123451234512345maxz2040201530..543782579462581021025,,,,(0,1)xxxxxstxxxxxxxxxxxxxxxxxxxx最优的整数解是x1=x2=x3=x4=1，x5=0，对应的最优值z=95.12若采用连续的线性规划问题求解，将xj=(0,1),替换为0≤xj≤1，那么最优解为x1=0.5789,x2=x3=x4=1,x5=0.7368.有部分变量取小数，这不符合实际，若采用舍入方法，则x1=x5=1，这意味着5个项目都要选择，显然是不可行解，对于采用“是否”决策问题，舍入法不可行。13习题某唱片公司与一位新的歌手签约录制8首歌曲，这8首歌曲的时间长度分别为8,3,5,5,9,6,7,12分钟，公司希望将所有的歌曲分配在磁带的两面，使得两面的歌曲时间长度尽量相同。请建立整数规划模型，求出最优解。142.集合覆盖问题在这一类问题中，会有许多的服务装置为一些设备提供互相重叠的服务，目标就是要确定安装数目最少的装置来覆盖每一个设备（满足服务需求）。例如，几个污水处理工厂可以选择建造在几个不同的位置，在不同的位置可以服务不同的几个城市，但一个城市可以得到几个不同工厂服务的时候就是重叠服务。1516274583街道G街道E街道A街道B街道C街道D街道H街道I街道K街道J例为了提高城市校园的安全性，A大学的保安部门希望在校园的每条主要街道上都至少有一部电话的情况下，使得安装的电话总数最少，下图给出了校园的主要街道图16将电话安装在街道的交叉口处是比较合理的，因为这样可以至少为两条街道提供服务。按照图中街道的设计可以看出，最多需要8部电话。定义1,0,jjxj如果在位置安装电话如果在位置不安装电话问题是求每一条街道都至少安装1部电话，则模型可写为：1712345781223457867261647245835min1A1B1C1D1E1F1G1H1I1J1Kzxxxxxxxstxxxxxxxxxxxxxxxxxxxxxx（街道）（街道）（街道）（街道）（街道）（街道）（街道）（街道）（街道）（街道）（街道）这个问题的最优解需要安装4部电话，分别在交叉口1，2，5，716274583街道G街道E街道A街道B街道C街道D街道H街道I街道K街道J18覆盖问题有以下几个重要的性质：(1)变量xj,j=1,2,…,n,都是二元变量；(2)约束左端项的系数是0或者1；(3)每一个约束右端项的形式都是(≥1);(4)目标函数是最小化1122,0,1,2,.nnjcxcxcxcjn其中上例中，对所有的j，cj=1.如果cj表示位置j安装电话的费用，那么这些系数就是这些费用值而不再是1.19习题MobileCo公司拿出1500万美元，最多建造7个发射台来覆盖15个相邻社区中尽可能多的人口。下表给出了每个发射台可以覆盖的社区以及建造这个发射台的费用以及社区人口。确定出需要建设哪几个发射台。发射台覆盖社区建造费用(百万)11，23.622，3，52.331，7，9，104.144，6，8，93.1556，7，9，112.865，7，10，12，142.65712，13，14，153.1各个社区人口数目社区123456789101112131415人口(千人)4310146791013116127516203.固定费用问题在这一类问题是处理一类同时包含两种费用形式的经济活动：一种费用称作“固定费”,只要启动这种活动就会有一个费用值；另一类费用是可变费用，正比于使用这种活动的程度。例如，在生产某种产品之前，需要购买一台机器，这台及其的费用是固定费，它与生产多少产品无关；一旦买进了机器，那么劳动力和原材料的消耗费用就正比于产品的数量。假定F是固定费用，c是变量的单位费用，x是产品的数量，那么总费用函数可以表示为,00,0FcxxCxx如果如果21例在美国有3家电话服务公司找我推销长途电话业务。MaBell公司收取固定费用16美元然后每分钟0.25美元；PaBell公司每月收取固定费25美元，但每分钟费用为0.21美元；BabyBell公司的每月固定费用为18美元，每分钟0.22美元。一般情况下，我平均每月使用的长途电话时间是200分钟。假设只有在我拨打电话以后公司才收取固定费。当然每月也可以使用多家电话公司，那么我该如何选择这3家电话公司，使得每月的电话费用最少？22定义x1=每个月使用MaBell公司的长途电话时间(分钟)x2=每个月使用PaBell公司的长途电话时间(分钟)x3=每个月使用BabyBell公司的长途电话时间(分钟)1,0,1,2,30,0iiixyix如果如果可以使用下面的约束来保证xj取正数时yj等于1.,1,2,3jjxMyj其中M是一个取足够大的数，使得不会限制变量xj的取值.由于我每个月的长途电话使用时间大约为200分钟，所以对所有的j，有xj≤200，因此取M=200即可.23完整的模型是minz=0.25x1+0.21x2+0.22x3+16y1+25y2+18y3s.t.x1+x2+x3=200x1≤200y1x2≤200y2x3≤200y3y1,y2,y3=(1,0)从上面的式子，只有但yi=1的时候，也就是当xj0的时候，第j个电话公司的固定费用才会在目标函数中起作用(根据模型的最后3个约束).如果在最优解中xj=0,那么由于目标函数z是最小化，又因为相应yi的系数是严格的正数，以及yi≥0,所以一定有yj=0才能达到最小.最优解x3=200,y3=1,其他变量取值为0，采用BabyBell公司拨打全部长途电话最合适。引入yi的目的是为了计算每个月的固定费.24习题JOBCO计划在3台机器上生产至少2000个小零件。任何一台机器上至少生产500个。下表给出了这个问题的相关数据。根据这个问题，建立整数线性规划模型，并给出最优解.机器固定费用每件产品的生产费用生产能力1300260021001080032005120025xj表示机器j生产的零件数目，j=1,2,3.如果使用机器j，那么yj=1；否则yj=0264.“或者-或者”和“如果-那么”约束在固定费用问题中，我们引入二元变量来处理不连续的目标函数。本节，我们仍然利用二元变量来处理模型中约束不满足同时性(“或者-或者”)或者依赖性(“如果-那么”)的情形.采用的变换不会改变约束的“或者”或“依赖”关系，我们只是利用数学上的技巧方法将这样的约束转化为“并且”的关系.例JOBCO公司需要在一台机器上处理3项工作。下表给出了每项工作的处理时间及交货日期。假定第一项工作处理时的日期为0，应交工期从0算起.求使得延期处罚最少的工序处理方案.工作处理时间(天)交货日期(天)延期处罚(美元/天)1525192202212315353427定义xj=工作j的开始加工日期(按天计算，从0开始计算)这个问题有两个约束条件：互不干扰约束(保证两项工作不能同时处理)，应交货日期约束.首先考虑互不干扰约束.假设工作i和工作j的处理时间分别为pi和pj，为了保证这两项工作不同时处理，那么必须满足xi≥xj+pj,或者xj≥xi+pi,取决于工作j是在工作i之前处理还是在其后处理.因为所有的数学规划都是仅仅处理并的约束，所以我们通过引入下面的二元变量来将“或者-或者”约束转化为“并的”约束：1,0,ijijyji若工作在工作之前加工若工作在工作之前加工对于足够大的数M，或者-或者约束可以用下面两个并的约束代替Myij+(xi-xj)≥pj和M(1-yij)+(xj-xi)≥pi28这样的转化可以保证在任何时候这两个约束只有1个是起作用的.如果yij=0，那么第1个约束是起作用的，而第2个约束是多余的(因为左端项包含充分大的数M，所以一定会大于pi)；如果yij=1,那么第1个约束是多余的，第2个约束是起作用的。下面再考虑应交工日期约束。给定工件j的应交工日期是dj，令sj是一个无限制的变量，那么相关的约束是xj+pj+sj=dj如果sj≥0，那么应交工日期的约束可以满足；如果sj≤0则会有一个延期的处罚。引用代换那么约束变为延期处罚