1、整数规划（下）整数规划（下）纯整数规划：纯整数规划：全部决策变量取整数值；全部决策变量取整数值；混合整数规划：混合整数规划：部分决策变量取整数值；部分决策变量取整数值；0-1规划：规划：决策变量取决策变量取0或或1。等等等等二、整数规划二、整数规划2.3.2 整数规划求解方法（匈牙利法）整数规划求解方法（匈牙利法）例：例：有一份说明书，要分别译成英、日、德、俄四种文字，有一份说明书，要分别译成英、日、德、俄四种文字，交甲、乙、丙、丁四个人去完成。因个人专长不同，他们完交甲、乙、丙、丁四个人去完成。因个人专长不同，他们完成翻译不同文字所需的时间如表所示。应如何分配，使四个成翻译不同文字所需的时间
2、如表所示。应如何分配，使四个人分别完成这四项任务总的时间为最小。人分别完成这四项任务总的时间为最小。2.3.2 匈牙利法匈牙利法（用于求解指派问题）（用于求解指派问题）2.3 整数规划求解方法整数规划求解方法321449738447798614939202323380121000402.3.2 匈牙利法匈牙利法（用于求解指派问题）（用于求解指派问题）2.3 整数规划求解方法整数规划求解方法指派问题解（最优指派）：指派问题解（最优指派）：使得指派矩阵上位于使得指派矩阵上位于不同行不同行不同列不同列的的n个元素之和最小（或最大）。比如个元素之和最小（或最大）。比如x11=1,x23=1,x32=1
3、,x44=1x11=1,x24=1,x32=1,x43=12109715414813141611415139指派矩阵：指派矩阵：2.3.2 匈牙利法匈牙利法（用于求解指派问题）（用于求解指派问题）2.3 整数规划求解方法整数规划求解方法2411109715148131416151394指派矩阵：指派矩阵：指派问题解（最优指派）：指派问题解（最优指派）：使得指派矩阵上位于使得指派矩阵上位于不同行不同行不同列不同列的的n个元素之和最小（或最大）。个元素之和最小（或最大）。？149392023233801210004024114 0 0 5 0()()()222 -2 -2 ()()()()9131
4、541116141381441579102 5911005324100115780 321100054230113080 5411000324501152802.3.2 匈牙利法匈牙利法（用于求解指派问题）（用于求解指派问题）2.3 整数规划求解方法整数规划求解方法最优指派：最优指派：x x1313=1,x=1,x2222=1,x=1,x3434=1,x=1,x4141=1=1最优值：最优值：9+4+11+4=289+4+11+4=28 0831132450112300002.3.2 匈牙利法匈牙利法（用于求解指派问题）（用于求解指派问题）2.3 整数规划求解方法整数规划求解方法2.3.2 匈
5、牙利法匈牙利法（用于求解指派问题）（用于求解指派问题）2.3 整数规划求解方法整数规划求解方法？2.3.2 匈牙利法匈牙利法（用于求解指派问题）（用于求解指派问题）2.3 整数规划求解方法整数规划求解方法 106434422523max3213221321321321或或，xxxxxxxxxxxxxxxxz11X(1 0 0),z3 ，3523321 xxx该条件称为过滤条件该条件称为过滤条件解：解：先通过试探找一个可行解（任意），如先通过试探找一个可行解（任意），如例：例：增加一个约束条件：增加一个约束条件：2.3.3 隐枚举法隐枚举法2.3 整数规划求解方法整数规划求解方法所有可能所有可能
6、的可行解的可行解约束条件约束条件可行解否可行解否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)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 8*101*zX，1233x2x5x3 过滤条件过滤条件2.3.3 隐枚举法隐枚举法2.3 整数规划求解方法整数规划求解方法X(1 0 0)，1231231223x2xx2x4xx4xx34xx6 所有可能所有可能的可行解的可行解约束条件约束条件可行解否可行解否Z值值(0，0，0)(0，0，1)(0，1，0)(1，0，0)(
7、0，1，1)(1，0，1)(1，1，0)(1，1，1)0 -1 1 0 1 5 0 2 1 1 8 8*101*zX，0 0 0 0 0 5-2 3 3 8 1 62.3.3 隐枚举法隐枚举法2.3 整数规划求解方法整数规划求解方法1233x2x5x3 过滤条件过滤条件所有可能所有可能的可行解的可行解约束条件约束条件可行解否可行解否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 6 5 3 3 1 0-2 8*101*zX，0 2 1 1 81233x2x5x8 过滤条件过滤条件2.3.3 隐枚举法隐枚举法2.3 整数规
8、划求解方法整数规划求解方法函数函数bintprog()使用的一般形式：使用的一般形式：12min*.*,0 1,1,2,nizfxst AxbAeqxbeqxxxxxorinx,fv,exitflag,output=bintprog(f,A,b,aeq,beq)其中：其中：x为最优解；为最优解；fv为最优值；为最优值；exitflag为输出标志：为输出标志：exitflag=1有最优解；有最优解；exitflag=0迭代迭代次数超过设定次数；次数超过设定次数；exitflag=-2约束区域不可行；约束区域不可行；exitflag=-3问题无解；问题无解；output表明算法和迭代情况。表明算法
9、和迭代情况。2.3.4 Matlab函数函数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;x fval123451234212345max2264.32552422501 i=1,2,5izxxxxxstxxxxxxxxxxx或（）例：例：2.3.4 Matlab函数函数bintprog()求解求解0-1规划规划2.3 整数规划求解方法整数规划求解方法MATLAB编程
10、如下：编程如下：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 整数规划求解方法整数规划求解方法蒙特卡洛法又称蒙特卡洛法又称计算机随机性模拟法计
11、算机随机性模拟法，或，或统计试验法统计试验法，是一种基于是一种基于“随机数随机数”的计算方法，能够比较逼真地描述事的计算方法，能够比较逼真地描述事物的特点及物理实验过程，可以物的特点及物理实验过程，可以解决一些数值方法难以解决解决一些数值方法难以解决的问题的问题。通过计算机仿真解决问题，也可以通过模拟检验模通过计算机仿真解决问题，也可以通过模拟检验模型的正确性，是型的正确性，是比赛中经常使用比赛中经常使用的方法。的方法。2.3.5 蒙特卡洛法蒙特卡洛法（可解决各类规划问题）（可解决各类规划问题）2.3 整数规划求解方法整数规划求解方法 用用显枚举法显枚举法试探需计算试探需计算1005=1010
12、个点，计算量太大。个点，计算量太大。应用应用蒙特卡洛蒙特卡洛随机计算随机计算106个点，找到个点，找到近似最优解近似最优解。应用概率理论估计可信度：应用概率理论估计可信度：假定最优点不是孤立的奇点，目标函数落在高值区的概率假定最优点不是孤立的奇点，目标函数落在高值区的概率为为 0.01（或（或0.00001），当计算），当计算106个点后，有任一个点落在高个点后，有任一个点落在高值区的概率为值区的概率为2.3.5 蒙特卡洛法蒙特卡洛法（可解决各类规划问题）（可解决各类规划问题）2.3 整数规划求解方法整数规划求解方法例：例：function f,g=mengte(x);f=x(1)2+x(2)
13、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 整数规划求解方法整数规划求解方法p0=0;ticfor 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
14、=f x0=x1;p0=f;end end f,g=mengte(x2);if sum(g=0)=4 if p0=f x0=x2;p0=f;end endendx0,p0toc2.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;
