文档介绍：运筹学第三版三、整数规划第5章整数规划
三、整数规划
第5章整数规划
清华大学出版社
第5章整数规划
第1节整数线性规划问题的提出
第2节分支定界解法
第3节割平面解法
第4节 0-1型整数线性规划
第5节指派问题
清华大学出版社
第1节整数线性规划问题的提出
在前面讨论的线性规划问题中,有些最优解可能是分数或小数,但对于某些问题,常要求解必须是整数(称为整数解)。例如,所求解是机器的台数、完成工作的人数或装货的车数等。
为满足整数解的要求,初看起来,似乎只要把已得到的带有分数或小数的解经过“舍入化整”就可以了。但这常常是不行的,因为化整后不见得是可行解;或虽是可行解,但不一定是最优解。
因此,对求最优整数解的问题,有必要另行研究。我们称这样的问题为整数线性规划(integer linear programming),简称ILP。
清华大学出版社
第1节整数线性规划问题的提出
整数线性规划的分类
如果所有的变量都限制为(非负)整数,就称为纯整数线性规划(pure integer linear programming)或称为全整数线性规划(all integer linear programming)
如果仅一部分变量限制为整数,则称为混合整数规划(mixed integer linear programming)。
整数线性规划的一种特殊情形是0-1规划,即变量的取值仅限于0或1。本章最后讲到的指派问题就是一个0-1规划问题。
清华大学出版社
第1节整数线性规划问题的提出
现举例说明用单纯形法求得的解不能保证是整数最优解。
例1 某厂拟用集装箱托运甲乙两种货物,每箱的体积、重量、可获利润以及托运所受限制如表5-1所示。问两种货物各托运多少箱,可使获得利润为最大?
表5-1
清华大学出版社
第1节整数线性规划问题的提出
解:设x1,x2分别为甲、乙两种货物的托运箱数(当然都是非负整数),这就是一个(纯)整数线性规划问题,用数学模型可表示为:
max z =20x1+10x2 ①
5x1+4x2≤24 ②
2x1+5x2≤13 ③(53>.1)
x1,x2≥0 ④
x1,x2整数⑤
该问题和线性规划问题的区别仅在于最后一个约束条件⑤。
现在我们暂不考虑这一条件,即解由①~④构成的线性规划问题(以后我们称这样的问题为与原问题相应的线性规划问题)。
清华大学出版社
第1节整数线性规划问题的提出
容易求得相应的线性规划问题的最优解为
x1=,x2=0,max z=96
清华大学出版社
第1节整数线性规划问题的提出
现在来分析上述线性规划问题的最优解是否是整数规划问题的最优解
因为x1表示的是托运甲种货物的箱数,目前得到的最优解不是整数,所以不合条件⑤的要求。
是不是可以把所得的非整数最优解经过“化整”就可得到合于条件⑤的整数最优解呢?
如将(x1=,x2=0)凑整为(x1=5,x2=0),这样就破坏了条件②(关于体积的限制),因而它不是可行解;
如将(x1=,x2=0),变为(x1=4,x2=0),这当然满足各约束条件,因而是可行解,但不是最优解,因为当x1=4,x2=0, 时z=80;而当x1=4,x2=1(这也是可行解)时,z=90。
清华大学出版社
第1节整数线性规划问题的提出
图中画(+)号的点表示可行的整数解。凑整得到的(5,0)点不在可行域内,而C点又不合于条件⑤。为了满足题中要求,表示目标函数的z的等值线必须向原点平行移动,直到第一次遇到带“+”号B点(x1=4,x2=1)为止。这样,z的等值线就由z=96变到z=90,它们的差值为Δz=96-90=6,表示利润的降低,这是由于变量的不可分性(装箱)所引起的。
图5-1
清华大学出版社
第1节整数线性规划问题的提出
由上例看出,将其相应的线性规划的最优解经过“化整”来解原整数线性规划,虽是最容易想到的,但常常得不到整数线性规划的最优解,甚至根本不是可行解。因此有必要对整数线性规划的解法进行专门研究。
清华大学出版社
第2节分支定界解法
在求解整数线性规划时,如果可行域是有界的,首先容易想到的方法就是穷举所有可行的整数解,即列出图5-1中所有标有“+”的整数点,然后比较它们的目标函数值,从而确定最优解。
对于规模较小的问题,变量个数很少,可行解的组合数也较小时,这个方法是可行的,也是有效的。
如在例1中,变量只有x1和x2。由条件②,x1所能取的整数值为0、1、2、3、4共5个;由条件
③,x2所能取的整数值为0、1、2共3个。因此所有可能的整数组合(不都是可行的)数是3×5=15个,穷举法还是勉强可用的。