运筹学5 整数规划.ppt

第五章整数线性规划目录
第1节整数线性规划问题的提出
第2节分支定界解法
第3节割平面解法
第4节 0-1型整数线性规划
第5节指派问题 
第6节整数规划的计算机求解
第1节整数线性规划问题的提出
一、问题的提出:
在前面讨论的线性规划问题中,有些最优解可能是分数或小数,但对于某些具体问题,常有要求解必须是整数的情形(称为整数解)。例如,所求解是机器的台数、完成工作的人数或装货的车数等,分数或小数的解就不合要求。
回本章目录
整数规划的数学模型
一般形式
整数线性规划中如果所有的变量都限制为(非负)整数,就称为纯整数线性规划(pure integer linear programming)或称为全整数线性规划(all integer linear programming);如果仅一部分变量限制为整数,则称为混合整数规划(mixed integer linear programming)。整数线性规划的一种特殊情形是0-1规划,它的变数取值仅限于0或1。本章最后讲到的指派问题就是一个0-1规划问题。
为了满足整数解的要求,初看起来,似乎只要把已得到的带有分数或小数的解经过“舍入化整”就可以了。但这常常是不行的,因为化整后不见得是可行解;或虽是可行解,但不一定是最优解。因此,对求最优整数解的问题,有必要另行研究。我们称这样的问题为整数线性规划(integer linear programming),简称ILP或IP,整数线性规划是最近几十年来发展起来的规划论中的一个分支。
现举例说明用前述单纯形法求得的解经“舍入化整”不能保证是整数最优解。例1某厂拟用集装箱托运甲乙两种货物,每箱的体积、重量、可获利润以及托运所受限制如表5-1所示。问两种货物各托运多少箱,可使获得利润为最大?
表5-1
现在我们解这个问题,设x1,x2分别为甲、乙两种货物的托运箱数(当然都是非负整数)。这是一个(纯)整数线性规划问题,用数学式可表示为:
max z =20x1+10x2 ①
5x1+4x2≤24 ②
2x1+5x2≤13 ③()
x1,x2≥0 ④
x1,x2整数⑤
它和线性规划问题的区别仅在于最后的条件⑤。现在我们暂不考虑这一条件,即解①~④(以后我们称这样的问题为原问题的松弛问题),
很容易求得最优解为:x1=,x2=0,max z=96
但x1是托运甲种货物的箱数,现在它不是整数,所以不合条件⑤的要求。
是不是可以把所得的非整数的最优解经过“化整”就可得到符合条件⑤的整数最优解呢?如将(x1=,x2=0)凑整为(x1=5,x2=0),这样就破坏了条件②(关于体积的限制),因而它不是可行解;如将(x1=,x2=0),变为(x1=4,x2=0),这当然满足各约束条件,因而是可行解,但不是最优解,因为当x1=4,x2=0, 时z=80.
非整数的最优解在C(,0)点达到。
但当x1=4,x2=1(这也是可行解)时,z=90。