整数规划数学模型及其解法.ppt

1、1,第四章 整数规划 Integer Programming,特点-解法-应用,2,知识点要求,了解整数规划的特点； 掌握逻辑变量的灵活运用； 掌握整数规划的求解方法： 匈牙利法：寻找位于不同行不同列的m个零元素、行和列的位势的确定 割平面法 分支定界法：分支与定界的条件 隐枚举法（0-1规划问题） 根据实际问题建立整数规划数学模型。,3,主要内容,整数规划的性质 整数规划的解法 匈牙利法 割平面法 分支定界法 隐枚举法（0-1规划问题） 整数规划的应用,4,引例1-1,例1某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、 重量，可获利润以及托运所受限制如表所示,5,甲种货物至多托运

2、4件， 问两种货物各托运多少件，可使获得利润最大？,引例1-2,6,引例2-1,例某公司计划在市区的东、西、南、北四区建立销售门市部， 拟议中有10个位置 Ai(i=1，2，3，.，10) 可供选择，,7,引例2-2,规定： 在东区由A1，A2，A3三个点至多选择两个； 在西区由A4，A5两个点中至少选一个； 在南区由A6，A7两个点中至少选一个； 在北区由A9，A9，A10三个点中至少选两个。,8,引例2-3 各点的设备投资及年获利预测表,投资总额不能超过720万元。 问应选择哪几个点，可使年利润为最大？,9,整数规划的特点（1）,在很多实际问题中，全部或部分变量的取值必须是整数，如人或机器

3、设备等不可分割。 此外还有一些问题，如要不要在某地建设工厂，可选用一个逻辑变量x，令x=1表示在该地建厂，x=0表示不在该地建厂，逻辑变量也是只允许取整数值的一类变量。,10,整数规划的特点（2）,纯整数线性规划： 在一个线性规划中要求全部变量取整数值，或简称纯整数规划。 混合整数(线性)规划： 在一个线性规划中只要求一部分变量取整数值。,11,整数规划的图解,有人认为，对整数规划问题的求解可以先不考虑对变量的整数约束，作为一般线性规划问题来求解，当解为非整数时可用四舍五人或凑整方法寻找最优解。 当然在变量取值很大时，用上述方法得到的解与最优解差别不大。但当变量取值较小时，得到的解就可能与实际

4、整数最优解差别很大。再者当问题规模较大时，用凑整办法来算工作量很大。,12,例1,求下述整数规划问题的最优解,13,14,如果不考虑x1、x2取整数的约束，用图解法求得最优解为(3.25，2.5)。由于x1、x2必须取整数值，实际上问题的可行解集只是图中可行域内的那些整数点。用凑整法来解时需要比较四种组合，但(4，3)、(4，2)、(3，3)都不是可行解，(3，2)虽属可行解，但代入目标函数得z=13，并非最优。实际上问题的最优解应该是(4，1)，z*=14。但我们注意到(4，1)不是可行域的顶点，因此直接用图解法或单纯形法都无法找出整数规划问题的最优解来，这就要求研究解整数规划问题的特殊方法

5、。,15,整数规划与对应的线性规划解的关系,1.任何求最大目标函数值的纯整数规划或混合整数规划的最大目标函数值小于或等于相应的线性规划的最大目标函数值； 2.任何求最小目标函数值的纯整数规划或混合整数规划的最小目标函数值大于或等于相应的线性规划的最小目标函数。 3.整数规划之相应线性规划的最优解经四舍五入不能得到其最优解,16,逻辑变量在建立数学模型中的作用,整数规划的模型对研究管理问题有重要意义。很多管理问题无法归结为线性规划的数学模型，但却可以通过设置逻辑变量建立起整数规划的数学模型。 M个约束条件中只有k个起作用； 约束条件的右端项可能是r个值（b1, b2, , br）中的某一个； 两

6、组条件中满足其中一组； 用以表达含固定费用的函数。,17,1M个约束条件中只有k个起作用,表明m个约束条件中有(m-k)个的右端项为（bi+M），不起约束作用，因而只有k个约束条件真正起到约束作用。,18,2约束条件的右端项可能是r个值（b1, b2, , br）中的某一个,19,3两组条件中满足其中一组,若x14，则x21； （1） 否则（即x14），则x23。 （2）,20,4用以表达含固定费用的函数,如用xj代表产品j的生产数量，其生产费用函数通常可表示为： 式中kj是同产量无关的生产准备费用。 问题的目标是使所有产品的总生产费用为最小。即：,21,设置一个逻辑变量yj， 当xj=0时，

7、yj=0，当xj0时，yj=1。 由此引进一个特殊的约束条件： 于是有：,22,逻辑变量应用举例-1,试用逻辑变量表达以下约束条件 变量x只能取2、3、5、8或11中的一个。 解题：右端项只能取多个值b1=2,b2=3,b3=5,b4=8,b5=11中的一个值,23,逻辑变量应用举例-2,用逻辑变量表述以下约束条件： 以下5个约束条件最多满足3个： x1+x2+x33 3x1+2x2+x35 x110 x24 x311,24,解题,将约束条件转换成统一型 -x1-x2-x3-3 -3x1-2x2-x3-5 x110 x24 x30时； yi=0，当xi=0时 最大利润的目标函数 maxz=4x

8、1+5x2+6x3-100yl-150y2-200y3,29,解题（2）,资源约束 2xl+4x2+8x3500 2xl+3x2+4x3300 xl+2x2+3x3100,30,解题（3）,固定投入约束 X1 ylM x2 y2M x3 y3M x1，x2，x3 0，且为整数 y1，y2，y3为0-1变量,31,解题（4）,计算结果 最优解为x1=100，x2=0，x3=0， 最大目标函数值为300，,32,整数规划的解法,匈牙利法 割平面法 分支定界法 隐枚举法（0-1规划问题）,33,解法1匈牙利法 应用于分配问题,分配问题也称指派问题(assignment problem)，是一种特殊的

9、整数规划问题。 假定有m项任务分配给m个人去完成，并指定每人完成其中一项，每项只交给其中一个人去完成，应如何分配使总的效率为最高。 解决分配问题的方法：表上作业法、匈牙利法,34,分配问题一般模型-1,例：有一份说明书，要分别译成英、日、德、俄四种文字，交甲、乙、丙、丁四个人去完成。因各人专长不同，他们完成翻译不同文字所需的时间(h)如表所示。问：如何分配任务使效率最高？,从人的角度看,从任务角度看,35,分配问题一般模型-2,假设 aij表示分配问题的效率矩阵 xij表示决策变量,36,分配问题一般模型-3,分配问题的一般数学模型,37,匈牙利法的基本定理1,如果从分配问题效率矩阵aij的每

10、一行元素中分别减去(或加上)一个常数ui(被称为该行的位势)，从每一列分别减去(或加上)一个常数vj(称为该列的位势)，得到一个新的效率矩阵bij，若其中 则bij的最优解等价于aij的最优解。,38,匈牙利法的基本定理2,若矩阵A的元素可分成“0”与非“0”两部分，则覆盖“0”元素的最少直线数等于位于不同行不同列的“0”元素的最大个数。,39,匈牙利法的计算步骤,举例说明,40,例：,有一份说明书，要分别译成英、日、德、俄四种文字，交甲、乙、丙、丁四个人去完成。因各人专长不同，他们完成翻译不同文字所需的时间(h)如表所示。问：如何分配任务使效率最高？,41,效率矩阵,42,第一步：找出效率矩

11、阵每行的最小元素， 并分别从每行中减去，有,min,43,第二步：再找出矩阵每列的最小元素， 再分别从各列中减去，有,44,第三步,经过上述两步变换后，矩阵的每行每列至少都有了一个零元素。 确定能否找出m个位于不同行不同列的零元素的集合(本例中m=4)， 直观法：m很小时，直接判断得到 非直观法：m很大时，根据一定规则寻找,45,非直观法-1,(1) 从第一行开始，若该行只有一个零元素，就对这个零元素打上( )号。 对打( )号零元素所在列画一条直线。 若该行没有零元素或有两个以上零元素(已划去的不计在内)，则转下一行，依次进行到最后一行；,46,非直观法-2,(2) 从第一列开始，若该列只有

12、一个零元素就对这个零元素打上( )号(同样不考虑已划去的零元素)， 对打( )号零元素所在行画一条直线。 若该列没有零元素或有两个以上零元素，则转下一列，依次进行到最后一列；,47,非直观法-3,(3) 重复(1)、(2)两个步骤，可能出现三种情况： 效率矩阵每行都有一个打( )号的零元素，很显然，按上述步骤得到的打( )号的零元素都位于不同行不同列，只要令对应打( )号零元素的xij=1就找到了问题的最优解；,48,非直观法-4, 打( )号的零元素个数小于m，但未被划去的零元素之间存在闭回路，这时可顺着闭回路的走向，对每个间隔的零元素打一( )号，然后对所有打( )号的零元素，或所在行，或

13、所在列画一条直线，如,49,非直观法-5, 矩阵中所有零元素或被划去，或打上( )号，但打( )号的零元素个数小于m，如本例：,50,第四步：为设法使每一行都有一个打( )号的零元素，需要继续按定理1对矩阵进行变换,(1) 从矩阵未被直线覆盖的数字中找出一个最小的数k； (2) 对矩阵的每行，当该行有直线覆盖时，令ui= 0，无直线覆盖的，令ui=k； (3) 对矩阵中有直线覆盖的列，令vj= -k，对无直线覆盖的列，令vj=0； (4) 从原矩阵的每个元素aij中分别减去ui和vj，得到一个新的矩阵。,51,第五步：回到第三步，反复进行，一直到矩阵的每一行都有一个打( )号的零元素为止，即找

14、到了最优分配方案。,52,最优分配方案为： 甲将说明书译成俄文，乙译成日文，丙译成英文，丁译成德文， 全部所需时间为4+4+9+11=28小时。,53,极大化的指派问题,对于目标为求极大的指派问题，先要对 效率矩阵进行处理：,找出效率矩阵中的最大值，分别用它去减阵中每一元素，得到新矩阵,对新得到的矩阵用原匈牙利法求解。,54,例、有 4 种机械要分别安装在4个工地，它们 在4个工地的工作效率不同，问应如何指 派，可使4台机械发挥的总效益最大？,55,解：,原效益矩阵中 max Cij= Cij=43 所以 bij= 43 Cij ( i , j=1, 2, 3, 4）,56,人数和任务数不相等

15、,例 、4项工作分配给6个人完成,57,解：虚设两项假想的任务,58,例、,4人完成5项任务，每人可完成12项,59,解：因每个人可担任一至二项任务，因此将4人 看作8人，再虚设3项任务，化为平衡指派问题。,60,最优解：甲无 乙C, D 丙B, E 丁A minZ=129,61,例、,4人完成5项任务，其中一人完成两项，其余每人一项,62,解：虚设一人戊，完成各任务时间为甲、乙、 丙、丁中最小者，化为平衡指派问题。,最优方案：甲B 乙D、C 丙E 丁A 最小时间131,63,整数规划解法2 分枝定界法,步骤： 1. 寻找替代问题并求解 2. 分枝与定界 3. 剪枝,64,基本思路,(B)为(

16、A)的松弛问题。,65,66,maxZ=40X1 + 90X2,例：,67,解：先解该整数规划对应的松弛问题,选X1分枝,68,选(2)继续分枝,69,70,整数规划解法3割平面法,割平面法的基本思想： 在整数规划问题的松弛问题中依次引进线性约束条件(称Gomory约束或割平面)，使问题的可行域逐步缩小。但每次切割只割去问题的部分非整数解，直到使问题的目标函数值达到最优的整数点成为缩小后可行域的一个顶点，这样就可以用求解线性规划问题的方法找出这个最优解。,71,割平面法解题步骤,第一步：把问题中所有约束条件的系数均化为整数，若不考虑变量的整数约束，可得到该整数规划的松弛问题G0 ，求解G0，若

17、得到整数解，求解结束；否则转入第二步； 第二步：找出非整数解变量中分数部分最大的一个基变量，处理得到Gomory约束； 第三步：将Gomory约束加到G0中得到新的线性规划问题G1 ； 第四步：重复第一至第三步一直到找出问题的整数最优解为止 。,72,割平面法实例,第一步：把问题中所有约束条件的系数均化为整数，若不考虑变量的整数约束，可得到该整数规划的松弛问题G0,73,加松弛变量，并用单纯形法求解得最终单纯形表 由于第一步得到的不是整数解，转第二步。 第二步：找出非整数解变量中分数部分最大的一个基变量。x2=5/2=2+1/2; x1=13/4=3+1/4 写出该行的约束：,74,x2所在行

18、的约束为 将式中所有常数分写成整数与一个正的分数值之和得： 移项得： 根据变量取整数值的要求，左端为整数，因而右端也必须取整数值。 又因x3，x40，故右端 又右端项必须取整数值，因此有,75,上式加上松弛变量后得 将 代入上式并简化得,（等价于Gomory约束 ）,76,从图中看出Gomory约束只割去线性规划问题可行域的部分非整数解，原有的整数解集全部均保留。,G0,77,第三步：将Gomory约束加到G0中得到新的线性规划问题G1,第四步：重复第一至第三步一直到找出问题的整数最优解为止：单纯形法求解-非整数解分数部分最大的变量-写出该变量约束条件-整理得Gomory约束-割去非整数解,7

19、8,因为G1仅仅在G0中加了一个新的约束，可以把这个约束直接反映到求解G0的最终单纯形表中，并用灵敏度分析中讲的方法来解。,由于表中得到的解仍非整数解，重复第二步,79,将等式两端的变量与常数分成整数与非整数部分得:,移项得：,新的Gomory约束,加松驰变量后得,写出非整数解变量中分数部分最大的基变量的约束式,80,加上Gomory约束后的新的线性规划,81,对偶单纯形法求解G2,82,图解,+,+,图 4-7,图 4-6,整数规划问题的解(4，1)已成为经过两次切割后可行域上的一个顶点。,Gomory约束,原问题约束,83,整数规划解法4 隐枚举法解0-1规划问题,不需列出决策变量取值的所

20、有组合，只需关心目标函数值的最优可行组合； 按目标系数值从优到劣的顺序依次列出组合，逐个检验其可行性； 最先满足所有约束条件的组合为最优组合； 劣于最优解的组合解释可行也不用列出而被隐去。,84,0-1规划,0-1规划：全部变量为0或1的逻辑变量的整数规划。 0，1表示方案的取舍。,85,简单隐枚举法(max),原则： (1)、用试探法，求出一个可行解，以它的目标值作为当前最好值Z0 (2)、增加过滤条件Z Z0 (3)、将xi 按ci由小大排列,86,解：观察得解(x1 , x2 , x3 )=(1 ,0 ,0) Z0 =3 过滤条件：3x1 - 2x2+5x3 3 将(x1 x2 x3 )

21、 (x2 x1 x3 ),87,88,产销量及运费率,应用举例1选址设计（2）,89,应用举例1选址设计（3）,a)问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成本和总的运输费用之和最小； b)如果由于政策要求必须在A2，A3建一个厂，应在哪几个地方建厂,90,解题（1）,解a) 设xij为从Ai运往Bj的运输量 yi=1，当Ai厂址被选中时； yi=0，当Ai厂址没选中时。,91,解题（2）,目标函数 minz=175y2+300y3+375y4+500y5+ 8xll+4x12+3x13+5X21+2x22+3x23+ 4x31+3x32+4x33+9x41+7x42+5x4

22、3+ 10 x51+4x52+2x53，,生产固定费用,运输费用,92,解题（3）,对A1产量的限制的约束条件： xll+x12+x1330,93,解题（4）,对A2，A3，A4，A5只有当选为厂址建设，才有生产量，所以它们的产量约束条件： x21+x22+x2310y2， x31+x32+x3320y3， x41+x42+x4330y4， x51+x52+x5340y5,94,解题（5）,满足销量的约束条件： xll+x21+x31+x41+x51=30 x12+x22+x32+x42+x52=20 x13+x23+x33+x43+x55=20 xij为非负整数 yi为0-1变量,95,数学模型,minz=175y2+300y3+375y4+500y5+8xll+4x12+3x1