运筹学第四章.ppt

1、OR3,1,OPERATIONS RESEARCH,运 筹 学 xuling,OR3,2,第四章 整数规划,本章要求 理解整数规划的含义 掌握分枝定界法的思想和方法 掌握0-1变量的含义和用法 掌握指派问题的算法,OR3,3,4.1 整数规划问题的提出,决策问题中经常有整数要求，如人数、件数、机器台数、货物箱数如何解决？四舍五入不行，枚举法太慢 问题分类：纯整数规划、混合整数规划、0-1整数规划 专门方法：分枝定界法、割平面法、隐枚举法、匈牙利法,OR3,4,问题举例（整数规划模型）,某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如下表：,货物,甲 乙,托运限制,体

2、积,每箱（米3）,5 4,24,重量,每箱（百斤）,2 5,13,利润,每箱（百元）,20 10,请问两种货物各托运多少箱，可使获得利润为最大？,OR3,5,3 2 1,4.2 整数规划图解法,x2,x1,1 2 3 4 5 6 7,2,3,1,B,A,（4.8,0),(4,1),5x1+4x2=24,2x1+5x2=13,OR3,6,图解法的启示,A（4.8，0）点是LP问题的可行解，不是IP问题的可行解，B（4，1）才是IP的最优解; 纯整数规划的可行解就是可行域中的整数点； 非整数点不是可行解，对于求解没有意义，故切割掉可行域中的非可行解，不妨碍整数规划问题的优化； IP问题的最优解不优

3、于LP问题的最优解。,OR3,7,4.3 分枝定界法,思路：切割可行域，去掉非整数点。一次分枝变成两个可行域，分别求最优解。 分枝定界法的步骤： 先不考虑整数约束，变成一般的LP问题，求其最优解，记为X*(0). 若求得的最优解X*(0)刚好就是整数解，则该整数解就是原IP的最优解，否则，转入下一步。 对原问题进行分枝，寻求整数最优解。,OR3,8,选取非整数解X*(0)的一个非整数分量xi*bi，其小数部分为di，以该非整数分量的相邻整数bi di和bi di1为边界将原问题分枝为两个子问题，并抛弃这两个整数之间的非整数区域： 在原LP模型中添加分枝约束xi bi di,构成第一个子问题；在

4、在原LP模型中添加分枝约束xi bi di1，构成第二个子问题。 对上面两个子问题按照LP方法求最优解。若某个子问题的解是整数解，则停止该子问题的分枝，并且把它的目标值与上一步求出的最优整数解相比较以决定取舍。 重复步直至获得原问题最优整数解为 止。,OR3,9,例题,例1. maxZ=5x1+7x2 7x1+24x284 3x1+2x2 18 x1，x2 0且为整数,OR3,10,4.3 割平面法,基本思想：新增加一些线性(不等式）约束条件，称为割平面，去“切割”相应的LP的可行域，并使切掉部分都是非整数解，所有整数解都被保留下来。当这种割平面足够多时，使相应LP和原IP具有相同的最优解。那

5、么，相应LP的最优解也就是原IP的最优解。,OR3,11,割平面法求解步骤,先不考虑整数约束，变成一般的LP问题，求其最优解，记为X*(0)。 若求得的最优解X*(0)刚好是整数解，则该整数解就是原IP的最优解，否则，转下步。 寻求割平面方程： 从最优表中抄下非整数解的约束方程：,OR3,12,将该约束方程所有系数和常数分解为整数和正分数之和； 将整系数项归写于方程左边，真分数项写于右边； 考虑整数条件约束。以上方程左边为整数，右边为非正数，即方程右边0。这就是所求的割平面方程。 将割平面方程标准规范化，加到原最优表中，用对偶单纯形法求新的最优解。 重复第3，4步，直至获得原问题最优整数解为止

6、。,OR3,13,例题,例2：求解整数规划： maxZ=x1+x2 -x1+x21 3x1+x2 4 x1,x20,且为整数 解法如下：,OR3,14,1、先去掉整数约束条件，当成一般LP问题求解，得最优解：x1=3/4,x2=7/4,z=5/2. 最终单纯形表如下： 2、该解不是整数解，转入下一步； 3、从最优表中抄下非整数解的约束方程： x1-1/4x3+1/4x4=3/4; x2+3/4x3+1/4x4=7/4,CB,XB,b,1 1,x1 x2, 7/4,x1,x2,x3,x4,1,1,0,0,1 0,0 1,-1/4 3/4, 1/4,5/2,0,0,-1/2,-1/2,OR3,15

7、,将该约束方程所有系数和常数分解为整数和正分数之和，并将整系数项归写于方程左边，真分数项写于右边； x1-x3=3/4-(3/4x3+1/4x4) x2-1=3/4-(3/4x3+1/4x4) 考虑整数条件约束。以上方程左边为整数，右边为非正数，即方程右边0。这就是所求的割平面方程。即 3/4-(3/4x3+1/4x4) 0，即-3x3x4 -3,x1-1/4x3+1/4x4=3/4; x2+3/4x3+1/4x4=7/4,OR3,16,4、将割平面方程标准规范化，加到原最优表中。,割平面方程：-3x3x4 -3,CB,XB,b,1 1 0,x1 x2 x5, 7/4 -3,x1,x2,x3,

8、x4,1,1,0,0,1 0 0,0 1 0,-1/4-1/4 -3, -1,5/2,0,0,-1/2,-1/2,0,x5,0 0 1,0,用对偶单纯形法求解,得新的最优解。若此时得到整数解，则解题过程完毕。否则，重复第3，4步，直至获得原问题最优整数解为止。此题计算得x1=1,x2=1,停止计算。此时最优解为：X*=(1,1)T, Z*=2.,OR3,17,4.4 01整数规划问题,某些特殊问题，只做是非选择，故变量设置简化为0或1，1代表选择，0代表不选择。 例3. 某城市拟在其东、西、南三个区域设立邮局，各地区都有几个具体的地点可供选择。要求不超过总投资100万元的条件下，做出盈利最大的

9、决策。,OR3,18,求解01规划的隐枚举法,隐枚举法：不需要列出所有组合，只需关心目标函数值得最优可行组合。按目标值从优到劣依次列出组合，逐个检验其可行性；最先满足所有约束条件的组合为最优解，劣于最优解的组合即使可行，也不列出检验而隐去。,OR3,19,求解01规划的隐枚举,隐枚举法的步骤： 1、先用试探的方法找出一个初始可行解X0，其目标函数值为Z0； 2、对原有约束增加一个过滤条件：以目标函数ZZ0（若目标函数是最小化，则ZZ0）作为过滤条件加到原有约束集中。 3、求解加入过滤条件的新问题。 按照隐枚举法的思路，依次检查各种变量的组合，每找到一个可行解，求出它的目标函数值Zi，若Zi Z

10、0，则将过滤条件换为ZZi。,OR3,20,隐枚举法举例：求解下列01整数规划,maxZ=3x1-x2+4x3 x1+3x2-2x3 4 x1+4x2+x3 4 2x2+x3 6 x1+x2 1 x1,x2,x3=0或1,OR3,21,解：求解过程列表如下：,由上表可知，最优解X*=(1,0,1)T，最优值Z*=7.,OR3,22,相互排斥的约束条件,现设运输有车运和船运两种方式，设用车运的体积限制为：5x1+4x2 24，用船运的体积限制为： 7x1+3x2 45，这两个条件是互相排斥的，怎样在同一个问题中表示呢？,OR3,23,关于固定费用问题,某工厂为了生产某种产品，有几种不同的生产方式

11、可供选择，如选定投资高的生产方式，由于产量大，因而分配到每件产品的变动成本就降低；反之，如选定投资低的生产方式，将来分配到每件产品的变动成本可能增加，所以必须全面考虑。今设有三种方式可供选择，令：xj表示采用第j种方式时的产量；cj表示采用第j种方式时每件产品的变动成本；kj表示采用第j种方式时的固定成本。为了说明成本的特点，暂不考虑其它约束条件。采用各种生产方式的总成本分别为： 在构成目标函数时，为了在同一问题中讨论，应引入01变量。,OR3,24,4.5 指派问题,例4 甲乙丙丁四个人完成A、B、C、D四项任务，每人完成一项任务，不同的人做不同的工作效率不同，如何指派不同的人去做不同的工作

12、使效率最高？,数模： minZ=cijxij xij=1 i=1,n xij=1 j=1,n Xij=0或1,OR3,25,指派问题的特点：,把m项工作分派给n个人去完成，既发挥各人特长又使总效率最高。 这是一类特殊的01规划问题。可采用隐枚举法，但比较麻烦，对于指派问题有一种专门的解法匈牙利法。,OR3,26,匈牙利法（又叫画圈法）,1、指派模型的标准型： 目标函数为最小化； 系数矩阵为方阵，且其所有元素为非负。 2、标准型指派问题的求解： （1）原理：找出一组位于系数矩阵中不同行，不同列的零元素，对其画圈，对应的xij=1；未画圈的元素对应的xij=0，此时，目标函数最优。找出并画圈的零元

13、素称为独立零元素。,OR3,27,（2）标准型指派问题的求解步骤： P129-130 第一步：变换系数矩阵，使其每行每列都出现0元素。方法如下： 从系数矩阵的每行元素减去该行的最小元素； 再从所得系数矩阵的每列元素中减去该列的最小元素。 第二步：试指派。 从只有一个零元素的行（列）开始，给这个零元素加圈，记作 ，表示该行（列）所代表的人只有一种任务可分派。然后划去该所在列（行）其它的所有零元素，记作0，表示该列所代表的任务已指派完毕；不必再考虑； 给只有一个0元素列（行）的0加圈，记作 ，然后划去所在行的其它零元素，记作0 。 反复进行 操作，直到所有0元素都被圈出或划掉为止。,OR3,28,

14、若元素的数目m等于矩阵的阶数n，则该指派问题的最优解已得到，若m n，则转入第三步。 第三步：作最少的直线覆盖所有0元素，以确定该系数矩阵中能找到最多的独立0元素，步骤如下： 对没有的行打号； 对已打号的行中所有含0元素的列打号； 再对打号的列中含元素的行打号； 重复 ，至得不出新的打号的行，列为止。 对没有打号的行画一横线，有打号的列划一纵线，这就得到覆盖所有0元素的最少直线数。令直线数为L，若L n，说明必须再变换当前的系数矩阵，从而转入下步；若L n，而m n，则应回到第二步重新试指派。 第四步：找出未被划线的元素中的最小元素，将打的行的每一元素减去这一最小元素，对打的列的每一元素加上这

15、一最小元素。转入第二步，循环执行，直至的个数等于方阵阶数为止。此时，最优解为方阵中所在位置换为1，其它元素换为0所形成的方阵。,OR3,29,相关问题,非标准型的转化将其化为标准型。 （1）求maxZ= cijxij 可令bij M-cij 求maxZ= cijxij 即求minZ= (M-cij)xij M是足够大的常数 (常取方阵中最大的数） ， 新问题的最优解就是原问题的最优解。,OR3,30,例题,例5：有四种机械要分别安装在甲乙丙丁4个工地，它们在4个工地工作效率不同，问应如何指派安排，才能使4台机械发挥总的效率最大？效率表如下：,OR3,31,（2）系数矩阵不是方阵，目标仍为最小化

16、型问题：系数矩阵化为方阵。 A： m个人分派做n项工作，每人只能完成一项，系数矩阵（Cij）为m n矩阵， m n。 若m n ，则增添虚拟的s= m - n列，补成方阵，但对应的Cij0，然后用标准型方法求解。,OR3,32,例题,6个人完成4项工作任务，由于个人技术和专长不同，他们完成4项工作任务 所获得的收益如下表，且规定每人只能完成一项工作，一项工作任务只需一人完成，试求使总收益最大的分派方案？,OR3,33,B： m个人分派做n项工作，每人可以完成12项，不能简单的补零了，要视具体情况而定。,OR3,34,例：设6项任务由4人担任，每人可担任12项，已知个人担任各项任务的费用如下，请问如何分配任务，使总的费用