管理运筹学第5章-整数规划

第五章整数规划（IP）整数规划问题；整数规划的割平面算法；整数规划的分支定界算法0-1整数规划指派问题；引例[1]：一般最优生产计划问题某工厂拟用集装箱托运甲、乙两种货物，有关资料如下表。问：甲乙两种货物各托运多少箱，可以获得最大利润？4.1整数规划问题货物体积（米3/箱）重量（吨/箱）利润（万元/箱）甲5220乙4510装运限制24米313吨设X1，X2分别表示甲、乙两种货物的托运箱数，S.T.5X1+4X2=242X1+5X2=13X1,X2=0MaxZ=20X1+10X2（LP）模型如下：S.T.5X1+4X2=242X1+5X2=13X1,X2=0MaxZ=20X1+10X2（IP）模型如下：X1,X2NX1,X2R引例[2]：约束条件可选择最优生产计划问题如果引例[1]中的集装箱运输有汽运和水运两种方式可供选择，其体积限制条件分别如下：5X1+4X2=24；（汽运）7X1+5X2=32；（水运）问：如何建立整数规划模型，可使工厂获得最大利润？设y=S.T.5X1+4X2=24+（1-y)M；7X1+5X2=32+yM；2X1+5X2=13X1,X2=0X1,X2N；y=0，1MaxZ=20X1+10X21,采用汽运方式；0,采用水运方式；则可建立（IP）模型：一、整数规划（IP）问题的性质（1）可行域：KLP/KIP；（2）最优解：X*LP/X*IP。6230x1x24引例[1]——需要研究整数规划问题的专用算法！问：如何求解上述整数规划问题？（1）四舍五入法——可能不可行；（2）完全枚举法——可能不实际；二、整数规划问题的分类（1）纯整数规划（AIP）；（2）混合整数规划（MIP）；（3）0-1规划（BIP）；——这里，Cj均为整数，j=1,2,…,n。4.2一般整数规划的分支定界算法一、算法思想设有最大化整数规划问题A,与他对应的线性规划问题B，若其最优解不符合A的整数条件，那么B的最优目标函数必是A的最优目标函数Z*的上界；而A的任意可行解的目标函数值将是Z*的下界。分支定界法就是将B的可行域分成子区域（分支），逐步减小上界，增大下界，逐步寻找到整数最优解。4.2一般整数规划的分支定界算法例1：求解下述（AIP）maxz=40x1+90x2s.t.9x1+7x2〈=567x1+20x2〈=70xj=0,整数，j=1，2（二）引例20x1x21（4.81，1.82）234561347K0’(K0’):X’0*=(4.81,1.82)TZ0*=35620x1x21（4.81，1.82）234561347(K1’)(K1’):X’1*=(4.00,2.10)TZ1*=349(K2’)(K2’):X’2*=(5.00,1.57)TZ2*=34120x1x21（4.81，1.82）234561347(K3’)(K3’):X’3*=(4.00,2.00)TZ3*=340(K2’)(K4’):X’4*=(1.42,3.00)TZ4*=327(K4’)20x1x21234561347(K3’)(K5’):X’5*=(5.44,1.00)TZ5*=308(K5’)(K6’):K’6=(K4’)（4.81，1.82）(K6’)=（二）分支定界法步骤----极大化问题将要求解的整数规划问题成为A,将与之对应的线性规划问题称为B（一）解问题B,会出现以下情况（1）B无可行解，则A无可行解----STOP（2）B有最优解，并符合A的整数条件-----最优解（3）B有最优解，但不符合A的整数条件----迭代（二）分支定界法步骤----极大化问题（二）用观察法找A的一个整数可行解，求其目标函数值，记为下界Z一般找x=0，得到z=0，成为下界（二）分支定界法步骤----极大化问题（三）分支与定界1、分支B的最优解中，任选一个不符合整数条件的x，其值为b，设【b】为小于b的最大整数，增加两个约束条件x》【b】+1；x《【b】将两个约束加入到问题中，求后继问题B1，B2的解2、定界以每一个后继问题为一个分支，标明求解结果，与其它问题的解的结果中，找到目标函数值最大者为新的上界Z，从已符合整数条件的各分支中，找最大目标函数值为新的下界z（二）分支定界法步骤----极大化问题（四）比较与剪支各分支中的最优目标函数中若有小于下界者，此支剪掉，不予考虑若大于下界者，且不符合整数条件的，重复第一步直到找到Z*=下界z，找到最优解（二）分支定界法步骤----极大化问题注意：1、下界z：必须是满足整数条件的解，得到的目标函数值2、上界Z：不需要满足整数条件3、当Z*=下界z，得到最优解三、例题与习题例1：求解下述（AIP）：maxz=3x1+4x2s.t.2x1+5x2=152x1-2x2=5xj=0,整数，j=1,24.3纯整数规划的割平面算法一、算法思想增加约束条件（割平面）：。至少切割掉X*（LP）；。切割区域不包含整数解。关键：如何增加割平面！用解线性规划的方法求解整数规划问题。首先，不考虑变量x是整数这一条件，但增加线性的约束条件（几何术语称谓割平面），使的原可行域中切割掉一部分，这部分只包含非整数解，没有切割掉任何证书可行解。此方法就是要怎么找到适当的割平面（不一定一次找到），使切割后最终得到这样的可行域，则它的一个整数坐标的极点就是原问题的最优解例[1]：Maxz=x1+x2s.t.-x1+x2=13x1+x2=4x1,x2》=0，整数（二）示例10x1x21割平面X1+2x2=3（3/4，7/4）三、求一个切割方程的步骤P121简述0-1整数规划•X=0或1•1、投资场所的选定---相互排斥的计划•2、相互排斥的约束条件•3、关于固定费用问题解0-1规划的方法•1、穷举法：•检查变量取值为0或1的每一组组合，比较目标函数值，求最优值。•2、隐枚举法：•只检查变量取值的一部分，就能求到问题的最优解，设计这样的方法，叫~~•分支定界法也是一种隐枚举法例题p124•1、用穷举法找所有的解，求目标函数值，比较-------------------32次计算•2、设计一个方法，检查解适合的条件，只要有不适合的，后面的计算省略—24次计算•3、改进方法，将检查的解范围缩小，更快的找到最优解---------11次计算4.5指派问题引例1：今有4辆装载不同货物的待卸车，派班员要分派给4个装卸班组，每个班组卸1辆。由于各个班组的技术特长不同，各个班组卸不同车辆所需时间如下表。问：派班员应如何分配卸车任务，可以使卸车所花费的总车辆小时最小？ijP1P2P3P4甲4341乙2365丙4354丁3266一、指派问题及其模型特征引例2：一份中文说明书需要译成英、日、德、俄四种文字（E，J，G，R），现有甲、乙、丙、丁四人可以完成上述任务，他们将说明书翻译成不同语种的文字所需时间如下表，且一项任务只能由一人去完成，每人只能完成一项任务。问：指派何人完成何工作，可使总花费时间最少？ijEJGR甲215134乙1041415丙9141613丁78119（1）n项工作怎样分配给n个工作人员去完成，可以使总花费时间最省；（2）n项加工任务怎样分配给n台机床去完成，可以使总费用最低；（3）n条航线，怎样指定艘班轮去完成航行任务，可以使总运输费用最低；。。。。。。——该类问题是运输问题的特殊形式，称为指派问题。（一）指派问题（二）指派问题的基本特征性质：特殊的运输问题//特殊0-1规划问题。特征：（1）决策变量为0-1变量；(2)发点数m=收点数n；（3）ai=bj=1i,j=1,2,…,n;（三）指派问题的基本模型目标函数系数矩阵（Cij)与指派问题左边模型一一对应！设Xij=1指派i人去完成j项任务;Xij=0否则；则0-1规划模型如下：MinZ=11nnijijijCX11,1,2,...,nijiXin11,1,2,...,nijjXjnXij=0,1四、匈牙利算法（一）基本概念（1）系数矩阵Cij；（2）解矩阵（Xij)（3）解矩阵的特征—各行各列的元素之和为1.*1000010000100001ijnnX*0001001001001000ijnnX*0100000110000010ijnnX如果对指派问题的系数矩阵（Cij）的任一行列各元素分别减去该行（列）的最小元素，得到新的矩阵（Bij），则以（Bij）为系数矩阵的新指派问题的最优解（Xij’*）和原指派问题的最优解（Xij*）相同。——（Bij）称为（Cij）的等效矩阵（二）基本定理——定理1的直观意义——定理1的求解意义43411236524354332654ijC3230014310211043-232100123()10011023ijB321(0)(0)12310(0)11(0)23推论：等效系数矩阵（Bij)的n个独立“0”元素对应的解矩阵的n个独立“1”元素为指派问题的最优解。原因为：BijXij*=0，为最小。则原问题有最优解，取到最小值。（三）基本算法步骤第一步：是指派问题的系数矩阵经变换后，在各行各列出现0元素。（1）从系数矩阵的每行元素减去该行最小元素；（2）再从所得的系数矩阵的每列元素减去该列最小元素；注意：某行（列）已经有0元素，就不必再减。得到一个新的系数矩阵B，由定理可知二者具有相同的最优解。（三）基本算法步骤第二步：试指派，以求最优解在等效系数矩阵B中寻找n个独立“0”元素（1）从只有一个“0”元素的行（列）开始，给“0”元素加圈，然后划去其所在列“0”元素；（2）从只有一个“0”元素的列（行）开始，给该“0”元素加圈，然后划去其所在行“0”元素；（3）反复以上2步骤，直至所有“0”元素被括出或被划去为止；（4）若画圈的“0”元素的个数m=矩阵的阶数n，则它们即为等效矩阵的n个独立“0”元素，其对应的解矩阵的个独立“1”元素即为最优解。若m《n,则未找到最优解，进行第三步（三）基本算法步骤第三步：做最少的直线覆盖所有的0元素1、对没有画圈的0的行，打√2、对已经打√的行中，含有的列，打√3、再对有√的列中含有圈的0的行，打√4、重复2.3步，直到没有新的√出现5、对没有画√的行已经画√的列画直线。若直线数l小于系数矩阵阶数n，则转入下一步。（三）基本算法步骤第四步：增加0元素，找新的等效矩阵。在未被直线覆盖的部分找出最小元素a未划去的元素减去a交叉元素加上a得到新的系数矩阵B1其他元素不变重复第二步，找寻最优解——指派问题等效系数矩阵中独立“0”元素的最多个数（m）等于能覆盖所有“0”元素的最小直线数（l）。——D.Konig定理的意义（示例：P132）（四）最小覆盖定理讲解：例题128例八作业：p1325.7了解：极大化指派问题----P131自学了解：极大化指派问题----P131自学