运筹学第五章

1第五章整数规划第五章整数规划学时安排：8学时教学目的：掌握若干特殊整数规划的解法教学内容：1.整数规划问题及特点2.分枝定界法与割平面法3.0-1规划4.指派问题教学重点：割平面法与指派问题教学难点：分枝定界法与割平面法2第五章整数规划教学内容第一节整数规划问题的提出第二节解纯整数规划的割平面法第三节分支定界法第四节０-１整数规划第五节指派问题3第一节整数规划问题的提出整数规划问题基本概念整数规划问题的数学模型整数规划解的特点第五章整数规划41.基本概念整数规划：要求部分或全部决策变量取整数值的规划问题。整数规划问题的松弛问题：不考虑整数条件的规划问题。整数线性规划：整数规划为线性规划纯整数线性规划（pureintegerlinearprogramming)

混合整数线性规划（mixedintegerlinearprogramming）

0-1整数线性规划(zero-oneintegerlinearprogramming）注意：后面提到的整数规划，一般指的都是整数线性规划。第五章整数规划52.整数规划数学模型的一般形式第五章整数规划63.整数规划解的特点问题：能否将松弛问题最优解的近似值（取整、四舍五入）作为整数规划问题的最优解？例1：求下述整数规划的最优解。第五章整数规划7第五章整数规划1234567x115234x2A(3.25,2.5)2x1+3x2=14X1+0.5x2

=4.5Z=3x1+2x2最优解为(4,1)8第五章整数规划结论：⑴不能把松弛问题的最优解通过“四舍五入”或“截尾”（即凑整）处理后作为整数规划的最优解。不过，在变量取值很大时，用上述方法得到的解与最优解差别不大。⑵点(4,1)不是可行域的顶点，所以直接用图解法或单纯形法无法求出整数规划问题的最优解．9第五章整数规划

整数线性规划的解与松弛问题的解既有联系，又有本质的区别。设IP的松弛问题的可行域为C，IP的可行域为C′，则有

C′⊂C

整数规划的可行解是松弛问题可行解集合的一个子集。所以：⑴IP的可行解一定是它的松弛问题的可行解。⑵IP的最优值不会优于其松弛问题的最优值。10第二节割平面法割平面方法的基本思想和步骤构造割平面约束的方法示例第五章整数规划112-x1+x2=13x1+x2=4maxZAA(3/4,7/4)C(1,1)1.割平面方法的基本思想和步骤基本思想：在IP问题的松弛问题中依次引进线性约束（称Gomory约束或割平面），使问题的可行域逐步缩小，所割去的区域仅包含问题的部分非整数解；当规划问题的最优解恰好位于缩小的可行域的一个顶点时，算法结束。第五章整数规划求解步骤：第五章整数规划求出松弛问题最优解，若为整数，则停止，否则转２构造割平面方程。构造的割平面约束应当具备两个性质：已获得的非整数最优解不满足该线性约束，从而保证在以后的解中不可能再出现。所有的整数解皆满足该线性约束，从而保证整数最优解始终都保留在以后每次所形成的新的线性规划的可行域中。14第五章整数规划3-10003-1013/79/731/71000101/7-2/7-3/70012/73/722/700-5/70-3/7X4=31/7不是整数，该行对应的方程是：CBXBbx1x2x3x4x5x1x2x4第五章整数规划X4-3/7x3+22/7x5=31/7基变量（整数）非基变量（整数）-3/7=-1+4/7

22/7=3+1/731/7=4+3/7在上述式子中，除第一部分X4

（即整数部分）外，我们将后面变量的系数与常数项皆化为两部分：不超过该数的最大整数与非负分数，即16第五章整数规划

将整数部分放在等式的左边,其余部分放在右边,得：17第五章整数规划上式的左边是一个整数，右边是一个小于１的数，因此，右边是一个小于或等于０的整数，即通过分析，可以得出上式具有如下两个性质：①松弛问题的非整数最优解不满足该式②

IP的所有整数可行解都满足此式18第五章整数规划构造割平面约束的一般方法如下：1、在松弛问题的最优表中，设b列的第k个分量bk为非整数，可将它分解为整数和非整数部分之和，即bk=Nk+fk，

Nk＜bk

且为整数，0＜fk＜1。2、然后，第k行中的每一个非基变量xj的系数akj也分解为整数与非负数之和的形式，即akj=Nkj+fkj;Nkj≤akj;0≤fk＜1,则割平面方程为：xj为非基变量通常，从最优单纯形表中，选择具有最大分数部分的非整分量所在行构造割平面约束，可以提高切割效果，减少切割次数。19第五章整数规划例２：用割平面法求解纯整数规划。解:1、用单纯形法求得松弛问题的最优表如下。20第五章整数规划3-10003-1013/79/731/71000101/7-2/7-3/70012/73/722/700-5/70-3/7⑴

松弛问题的最优解为非整数,而在13/7=1+6/7

，9/7=1+2/7，31/7=4+3/7的非负分数中,6/7最大。所以，将13/7所在的行中非基变量所对应的系数进行分解:1/7=0+1/72/7=0+2/7。割平面方程为：CBXBbx1x2x3x4x5x1x2x421第五章整数规划3-100003-10013/79/731/7-6/7100001001/7-2/7-3/7-1/700102/73/722/7-2/7000100-5/70-3/70

将割平面约束⑴变为等式约束后，并入松弛问题的最优表中，见下表。CBXBbx1x2x3x4x5x1x2x4x6x622第五章整数规划3-100003-10015/45/27/41000010000100-1/4-1/21/400011-5/4-11/2-3/4000-1/40-17/4利用对偶单纯形法求出最优解，见下表。CBXBbx1x2x3x4x5x1x2x3x5x623第五章整数规划由上表第四行产生的割平面约束为：3-1000003-100015/45/27/41000001000001000-1/4-1/21/4-1/40001010-5/40-11/20-3/40-1/41000-1/40-17/40x1x2x4x6CBXBbx1x2x3x4x5x6x7-3/4x724第五章整数规划3-1000003-10001241100000100000100000010001010-1-1-5-2-111-400000-4-1x1x2x4x6CBXBbx1x2x3x4x5x6x43x725第五章整数规划3x1-2x2=35x1+4x2=102x1+x2=5ABCDmax

12315234-1/7x3-2/7x5≤

-6/7x1≤1-1/4x4-1/4x6≤-3/4x1+x2≥3x1≤1x1+x2≥3EF3x1-2x2≤35x1+4x2≥102x1+x2≤5maxZ=3x1-x23x1-2x2+

x3=35x1+4x2–

x4=102x1+x2+

x5=5maxZ=3x1-x2F26第五章整数规划案例32x1+x2≤64x1+5x2≤20x1,x2≥0且为整数maxZ=x1+x21、求出松弛问题的最优解2x1+x2+x3=64x1+5x2+x4=20x1,x2,

x3,x4≥0且为整数maxZ=x1+x227第五章整数规划110015/3105/6-1/618/301-2/31/300-1/6-1/6x1x2CBXBbx1x2x3x42、构造割平面第五章整数规划11000

15/3105/6-1/6018/301-2/31/300-2/300-5/6-5/6100-1/6-1/60x1x2CBXBbx1x2x3x4x5x5第五章整数规划11000

11100-11116/50101-4/504/50011-6/50000-1/5x1x2CBXBbx1x2x3x4x3x53、构造割平面第五章整数规划110000

11100-110116/50101-4/5004/50011-6/500-4/50000-4/510000-1/50x1x2CBXBbx1x2x3x4x3x5x6x6第五章整数规划110000

10100-105/41401010-10200110-3/20100001-5/400000-1/4x1x2CBXBbx1x2x3x4x3x5x5x6第五章整数规划2x1+x2≤64x1+5x2≤20x1,x2≥0且为整数maxZ=x1+x2

123451523462x1+x2=64x1+5x2=20maxZA(5/3,8/3)B(1,16/5)C(9/5,12/9)D(0,4)E(2,2)F(1,3)第三节分支定界法一、分支定界法步骤二、示例第五章整数规划第五章整数规划１２３x1x254321x1+9/14x2=51/14-2x1+x2=1/3maxA(3/2,10/3)x1=1x1=2BC第五章整数规划LP2(CGE):C(2,23/9);Z=41/9LP1(BFD):B(1,7/3);Z=10/3不可能区域１２３５４３２１０x1x2maxABCx1=1x1=2EDFGMHLP21(HMEG):M(33/14,2);Z=61/14x1=3NLLP212(NEL):N(3,1);Z=4LP211(HG):H(2,2);Z=436一、分支定界法步骤第五章整数规划1分支假设松弛问题的最优解不是整数解，则选择一个非整数分量构造两个约束条件：分别加入松弛问题中，得到两个子问题LP1与LP2,即后继问题，并求解之。x1+9/14x2≤51/14-2x1+x2≤1/3x1≤1x1,x2≥0,且为整数maxZ=x1+x2LP1x1+9/14x2≤51/14-2x1+x2≤1/3x1≥2x1,x2≥0,且为整数maxZ=x1+x2LP237一、分支定界法步骤第五章整数规划2定界（以求极大值为例）以最优目标函数值中最大者（针对没有分支的线性规划问题而言）为上界，以符合整数条件的各子问题中目标函数值最大者作为下界。若无整数解，在Z≥0的情况下，令Z=03比较与剪枝若上界等于下界，则停止；否则，剪去小于下界的分支。对于大于下界的分支，继续重复２（函数值较大的分支优先）。38第五章整数规划X1≤1X1≥2X2≤2X2≥3X1≤2X1≥3LP0S:X1=3/2；X2=10/3；Z0=29/6S2X1=1,X2=7/3,Z=10/3LP1S1X1=2,X2=23/9,Z=41/9LP2S11X1=33/14,X2=2,Z=61/14LP21无可行解LP22S111X1=3,X2=1,Z=4LP211S112X1=2,X2=2,Z=4LP21239第五章整数规划使用范围:纯整数、混合整数规划9x1+7x2≤567x1+20x2≤70x1,x2≥0,且为整数maxZ=40x1+90x2LP例2:40第五章整数规划9x1+7x2=561

2

3456789x1x2123456787x1+20x2=70maxZx1=4x1=5B(4,2.1);Z=349x2=2x2=3E(4,2);Z=340D(1.42,3);Z=327C(5,1.57);Z=341x2=1LP2(OGBH):BLP1(MKC):CHMA(4.81,1.82)GOKF(5.44,1);Z=30841第五章整数规划X1≤4X1≥5X2≤2X2≥3X2≤1X2≥2LP0S:X1=4.81；X2=1.82；Z0=356S1X1=5,X2=1.57,Z=341LP1:CS2X1=4,X2=2.1,Z=349LP2:BX1=4,X2=2,Z=340S21LP21:EX1=1.42,X2=3,Z=327LP22:DS11X1=5.44,X2=1,Z=308LP11:FLP12无可行解第四节0-1整数规划一、0-1变量及其应用二、0-1规划的隐枚举法第五章整数规划43注：决策时，如果要考虑某个特定方案是否被选取（即多个方案不一定全用），可以使用0-1变量。【例1】某公司欲在东、西、南三区建立门市部，共有7个门市部可供选择。规定；在东区，由A1、A2、A3三个点中至多选两个；在西区，由A4、A5两点中至少选一个；在南区，由A6、A7两点中至少选一个。选用Ai点，投资为bi元，，每年可获利润ci元，但投资总额不能超过B元。问应选择哪几个点可使年利润最大？一、0-1变量及应用第五章整数规划44解：设Ai被选用Ai不被选用则问题变为第五章整数规划45【例2】含有相互排斥的约束条件问题120150100250工时限额（h/周）400.40.50.10.7A2250.20.30.20.3A1利润（元／件）B3方式1方式2B2B1工时/件工序产品第五章整数规划46要求B3只能从加工方式Ⅰ与Ⅱ中选择一种，那么工厂应如何安排生产，才能使总利润最大？设生产两种产品分别为x1与x2件当工序B3选用加工方式Ⅰ，即满足当工序B3不选用加工方式Ⅰ当工序B3选用加工方式Ⅱ，即满足当工序B3不选用加工方式Ⅱ第五章整数规划47当工序B3选用加工方式Ⅰ，即满足当工序B3不选用加工方式Ⅰ当工序B3选用加工方式Ⅱ，即满足当工序B3不选用加工方式Ⅱ方式Ⅰ与Ⅱ中选择一种等价于第五章整数规划48则数学模型为：第五章整数规划49该问题也可以令：当工序B3采用加工方式Ⅰ当工序B3采用加工方式Ⅱ则从两种加工方式中选择一种等价于：第五章整数规划50一般情形下，如果有P个约束条件，q个起作用可以令：当第i个起作用当第i个不起作用则问题转化为：第五章整数规划51【例3】试利用0-1变量将下列各约束条件表示成一般的线性约束条件。⑴解：设选第一个约束选第二个约束则原命题等价于第五章整数规划52⑵x3只能取r1,r2,…,rk中的一个。⑶若x2≤4,则x5≥0；否则，x5≤3设x3取ri否则则设当x2≤4；当x2＞4第五章整数规划53则（4）当变量可以取多个整数值时，可以用多个0-1变量来表示，例如，x≤9可以表示为

x=20y0+21y1+22y2+23y3≤9

其中，y0,y1,y2,y3是0-1变量。第五章整数规划54二、0-1规划的隐枚举法枚举法是解0-1规划的一种算法。具体方法就是检查每个变量等于0或1的所有组合。满足所有约束条件，且使目标函数值达到最优的组合就是0-1规划的最优解。由于当0-1变量有n个时，须检查2n个变量组合，而当n>15时，这几乎是不可能的。所以有人提出隐枚举法。第五章整数规划55寻找一种方法，使问题在达到最优解之前，仅须依次检查所有可能变量组合的很少一部分。下面介绍两种这样的方法。求解步骤：【例4】求解1.隐枚举方法的求解思路和方法第五章整数规划56１、先找一个可行解,如（0,0,0)，并将其目标函数值z=0

作为下界；２、由上步得出过滤条件

3x1-2x2+5x3≥0３、对某种变量的组合，检验其是否满足上述过滤条件，若满足且又是可行解，则修改过滤条件。重复步骤3。第五章整数规划57第五章整数规划(x2,x1,x3)Z值约束条件过滤条件√(0,0,0)0√√(0,0,1)5√√(0,1,1)8√√(1,1,1)658第五章整数规划注意:上述计算步骤还可以进一步得到改善，即对极大化问题，若将目标函数中xj的价值系数按递增（不减）的次序排列（求极小，价值系数按照递减的次序排列）。即则可知(0,0,1)的目标值一定不小于(0,1,0)及(1,0,0)的目标值。同样(0,1,1)的目标值一定不小于(1,1,0)与(1,0,1)的目标值。故若(0,0,0)、(0,0,1)、(0,1,1)、(1,1,1)都为可行解，则其他变量的组合可不必考虑。第五章整数规划59第五节指派问题一、指问题的标准形式及数学模型二、匈牙利方法三、非标准形式的指派问题601、指派问题（assignmentproblem)假定n个人去做n件事，并指定每人完成其中一项，每项交给其中一个人去完成（即人与事一一对应)，问应如何分配才能使完成这件事的总费用最少。2、标准形式的数学模型指派问题的系数矩阵设第i人完成第j件事的费用为cij

，则称一、指派问题的标准形式及数学模型第五章整数规划61为指派问题的系数矩阵（coefficientmatrix)或效率矩阵。令指派第i人做第j件事不指派第i人做第j件事则数学模型为：第五章整数规划62可以看出：⑴标准形式的指派问题是特殊的运输问题。也是特殊的0-1整数规划问题。⑵每一个可行解可用一个解矩阵表示X中每行及每列都有且仅有一个１，所以共有个可行解。第五章整数规划63第五章整数规划1、思想依据如果系数矩阵的所有元素cij≥0，而其中存在n个位于不同行不同列的零元素，则对应的指派方案总费用为零，从而也一定是最优的。如令二、匈牙利方法64问题：如何产生或者寻找n个位于不同行不同列的零元素定理1、如果从分配问题的系数矩阵的每行（或每列）各元素分别减去(或加上)一个常数，得到一个新的矩阵则以C和C′为系数矩阵的两个指派问题有相同的最优解（见下页）。2、理论基础（康尼格定理）第五章整数规划65第五章整数规划minZ=c11x11+c12x12+…+cnnxnnx11+x12+…+

x1n=1…….xn1+xn2+…+

xnn=1x11+x21+…+

xn1=1……x1n+x2n+…+

xnn=1xij=0或1minZ(1)=(c11–k)x11+(c12–k)

x12+…+(c1n–k)x1n+c21x21+…+cnnxnnminZ(1)=c11x11+c12x12+…+cnnxnn-k(x11+x12+…+x1n)

=c11x11+c12x12+…+cnnxnn-k66第五章整数规划67第五章整数规划⑵若矩阵C的元素可分成“０”与非“０”两部分，则覆盖“０”元素的最少直线数目，等于位于不同行不同列独立零元素的最大个数。68第五章整数规划1、变换系数矩阵对各行