整数规划下纯整数规划全部决策变量取整数值混合整数规划.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,整数规划（下）,纯整数规划：,全部决策变量取整数值；,混合整数规划：,部分决策变量取整数值；,0-1,规划：,决策变量取,0,或,1,。,等等,1,二、整数规划,2.3.2,整数规划求解方法（匈牙利法）,2,例：,有一份说明书，要分别译成英、日、德、俄四种文字，交甲、乙、丙、丁四个人去完成。因个人专长不同，他们完成翻译不同文字所需的时间如表所示。应如何分配，使四个人分别完成这四项任务总的时间为最小。,2.3.2,匈牙利法,（用于求解指派问题）,2.3,整数规划求解方法,3,2.3.2,匈牙利法,（用于求解指派问题）,2.3,整数规划求解方法,指派问题解（最优指派）：,使得指派矩阵上位于,不同行,不同列,的,n,个元素之和最小（或最大）。比如,x,11,=1,x,23,=1,x,32,=1,x,44,=1,x,11,=1,x,24,=1,x,32,=1,x,43,=1,指派矩阵：,4,2.3.2,匈牙利法,（用于求解指派问题）,2.3,整数规划求解方法,指派矩阵：,指派问题解（最优指派）：,使得指派矩阵上位于,不同行,不同列,的,n,个元素之和最小（或最大）。,？,5,2,4,11,4,0 0 5 0,(),(),(),2,2,2,-2 -2,(),(),(),(),2.3.2,匈牙利法,（用于求解指派问题）,2.3,整数规划求解方法,6,最优指派：,x,13,=1,x,22,=1,x,34,=1,x,41,=1,最优值：,9+4+11+4=28,2.3.2,匈牙利法,（用于求解指派问题）,2.3,整数规划求解方法,7,2.3.2,匈牙利法,（用于求解指派问题）,2.3,整数规划求解方法,？,8,2.3.2,匈牙利法,（用于求解指派问题）,2.3,整数规划求解方法,9,该条件称为过滤条件,解：,先通过试探找一个可行解（任意），如,例：,增加一个约束条件：,2.3.3,隐枚举法,2.3,整数规划求解方法,10,(0,，,0,，,0),(0,，,0,，,1),(0,，,1,，,0),(1,，,0,，,0),(0,，,1,，,1),(1,，,0,，,1),(1,，,1,，,0),(1,，,1,，,1),0,5,-1,1,0,1,5,-2,3,1,1,1,0,5,3,1,5,8,0,2,1,1,8,1,6,2,6,过滤条件,2.3.3,隐枚举法,2.3,整数规划求解方法,11,(0,，,0,，,0),(0,，,0,，,1),(0,，,1,，,0),(1,，,0,，,0),(0,，,1,，,1),(1,，,0,，,1),(1,，,1,，,0),(1,，,1,，,1),0,-1,1,0,1,5,0,2,1,1,8,0,0,0,0,0,5,-2,3,3,8,1,6,2.3.3,隐枚举法,2.3,整数规划求解方法,过滤条件,12,(1,，,0,，,1),(1,，,1,，,1),(0,，,1,，,1),(1,，,0,，,0),(0,，,1,，,1),(1,，,1,，,0),(0,，,0,，,0),(0,，,1,，,0),8,6,5,3,3,1,0,-2,0,2,1,1,8,过滤条件,2.3.3,隐枚举法,2.3,整数规划求解方法,13,函数,bintprog(),使用的一般形式：,x,fv,exitflag,output=bintprog(f,A,b,aeq,beq),其中：,x,为最优解；,fv,为最优值；,exitflag,为输出标志：,exitflag=1,有最优解；,exitflag=0,迭代次数超过设定次数；,exitflag=-2,约束区域不可行；,exitflag=-3,问题无解；,output,表明算法和迭代情况。,2.3.4 Matlab,函数,bintprog(),求解,0-1,规划,2.3,整数规划求解方法,14,MATLAB,编程如下：,f=-1,2,2,-6,-4;,A=3,2,-1,1,2;2,4,-2,-1,-2;,b=5,5;,x,fv,ex=bintprog(f,A,b,);,fval=-fv;,x,fval,例：,2.3.4 Matlab,函数,bintprog(),求解,0-1,规划,2.3,整数规划求解方法,15,MATLAB,编程如下：,c=3 8 2 10 3;8 7 2 9 7;6 4 2 7 5;8 4 2 3 5;9 10 6 9 10;,c=c(:);,a=zeros(10,25);,for i=1:5,a(i,(i-1)*5+1:5*i)=1;,a(5+i,i:5:25)=1;,end,b=ones(10,1);,x,y=bintprog(c,a,b);,x=reshape(x,5,5),y,例：,用函数,bintprog(),求解指派问题,2.3.4 Matlab,函数,bintprog(),求解,0-1,规划,2.3,整数规划求解方法,16,蒙特卡洛法又称,计算机随机性模拟法,，或,统计试验法,，是一种基于“随机数”的计算方法，能够比较逼真地描述事物的特点及物理实验过程，可以,解决一些数值方法难以解决的问题,。,通过计算机仿真解决问题，也可以通过模拟检验模型的正确性，是,比赛中经常使用,的方法。,2.3.5,蒙特卡洛法,（可解决各类规划问题）,2.3,整数规划求解方法,17,用,显枚举法,试探需计算,1005=1010,个点，计算量太大。应用,蒙特卡洛,随机计算,106,个点，找到,近似最优解,。,应用概率理论估计可信度：,假定最优点不是孤立的奇点，目标函数落在高值区的概率为,0.01,（或,0.00001,），当计算,106,个点后，有任一个点落在高值区的概率为,2.3.5,蒙特卡洛法,（可解决各类规划问题）,2.3,整数规划求解方法,例：,18,function f,g=mengte(x);,f=x(1)2+x(2)2+3*x(3)2+4*x(4)2+2*x(5)-8*x(1),-2*x(2)-3*x(3)-x(4)-2*x(5);,g=sum(x)-400,x(1)+2*x(2)+2*x(3)+x(4)+6*x(5)-800,2*x(1)+x(2)+6*x(3)-200,x(3)+x(4)+5*x(5)-200;,2.3.5,蒙特卡洛法,（可解决各类规划问题）,2.3,整数规划求解方法,19,p0=0;,tic,for i=1:106,x=99*rand(5,1);,x1=floor(x);x2=ceil(x);,f,g=mengte(x1);,if sum(g=0)=4,if p0=f,x0=x1;p0=f;,end,end,f,g=mengte(x2);,if sum(g=0)=4,if p0=f,x0=x2;p0=f;,end,end,end,x0,p0,toc,2.3.5,蒙特卡洛法,（可解决各类规划问题）,2.3,整数规划求解方法,function f,g=mengte(x);,f=x(1)2+x(2)2+3*x(3)2+4*x(4)2+2*x(5)-8*x(1),-2*x(2)-3*x(3)-x(4)-2*x(5);,g=sum(x)-400,x(1)+2*x(2)+2*x(3)+x(4)+6*x(5)-800,2*x(1)+x(2)+6*x(3)-200,x(3)+x(4)+5*x(5)-200;,20,