运筹学第五章课件

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

2、题：不考虑整数条件的规划问题。 整数线性规划：整数规划为线性规划 纯整数线性规划（pure integer linear programming) 混合整数线性规划（mixed integer linear programming） 0-1整数线性规划(zero-one integer linear programming） 注意：后面提到的整数规划，一般指的都是整数线性规划。,第五章 整数规划,5,2. 整数规划数学模型的一般形式,第五章 整数规划,6,3. 整数规划解的特点,问题：能否将松弛问题最优解的近似值（取整、四舍五入）作为整数规划问题的最优解？,例1：求下述整数规划的最优解。,第五

3、章 整数规划,7,第五章 整数规划,A (3.25,2.5),2x1+3x2=14,X1+0.5x2 =4.5,Z=3x1+2x2,最优解为(4,1),8,第五章 整数规划,结论： 不能把松弛问题的最优解通过“四舍五入”或“截尾”（即凑整）处理后作为整数规划的最优解。不过，在变量取值很大时，用上述方法得到的解与最优解差别不大。 点(4,1)不是可行域的顶点，所以直接用图解法或单纯形法无法求出整数规划问题的最优解,9,第五章 整数规划,整数线性规划的解与松弛问题的解既有联系，又有本质的区别。设 IP的松弛问题的可行域为C，IP的可行域为C，则有 CC 整数规划的可行解是松弛问题可行解集合的一个子

4、集。所以： IP的可行解一定是它的松弛问题的可行解。 IP的最优值不会优于其松弛问题的最优值。,10,第二节 割平面法,割平面方法的基本思想和步骤 构造割平面约束的方法 示例,第五章 整数规划,A(3/4,7/4),C(1,1),1. 割平面方法的基本思想和步骤,基本思想： 在IP问题的松弛问题中依次引进线性约束（称Gomory约束或割平面），使问题的可行域逐步缩小，所割去的区域仅包含问题的部分非整数解；当规划问题的最优解恰好位于缩小的可行域的一个顶点时，算法结束。,第五章 整数规划,求解步骤：,第五章 整数规划,求出松弛问题最优解，若为整数，则停止，否则转 构造割平面方程。构造的割平面约束应

5、当具备两个性质： 已获得的非整数最优解不满足该线性约束，从而保证在以后的解中不可能再出现。 所有的整数解皆满足该线性约束，从而保证整数最优解始终都保留在以后每次所形成的新的线性规划的可行域中。,14,第五章 整数规划,X4=31/7不是整数，该行对应的方程是：,CB,XB,b,x1,x2,x3,x4,x5,x1,x2,x4,第五章 整数规划,X4 - 3/7 x3 + 22/7 x5 = 31/7,基变量（整数）,非基变量（整数）,-3/7 = -1+4/7 22/7= 3 + 1/7 31/7= 4 + 3/7,在上述式子中，除第一部分X4 （即整数部分）外，我们将后面变量的系数与常数项皆化

6、为两部分：不超过该数的最大整数与非负分数，即,16,第五章 整数规划,将整数部分放在等式的左边,其余部分放在右边,得：,17,第五章 整数规划,上式的左边是一个整数，右边是一个小于的数，因此，右边是一个小于或等于的整数，即,通过分析，可以得出上式具有如下两个性质：,松弛问题的非整数最优解不满足该式,IP的所有整数可行解都满足此式,18,第五章 整数规划,构造割平面约束的一般方法如下： 1、在松弛问题的最优表中，设b列的第k个分量bk为非整数，可将它分解为整数和非整数部分之和，即bk =Nk + fk ， Nk bk 且为整数，0 fk 1。 2、然后，第k行中的每一个非基变量 xj的系数 ak

7、j也分解为整数与非负数之和的形式，即 akj= Nkj + fkj ;Nkj akj ; 0 fk 1,则割平面方程为：,xj为非基变量,通常，从最优单纯形表中，选择具有最大分数部分的非整分量所在行构造割平面约束，可以提高切割效果，减少切割次数。,19,第五章 整数规划,例：用割平面法求解纯整数规划。,解: 1、用单纯形法求得松弛问题的最优表如下。,20,第五章 整数规划,松弛问题的最优解为非整数,而在13/7=1+6/7 ，9/7=1+2/7 ， 31/7=4+3/7的非负分数中,6/7最大。所以，将13/7所在的行中非基变量所对应的系数进行分解: 1/7=0+1/7 2/7=0+2/7。割

8、平面方程为：,21,第五章 整数规划,将割平面约束变为等式约束后，并入松弛问题的最优表中，见下表。,22,第五章 整数规划,利用对偶单纯形法求出最优解，见下表。,23,第五章 整数规划,由上表第四行产生的割平面约束为：,24,第五章 整数规划,25,第五章 整数规划,E,26,第五章 整数规划,案例3,1、求出松弛问题的最优解,27,第五章 整数规划,x1,x2,CB,XB,b,x1,x2,x3,x4,2、构造割平面,第五章 整数规划,x1,x2,CB,XB,b,x1,x2,x3,x4,x5,x5,第五章 整数规划,x1,x2,CB,XB,b,x1,x2,x3,x4,x3,x5,3、构造割平面

9、,第五章 整数规划,x1,x2,CB,XB,b,x1,x2,x3,x4,x3,x5,x6,x6,第五章 整数规划,x1,x2,CB,XB,b,x1,x2,x3,x4,x3,x5,x5,x6,第五章 整数规划,B(1,16/5),C(9/5,12/9),D(0,4),E(2,2),F(1,3),第三节 分支定界法,一、分支定界法步骤,二、示例,第五章 整数规划,第五章 整数规划,B,C,第五章 整数规划,LP2(CGE): C(2,23/9);Z=41/9,LP1(BFD): B(1,7/3);Z=10/3,M,H,LP21(HMEG): M(33/14,2);Z=61/14,x1=3,N,L,

10、LP212(NEL): N(3,1);Z=4,LP211(HG): H(2,2);Z=4,36,一、分支定界法步骤,第五章 整数规划,1分支 假设松弛问题的最优解不是整数解，则选择一个非整数分量构造两个约束条件：,分别加入松弛问题中，得到两个子问题LP1与LP2, 即后继问题，并求解之。,37,一、分支定界法步骤,第五章 整数规划,2定界（以求极大值为例） 以最优目标函数值中最大者（针对没有分支的线性规划问题而言）为上界，以符合整数条件的各子问题中目标函数值最大者作为下界。若无整数解，在Z0的情况下，令Z=0 3比较与剪枝 若上界等于下界，则停止；否则，剪去小于下界的分支。对于大于下界的分支，

11、继续重复（函数值较大的分支优先）。,38,第五章 整数规划,X11,X12,X22,X23,X12,X13,39,第五章 整数规划,使用范围:纯整数、混合整数规划,40,第五章 整数规划,9x1+7x2 = 56,7x1+20 x2 =70,x1=4,x1=5,LP2(OGBH):B,LP1(MKC):C,H,M,41,第五章 整数规划,X14,X15,X22,X23,X21,X22,第四节 0-1 整数规划,一、0-1变量及其应用,二、0-1规划的隐枚举法,第五章 整数规划,43,注：决策时，如果要考虑某个特定方案是否被选取（即多个方案不一定全用），可以使用0-1变量。 【例1】某公司欲在东

12、、西、南三区建立门市部，共有7个门市部可供选择。规定；在东区，由A1、A2、A3三个点中至多选两个；在西区，由A4、A5两点中至少选一个；在南区，由A6、A7两点中至少选一个。选用Ai点，投资为bi元，每年可获利润ci元，但投资总额不能超过B元。问应选择哪几个点可使年利润最大？,一、0-1变量及应用,第五章 整数规划,44,解：设,则问题变为,第五章 整数规划,45,【例2】含有相互排斥的约束条件问题,120,150,100,250,工时限额（h/周）,40,0.4,0.5,0.1,0.7,A2,25,0.2,0.3,0.2,0.3,A1,利润 （元件）,B3 方式1 方式2,B2,B1,工时

13、/件 工序 产品,第五章 整数规划,46,要求B3只能从加工方式与中选择一种，那么工厂应如何安排生产，才能使总利润最大？,设生产两种产品分别为x1与x2件,第五章 整数规划,47,方式与中选择一种等价于,第五章 整数规划,48,则数学模型为：,第五章 整数规划,49,该问题也可以令：,则从两种加工方式中选择一种等价于：,第五章 整数规划,50,一般情形下，如果有 P个约束条件，q个起作用,可以令：,则问题转化为：,第五章 整数规划,51,【例3】试利用0-1变量将下列各约束条件表示成一般的线性约束条件。,解： 设,则原命题等价于,第五章 整数规划,52,x3只能取r1, r2, , rk中的一

14、个。,若x24,则x50；否则， x53,则,第五章 整数规划,53,则,（4）当变量可以取多个整数值时，可以用多个 0-1变量来表示， 例如， x9可以表示为 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个变量组合，而当 n15时，这几乎是不可能的。所以有人提出隐枚举法。,第五章 整数规划,5

15、5,寻找一种方法，使问题在达到最优解之前，仅须依次检查所有可能变量组合的很少一部分。下面介绍两种这样的方法。,求解步骤：,【例4】求解,1 .隐枚举方法的求解思路和方法,第五章 整数规划,56,、先找一个可行解,如（0,0,0)，并将其目标函数值z=0 作为下界；,、由上步得出过滤条件 3x1- 2x2+ 5x30,、对某种变量的组合，检验其是否满足上述过滤条件，若满足且又是可行解，则修改过滤条件。重复步骤3。,第五章 整数规划,57,第五章 整数规划,58,第五章 整数规划,注意:上述计算步骤还可以进一步得到改善，即对极大化问题，若将目标函数中xj的价值系数按递增（不减）的次序排列（求极小，

16、价值系数按照递减的次序排列）。即,则可知(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,第五节指派问题,一、指问题的标准形式及数学模型,二、匈牙利方法,三、非标准形式的指派问题,60,1、指派问题（assignment problem),假定n个人去做n件事，并指定每人完成其中一项，每项交给其中一个人去完成（即人与事一一对应)，问应如何分配才能使完成这件事的总费用最

17、少。,2、标准形式的数学模型,指派问题的系数矩阵,设第i人完成第j件事的费用为cij ，则称,一、指派问题的标准形式及数学模型,第五章 整数规划,61,为指派问题的系数矩阵（coefficient matrix)或效率矩阵。,则数学模型为：,第五章 整数规划,62,可以看出： 标准形式的指派问题是特殊的运输问题。也是特殊的0-1整数规划问题。,每一个可行解可用一个解矩阵表示,X中每行及每列都有且仅有一个，所以共有,个可行解。,第五章 整数规划,63,第五章 整数规划,1、思想依据,如果系数矩阵的所有元素cij0 ，而其中存在n个位于不同行不同列的零元素，则对应的指派方案总费用为零，从而也一定是

18、最优的。,如,令,二、匈牙利方法,64,问题：如何产生或者寻找n个位于不同行不同列的零元素,定理1、如果从分配问题的系数矩阵,的每行（或每列）各元素分别减去(或加上)一个常数，得到一个新的矩阵,则以C和C为系数矩阵的两个指派问题有相同的最优解（见下页）。,2、理论基础（康尼格定理）,第五章 整数规划,65,第五章 整数规划,minZ(1)= (c11 k)x11+ (c12 k) x12+ (c1n k)x1n + c21 x21+ cnn xnn,minZ(1) = c11 x11+ c12 x12+ cnn xnn -k(x11 + x12+ + x1n ) = c11 x11+ c12

19、x12+ cnn xnn -k,66,第五章 整数规划,67,第五章 整数规划,若矩阵C的元素可分成“”与非“”两部分，则覆盖“”元素的最少直线数目，等于位于不同行不同列独立零元素的最大个数。,68,第五章 整数规划,1、变换系数矩阵,对各行元素分别减去该行中的最小元素，再对各列元素分别减去该列中的最小元素。直到每行每列都有0元素为止。,三、匈牙利方法步骤,69,第五章 整数规划,在零元素最少的行（或列）开始，选择一个0元素，并加上标记：,独立零元素的含义是：它所在行的人，已经不能再安排其他的事情做；它所在列的事（工作），已经有人去做。 如此反复，直到所有的零元素都被划去为止。在此过程中，若存在零元素的闭回路，可任选其中一个零元素加标记，同时划去同行和同列中的其他零元素。,2、在变换后的矩阵中确定独立零元素,同时，划去此零元素所在行及其列的其他零元素。获标记的零