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

《运筹学导论之整数线性规划.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

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

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

3、=0)，这当然满足各约束条件，因而是可行解，但不是最优解，因为当x1=4，x2=0,时z=80.非整数的最优解在C(4.8，0)点达到。6但当x1=4，x2=1(这也是可行解)时，z=90。本例还可以用图解法来说明图中(+)表示可行整数解。凑整的(5，0)不在可行域内，而C点又不合于条件⑤。目标函数z的等值线必须向原点平行移动，直到首次遇到带“+”号B点(x1=4，x2=1)为止。此时，z值就由z=96变到z=90，Δz=96-90=6表示利润的降低，这是由于变量的不可分性(装箱)所引起的。7将其相应的线性规划的最优解“化整”来解原整数线性规划，虽是最容易想到的，但往往不可

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

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

6、是x1=x2=x3=x4=1，x5=0，对应的最优值z=95.11若采用连续的线性规划问题求解，将xj=(0,1),替换为0≤xj≤1，那么最优解为x1=0.5789,x2=x3=x4=1,x5=0.7368.有部分变量取小数，这不符合实际，若采用舍入方法，则x1=x5=1，这意味着5个项目都要选择，显然是不可行解，对于采用“是否”决策问题，舍入法不可行。12习题某唱片公司与一位新的歌手签约录制8首歌曲，这8首歌曲的时间长度分别为8,3,5,5,9,6,7,12分钟，公司希望将所有的歌曲分配在磁带的两面，使得两面的歌曲时间长度尽量相同。请建立整数规划模型，求出最优解。132

7、.集合覆盖问题在这一类问题中，会有许多的服务装置为一些设备提供互相重叠的服务，目标就是要确定安装数目最少的装置来覆盖每一个设备（满足服务需求）。例如，几个污水处理工厂可以选择建造在几个不同的位置，在不同的位置可以服务不同的几个城市，但一个城市可以得到几个不同工厂服务的时候就是重叠服务。1416274583街道G街道E街道A街道B街道C街道D街道H街道I街道K街道J例为了提高城市校园的安全性，A大学的保安部门希望在校园的每条主要街道上都至少有一部电话的情况下，使得安装的电话总数最少，下图给出了校园的主要街道图15将电