1、第三章 最優(yōu)化計(jì)算方法,單變量?jī)?yōu)化 多變量?jī)?yōu)化 線性規(guī)劃 離散最優(yōu)化,單變量?jī)?yōu)化,例3.1 再來(lái)考慮售豬問(wèn)題。但現(xiàn)在考慮到豬的生長(zhǎng)率不是常數(shù)的事實(shí)。假設(shè)現(xiàn)在豬還小，生長(zhǎng)率是增加的。什么時(shí)候?qū)⒇i售出從而獲得最大收益？,求解模型圖像法,clear all; close all; syms x y = (0.65-0.01*x)*200*exp(0.025*x)-0.45*x; ezplot(y,0,40); grid on,ezplot(y,18,22); grid on,ezplot(y,19,20); grid on,數(shù)值方法求解-Matlab,dydx = diff(y,x) xmax =

2、solve(dydx); xmax = double(xmax) xmax =xmax(1) ymax=subs(y,x,xmax),Newton 法,求方程F(x)=0的根. 牛頓法： x(n)=x(n-1)-F(x(n-1)/F(x(n-1),F = dydx; F1 = diff(F,x); format long N = 10; % number of iterations x0 = 19 % initial guess fprintf( iteration xvaluenn); for i=1:N x1=x0-subs(F,x,x0)/subs(F1,x,x0); fprintf(%

3、5.0f %1.16fn, i, x1); x0 = x1; end display(Hence, the critical point (solution of F=0) is (approx), x1,靈敏性分析,考慮最優(yōu)售豬時(shí)間關(guān)于小豬增長(zhǎng)率c=0.025的靈敏性。,xvalues = 0; for c = 0.022:0.001:0.028 y = (0.65-0.01*x)*200*exp(c*x)-0.45*x; dydx=diff(y,x); xmaxc=solve(dydx); xmaxc = double(xmaxc); xmaxc = xmaxc(1); xvalues =

4、 xvalues; xmaxc; end xvalues = xvalues(2:end);,cvalues = 0.022:0.001:0.028; cvalues=cvalues; % transposes the row into a column format short; display(cvalues,xvalues),例3.2 更新消防站的位置。對(duì)響應(yīng)時(shí)間數(shù)據(jù)的統(tǒng)計(jì)分析給出：對(duì)離救火站r英里打來(lái)的求救電話，需要的響應(yīng)時(shí)間估計(jì)為 。下圖給出了從消防管員處得到的從城區(qū)不同區(qū)域打來(lái)的求救電話頻率的估計(jì)數(shù)據(jù)。求新的消防站的最佳位置。,3.2 多變量最優(yōu)化,設(shè)(x,y)為新消防站的位置，對(duì)

5、求救電話的平均響應(yīng)時(shí)間為： 問(wèn)題為在區(qū)域0=x=6, 0=y=6上求z=f(x,y)的最小值。,繪制目標(biāo)函數(shù)圖形,clear all syms x y r1 = sqrt(x-1)2+(y-5)2)0.91; r2 = sqrt(x-3)2+(y-5)2)0.91; r3 = sqrt(x-5)2+(y-5)2)0.91; r4 = sqrt(x-1)2+(y-3)2)0.91; r5 = sqrt(x-3)2+(y-3)2)0.91; r6 = sqrt(x-5)2+(y-3)2)0.91; r7 = sqrt(x-1)2+(y-1)2)0.91; r8 = sqrt(x-3)2+(y-1)

6、2)0.91; r9 = sqrt(x-5)2+(y-1)2)0.91; z = 3.2+1.7*(6*r1+8*r2+8*r3+21*r4+6*r5+3*r6+18*r7+8*r8+6*r9)/84; ezmesh(z),繪制等值線圖,ezcontourf(z,0 6 0 6) colorbar, grid on,隨機(jī)搜索算法,算法：隨機(jī)搜索算法 變量：a=x的下限，b=x的上限 c=y的下限，d=y的上限 xmin,ymin,zmin 輸入：a,b,c,d,N 過(guò)程：開(kāi)始 x=randoma,b,y=randomc,d zmin=f(x,y) 對(duì)n=1到N循環(huán) 開(kāi)始 x=randoma,b

7、 y=randomc,d z=f(x,y) 若zzmin,則 xmin=x,ymin=y,zmin=z 結(jié)束 結(jié)束 輸出：xmin,ymin,zmin,代碼實(shí)現(xiàn),a=0; b=6; c=0; d=6; N=1000; x0 = a+(b-a)*rand(1); y0 = c+(d-c)*rand(1); zmin = subs(z,x,y,x0,y0); fprintf( Iteration xmin ymin zmin valuenn); for n=1:N xnew=a+(b-a)*rand(1); ynew=c+(d-c)*rand(1); znew=subs(z,x,y,xnew,yn

8、ew); if znewzmin xmin=xnew; ymin=ynew; zmin=znew; fprintf(%4.0f %1.6f %1.6f %1.6fn, n, xmin, ymin, zmin); end end,靈敏性分析,a=1.5; b=2; c=2.5; d=3; N=100; x0 = a+(b-a)*rand(1); y0 = c+(d-c)*rand(1); zmin = subs(z,x,y,x0,y0); fprintf( Iteration xmin ymin zmin valuenn); for n=1:N xnew=a+(b-a)*rand(1); yne

9、w=c+(d-c)*rand(1); znew=subs(z,x,y,xnew,ynew); if znewzmin xmin=xnew; ymin=ynew; zmin=znew; fprintf(%4.0f %1.6f %1.6f %1.6fn, n, xmin, ymin, zmin); end end,例3.3 一家草坪家俱廠商生產(chǎn)兩種草坪椅。一種是木架的，一種是鋁管架的。木架椅的生產(chǎn)價(jià)格為每把18美元，鋁管椅為每把10美元。在產(chǎn)品出售的市場(chǎng)上，可以售出的數(shù)量依賴于價(jià)格。據(jù)估計(jì)，若每天售出x把木架椅，y把鋁管椅，木架椅和鋁管椅的出售價(jià)格分別不能超過(guò) ，求最優(yōu)生產(chǎn)量。,問(wèn)題,在生產(chǎn)量的可

10、行域x=0,y=0上求利潤(rùn)函數(shù)z=f(x,y)的最大值。,繪制目標(biāo)函數(shù)及等值線圖,clear all, close all syms x1 x2 z=x1*(10+31*x1(-0.5)+1.3*x2(-0.2)-18*x1+ x2*(5+15*x2(-0.4)+.8*x1(-0.08)-10*x2; ezsurfc(z, 0.1 10 0.1 10); title(Objective Function z);,最優(yōu)值點(diǎn)大致位于x=5,y=6,隨機(jī)搜索求近似最優(yōu)值,a=0; b=10; c=0; d=10; N=1000; x10 = a+(b-a)*rand(1); x20 = c+(d-c

11、)*rand(1); zmin = subs(-z,x1,x2,x10,x20); fprintf( Iteration x1min x2min zmin valuenn); for n=1:N x1new=a+(b-a)*rand(1); x2new=c+(d-c)*rand(1); znew=subs(-z,x1,x2,x1new,x2new); if znewzmin x1min=x1new; x2min=x2new; zmin=znew; fprintf(%4.0f %1.6f %1.6f %1.6fn, n, x1min, x2min, zmin); end end,牛頓法求較精確的

12、近似值,牛頓法見(jiàn)書(shū)p.56 x=x1;x2; F=diff(z,x1); G=diff(z,x2); Dz=F;G; % the gradient vector of z 即求方程組Dz=0的解。,牛頓法代碼實(shí)現(xiàn),dFdx1=diff(F,x1); dFdx2=diff(F,x2); dGdx1=diff(G,x1); dGdx2=diff(G,x2); D2z =dFdx1 dFdx2; dGdx1 dGdx2; % Jacobian of Dz (same as Hessian of D2z) x0=5;5; % initial guess N=10; % number of iterat

13、ions for i=1:N Dz0=subs(Dz,x1,x2,x0(1),x0(2); D2z0=subs(D2z,x1,x2,x0(1),x0(2); xnew=x0-inv(D2z0)*Dz0; x0=xnew; end xmax = xnew zmax = subs(z,x1,x2, xmax(1),xmax(2),xmax figure, ezcontourf(z,0.1 10 0.1 10) hold on plot3(xmax(1),xmax(2),zmax, mo, LineWidth,2,. MarkerEdgeColor,k, MarkerFaceColor,.49 1

14、.63,. MarkerSize,12); title(Countour plot and optimal value);,3.3 線性規(guī)劃,例3.4 一個(gè)家庭農(nóng)場(chǎng)有625英畝的土地可用來(lái)種植農(nóng)作物。這個(gè)家庭可考慮種植的農(nóng)作物有玉米、小麥、燕麥。預(yù)計(jì)有1000英畝-英尺的灌溉用水，農(nóng)場(chǎng)工人每周可以投入的工作時(shí)間為300小時(shí)。其他數(shù)據(jù)如下表。為獲得最大收益，每種作物應(yīng)各種植多少？,農(nóng)場(chǎng)問(wèn)題的有關(guān)數(shù)據(jù),變量：x1,x2,x3=種植玉米、小麥、燕麥的畝數(shù) w=需要的灌溉用水（英畝-英尺） l=需要的勞力（人-小時(shí)/周） t=種植作物的總英畝數(shù) y=總收益（美元）,假設(shè)：w=3.0 x1+1.0 x2

15、+1.5x3=0 目標(biāo)：求y的最大值,建模方法線性規(guī)劃,線性規(guī)劃簡(jiǎn)介見(jiàn)書(shū)p.59 可以用lindo/lingo軟件求解,模型求解,MAX 400 X1 + 200 X2 + 250 X3 SUBJECT TO 3 X1 + X2 + 1.5 X3 = 1000 0.8 X1 + 0.2 X2 + 0.3 X3 = 300 X1 + X2 + X3 = 625 END,reduced cost值表示當(dāng)該非基變量增加一個(gè)單位時(shí)（其他非基變量保持不變）目標(biāo)函數(shù)減少的量(對(duì)max型問(wèn)題) 也可理解為：為了使該非基變量變成基變量，目標(biāo)函數(shù)中對(duì)應(yīng)系數(shù)應(yīng)增加的量,靈敏性分析,增加1英畝-英尺灌溉水量對(duì)最優(yōu)解

16、的影響 MAX 400 X1 + 200 X2 + 250 X3 SUBJECT TO 3 X1 + X2 + 1.5 X3 = 1001 0.8 X1 + 0.2 X2 + 0.3 X3 = 300 X1 + X2 + X3 = 625 END,玉米收益的少量提高對(duì)最優(yōu)解的影響,農(nóng)作物每英畝收益會(huì)隨氣候及市場(chǎng)變化 MAX 450 X1 + 200 X2 + 250 X3 SUBJECT TO 3 X1 + X2 + 1.5 X3 = 1000 0.8 X1 + 0.2 X2 + 0.3 X3 = 300 X1 + X2 + X3 = 625 END,燕麥?zhǔn)找娴纳倭刻岣邔?duì)最優(yōu)解的影響,MAX

17、400 X1 + 200 X2 + 260 X3 SUBJECT TO 3 X1 + X2 + 1.5 X3 = 1000 0.8 X1 + 0.2 X2 + 0.3 X3 = 300 X1 + X2 + X3 = 625 END,新品種玉米,這種玉米新品種需要較少的灌溉用水2.5英畝-英尺（而不是3.0）。 MAX 400 X1 + 200 X2 + 250 X3 SUBJECT TO 2.5 X1 + X2 + 1.5 X3 = 1000 0.8 X1 + 0.2 X2 + 0.3 X3 = 300 X1 + X2 + X3 = 625 END,新增另一新的作物大麥,一英畝大麥需要1.5英

18、畝-英尺的水和0.25人-小時(shí)的勞力，預(yù)期可獲得200美元的收益。 用一個(gè)新的決策變量x4表示種植大麥的英畝數(shù)。 MAX 400 X1 + 200 X2 + 250 X3 + 200 x4 SUBJECT TO 3 X1 + X2 + 1.5 X3 + 1.5 x4 = 1000 0.8 X1 + 0.2 X2 + 0.3 X3 + 0.25 x4 = 300 X1 + X2 + X3 + x4 = 625 END,例3.5 運(yùn)輸問(wèn)題,一家大建筑公司正在三個(gè)地點(diǎn)開(kāi)掘。同時(shí)又在其他4個(gè)地點(diǎn)建筑，這里需要土方的填充。在1，2，3處挖掘產(chǎn)生的土方分別為每天150，400，325立方碼。建筑地點(diǎn)A,B

19、,C,D處需要的填充土方為每天175，125，225，450立方碼。也可以從地點(diǎn)4用每立方碼5美元的價(jià)格獲得額外的填充土方。填充土方運(yùn)輸?shù)馁M(fèi)用約為一貨車(chē)容量（10立方碼）每英里20美元。下表給出了各地點(diǎn)間距離的英里數(shù)。求使公司花費(fèi)最少的運(yùn)輸計(jì)劃。,建筑地點(diǎn)間的距離,變量： xij=從地點(diǎn)i運(yùn)到地點(diǎn)j的土方量（立方碼） si=從地點(diǎn)i運(yùn)出的土方量（立方碼） rj=運(yùn)到地點(diǎn)j的土方量（立方碼） cij=從地點(diǎn)i運(yùn)到地點(diǎn)j的土方運(yùn)輸費(fèi)用（美元/立方碼） dij=地點(diǎn)i到地點(diǎn)j的距離（英里） C=總運(yùn)費(fèi)（美元）,假設(shè),s1=x1A+x1B+x1C+x1D s2=x2A+x2B+x2C+x2D s3=x

20、3A+x3B+x3C+x3D s4=x4A+x4B+x4C+x4D rA=x1A+x2A+x3A+x4A rB= x1B+x2B+x3B+x4B rC=x1C+x2C+x3C+x4C rD=x1D+x2D+x3D+x4D,S1=175,rB=125,rC=225,rD=450; cij=2dij,i=1,2,3 cij=2dij+5,i=4 C=c1Ax1A+c1Bx1B+c1Cx1C+c1Dx1D +c2Ax2A+c2Bx2B+c2Cx2C+c2Dx2D +c3Ax3A+c3Bx3B+c3Cx3C+c3Dx3D +c4Ax4A+c4Bx4B+c4Cx4C+c4Dx4D 目標(biāo)：求C的最小值。,

21、線性規(guī)劃的標(biāo)準(zhǔn)形式,Min y=10 x1A+4x1B+12x1C+20 x1D +8x2A+10 x2B+14x2C+10 x2D +14x3A+12x3B+8x3C+8x3D +23x4A+25x4B+17x4C+9x4D 約束條件：,x1A+x1B+x1C+x1D=175 x1B+x2B+x3B+x4B=125 x1C+x2C+x3C+x4C=225 x1D+x2D+x3D+x4D=450 xij=0,i=1,2,3,4;j=A,B,C,D.,問(wèn)題求解,MIN 10 x1A+4x1B+12x1C+20 x1D +8x2A+10 x2B+14x2C+10 x2D +14x3A+12x3B+

22、8x3C+8x3D +23x4A+25x4B+17x4C+9x4D SUBJECT TO x1A+x1B+x1C+x1D=175 x1B+x2B+x3B+x4B=125 x1C+x2C+x3C+x4C=225 x1D+x2D+x3D+x4D=450 END,穩(wěn)健性分析,MIN 10 x1A+4x1B+12x1C+20 x1D +8x2A+10 x2B+14x2C+10 x2D +14x3A+12x3B+8x3C+8x3D +23x4A+25x4B+17x4C+9x4D SUBJECT TO x1A+x1B+x1C+x1D=150 x2A+x2B+x2C+x2D=400 x3A+x3B+x3C+

23、x3D=325 x1A+x2A+x3A+x4A=175 x1B+x2B+x3B+x4B=125 x1C+x2C+x3C+x4C=225 x1D+x2D+x3D+x4D=450 END,3.4 離散最優(yōu)化,例3.6 仍考慮農(nóng)場(chǎng)問(wèn)題。這個(gè)家庭有625英畝的土地用來(lái)種植。有5塊每塊120英畝的土地和另一塊25英畝的土地。這家人想在每塊地上種植一種作物：玉米、小麥或燕麥。與前面一樣，有1000英畝-英尺可用的灌溉用水，每周農(nóng)場(chǎng)工人可提供300小時(shí)的勞力。其他數(shù)據(jù)下表給出。求應(yīng)在每塊地中種哪種植物，從而使總收益達(dá)最大。,農(nóng)場(chǎng)問(wèn)題的有關(guān)數(shù)據(jù),變量,x1=種植玉米的120英畝地塊數(shù) x2=種植小麥的120英

24、畝地塊數(shù) x3=種植燕麥的120英畝地塊數(shù) x4=種植玉米的25英畝地塊數(shù) x5=種植小麥的25英畝地塊數(shù) x6=種植燕麥的25英畝地塊數(shù) w=需要的灌溉用水（英畝-英尺） l=需要的勞力（人-小時(shí)/周） t=種植作物的總英畝數(shù) y=總收益（美元）,假設(shè),w=120(3.0 x1+1.0 x2+1.5x3)+25(3.0 x4+1.0 x5+1.5x6) l=120(0.8x1+0.2x2+0.3x3)+25(0.8x4+0.2x5+0.3x6) t=120(x1+x2+x3)+25(x4+x5+x6) y=120(400 x1+200 x2+250 x3)+25(400 x4+200 x5+

25、250 x6) w=1000,l=300,t=625 x1+x2+x3=5, x4+x5+x6=1,x1,x6為非負(fù)整數(shù)。 目標(biāo)：求y最大值。,整數(shù)規(guī)劃的標(biāo)準(zhǔn)形式：,max y=48000 x1+24000 x2+30000 x3+10000 x4+5000 x5+6250 x6 s.t. 375x1+125x2+187.5x3+75x4+25x5+37.5x6=1000 100 x1+ 25x2+ 37.5x3+ 20 x4+ 5x5 +7.5x6 =300 x1 +x2 +x3 =5 x4 +x5 +x6 =1 x1,x6為非負(fù)整數(shù).,問(wèn)題求解,MAX 48000 x1+24000 x2+

26、30000 x3+10000 x4+5000 x5+6250 x6 SUBJECT TO 375x1+125x2+187.5x3+75x4+25x5+37.5x6=1000 100 x1+25x2+37.5x3+20 x4+5x5+7.5x6=300 x1+x2+x3=5 x4+x5+x6=1 END GIN 6,靈敏性分析,有100英畝-英尺的額外灌溉水量可用。 只要灌溉水量不低于1000-25=975，最優(yōu)解不會(huì)改變。 可用水量只有950時(shí)，又如何？ 以上靈敏性分析顯示，IP問(wèn)題解的不可預(yù)期的特點(diǎn)。,穩(wěn)健性分析,例如最小地塊為2時(shí)，問(wèn)題為：,Max y=800 x1+400 x2+500

27、x3 s.t. 6.0 x1+2.0 x2+3.0 x3=1000 1.6x1+0.4x2+0.6x3=300 x1+x2+x3=312 x1,x2,x3為非負(fù)整數(shù)。,問(wèn)題求解,MAX 800 x1+400 x2+500 x3 SUBJECT TO 6.0 x1+2.0 x2+3.0 x3=1000 1.6x1+0.4x2+0.6x3=300 x1+x2+x3=312 END GIN 3,例3.7,仍考慮例3.5中的土方問(wèn)題。在使用10立方碼載重量的卡車(chē)運(yùn)輸?shù)那闆r下，公司已經(jīng)確定了最優(yōu)的運(yùn)輸方案。公司又有3輛更大的卡車(chē)可用于運(yùn)輸，載重量為20立方碼。使用這些車(chē)輛可能會(huì)在運(yùn)輸中節(jié)省一些資金。載重

28、10立方碼的卡車(chē)平均用20分鐘裝車(chē)，5分鐘卸車(chē)，每小時(shí)平均開(kāi)20英里，費(fèi)用為每英里單位重量20美元。載重量20立方碼的卡車(chē)30分鐘裝車(chē)，5分鐘卸車(chē)，每小時(shí)平均開(kāi)20英里，費(fèi)用為每英里單位重量30美元，為最大限度地節(jié)省運(yùn)輸費(fèi)用，應(yīng)如何安排車(chē)輛的使用？,第一步，提出問(wèn)題,哪條路上使用哪種卡車(chē)？,假設(shè)每條路上只使用一種類(lèi)型的卡車(chē)。 由于大卡車(chē)運(yùn)量是小卡車(chē)的2倍，而費(fèi)用卻不到小卡車(chē)的2倍，因此，我們希望將這些卡車(chē)安排到能節(jié)約資金最多的路線上。 計(jì)算每條路上使用不同類(lèi)型的卡車(chē)能節(jié)約的費(fèi)用。,例如路線1：從1到B運(yùn)125立方碼，距離2英里。 小卡車(chē)一次裝車(chē)20分鐘，卸車(chē)5分鐘，每小時(shí)20英里要開(kāi)6分鐘，因

29、此運(yùn)一次需要31分鐘。125立方碼的土需要運(yùn)13次，共需13*31=403分鐘。假設(shè)一個(gè)工作日是8小時(shí)，這樣每輛卡車(chē)工作時(shí)間不超過(guò)480分鐘。因此，路線1用一輛卡車(chē)就足夠。,小卡車(chē)運(yùn)輸費(fèi)用：13（次）*2（英里/次）*20（美元/英里）=520美元 如果線路1用大卡車(chē)，運(yùn)一次需要30+5+6=41分鐘，為運(yùn)走125立方碼的土，需要7次，共需7*41=287分鐘，因此一輛大卡車(chē)足夠。 大卡車(chē)運(yùn)輸費(fèi)用為420美元，比用小卡車(chē)節(jié)省100美元。,類(lèi)似計(jì)算其他路線上的情況,路線2：需要大卡車(chē)1輛，節(jié)約費(fèi)用360美元 路線3：需要大卡車(chē)2輛，節(jié)約費(fèi)用400美元 路線4：需要大卡車(chē)1輛，節(jié)約費(fèi)用200美元 路線5：需要大卡車(chē)2輛，節(jié)約費(fèi)用640美元,變量及假設(shè),變量： xi=1 如果在路線i上使用大卡車(chē) xi=0 如果在路線i上使用小卡車(chē) T=用的大卡車(chē)總數(shù) y=節(jié)約的總費(fèi)用（美元）,假設(shè) T=1x1+1x2+2x3+1x4+2