第八章整数规划

第八章整数规划第一节整数规划的图解法第二节分枝定界法整数规划（IntegerProgramming，简称IP）整数规划中要求部分或全部决策变量取整数值。根据规划模型是否为线性，可分为整数线性规划（ILP）和整数非线性规划（INLP）。根据受整数约束的变量范围，可分为纯整数规划（PureIP）、混合整数规划（MixedIP）和0－1规划。第一节整数规划的图解法对二维ILP问题，图解法是最简单的。解法：在LP问题最优解基础上，让目标函数等值线逆着其法线方向朝可行域内平移，首次碰到的整数点（ILP的整数可行解），即为ILP问题的最优解。

例、某厂拟用火车装运甲、乙两种货物集装箱，每箱的体积、重量、可获利润以及装运所受限制如下：货物集装箱体积(米3)重量(百斤)利润(百元) 甲5220乙 4510托运限制24 13 问两种货物各装运多少箱，可使获得利润最大？例：设甲、乙两种货物装运箱数分别为x1和x2。显然，x1、x2都要求为整数,于是可建立整数规划模型如下：

Maxz＝20x1+10x2

s.t.5x1+4x2≤24(1)2x1+5x2≤13(2)x1,x2≥0(3)x1,x2为整数(4)它和线性规划问题的区别在于条件(4)。x1x2（4.8，0）O找到的第一个整数点（4，1），即IP问题的最优解解决整数规划的两种初始想法：1、一一列举所有可行方案；2、先放弃整数性要求，求得一个LP问题的最优解后，然后用四舍五入法取整数解。整数规划问题的解法值得探讨。第二节分枝定界法首先，理解一个问题：原问题与松弛问题解的关系？一般将一个规划问题去掉若干约束条件而得到的规划问题称为原问题的松弛问题；例如：S1→S2（松弛问题）

Maxz=6x1+5x2

2x1+x2≤9

5x1+7x2≤35

x1≥0，x2≥0x2≤2s.t.减少条件形成松弛问题S2减少条件x2≤2后，x1、x2的取值范围（设为S2）比最初（设为S1）大，如图S2S1因为S1S2，所以z=6x1+5x2在S2上的最大值不超过S2上的最大值（因S1上的最大值也是S2上的值）。∪对于目标函数最小化的问题亦然。意义：松弛问题的目标函数值比原问题的目标函数值更优。IP问题去掉整数性约束，一般称为该IP问题的伴随LP问题；伴随LP问题是IP问题的一个松弛问题；对伴随LP问题的解，可称之为IP问题的LP解；伴随LP问题的最优值一定比IP问题的更优。例求解IP问题Maxz=40x1+90x29x1+7x2≤

567x1+20x2≤70x1,x2≥0,整数R0:z0=356x1=4.81x2=1.82R1:z1=349x1=4.00x2=2.10R2:z2=341x1=5.00x2=1.57R12:z12=327x1=1.42x2=3.00x2≥3R11:z11=340x1=4.00x2=2.00R21:z21=308x1=5.44x2=1.00R22:无可行解x1≤4x2≤1x1≥5x2≥2伴随问题R0为:Maxz=40x1+90x29x1+7x2≤567x1+20x2≤70x1,x2≥0问题R2为:Maxz=40x1+90x29x1+7x2≤567x1+20x2≤

70x1≥5x1,x2≥

0问题R1为:Maxz=40x1+90x29x1+7x2≤567x1+20x2≤

70x1≤4x1,x2≥0x2≤2问题R11为:Maxz=40x1+90x29x1+7x2≤567x1+20x2≤

70x1≤4x2≤2x1,x2≥0问题R12为:Maxz=40x1+90x29x1+7x2≤567x1+20x2≤

70x1≤4x2≥3x1,x2≥

0三点说明1、分支顺序：目标值大的先分支；2、下级分支问题的最优值一定比上级分支问题的最优值小。3、各分支的取舍：若已取得一整数可行解，凡是目标函数值小于该整数可行解的分支都可以舍去。对目标函数最大化的IP问题R，其伴随LP问题为R0，分枝定界法的步骤为：(1)用观察法求R的一个可行解。其目标值便是R的最优目标值z*的一个下界z。(2)求解R0，得R0的最优解x(0)和最优值z0。若x(0)符合R的整数条件，则显然x(0)也是R的最优解，结束；否则，以R0作为一个分枝标明求解的结果，z0是问题R的最优目标值z*的一个上界z。(3)分枝。取目标函数值最大的一个枝Rs，在Rs的解中任选一不符合整数条件的变量xj，其值为bj，构造两个约束条件xj≤[bj]和xj≥[bj]+1。将两个约束条件分别加入问题Rs，得两个后继规划问题Rs1和Rs2。不考虑整数条件求解这两个后继问题，以每个后继问题为一分枝标明求解的结果。(4)定界。在各分枝中找出