《运筹学第五章(清华三版)》由会员分享，可在线阅读，更多相关《运筹学第五章(清华三版)（84页珍藏版）》请在金锄头文库上搜索。
1、第五章 整数规划,教学目的：掌握若干特殊整数规划的解法 教学内容：1.整数规划问题及特点2.分枝定界法与割平面法3.0-1规划4.指派问题 教学重点：割平面法与指派问题 教学难点：分枝定界法与割平面法 学时安排：4学时。,教学内容,第一节 整数规划的数学模型及解的特点 第二节 解纯整数规划的割平面法 第三节 分支定界法 第四节 0-1整数规划 第五节 指派问题,第一节 整数规划问题的提出,1.整数规划问题基本概念 2.整数规划问题的特点,1.整数规划问题基本概念,（1）整数规划：要求部分或全部决策变量取整数值的规划问题。 （2）整数规划问题的松弛问题：不考虑整数条件的规划问题。 （3）整数线性
2、规划部分或全部变量取整数值的线性规划 纯整数线性规划（pure integer linear programming) 混合整数线性规划（mixed） 0-1整数线性规划(zero-one）,2.整数规划问题的特点,问题：能否将松弛问题的最优解近似作为整数规划问题的最优解？,例5-1：求下述整数规划的最优解。,A (3.25,2.5),2x1+3x2=14,X1+0.5x2 =4.5,Z=3x1+2x2,最优解为(4,1),2.整数规划问题的特点,结论： 不能把松弛问题的最优解通过“四舍五入”或“截尾”（即凑整）处理后作为整数规划的最优解。不过，在变量取值很大时，用上述方法得到的解与最优解差别
3、不大。 点(4,1)不是可行域的顶点，所以直接用图解法或单纯形法无法求出整数规划问题的最优解,整数线性规划的解与松弛问题的解既有联系，又有本质的区别。设 IP的松弛问题的可行域为C，IP的可行域为C，则有 CC 整数规划的可行解是松弛问题可行解集合的一个子集。所以 IP的可行解一定是它的松弛问题的可行解。 IP的最优值不会优于其松弛问题的最优值。,第二节 割平面法,A(3/4,7/4),C(1,1),一、基本思想：在IP的松弛问题中,每次增加一个线性约束，即Gomory约束或割平面。它的作用是：割去可行域中不包含问题整数解的部分，使松弛问题的可行域逐步缩小；最终，目标函数值达到最优的整数点成为
4、缩减可行域的一个顶点。,二、求解步骤,、求出松弛问题最优解，若为整数，则停止，否则转 、构造割平面方程。 构造的割平面约束应当具备两个性质： 已获得的非整数最优解不满足该线性约束，从而保证在以后的解中不可能再出现。 所有的整数解皆满足该线性约束，从而保证整数最优解始终都保留在以后每次所形成的新的线性规划的可行域中。,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
5、,在上述式子中，除第一部分X4 （即整数部分）外，我们将后面变量的系数与常数项皆化为两部分：不超过该数的最大整数与非负分数，即,将整数部分放在等式的左边,其余部分放在右边,得：,上式的左边是一个整数，右边是一个小于的数，因此，右边是一个小于或等于的整数，即,通过分析，可以得出上式具有如下两个性质：, 松弛问题的非整数最优解不满足该式, IP的所有整数可行解都满足此式,构造割平面约束的一般方法如下： (1)在松弛问题的最优表中，设b列的第k个分量bk为非整数，可将它分解为整数和非整数部分之和，即bk =Nk + fk ， Nk bk 且为整数，0 fk 1。 (2)然后，第k行中的每一个非基变量
6、 xj的系数 akj也分解为整数与非负数之和的形式，即 akj= Nkj + fkj ;Nkj akj ; 0 fk 1,则割平面方程为：,xj为非基变量,通常，从最优单纯形表中，选择具有最大分数部分的非整分量所在行构造割平面约束，可以提高切割效果，减少切割次数。,例5-2 用割平面法求解纯整数规划。,解: 用单纯形法求得松弛问题的最优表如下。,松弛问题的最优解为非整数,而在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。割平面方程为：,将割平面约束
7、变为等式约束后，并入松弛问题的最优表中，见下表。,利用对偶单纯形法求出最优解，见下表。,由上表第四行产生的割平面约束为：,E,例5-3,求出松弛问题的最优解,x1,x2,CB,XB,b,x1,x2,x3,x4,构造割平面,x1,x2,CB,XB,b,x1,x2,x3,x4,x5,x5,x1,x2,CB,XB,b,x1,x2,x3,x4,x3,x5,构造割平面,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),
8、例5-4：某公司欲在东、西、南三区建立门市部，共有7个地方可供选择。规定；在东区，由A1、A2、A3三个点中至多选两个；在西区，由A4、A5两点中至少选一个；在南区，由A6、A7两点中至少选一个。选用Ai点，投资为bi元，每年可获利润ci元，但投资总额不能超过B元。问应选择哪几个点可使年利润最大？,解：设,0-1变量作为逻辑变量，常用来表示系统处于某个特定状态，或对某个决策方案的选择。,第三节 0-1整 数 规 划,一、0-1变量及其应用,例5-5 含有相互排斥的约束条件问题,120,0.4,0.2,40,25,利润 （元件）,150,0.5,0.3,B3,100,0.1,0.2,B2,250
9、,工时限额（h/周）,0.7,A2,0.3,A1,B1,产品,工时件,工序,方式 方式,要求 B3 只能从加工方式与中选择一种，那么工厂应如何安排生产，才能使总利润最大？,解：设生产两种产品分别为x1与x2件。,当工序B3选用加工方式，即满足,当工序B3不选用加工方式,当工序B3选用加工方式，即满足,当工序B3不选用加工方式,方式与中选择一种等价于,该问题也可以令,当工序B3采用加工方式,当工序B3采用加工方式,则，仅从加工方式中选择一种等价于：,设：P个约束条件中有q个约束起作用，,令,当第 i 个约束起作用,当第 i 个约束不起作用,相互排斥约束的一般情况。,则该问题等价于,例5-6 试利
10、用0-1变量将下列各约束条件表示成一般的线性约束条件。, x1+x23 或 2x1+3x28,解： 令,选第一个约束,选第二个约束,则原命题等价于,则, 若x24,则x50;否则， x53。,设,则, 用0-1变量表示整数变量。任何一个整数变量xu，可以表示为：,其中，K满足 2k+1u+1。,例如， x9，可以表示为：x = 20y0 + 21y1 + 22y2 + 23y3 ，y0 等为0-1变量。,枚举法是解0-1规划的一种算法。具体做法是：检查每个变量等于0或1的所有组合。满足所有约束条件，且使目标函数值最优的组合就是0-1规划的最优解。由于n个变量时，须检查2n个变量组合，而当 n1
11、5时，这几乎是不可能的。所以，有人提出了隐枚举法。,二、0-1规划的解法隐枚举法,例5-7,先找一个可行解,如（0,0,0)，并将其目标函数值Z=0作为下界。,由上步得出过滤性约束条件,对某种变量的组合，检验其是否满足上述过滤条件，若满足且又是可行解，则修改过滤条件，重复。,注意:上述计算步骤还可以进一步得到改善，即对极大化问题，若将目标函数中xj的价值系数按递增（不减）的次序排列（求极小，价值系数按照递减的次序排列）。即,则可知(0,0,1)的目标值一定不小于(0,1,0)及(1,0,0)的目标值。同样(0,1,1)的目标值一定不小于(1,1,0)与(1,0,1)的目标值。故若(0,0,0)
12、、(0,0,1)、(0,1,1)、(1,1,1)都为可行解，则其他变量的组合可不必考虑。,第四节 分支定界法,B,C,例5-8,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,LP212(NEL): N(3,1);Z=4,LP211(HG): H(2,2);Z=4,分支定界法步骤,1 分支 假设松弛问题的最优解不是整数解，则选择一个非整数分量构造两个约束条件：,分别加入松弛问题中，得到两个子问题LP1与LP2, 即后继问题，并求解之。,第四节:分 支
13、 定 界 法,2 定界（以求极大值为例）以最优目标函数值中最大者（针对没有分支的线性规划问题而言）为上界，以符合整数条件的各子问题中目标函数值最大者作为下界。若无整数解，在Z0的情况下，令Z=0 3 比较与剪枝若上界等于下界，则停止；否则，剪去小于下界的分支。对于大于下界的分支，继续重复2（函数值较大的分支优先）。,X11,X12,X22,X23,X1 3,X1 2,使用范围:纯整数、混合整数规划,9x1+7x2 = 56,7x1+20x2 =70,x1=4,x1=5,LP2(OGBH):B,LP1(MKC):C,H,M,X1 5,X1 4,X22,X23,X21,X22,第五节 指派问题,一
14、、标准形式指派问题及其数学模型 二、标准形式指派问题数学模型的特点 三、标准形式指派问题的解法匈牙利解法 四、非标准形式的指派问题,假定n个人去做n件事，要求每人完成其中一件，每件事交给其中一个人去完成（即人与事都不闲置），每人做各种事的费用（或时间）已知，试求总费用最小的分配方案。,一、标准形式指派问题及其数学模型,1.问题的提出,特点： （1）人和事数目相等 （2）一人只能做一件事，一件事只能有一个人来做 （3）目标极小化,2.指派问题的数学模型,x11,x12,x1n,xn1,xn2,xnn,minZ= c11 x11+ c12 x12+ cnn xnn,x11+ x12+ x1n =1 . xn1+ xn2+ xnn =1,
