整數(shù)規(guī)劃下純整數(shù)規(guī)劃全部決策變量取整數(shù)值混合整數(shù)規(guī)劃

1、整數(shù)規(guī)劃（下） 純整數(shù)規(guī)劃：全部決策變量取整數(shù)值； 混合整數(shù)規(guī)劃：部分決策變量取整數(shù)值； 0-1規(guī)劃：決策變量取0或1。等等二、整數(shù)規(guī)劃2.3.2 整數(shù)規(guī)劃求解方法（匈牙利法）例： 有一份說(shuō)明書(shū)，要分別譯成英、日、德、俄四種文字，交甲、乙、丙、丁四個(gè)人去完成。因個(gè)人專長(zhǎng)不同，他們完成翻譯不同文字所需的時(shí)間如表所示。應(yīng)如何分配，使四個(gè)人分別完成這四項(xiàng)任務(wù)總的時(shí)間為最小。2.3.2 匈牙利法（用于求解指派問(wèn)題）2.3 整數(shù)規(guī)劃求解方法2.3.2 匈牙利法（用于求解指派問(wèn)題）2.3 整數(shù)規(guī)劃求解方法指派問(wèn)題解（最優(yōu)指派）：使得指派矩陣上位于不同行不同列的n個(gè)元素之和最小（或最大）。比如x11=1,

2、x23=1, x32=1, x44=1x11=1, x24=1, x32=1, x43=1指派矩陣：2.3.2 匈牙利法（用于求解指派問(wèn)題）2.3 整數(shù)規(guī)劃求解方法指派矩陣：指派問(wèn)題解（最優(yōu)指派）：使得指派矩陣上位于不同行不同列的n個(gè)元素之和最?。ɑ蜃畲螅?。？24114 0 0 5 0( )( )( )222 -2 -2 ( )( )( )( )2.3.2 匈牙利法（用于求解指派問(wèn)題）2.3 整數(shù)規(guī)劃求解方法最優(yōu)指派：x13=1, x22=1, x34=1, x41=1最優(yōu)值：9+4+11+4=282.3.2 匈牙利法（用于求解指派問(wèn)題）2.3 整數(shù)規(guī)劃求解方法2.3.2 匈牙利法（用于求解指

3、派問(wèn)題）2.3 整數(shù)規(guī)劃求解方法？2.3.2 匈牙利法（用于求解指派問(wèn)題）2.3 整數(shù)規(guī)劃求解方法該條件稱為過(guò)濾條件解：先通過(guò)試探找一個(gè)可行解（任意），如例：增加一個(gè)約束條件：2.3.3 隱枚舉法2.3 整數(shù)規(guī)劃求解方法所有可能的可行解約束條件可行解否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 過(guò)濾條件2.3.3 隱枚舉法2.3 整數(shù)規(guī)劃求解方法所有可能的可行解約束條件可行解否Z值(0，0，0)(0，0，1)(

4、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 62.3.3 隱枚舉法2.3 整數(shù)規(guī)劃求解方法過(guò)濾條件所有可能的可行解約束條件可行解否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 0 2 1 1 8過(guò)濾條件2.3.3 隱枚舉法2.3 整數(shù)規(guī)劃求解方法函數(shù)bintprog()使用的一般形式：x, fv, exitflag, output= bintprog(f,A,

5、b,aeq, beq)其中：x為最優(yōu)解； fv為最優(yōu)值；exitflag為輸出標(biāo)志：exitflag=1有最優(yōu)解；exitflag=0迭代次數(shù)超過(guò)設(shè)定次數(shù)；exitflag=-2約束區(qū)域不可行；exitflag=-3問(wèn)題無(wú)解；output表明算法和迭代情況。2.3.4 Matlab函數(shù)bintprog()求解0-1規(guī)劃2.3 整數(shù)規(guī)劃求解方法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函數(shù)bintprog

6、()求解0-1規(guī)劃2.3 整數(shù)規(guī)劃求解方法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例：用函數(shù)bintprog()求解指派問(wèn)題2.3.4 Matlab函數(shù)bintprog()求解0-1規(guī)劃2.3 整數(shù)規(guī)劃求解方法蒙特卡洛法又稱計(jì)算機(jī)隨機(jī)性模擬法，

7、或統(tǒng)計(jì)試驗(yàn)法，是一種基于“隨機(jī)數(shù)”的計(jì)算方法，能夠比較逼真地描述事物的特點(diǎn)及物理實(shí)驗(yàn)過(guò)程，可以解決一些數(shù)值方法難以解決的問(wèn)題。通過(guò)計(jì)算機(jī)仿真解決問(wèn)題，也可以通過(guò)模擬檢驗(yàn)?zāi)Ｐ偷恼_性，是比賽中經(jīng)常使用的方法。2.3.5 蒙特卡洛法（可解決各類規(guī)劃問(wèn)題）2.3 整數(shù)規(guī)劃求解方法 用顯枚舉法試探需計(jì)算1005 =1010個(gè)點(diǎn)，計(jì)算量太大。應(yīng)用蒙特卡洛隨機(jī)計(jì)算106個(gè)點(diǎn)，找到近似最優(yōu)解。 應(yīng)用概率理論估計(jì)可信度： 假定最優(yōu)點(diǎn)不是孤立的奇點(diǎn)，目標(biāo)函數(shù)落在高值區(qū)的概率為 0.01（或0.00001），當(dāng)計(jì)算106個(gè)點(diǎn)后，有任一個(gè)點(diǎn)落在高值區(qū)的概率為2.3.5 蒙特卡洛法（可解決各類規(guī)劃問(wèn)題）2.3 整數(shù)規(guī)

8、劃求解方法例：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 蒙特卡洛法（可解決各類規(guī)劃問(wèn)題）2.3 整數(shù)規(guī)劃求解方法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=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 蒙特卡洛法（可解決各類規(guī)劃問(wèn)題）2.3 整數(shù)規(guī)劃求解方法function f,g=mengte(x);f=x(1)2+x(2)2+3*x(3)2+4*x(4