资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,1,、,基本概念,2,、分枝定界,3,、割平面法,4,、,0-1,型整数规划,5,、指派问题与匈牙利解法,第,2,章 整数规划,1、基本概念第2章 整数规划,1,第,2,章 整数规,划 基本概念,许多线性规划中，决策变量具有不可分割的性质，如人数、设备的台数、车辆船只数、方案个数等。,如果有一个规划中要求所有决策变量都取整数，就是纯整数规划问题；若有部分决策变量要求取整数，就是混合整数规划问题；,在实践中也有大量的问题需要决策者判断“是与否”、“有与无”、“取与舍”等逻辑问题。这些问题可转化为决策变量是取,0,还是取,1.,就是所谓的,0-1,型整数规划问题。,整,数规,划简称为,IP,问题（,integer programming),。,整,数线性规,划简称为,ILP,问题。,第2章 整数规划 基本概念 许多线性规划中，决策变量具,2,第,2,章 整数规,划 分枝定界,第2章 整数规划 分枝定界,3,第,2,章 整数规,划 分,枝定界,第2章 整数规划 分枝定界,4,第,2,章 整数规划分枝定界,第2章 整数规划分枝定界,5,第,2,章 整数规,划 分,枝定界,x,1,=4,第2章 整数规划 分枝定界x1=4,6,第,2,章 整数规划分枝定界,LP,0,:x,1,=3.75,x,2,=1.25,Z=23.75,LP,1,:x,1,=3,x,2,=2,Z=23,LP,2,:x,1,=4,x,2,=0.83,Z=23.3,x1=4,LP,3,:x,1,=4.5,x,2,=0,Z=22.5,LP,4,:,无解,x2=1,x1=5,LP,5,:x,1,=4,x,2,=0,Z=20,LP,6,:,无解,第2章 整数规划分枝定界LP0:x1=3.75,x2=1,7,第,2,章 整数规划分枝定界,若某个分枝得到的是不满足整数条件的最优解，要区分下列情况：,（,1,）该最优解目标函数值不大于当前下界（观测得到的一个原问题可行解的目标函数值），则该分枝不可能有原问题的最优解，不需要继续分枝，称之为“枯枝”，需要剪掉；,（,2,）,该最优解目标函数,值大,于当前下,界，则仍需要进行分枝。,第2章 整数规划分枝定界若某个分枝得到的是不满足整数条件的最,8,第,2,章 整数规划分枝定界,第一章中的轰炸机群的例子，伴随规划（除去了整数约束）结果：,x=7.11,0,0,40.89,0,0,0,31.999 fval,=-,9.057,人,工确定一个整数可行解：,7,0,0,40,0,0,0,32 fval=-8.932974734624262,（,1,）,x1=8,x*=(8,0,0,40,0,0,0,32),fval=-,9.052161142343470 (,出现更优的可行解,),（,1.1,）,x1=,7,x8,=,31,x*=(6.4889,0,0,41.5111,0,1,0,31),fval=-,9.03966425(,枯枝,),（,1.2,）,x1=,32,x,*=(7,0,0,40.981,000,32)fval=-,9.0555108(,继续分枝,),（,1.2.1,）,x1=32,x4=41,x,*=(,6.9767,0,0,41,0,0,0,32,)fval=-9.05514(,继续分枝,),（,1.2.2.1,）,x1=32,x4=,41,x,*=(6,0,0,41.80,0,0,0,32)fval=,-9.039639,(,枯枝,),（,1.2.2.2,）,x1=7,x8,=32,x4=,41,(,无解,),第2章 整数规划分枝定界第一章中的轰炸机群的例子，伴随规划（,9,(1.1,),x1=7,x8=32,x4=41,x0=0,0,0,0,0,0,0,0;,options=optimset(LargeScale,off,Simplex,on);%,使用单纯形法，提升精确度,c=log10(0.76),log10(0.8),log10(0.85),log10(0.75),log10(0.92),log10(0.84),log10(0.88),log10(0.8);,A=1,1,1,1,0,0,0,0;0,0,0,0,1,1,1,1;537.5,560,605,650,462.5,480,515,550;0,0,0,0,0,0,0,-1;0,0,0,-1,0,0,0,0;,b=48,32,48000,-32,-41;,lb=0,0,0,0,0,0,0,0;,ub=;,Aeq=1,0,0,0,0,0,0,0;,beq=7;,x,fval,exitflag,output,lambda=linprog(c,A,b,Aeq,beq,lb,ub,x0,options),第,2,章 整数规划分枝定界,(1.1)x1=7,x8=0,f(x)=0,无法直接加入模型（造成无解）,取一个,0-1,型变量,y,，一个很大的正数,M,-f(x)+3=My,f(x)=M(1-y),可以加入模型,第2章 整数规划 0-1型整数规划 处理一些特,18,第,2,章 整数规划,0-1,型整数规划 处理一些特殊约束,用,0-1,型整数规划处理一些特殊约,束,2,、多中选一的约束,f,i,(x)=0,i=1,2,.,n,引,入,n,个,0-1,型整数变量,y,i,，上式写为：,f,i,(x)=M(1-y,i,),i=1,2,.,n,y,1,+y,2,+.+y,n,=1,如,果是多中选,k,个约束：,y,1,+y,2,+.+,y,n,=k,第2章 整数规划 0-1型整数规划 处理一些特,19,第,2,章 整数规划,0-1,型整数规划 典型应用,1,、背包问题,登山队,员要携带的物品有：食品、氧气、冰镐、绳索、帐篷、照相器材、通信器材等，每种物品的重量及重要性系数见下表，最大携带,25KG,，请选择：,序号,1,2,3,4,5,6,7,物品,食品,氧气,冰镐,绳索,帐篷,照相器材,通信设备,重量,/,KG,5,5,2,6,12,2,4,重要性系数,20,15,18,14,8,4,10,分枝定,界,割平面法,贪,心,最大,10,重量,9,，价值,9,重量,6,，价值,2,重量,5,，价值,6,第2章 整数规划 0-1型整数规划 典型,20,第,2,章 整数规划,0-1,型整数规划 典型应用,2,、集合覆盖和布点问题,某城市消防队布点问题。该城市,6,个区，每个区都可以建消防站，市政府希望设置的消防站最少，但必须满足任何区发生火警，,15min,内能赶到。,各区之间的消防车行驶时间见下表：,地区,1,地区,2,地区,3,地区,4,地区,5,地区,6,地区,1,0,10,16,28,27,20,地区,2,10,0,24,32,17,10,地区,3,16,24,0,12,27,21,地区,4,28,32,12,0,15,25,地区,5,27,17,27,15,0,14,地区,6,20,10,21,25,14,0,第2章 整数规划 0-1型整数规划 典型应用,21,第,2,章 整数规,划,0-1,型整数规划 典型应用,地区,1,地区,2,地区,3,地区,4,地区,5,地区,6,地区,1,0,10,16,28,27,20,地区,2,10,0,24,32,17,10,地区,3,16,24,0,12,27,21,地区,4,28,32,12,0,15,25,地区,5,27,17,27,15,0,14,地区,6,20,10,21,25,14,0,地,区,1,或者地区,2,必须至少建立一个，才能满足地区,1,要求,地,区,1,、,2,或者,6,必须至少建立一个，才能满足地区,2,要求,，,i=1,2,.,6,第2章 整数规划 0-1型整数规划 典型应用,22,第,2,章 整数规划,0-1,型规划 解决小规模,0-1,型规划问题的隐枚举法,第2章 整数规划 0-1型规划 解决小规模0-,23,第,2,章 整数规划,0-1,型规划 隐枚举法,点,过滤条件,约束,z,值,5,1,2,3,4,(0,0,0),T,NO,(0,0,1),T,YES,YES,YES,YES,YES,5,(0,1,0),T,NO,(0,1,1),T,NO,(1,0,0),T,NO,(1,0,1),T,YES,YES,YES,YES,YES,8,(1,1,0),T,NO,(1,1,1),T,NO,第2章 整数规划 0-1型规划 隐枚举法 点,24,第,2,章 整数规划,指派问,题与匈牙利解法,对,于第,i,个人，只能完成,1,项工作,对,于第,j,项工作，只能由,1,个人完成,第2章 整数规划 指派问题与匈牙利解法 对于第i个,25,第,2,章 整数规划,指派问,题与匈牙利解法,定,理,1,：设指派问题效率矩阵,C,，若将该矩阵的某一行（或列）的各个元素都减去同一个常数,t,（可正可负），得到新的效率矩阵,C,，则以,C,为效率矩阵的新指派问题与原指派问题最优解相同，最优值比原最优值减去,t,。,第2章 整数规划 指派问题与匈牙利解法 定理1：设,26,第,2,章 整数规划,指派问,题与匈牙利解法,用圈,0,法进行行列检验。每行只有一个未标记的,0,时，用圈标记，然后该,0,所在列的其他未标记的,0,用记号,划去。重复行检查，直到每一行都没有未被标记的,0,或至少有两个未被标记的,0,为止。再进行列检验。,（,1,）每行均有圈,0,出现，个数,m=n.,进,行指派：令圈,0,位置的决策变量,=1,，其他,=0,，得到最优解；,（,2,）存在未标记过的,0,，但它们所在的行和列中，至少有,2,个,任选,1,个圈上，再进行行列检查，最后出现情况（,1,）或（,3,）；,（,3,）不存在未被标记过的,0,，但圈,0,的个数,mn,。,作,最小直线覆盖当前所有,0,元,素。,第2章 整数规划 指派问题与匈牙利解法 用圈0法进行,27,第,2,章 整数规划,指派问,题与匈牙利解法,减,去各行各列中的最小元素,-7,-6,-7,-6,-4,-0,-0,-0,-0,-0,该行只有一个,0,该列只有一个,0,圈,0,个数,=40,表示优化过程中变量收敛于解,X,，,exitflag0,表示计算不收敛。,output,有,3,个分量，,iterations,表示优化过程的迭代次数，,cgiterations,表示,PCG,迭代次数，,algorithm,表示优化所采用的运算规则,。,第,2,章 整数规划,0-1,规划的,matlab,解法,MATLAB解0-1规划问题的函数是bintprogx=,30,f,=-3 2-5;,A=1,2,-1;1,4,1;1,1,0;0,4,1;,b=2;4;3;6;,x=bintprog(f,A,b),Optimization terminated.,x=,1,0,1,f=-3 2-5;,31,第,2,章 整数规划,应用举例,招,聘问题：,本公,司,7,个部门，招聘,8,个人，每个部分至少招,1,个人，笔试共,16,人通过，成绩见下表；各个部分对人才的考察侧重点不同，面试阶段通过各方面打分汇总计算，,部,门评分成绩见下表（各部门对应聘者的评分），请确定录用方案（不考虑应聘人员对各部门的意愿）。（两种成绩权重相等）,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,笔试成绩,1,0.8454,0.4412,0.7787,0.6241,0.3899,0.5358,0.6101,0.6316,0.2059,0.1471,0.5219,0.0588,0.1546,0.3594,0.33,部门,1,0.8328,0.7284,0.6503,0.7956,0.7225,0.6085,0.7607,0.7306,0.7688,0.5809,0.6099,0.7978,0.6503,0.6563,0.7607,0.7225,部门,2,、,3,0.87,0.835,0.6853,0.835,0.79
展开阅读全文