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

《运筹学导论之整数线性规划》由会员分享，可在线阅读，更多相关《运筹学导论之整数线性规划（61页珍藏版）》请在金锄头文库上搜索。

1、1,第6章 整数线性规划,2,整数线性规划问题的提出,对于某些具体问题，决策变量必须是整数的情形(称为整数解)。例如，机器台数、人数、装货车数等，含小数的解不合要求。 为满足整数解要求，能否把已得到的含有分数的解 “圆整”？,3,下例说明单纯形法求得的解不能保证是整数最优解。 例1 COSCO公司拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如下表所示。问两种货物各托运多少箱，可使获得利润为最大?,4,现在我们解这个问题，设x1，x2分别为甲、乙两种货物的托运箱数(当然都是非负整数)。这是一个(纯)整数线性规划问题，用数学式可表示为： max z =20x1+10x2

2、5x1+4x224 2x1+5x213 x1，x20 x1，x2整数 ,5,它和线性规划问题的区别仅在于最后的条件。现在我们暂不考虑这一条件，即解(以后我们称这样的问题为与原问题相应的线性规划问题)，,很容易求得最优解为：x1=4.8，x2=0，max z=96,6,但x1是托运甲种货物的箱数，现在它不是整数，所以不合条件的要求。 是否可以把所得的非整数的最优解经过“化整”就可得到合于条件的整数最优解呢? 如将(x1=4.8，x2=0)凑整为(x1=5，x2=0)，这样就破坏了条件(关于体积的限制)，因而它不是可行解； 如将(x1=4.8，x2=0)舍去尾数0.8，变为(x1=4，x2=0)，

3、这当然满足各约束条件，因而是可行解，但不是最优解，因为当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,将其相应的线性规划的最优解“化整”来解原整数线性规划，虽是最容易想到的，但往往不可行。 化

4、整后不见得是可行解；或虽是可行解，但不一定是最优解。 因此有必要对整数线性规划的解法进行专门研究。,由上例看出，,9,此类问题为整数线性规划(Integer Linear Programming ，ILP)，整数线性规划是最近几十年来发展起来的规划论中的一个分支。 整数线性规划中如果所有的变量都限制为(非负)整数，就称为纯整数线性规划(pure integer linear programming)或称为全整数线性规划(all integer linear programming)； 如果仅一部分变量限制为整数，则称为混合整数规划(mixed integer linear programmin

5、g)。 整数线性规划的一种特殊情形是0-1规划，它的变量取值仅限于0或1。指派问题就是一个0-1规划问题。,10,8.1 应用实例介绍,1. 资本预算 在个人项目中投资中，既要考虑这些在个人项目中投资的收益，又要考虑有限的总预算。 例 在一个3年的规划周期内，有5个项目可供选择。下表给出了每一项目可以带来的期望收益以及相应每年的支出(单位：100万没有)，那么这个3年规划周期应该选择哪些项目？,11,问题可以化为一个对于每个项目的选择为“是-否”的决策，引入二元变量 xj,那么整数线性规划模型是,最优的整数解是x1= x2= x3= x4=1， x5= 0，对应的最优值z=95.,12,若采用

6、连续的线性规划问题求解，将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分钟，公司希望将所有的歌曲分配在磁带的两面，使得两面的歌曲时间长度尽量相同。请建立整数规划模型，求出最优解。,14,2. 集合覆盖问题 在这一类问题中，会有许多的服务装置为一些设备提

7、供互相重叠的服务，目标就是要确定安装数目最少的装置来覆盖每一个设备（满足服务需求）。例如，几个污水处理工厂可以选择建造在几个不同的位置，在不同的位置可以服务不同的几个城市，但一个城市可以得到几个不同工厂服务的时候就是重叠服务。,15,1,6,2,7,4,5,8,3,街道G,街道E,街道A,街道B,街道C,街道D,街道H,街道I,街道K,街道J,例 为了提高城市校园的安全性，A大学的保安部门希望在校园的每条主要街道上都至少有一部电话的情况下，使得安装的电话总数最少，下图给出了校园的主要街道图,16,将电话安装在街道的交叉口处是比较合理的，因为这样可以至少为两条街道提供服务。按照图中街道的设计可以

8、看出，最多需要8部电话。 定义,问题是求每一条街道都至少安装1部电话，则模型可写为：,17,这个问题的最优解需要安装4部电话，分别在交叉口1，2，5，7,18,覆盖问题有以下几个重要的性质： (1)变量xj , j=1,2,n,都是二元变量； (2)约束左端项的系数是0或者1； (3)每一个约束右端项的形式都是(1); (4)目标函数是最小化,上例中，对所有的 j，cj=1. 如果 cj 表示位置 j 安装电话的费用，那么这些系数就是这些费用值而不再是1.,19,习题 MobileCo公司拿出1500万美元，最多建造7个发射台来覆盖15个相邻社区中尽可能多的人口。下表给出了每个发射台可以覆盖的

9、社区以及建造这个发射台的费用以及社区人口。确定出需要建设哪几个发射台。,各个社区人口数目,20,3. 固定费用问题 在这一类问题是处理一类同时包含两种费用形式的经济活动：一种费用称作“固定费”,只要启动这种活动就会有一个费用值；另一类费用是可变费用，正比于使用这种活动的程度。例如，在生产某种产品之前，需要购买一台机器，这台及其的费用是固定费，它与生产多少产品无关；一旦买进了机器，那么劳动力和原材料的消耗费用就正比于产品的数量。假定F是固定费用，c是变量的单位费用，x是产品的数量，那么总费用函数可以表示为,21,例 在美国有3家电话服务公司找我推销长途电话业务。MaBell公司收取固定费用16美

10、元然后每分钟0.25美元；PaBell公司每月收取固定费25美元，但每分钟费用为0.21美元；BabyBell公司的每月固定费用为18美元，每分钟0.22美元。一般情况下，我平均每月使用的长途电话时间是200分钟。假设只有在我拨打电话以后公司才收取固定费。当然每月也可以使用多家电话公司，那么我该如何选择这3家电话公司，使得每月的电话费用最少？,22,定义 x1=每个月使用MaBell公司的长途电话时间(分钟) x2=每个月使用PaBell公司的长途电话时间(分钟) x3=每个月使用BabyBell公司的长途电话时间(分钟),可以使用下面的约束来保证 xj 取正数时yj等于1.,其中M是一个取足

11、够大的数，使得不会限制变量xj的取值. 由于我每个月的长途电话使用时间大约为200分钟，所以对所有的j，有xj200，因此取M=200即可.,23,完整的模型是 min z=0.25x1+ 0.21x2+ 0.22x3+ 16y1+ 25y2+ 18y3 s.t. x1+x2+x3=200 x1 200y1 x2 200y2 x3200y3 y1,y2,y3=(1,0),从上面的式子，只有但yi=1的时候，也就是当xj0的时候，第j个电话公司的固定费用才会在目标函数中起作用(根据模型的最后3个约束). 如果在最优解中xj=0, 那么由于目标函数z是最小化，又因为相应 yi 的系数是严格的正数，

12、以及yi0, 所以一定有yj=0才能达到最小.,最优解x3=200, y3=1,其他变量取值为0，采用BabyBell公司拨打全部长途电话最合适。 引入yi的目的是为了计算每个月的固定费.,24,习题 JOBCO计划在3台机器上生产至少2000个小零件。任何一台机器上至少生产500个。下表给出了这个问题的相关数据。,根据这个问题，建立整数线性规划模型，并给出最优解.,25,xj 表示机器 j 生产的零件数目，j=1,2,3. 如果使用机器 j，那么yj=1；否则yj=0,26,4. “或者-或者”和“如果-那么”约束 在固定费用问题中，我们引入二元变量来处理不连续的目标函数。本节，我们仍然利用

13、二元变量来处理模型中约束不满足同时性(“或者-或者”)或者依赖性(“如果-那么”)的情形.采用的变换不会改变约束的“或者”或“依赖”关系，我们只是利用数学上的技巧方法将这样的约束转化为“并且”的关系. 例 JOBCO公司需要在一台机器上处理3项工作。下表给出了每项工作的处理时间及交货日期。假定第一项工作处理时的日期为0，应交工期从0算起. 求使得延期处罚最少的工序处理方案.,27,定义xj=工作 j 的开始加工日期(按天计算，从0开始计算) 这个问题有两个约束条件：互不干扰约束(保证两项工作不能同时处理)，应交货日期约束. 首先考虑互不干扰约束. 假设工作i和工作j的处理时间分别为pi和pj，

14、为了保证这两项工作不同时处理，那么必须满足xixj+pj, 或者xjxi+pi, 取决于工作 j 是在工作 i 之前处理还是在其后处理. 因为所有的数学规划都是仅仅处理并的约束，所以我们通过引入下面的二元变量来将“或者-或者”约束转化为“并的”约束：,对于足够大的数M，或者-或者约束可以用下面两个并的约束代替 Myij+(xi-xj)pj和M(1-yij)+(xj-xi)pi,28,这样的转化可以保证在任何时候这两个约束只有1个是起作用的. 如果yij=0，那么第1个约束是起作用的，而第2个约束是多余的(因为左端项包含充分大的数 M，所以一定会大于pi)；如果yij= 1,那么第1个约束是多余

15、的，第2个约束是起作用的。 下面再考虑应交工日期约束。给定工件j的应交工日期是dj，令sj是一个无限制的变量，那么相关的约束是 xj+pj+sj=dj 如果sj0，那么应交工日期的约束可以满足；如果sj0则会有一个延期的处罚。引用代换 那么约束变为 延期处罚的费用正比例于 这个问题的模型可以写为,见3.1.2节，p.78,29,引入整数变量y12,y13,y23是为了将“或者-或者”转化为“并的”约束. 构造的模型是一个混合整数线性规划模型。 为了求解这个模型，取M=100，这比3项工作处理时间总和还要大。 最优解是x1=20,x2=0,x3=25. 说明工作2在0时刻开始，工作1在第20天开

16、始，工作3在第25天开始，最优的处理顺序是213. 同时这个解还表明工作2在第0+20=20天完成，工作1在第20+5天完成，工作3在第25+15=40天完成，所以工作3延误了40-35=5天，罚款费用为534=170美元。,30,8.2 整数规划算法,在求解整数线性规划时，如果可行域是有界的，首先容易想到的方法就是穷举变量的所有可行的整数组合，就像在例1的图中给出所有“+”号的点那样，然后比较它们的目标函数值以定出最优解。 对于小型的问题，变量数很少，可行的整数组合数也是很小时，这个方法是可行的，也是有效的。,31,根据例1，如果决策变量数很少，穷举法还是勉强可用的。例如，例1的组合(不都是可行的)数是35=15个。 对于大型的问题，可行的整数组合数是很大的。例如在指派问题中，将n项任务指派n个人去完成，不同的指派方案共有n!种，当n=10，这个数就超过300万；当n=20，这个数就超过21018，如果一一计算，就是用每秒百万次的计算机，也要几