hnor5整数规划

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第五章 整数线性规划,本章要求,理解整数规划的含义,掌握分枝定界法的思想和方法,掌握0-1整数规划的含义和用法,掌握指派问题的算法,5.1 整数规划问题的提出,决策问题中经常有整数要求，如人数、件数、机器台数、货物箱数如何解决？四舍五入不行，枚举法太慢,问题分类：,纯整数规划,、混合整数规划、,0-1整数规划,专门方法：分枝定界法、割平面法、隐枚举法、匈牙利法,一、问题举例,例1. 某集装箱运输公司，箱型标准体积24m,3,，重量13T,现有两种货物可以装运，甲货物体积5m,3,、重量2T、每件利润2000元；乙货物体积4m,3,、重量5T、每件利润1000元，如何装运获利最多？,Max Z=2000x1+1000x2,st,5x,1,+4x,2,24,2x,1,+5x,2,13,x,1,x,2,0,且为整数,解此LP问题，得：X,1,=4.8，X,2,=0,显然不是可行解,二、整数规划图解法,x,2,x,1,1 2 3 4 5 6 7,2,3,1,B,A,三、图解法的启示,A（4.8，0）点是LP问题的可行解，不是ILP问题的可行解，B（4，1）才是ILP的最优解,纯整数规划的可行解就是可行域中的整数点,非整数点不是可行解，对于求解没有意义，故切割掉可行域中的非可行解，不妨碍整数规划问题的优化,ILP问题的最优解不优于LP问题的最优解,解：先不考虑整数要求，解相应的LP问题，得：x,1,=4.8 x,2,=0 Z=9600 不是可行解,Z=9600是IP问题的上界，记为：Z=9600,5.2 分枝定界法,一、思路：切割可行域，去掉非整数点。一次分枝变成两个可行域，分别求最优解,例2. maxZ=2000x1+1000x2,5x,1,+4x,2,24,2x,1,+5x,2,13,x,1,x,2,0,且为整数,二、整数规划分枝定界法,x,2,x,1,1 2 3 4 5 6 7,2,3,1,B,A,二、分枝定界法（续）,X,1,=4.8不符合要求，切掉45之间的可行域，可行域变成两块，即原有约束条件再分别附加约束条件x,1,4,和,x,1,5,原问题分解为两个,maxZ=2000x1+1000x2 maxZ=2000x1+1000x2,5x1+4x2,24 5x1+4x2,24,2x1+5x2,13 ( IP1 ) 2x1+5x2,13 (IP2),x1,4 x1 5,x1,x2,0,且为整数 x1,x2,0,且为整数,二、分枝定界法（续）,不考虑整数要求，解相应LP问题。,解IP1得：x1=4 ,x2=1 z=9000,解IP2得：无可行解,此时可以断定IP问题的下界为9000，记为,Z,=9000,由于目前的分枝末梢最大值是9000，故IP问题的上界便是9000。由于,Z,=Z，此时已得IP问题的最优解，即x1=4,x2=1,Z=9000,三、分枝定界法的解题步骤,1、不考虑整数约束，解相应LP问题,2、检查是否符合整数要求，是，则得最优解，完毕。否则，转下步,3、任取一个非整数变量x,i,=b,i,，构造两个新的约束条件：x,i,b,i, ,x,i,b,i,+1,分别加入到上一个LP问题，形成两个新的分枝问题。,4、不考虑整数要求，解分枝问题。若整数解的Z值,所有分枝末梢的Z值，则得最优解。否则， 取Z值最大的非整数解，继续分解，转第 3步。,5.3 01型整数规划,某些特殊问题，只做是非选择，故变量设置简化为0或1，1代表选择，0代表不选择。,例3. 600万元投资5个项目，求利润最大的方案？,解：,0 当j项目未被选中,1 当j项目被选中,建模：设x,j,=,max Z=160x1+210x2+60x3+80x4+180x5,210x1+300x2+150x3+130x4+260x5,600,X1+x2+x3=1,X3+x4=1,x5,x1,Xj=0或1 j=1，2,5,增加过滤条件：,160x1+210x2+60x3+80x4+180x5,240,5.3 01型整数规划,用隐枚举法解例3：,（1，1，1，1，1）,（1，1，1，1，0）,（1，1，1，0，1）,（1，1，1，0，0）,（1，1，0，1，1）,（1，1，0，1，0）,（1，1，0，0，1）,（1，1，0，0，0）,（1，0，1，1，1）,（1，0，1，1，0）,（1，0，0，1，1）,.,一、0-1变量及其应用,（1）表达变量x可取0与9之间的任意整数的约束条件：,一、0-1变量及其应用（续）,（2）含相互排斥的约束条件的问题,例5：设工序B的每周工时约束条件为：,现在假设工序B还有一种新的加工方式，相应每周工时约束为：,如果工序B只能从两种加工方式中选择一种，问如何建立该问题约束条件？,一、0-1变量及其应用（续）,解：可以引入0-1变量y,1,和y,2,若工序B采用原加工方式,若工序B不采用原加工方式,若工序B采用新加工方式,若工序B不采用新加工方式,二、求解01规划的隐枚举法,例4。求解0-1整数规划,Max,解：求解过程列表如下所示：,1,6,Z8,8,3,3,-2,Z5,5,（1，1，0）,（1，1，1）,（1，0，1）,（1，0，0）,（0，1，1）,（0，1，0）,（0，0，1）,Z0,0,（0，0，0）,d,c,b,a,过滤条件,约束条件,Z值,（x,1,x,2,x,3,),5.4 指派问题,例6 甲乙丙丁四个人，A、B、C、D四项任务，不同的人做不同的工作效率不同，如何指派不同的人去做不同的工作使效率最高？,任务人 时间,A B C D,甲,乙,丙,丁,4 10 7 5,2 7 6 3,3 3 4 4,4 6 6 3,数模,：,Min Z=cijxij,xij=1 i=1,n,xij=1 j=1,n,Xij=0或1,(一)指派问题解法匈牙利法,解：类似运输问题的最小元素法,第一步,造0,各行各列减其最小元素,4,10,7,5,2,7,6,3,3,3,4,4,4,6,6,3,0,6,3,1,0,5,4,1,0,0,1,1,1,3,3,0,0,6,2,1,0,5,3,1,0,0,0,1,1,3,2,0,第二步 进行最优性检验：,方法：用尽可能最少的水平或垂直的直线划去全部的0元素，如果所画的直线恰好等于矩阵的行数或列数，即为最优解。否则转下一步；,0,6,2,1,0,5,3,1,0,0,0,1,1,3,2,0,(一)指派问题解法匈牙利法（续）,(一)指派问题解法匈牙利法（续）,第三步 调整方案,方法：在所有未划去的元素中减去其中最小元素，然后在所划直线的交叉点加上这一最小元素；,然后转第二步。直至求到最优方案。,0,6,2,1,0,5,3,1,0,0,0,1,1,3,2,0,0,5,1,0,0,4,2,0,1,0,0,1,2,3,2,0,(一)指派问题解法匈牙利法（续）,第三步 确定最优方案,先从只有一个,0,元素的行开始，给这个,0,元素加上标记，将所在列的其他,0,元素划去，完成第一个指派任务；,再从只有一个,0,元素的列开始，这个,0,元素加上标记，将所在列的其他,0,元素划去，完成一个指派任务；,反复进行以上两步，直至所有,0,元素都被划去；,当标记的,0,元素的数目恰好等于矩阵的行数或列数时，则最优指派方案找到。,0,4,0,0,0,3,1,0,2,0,0,2,2,2,1,0,最优解：,x44=1,x21=1,x13=1,x23=1, Z=12,(一)指派问题解法匈牙利法（续）,0,4,0,0,0,3,1,0,2,0,0,2,2,2,1,0,(二)非标准形式的指派问题,1)最大化指派问题,2)人数和事数不等的指派问题,3)一个人可做几件事的指派问题,4)某事一定不能由某人做的指派问题,例：书上P147 例13,练习5.4 P148,解：设第i名队员身高为h,i,，出场情况为X,i,（i=1，2，8），则：,Max,练习5.13 P151,