第五章 运筹学 整数规划

第五章整数规划教学目的：掌握若干特殊整数规划的解法教学内容：1.整数规划问题及特点

2.分枝定界法与割平面法

3.0-1规划

4.指派问题教学重点：割平面法与指派问题教学难点：分枝定界法与割平面法学时安排：8-10学时。教学内容第一节整数规划的数学模型及解的特点第二节解纯整数规划的割平面法第三节分支定界法第四节０－１整数规划第五节指派问题第一节整数规划的数学模型及解的特点

一.整数规划问题基本概念

（1）整数规划：要求部分或全部决策变量取整数值的规划问题。（2）整数规划问题的松弛问题：不考虑整数条件的规划问题。（3）整数线性规划——部分或全部变量取整数值的线性规划分类：

纯整数线性规划（pureintegerlinearprogramming)

混合整数线性规划（mixed

integerlinearprogramming)

０-１整数线性规划(zero-one

integerlinearprogramming）二.整数规划问题的数学模型

三.整数规划问题的特点问题：能否将松弛问题的最优解近似作为整数规划问题的最优解？例１：求下述整数规划的最优解。三.整数规划问题的特点1234567x115234x2A(3.25,2.5)maxZ=3x1+2x22x1+3x2≤14x1+0.5x2

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

三、整数规划问题的特点

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

C′⊂C

整数规划的可行解是松弛问题可行解集合的一个子集。所以⑴IP的可行解一定是它的松弛问题的可行解。⑵IP的最优值不会优于其松弛问题的最优值。第二节割平面法112-x1+x2=13x1+x2=4maxZAA(3/4,7/4)C(1,1)第二节割平面法

一、基本思想：在IP的松弛问题中,每次增加一个线性约束，即Gomory约束或割平面。它的作用是：割去可行域中不包含问题整数解的部分，使松弛问题的可行域逐步缩小；最终，目标函数值达到最优的整数点成为缩减可行域的一个顶点。二、求解步骤１、求出松弛问题最优解，若为整数，则停止，否则转２２、构造割平面方程。构造的割平面约束应当具备两个性质：⑴已获得的非整数最优解不满足该线性约束，从而保证在以后的解中不可能再出现。⑵所有的整数解皆满足该线性约束，从而保证整数最优解始终都保留在以后每次所形成的新的线性规划的可行域中。3-10003-1013/79/731/71000101/7-2/7-3/70012/73/722/700-5/70-3/7X4=31/7不是整数，该行对应的方程是：CBXBbx1x2x3x4x5x1x2x4X4-3/7x3+22/7x5=31/7基变量（整数）非基变量（整数）-3/7=-1+4/7

22/7=3+1/731/7=4+3/7

在上述式子中，除第一部分X4

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

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

IP的所有整数可行解都满足此式构造割平面约束的一般方法如下：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为非基变量通常，从最优单纯形表中，选择具有最大分数部分的非整分量bm所在行构造割平面约束，可以提高切割效果，减少切割次数。例２用割平面法求解纯整数规划。解:1、用单纯形法求得松弛问题的最优表如下。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。割平面方程为：CBXBbx1x2x3x4x5x1x2x43-100003-10013/79/731/7-6/7100001001/7-2/7-3/7-1/700102/73/722/7-2/7000100-5/70-3/70

将割平面约束⑴变为等式约束后，并入松弛问题的最优表中，见下表。CBXBbx1x2x3x4x5x1x2x4x6x63-100003-10015/45/27/41000010000100-1/4-1/21/400011-5/4-11/2-3/4000-1/40-17/4利用对偶单纯形法求出最优解，见下表。CBXBbx1x2x3x4x5x1x2x3x5x6由上表第四行产生的割平面约束为：3-1000003-100015/45/27/41000001000001000-1/4-1/21/4-1/40001010-5/40-11/20-3/40-1/41000-1/40-17/40x1x2x3x5CBXBbx1x2x3x4x5x6x7-3/4x73-1000003-10001241100000100000100000010001010-1-1-5-2-111-400000-4-1x1x2x3x5CBXBbx1x2x3x4x5x6x43x73x1-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-x2F例32x1+x2≤64x1+5x2≤20x1,x2≥0且为整数maxZ=x1+x21、求出松弛问题的最优解2x1+x2+x3=64x1+5x2+x4=20x1,x2,

x3,x4≥0且为整数maxZ=x1+x2110015/3105/6-1/618/301-2/31/300-1/6-1/6x1x2CBXBbx1x2x3x42、构造割平面11000

15/3105/6-1/6018/301-2/31/30

0-2/300-5/6-5/6100-1/6-1/60x1x2CBXBbx1x2x3x4x5x511000

11100-11116/50101-4/5

04/50011-6/50000-1/5x1x2CBXBbx1x2x3x4x3x53、构造割平面110000

11100-110116/50101-4/5004/50011-6/50

0-4/50000-4/510000-1/50x1x2CBXBbx1x2x3x4x3x5x6x6110000

10100-105/41401010-10200110-3/20100001-5/400000-1/4x1x2CBXBbx1x2x3x4x3x5x5x62x1+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)

例1：某公司欲在东、西、南三区建立门市部，共有7个地方可供选择。规定:在东区，由A1、A2、A3三个点中至多选两个；在西区，由A4、A5两点中至少选一个；在南区，由A6、A7两点中至少选一个。选用Ai点，投资为bi元，每年可获利润ci元，但投资总额不能超过B元。问应选择哪几个点可使年利润最大？解：设一、0-1型整数规划问题的描述：

0-1变量作为逻辑变量，常用来表示系统处于某个特定状态，或对某个决策方案的选择。第三节:０-１型整数规划例2含有相互排斥的约束条件问题。1200.40.24025利润（元／件）1500.50.3B31000.10.2B2250工时限额（h/周）0.7A20.3A1B1产品工时／件工序方式Ⅰ方式Ⅱ要求B3只能从加工方式Ⅰ与Ⅱ中选择一种，那么工厂应如何安排生产，才能使总利润最大？解：设生产两种产品分别为x1与x2件。当工序B3选用加工方式Ⅰ，即满足当工序B3不选用加工方式Ⅰ当工序B3选用加工方式Ⅱ，即满足当工序B3不选用加工方式Ⅱ方式Ⅰ与Ⅱ中选择一种等价于该问题也可以令当工序B3采用加工方式Ⅰ

当工序B3采用加工方式Ⅱ则，仅从加工方式中选择一种等价于：设：P个约束条件中有q个约束起作用，令当第i个约束起作用

当第i个约束不起作用相互排斥约束的一般情况。则该问题等价于例3试利用0-1变量将下列各约束条件表示成一般的线性约束条件。⑴x1+x2≤3或2x1+3x2≥8解：令选第一个约束选第二个约束则原命题等价于⑵则⑶若x2≤4,则x5≥0;否则，x5≤3。设则（4）用0-1变量表示整数变量。任何一个整数变量x≤u，可以表示为：其中，K满足2k+1≥u+1。例如，x≤9，可以表示为：

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

、y1、y2、y3为0-1变量。

枚举法是解0-1规划的一种算法。具体做法是：检查每个变量等于0或1的所有组合。满足所有约束条件，且使目标函数值最优的组合就是0-1规划的最优解。由于n个变量时，须检查2n个变量组合，而当n>15时，这几乎是不可能的。所以，有人提出了隐枚举法。二、0-1型整数规划的解法——隐枚举法(x1,x2,x3)Z值约束条件(0,0,0)0√(0,0,1)5√(0,1,0)-2√(0,1,1)3×(1,0,0)3√(1,0,1)8√(1,1,0)1×(1,1,1)6×１、先找一个可行解,如（0,0,0)，并将其目标函数值Z=0作为下界。２、由上步得出过滤性约束条件

３、对某种变量的组合，检验其是否满足上述过滤条件，若满足且又是可行解，则修改过滤条件，重复（３）。隐枚举法步骤(x1,x2,x3)Z值约束条件过滤条件(0,0,0)0√z≥0(0,0,1)5√z≥5(0,1,0)-2(0,1,1)3(1,0,0)3(1,0,1)8√z≥8(1,1,0)1(1,1,1)6注意:上述计算步骤还可以进一步得到改善，即对极大化问题，若将目标函数中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)都为可行解，则其他变量的组合可不必考虑。(x2,x1,x3)Z值约束条件过滤条件√(0,0,0)0√√(0,0,1)5√√(0,1,1)8√√(1,1,1)6作业：P149:5.6(1)、5.8(1)第四节：分支定界法１２３x1x254321x1+9/14x2=51/14-2x1+x2=1/3maxA(3/2,10/3)x1=1x1=2BCLP2(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=4第四节:分支定界法第四节:分支定界法—步骤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+x2LP2第四节:分支定界法2定界（以求极大值为例）以最优目标函数值中最大者（针对没有分支的线性规划问题而言）为上界，以符合整数条件的各子问题中目标函数值最大者作为下界。若无整数解，在Z≥0的情况下，令Z=03比较与剪枝若上界等于下界，则停止；否则，剪去小于下界的分支。对于大于下界的分支，继续重复２（函数值较大的分支优先）。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=4LP212第四节:分支定界法使用范围:纯整数、混合整数规划9x1+7x2≤567x1+20x2≤70x1,x2≥0,且为整数maxZ=40x1+90x2LP例2: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=308X1≤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无可行解第五节指派问题一、标准形式指派问题及其数学模型二、标准形式指派问题数学模型的特点三、标准形式指派问题的解法—匈牙利解法四、非标准形式的指派问题假定n个人去做n件事，要求每人完成其中一件，每件事交给其中一个人去完成（即人与事都不闲置），每人做各种事的费用（或时间）已知，试求总费用最小的分配方案。一、标准形式指派问题及其数学模型1.问题的提出特点：（1）人和事数目相等（2）一人只能做一件事，一件事只能有一个人来做（3）目标极小化2、指派问题的数学模型事人费用人1…..人n事1事2…事nc11c12c1ncn1cn2cnnx11x12x1nxn1xn2xnnminZ=c11x11+c12x12+…+cnnxnnx11+x12+…+

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

xnn=1x11+x21+…+

xn1=1……x1n+x2n+…+

xnn=1xij=0或1；i,j=1,…,n一人只能做一件事一件事只能一人来做minZ=c11x11+c12x12+…+cnnxnnx11+x12+…+

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

xnn=1x11+x21+…+

xn1=1……x1n+x2n+…+

xnn=1xij=0或11.标准形式的指派问题是特殊的运输问题。用表上作业法求解时有2n-1个基变量，其中只有n个取“1”值，其余都取“0”值。也是特殊的０－１整数规划问题，共有解组合2n×n个，用隐枚举法也不合适。2.每一个可行解可用解矩阵来表示：

因为X中每行及每列都有且仅有一个１，所以，共有n!个可行解（n个1的分配方式）。二、指派问题数学模型的特点1、思想依据如果系数矩阵的所有元素cij≥0，而其中存在n个位于不同行不同列的零元素，则对应的指派方案总费用为零，从而也一定是最优的。如令三、匈牙利方法⑴如果从分配问题的系数矩阵C=(cij)n×n的每行（或每列）各元素分别减去一个常数，得到一个新的矩阵C′=(cij′)n×n，则以C和C′为系数矩阵的两个指派问题具有相同的最优解。2、理论基础（康尼格定理）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-k2、理论基础（康尼格定理）⑵若矩阵C的元素可分成“０”与非“０”两部分，则覆盖“０”元素的最少直线数目，等于位于不同行不同列独立零元素的最大个数。1、变换系数矩阵对各行元素分别减去该行中的最小元素，再对各列元素分别减去该列中的最小元素。直到每行每列都有0元素为止。三、匈牙利方法步骤在零元素最少的行（或列）开始，选择一个0元素，并加上标记：独立零元素的含义是：它所在行的人，已经不能再安排其他的事情做；它所在列的事（工作），已经有人去做。如此反复，直到所有的零元素都被划去为止。在此过程中，若存在零元素的闭回路，可任选其中一个零元素加标记，同时划去同行和同列中的其他零元素。０2、在变换后的矩阵中确定独立零元素

同时，划去此零元素所在行及其列的其他零元素。获标记的零元素称为独立零元素。3、覆盖(1)对没有独立零元素的行打√。(2)在已打√的行中,对元素所在的列打√。(3)在打√的列中,对独立零元素所在的行打√。(4)重复(2)和(3),直到无法打√为止。(5)对没有打√的行划线,对打√的列划线,这样就得到了能覆盖所有零元素的最少直线数目的直线集合。√√√在未被直线覆盖的元素中找出一个最小元素；对未被直线覆盖的元素所在的行（或列）中各个元素都减去这一最小元素，然后在出现负元素的列(或行）中加上这一最小元素。5、重复上述各个步骤，直至得到完全的分配方案为止。4、继续变换系数矩阵X※＝√√√√√√⑵目标函数极小化；⑴cij≥0；⑶人与工作个数相等。匈牙利方法适用范围1．最大化指派问题四、非标准形式的指派问题现准备分派4个人去做4件事，每个人做每件事所得到的利润如下表，问分派哪个人去完成哪项工作，使总利润最大？甲乙丙丁ABCD15182124192322182617161919212317人事1、最大化指派问题maxZ=15

x11+18

x12+…+17

x44x11+x12+x13+

x14=1…….x41+x42+x43+

x44=1x11+x21+x31+

x41