整数线性规划-第1-4节

《整数线性规划-第1-4节》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第5章整数规划第1节整数规划问题的提出第2节分支定界解法(选讲)第3节割平面解法(选讲)第4节0-1型整数规划第5节指派问题第1节整数线性规划问题的提出在前面讨论的线性规划问题中，有些最优解可能是分数或小数，但对于某些具体问题，常有要求解答必须是整数的情形(称为整数解)。例如，所求解是机器的台数、完成工作的人数或装货的车数等，分数或小数的解答就不合要求。为了满足整数解的要求，初看起来，似乎只要把已得到的带有分数或小数的解经过“舍入化整”就可以了。但这常常是不行的，因为化整后不见得是可行解；或虽是可行解，但不一定是最优解。因此

2、，对求最优整数解的问题，有必要另行研究。我们称这样的问题为整数规划(integerlinearprogramming)，简称ILP.整数线性规划中如果所有的变量都限制为(非负)整数，就称为纯整数线性规划(pureintegerlinearprogramming)或称为全整数线性规划(allintegerlinearprogramming)；如果仅一部分变量限制为整数，则称为混合整数规划(mixedintegerlinearprogramming)。整数线性规划的一种特殊情形是0-1规划，它的变数取值仅限于0或1。本章最后讲到

3、的指派问题就是一个0-1规划问题。第1节整数线性规划问题的提出现举例说明用前述单纯形法求得的解不能保证是整数最优解。例1某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如表5-1所示。问两种货物各托运多少箱，可使获得利润为最大?表5-1第1节整数线性规划问题的提出现在我们解这个问题，设x1，x2分别为甲、乙两种货物的托运箱数(当然都是非负整数)。这是一个(纯)整数线性规划问题，用数学式可表示为：maxz=20x1+10x2①5x1+4x2≤24②2x1+5x2≤13③(5.1)x1，x2≥0④x1，

4、x2整数⑤第1节整数线性规划问题的提出它和线性规划问题的区别仅在于最后的条件⑤。现在我们暂不考虑这一条件，即解①～④(以后我们称这样的问题为与原问题相应的线性规划问题)，也称为其松弛问题。很容易求得最优解为:x1=4.8，x2=0，maxz=96但x1是托运甲种货物的箱数，现在它不是整数，所以不合条件⑤的要求。是不是可以把所得的非整数的最优解经过“化整”就可得到合于条件⑤的整数最优解呢?如将(x1=4.8，x2=0)凑整为(x1=5，x2=0)，这样就破坏了条件②(关于体积的限制)，因而它不是可行解；如将(x1=4.8，x2

5、=0)舍去尾数0.8，变为(x1=4，x2=0)，这当然满足各约束条件，因而是可行解，但不是最优解，因为当x1=4，x2=0,时z=80.非整数的最优解在C(4.8，0)点达到。第1节整数线性规划问题的提出但当x1=4，x2=1(这也是可行解)时，z=90。图中画(+)号的点表示可行的整数解。凑整的(5，0)点不在可行域内，而C点又不合于条件⑤。为了满足题中要求，表示目标函数的z的等值线必须向原点平行移动，直到第一次遇到带“+”号B点(x1=4，x2=1)为止。这样，z的等值线就由z=96变到z=90，它们的差值Δz=96-

6、90=6表示利润的降低，这是由于变量的不可分性(装箱)所引起的。第1节整数线性规划问题的提出由上例看出，将其相应的线性规划的最优解“化整”来解原整数线性规划，虽是最容易想到的，但常常得不到整数线性规划的最优解，甚至根本不是可行解。因此有必要对整数线性规划的解法进行专门研究。第1节整数线性规划问题的提出♂返回第2节分支定界解法在求解整数线性规划时，如果可行域是有界的，首先容易想到的方法就是穷举变量的所有可行的整数组合，就像在图5-1中画出所有“+”号的点那样，然后比较它们的目标函数值以定出最优解。对于小型的问题，变量数很少，可

7、行的整数组合数也是很小时，这个方法是可行的，也是有效的。在例1中，变量只有x1和x2由条件②，x1所能取的整数值为0、1、2、3、4共5个；由条件③，x2所能取的整数值为0、1、2共3个，它的组合(不都是可行的)数是3×5=15个，穷举法还是勉强可用的。对于大型的问题，可行的整数组合数是很大的。例如在本章第5节的指派问题(这也是整数线性规划)中，将n项任务指派n个人去完成，不同的指派方案共有n!种，当n=10，这个数就超过300万；当n=20，这个数就超过2×1018，如果一一计算，就是用每秒百万次的计算机，也要几万年的功夫

8、，很明显，解这样的题，穷举法是不可取的。所以我们的方法一般应是仅检查可行的整数组合的一部分，就能定出最优的整数解。分支定界解法(branchandboundmethod)就是其中的一个.分支定界法可用于解纯整数或混合的整数线性规划问题。在20世纪60年代初由LandDoig和Dakin等人