运筹学导论第八版8整数线性规划.pptx

第6章 整数线性规划整数线性规划问题的提出对于某些具体问题，决策变量必须是整数的情形(称为整数解)。例如，机器台数、人数、装货车数等，含小数的解不合要求。为满足整数解要求，能否把已得到的含有分数的解 “圆整”？下例说明单纯形法求得的解不能保证是整数最优解。例1 COSCO公司拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如下表所示。问两种货物各托运多少箱，可使获得利润为最大?现在我们解这个问题，设x1，x2分别为甲、乙两种货物的托运箱数(当然都是非负整数)。这是一个(纯)整数线性规划问题，用数学式可表示为： max z =20x1+10x2 ① 5x1+4x2≤24 ② 2x1+5x2≤13 ③ x1，x2≥0 ④ x1，x2整数 ⑤它和线性规划问题的区别仅在于最后的条件⑤。现在我们暂不考虑这一条件，即解①～④(以后我们称这样的问题为与原问题相应的线性规划问题)，很容易求得最优解为：x1=4.8，x2=0，max z=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表示利润的降低，这是由于变量的不可分性(装箱)所引起的。 由上例看出，将其相应的线性规划的最优解“化整”来解原整数线性规划，虽是最容易想到的，但往往不可行。化整后不见得是可行解；或虽是可行解，但不一定是最优解。因此有必要对整数线性规划的解法进行专门研究。此类问题为整数线性规划(Integer Linear Programming ，ILP)，整数线性规划是最近几十年来发展起来的规划论中的一个分支。整数线性规划中如果所有的变量都限制为(非负)整数，就称为纯整数线性规划(pure integer linear programming)或称为全整数线性规划(all integer linear programming)；如果仅一部分变量限制为整数，则称为混合整数规划(mixed integer linear programming)。整数线性规划的一种特殊情形是0-1规划，它的变量取值仅限于0或1。指派问题就是一个0-1规划问题。 1. 资本预算在个人项目中投资中，既要考虑这些在个人项目中投资的收益，又要考虑有限的总预算。例 在一个3年的规划周期内，有5个项目可供选择。下表给出了每一项目可以带来的期望收益以及相应每年的支出(单位：100万没有)，那么这个3年规划周期应该选择哪些项目？项目每年支出收益12315182024710403392204741155861030可用资金2525258.1 应用实例介绍问题可以化为一个对于每个项目的选择为“是-否”的决策，引入二元变量 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. 集合覆盖问题在这一类问题中，会有许多的服务装置为一些设备提供互相重叠的服务，目标就是要确定安装数目最少的装置来覆盖每一个设备（满足服务需求）。例如，几个污水处理工厂可以选择建造在几个不同的位置，在不同的位置可以服务不同的几个城市，但一个城市可以得到几个不同工厂服务的时候就是重叠服务。例为了提高城市校园的安全性，A大学的保安部门希望在校园的每条主要街道上都至少有一部电话的情况下，使得安装