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

《整数规划下纯整数规划全部决策变量取整数值混合整数规划.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、整数规划（下）纯整数规划：全部决策变量取整数值；混合整数规划：部分决策变量取整数值；0-1规划：决策变量取0或1。等等二、整数规划2.3.2整数规划求解方法（匈牙利法）例：有一份说明书，要分别译成英、日、德、俄四种文字，交甲、乙、丙、丁四个人去完成。因个人专长不同，他们完成翻译不同文字所需的时间如表所示。应如何分配，使四个人分别完成这四项任务总的时间为最小。2.3.2匈牙利法（用于求解指派问题）2.3整数规划求解方法2.3.2匈牙利法（用于求解指派问题）2.3整数规划求解方法指派问题解（最优指派）：使得指派矩阵上位于不同行不同列的n个元素之和最小（或最大）。比如x11=1,x

2、23=1,x32=1,x44=1x11=1,x24=1,x32=1,x43=1指派矩阵：2.3.2匈牙利法（用于求解指派问题）2.3整数规划求解方法指派矩阵：指派问题解（最优指派）：使得指派矩阵上位于不同行不同列的n个元素之和最小（或最大）。？241140050()()()222-2-2()()()()2.3.2匈牙利法（用于求解指派问题）2.3整数规划求解方法最优指派：x13=1,x22=1,x34=1,x41=1最优值：9+4+11+4=282.3.2匈牙利法（用于求解指派问题）2.3整数规划求解方法2.3.2匈牙利法（用于求解指派问题）2.3整数规划求解方法？2.3.2

3、匈牙利法（用于求解指派问题）2.3整数规划求解方法该条件称为过滤条件解：先通过试探找一个可行解（任意），如例：增加一个约束条件：2.3.3隐枚举法2.3整数规划求解方法所有可能的可行解约束条件可行解否Z值(0，0，0)(0，0，1)(0，1，0)(1，0，0)(0，1，1)(1，0，1)(1，1，0)(1，1，1)05-1101√5-231110√5315×80211√81626×过滤条件2.3.3隐枚举法2.3整数规划求解方法所有可能的可行解约束条件可行解否Z值(0，0，0)(0，0，1)(0，1，0)(1，0，0)(0，1，1)(1，0，1)(1，1

4、，0)(1，1，1)0√-1101√50211√8000005-2338162.3.3隐枚举法2.3整数规划求解方法过滤条件所有可能的可行解约束条件可行解否Z值(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√653310-202118过滤条件2.3.3隐枚举法2.3整数规划求解方法函数bintprog()使用的一般形式：[x,fv,exitflag,output]=bintprog(f,A,b,aeq,beq)其中：x为最优解；fv为最优值；exitflag为输出标志：exitflag=1有最优解；

5、exitflag=0迭代次数超过设定次数；exitflag=-2约束区域不可行；exitflag=-3问题无解；output表明算法和迭代情况。2.3.4Matlab函数bintprog()求解0-1规划2.3整数规划求解方法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;xfval例：2.3.4Matlab函数bintprog()求解0-1规划2.3整数规划求解方法MATLAB编程如下：c=[382103;8729

6、7;64275;84235;9106910];c=c(:);a=zeros(10,25);fori=1:5a(i,(i-1)*5+1:5*i)=1;a(5+i,i:5:25)=1;endb=ones(10,1);[x,y]=bintprog(c,[],[],a,b);x=reshape(x,[5,5]),y例：用函数bintprog()求解指派问题2.3.4Matlab函数bintprog()求解0-1规划2.3整数规划求解方法蒙特卡洛法又称计算机随机性模拟法，或统计试验法，是一种基于“随机数”的计算方法，能够比较逼真地描述事物的特点及物理实验过程，可以解决一些数值方法难以解

7、决的问题。通过计算机仿真解决问题，也可以通过模拟检验模型的正确性，是比赛中经常使用的方法。2.3.5蒙特卡洛法（可解决各类规划问题）2.3整数规划求解方法用显枚举法试探需计算100^5=10^10个点，计算量太大。应用蒙特卡洛随机计算10^6个点，找到近似最优解。应用概率理论估计可信度：假定最优点不是孤立的奇点，目标函数落在高值区的概率为0.01（或0.00001），当计算10^6个点后，有任一个点落在高值区的概率为2.3.5蒙特卡洛法（可解决各类规划问题）2.3整数规划求解方法例：function[f