《最优化计算方法PPT课件.ppt》由会员分享，可在线阅读，更多相关《最优化计算方法PPT课件.ppt（78页珍藏版）》请在三一文库上搜索。
1、1,第三章 最优化计算方法,单变量优化 多变量优化 线性规划 离散最优化,2,单变量优化,例3.1 再来考虑售猪问题。但现在考虑到猪的生长率不是常数的事实。假设现在猪还小，生长率是增加的。什么时候将猪售出从而获得最大收益？,3,求解模型图像法,clear all; close all; syms x y = (0.65-0.01*x)*200*exp(0.025*x)-0.45*x; ezplot(y,0,20); grid on,4,ezplot(y,0,20),5,ezplot(y,0,40),6,ezplot(y,18,22); grid on,7,ezplot(y,19,20); gr
2、id on,8,数值方法求解-Matlab,dydx = diff(y,x) xmax = solve(dydx); xmax = double(xmax) xmax =xmax(1) ymax=subs(y,x,xmax),9,Newton 法,求方程F(x)=0的根. 牛顿法： x(n)=x(n-1)-F(x(n-1)/F(x(n-1),10,F = dydx; F1 = diff(F,x); format long N = 10; % number of iterations x0 = 19 % initial guess fprintf( iteration xvaluenn); fo
3、r i=1:N x1=x0-subs(F,x,x0)/subs(F1,x,x0); fprintf(%5.0f %1.16fn, i, x1); x0 = x1; end display(Hence, the critical point (solution of F=0) is (approx), x1,11,灵敏性分析,考虑最优售猪时间关于小猪增长率c=0.025的灵敏性。,12,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(
4、dydx); xmaxc = double(xmaxc); xmaxc = xmaxc(1); xvalues = xvalues; xmaxc; end xvalues = xvalues(2:end);,13,cvalues = 0.022:0.001:0.028; cvalues=cvalues; % transposes the row into a column format short; display(cvalues,xvalues),14,例3.2 更新消防站的位置。对响应时间数据的统计分析给出：对离救火站r英里打来的求救电话，需要的响应时间估计为 。下图给出了从消防管员处得到
5、的从城区不同区域打来的求救电话频率的估计数据。求新的消防站的最佳位置。,3.2 多变量最优化,15,16,设(x,y)为新消防站的位置，对求救电话的平均响应时间为： 问题为在区域0=x=6, 0=y=6上求z=f(x,y)的最小值。,17,绘制目标函数图形,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 = sq
6、rt(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)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),18,19,绘制等值线图,ezcontourf(z,0 6 0 6) colorbar, grid on,20,随机搜索算法,算法：随机搜索算法 变量：a=x的下限，b=x的上限 c=y的下限，d=y的上限 xmin,ymin,zm
7、in 输入：a,b,c,d,N 过程：开始 x=randoma,b,21,y=randomc,d zmin=f(x,y) 对n=1到N循环 开始 x=randoma,b y=randomc,d z=f(x,y) 若zzmin,则 xmin=x,ymin=y,zmin=z 结束 结束 输出：xmin,ymin,zmin,22,代码实现,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
8、valuenn); for n=1:N xnew=a+(b-a)*rand(1); ynew=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,23,灵敏性分析,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
9、,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,ynew); if znewzmin xmin=xnew; ymin=ynew; zmin=znew; fprintf(%4.0f %1.6f %1.6f %1.6fn, n, xmin, ymin, zmin); end end,24,例3.3 一家草坪家俱厂商生产两种草坪椅。一种是木架的，一种是铝管架的。木架椅的生产价格为每把18美元
10、，铝管椅为每把10美元。在产品出售的市场上，可以售出的数量依赖于价格。据估计，若每天售出x把木架椅，y把铝管椅，木架椅和铝管椅的出售价格分别不能超过 ，求最优生产量。,25,问题,在生产量的可行域x=0,y=0上求利润函数z=f(x,y)的最大值。,26,绘制目标函数及等值线图,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 Functi
11、on z);,27,最优值点大致位于x=5,y=6,28,随机搜索求近似最优值,a=0; b=10; c=0; d=10; N=1000; x10 = a+(b-a)*rand(1); x20 = c+(d-c)*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=
12、x1new; x2min=x2new; zmin=znew; fprintf(%4.0f %1.6f %1.6f %1.6fn, n, x1min, x2min, zmin); end end,29,牛顿法求较精确的近似值,牛顿法见书p.56 x=x1;x2; F=diff(z,x1); G=diff(z,x2); Dz=F;G; % the gradient vector of z 即求方程组Dz=0的解。,30,牛顿法代码实现,dFdx1=diff(F,x1); dFdx2=diff(F,x2); dGdx1=diff(G,x1); dGdx2=diff(G,x2); D2z =dFdx1
13、 dFdx2; dGdx1 dGdx2; % Jacobian of Dz (same as Hessian of D2z) x0=5;5; % initial guess N=10; % number of iterations 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),31,xmax figure, ezcontour
14、f(z,0.1 10 0.1 10) hold on plot3(xmax(1),xmax(2),zmax, mo, LineWidth,2,. MarkerEdgeColor,k, MarkerFaceColor,.49 1 .63,. MarkerSize,12); title(Countour plot and optimal value);,32,3.3 线性规划,例3.4 一个家庭农场有625英亩的土地可用来种植农作物。这个家庭可考虑种植的农作物有玉米、小麦、燕麦。预计有1000英亩-英尺的灌溉用水，农场工人每周可以投入的工作时间为300小时。其他数据如下表。为获得最大收益，每种作物
15、应各种植多少？,33,农场问题的有关数据,34,变量：x1,x2,x3=种植玉米、小麦、燕麦的亩数 w=需要的灌溉用水（英亩-英尺） l=需要的劳力（人-小时/周） t=种植作物的总英亩数 y=总收益（美元）,35,假设：w=3.0 x1+1.0 x2+1.5x3=0 目标：求y的最大值,36,建模方法线性规划,线性规划简介见书p.59 可以用lindo/lingo软件求解,37,模型求解,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 + X
16、2 + X3 = 625 END,38,reduced cost值表示当该非基变量增加一个单位时（其他非基变量保持不变）目标函数减少的量(对max型问题) 也可理解为：为了使该非基变量变成基变量，目标函数中对应系数应增加的量,39,灵敏性分析,增加1英亩-英尺灌溉水量对最优解的影响 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,40,玉米收益的少量提高对最优解的影响,农作物每英亩收益会随气候及市场变化
17、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,41,燕麦收益的少量提高对最优解的影响,MAX 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,42,新品种玉米,这种玉米新品种需要较少的灌溉用水2.5英亩-英尺（而不是3.0
18、）。 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,43,新增另一新的作物大麦,一英亩大麦需要1.5英亩-英尺的水和0.25人-小时的劳力，预期可获得200美元的收益。 用一个新的决策变量x4表示种植大麦的英亩数。 MAX 400 X1 + 200 X2 + 250 X3 + 200 x4 SUBJECT TO 3 X1 + X2 + 1.5 X3 + 1.5 x4 = 1000 0.8 X1 +
19、0.2 X2 + 0.3 X3 + 0.25 x4 = 300 X1 + X2 + X3 + x4 = 625 END,44,例3.5 运输问题,一家大建筑公司正在三个地点开掘。同时又在其他4个地点建筑，这里需要土方的填充。在1，2，3处挖掘产生的土方分别为每天150，400，325立方码。建筑地点A,B,C,D处需要的填充土方为每天175，125，225，450立方码。也可以从地点4用每立方码5美元的价格获得额外的填充土方。填充土方运输的费用约为一货车容量（10立方码）每英里20美元。下表给出了各地点间距离的英里数。求使公司花费最少的运输计划。,45,建筑地点间的距离,46,变量： xij=
20、从地点i运到地点j的土方量（立方码） si=从地点i运出的土方量（立方码） rj=运到地点j的土方量（立方码） cij=从地点i运到地点j的土方运输费用（美元/立方码） dij=地点i到地点j的距离（英里） C=总运费（美元）,47,假设,s1=x1A+x1B+x1C+x1D s2=x2A+x2B+x2C+x2D s3=x3A+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,48,S1=175,rB=125,rC=225,rD=
21、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 目标：求C的最小值。,49,线性规划的标准形式,Min y=10 x1A+4x1B+12x1C+20 x1D +8x2A+10 x2B+14x2C+10 x2D +14x3A+12x3B+8x3C+8x3D +23x4A+25x4B+17x4C+9x4D 约束条件：,50,x1A+x1B+x
22、1C+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.,51,问题求解,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=175 x1B+x2B+x3B+x4B=125 x1C+x2C+x3C+x4C=225 x1D+x2D+x3D+x4D=450 E
23、ND,52,稳健性分析,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+x3D=325 x1A+x2A+x3A+x4A=175 x1B+x2B+x3B+x4B=125 x1C+x2C+x3C+x4C=225 x1D+x2D+x3D+x4D=450 END,53,3.4 离散最优化,例3.6 仍考虑农场问题。这个家庭有
24、625英亩的土地用来种植。有5块每块120英亩的土地和另一块25英亩的土地。这家人想在每块地上种植一种作物：玉米、小麦或燕麦。与前面一样，有1000英亩-英尺可用的灌溉用水，每周农场工人可提供300小时的劳力。其他数据下表给出。求应在每块地中种哪种植物，从而使总收益达最大。,54,农场问题的有关数据,55,变量,x1=种植玉米的120英亩地块数 x2=种植小麦的120英亩地块数 x3=种植燕麦的120英亩地块数 x4=种植玉米的25英亩地块数 x5=种植小麦的25英亩地块数 x6=种植燕麦的25英亩地块数 w=需要的灌溉用水（英亩-英尺） l=需要的劳力（人-小时/周） t=种植作物的总英亩数
25、 y=总收益（美元）,56,假设,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+250 x6) w=1000,l=300,t=625 x1+x2+x3=5, x4+x5+x6=1,x1,x6为非负整数。 目标：求y最大值。,57,整数规划的标准形式：,max y=48000 x1+24000 x2+3
26、0000 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为非负整数.,58,问题求解,MAX 48000 x1+24000 x2+30000 x3+10000 x4+5000 x5+6250 x6 SUBJECT TO 375x1+125x2+187.5x3+75x4+25x5+37.5x6=1000 100 x1+25x2+37.5x3
27、+20 x4+5x5+7.5x6=300 x1+x2+x3=5 x4+x5+x6=1 END GIN 6,59,灵敏性分析,有100英亩-英尺的额外灌溉水量可用。 只要灌溉水量不低于1000-25=975，最优解不会改变。 可用水量只有950时，又如何？ 以上灵敏性分析显示，IP问题解的不可预期的特点。,60,稳健性分析,61,例如最小地块为2时，问题为：,Max y=800 x1+400 x2+500 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为非负整数。,62,问题求解,MAX
28、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,63,例3.7,仍考虑例3.5中的土方问题。在使用10立方码载重量的卡车运输的情况下，公司已经确定了最优的运输方案。公司又有3辆更大的卡车可用于运输，载重量为20立方码。使用这些车辆可能会在运输中节省一些资金。载重10立方码的卡车平均用20分钟装车，5分钟卸车，每小时平均开20英里，费用为每英里单位重量20美元。载重量20立方码的卡车30分钟装车，5分钟卸车，每小时平均开20英里，费用为每英
29、里单位重量30美元，为最大限度地节省运输费用，应如何安排车辆的使用？,64,第一步，提出问题,65,哪条路上使用哪种卡车？,假设每条路上只使用一种类型的卡车。 由于大卡车运量是小卡车的2倍，而费用却不到小卡车的2倍，因此，我们希望将这些卡车安排到能节约资金最多的路线上。 计算每条路上使用不同类型的卡车能节约的费用。,66,例如路线1：从1到B运125立方码，距离2英里。 小卡车一次装车20分钟，卸车5分钟，每小时20英里要开6分钟，因此运一次需要31分钟。125立方码的土需要运13次，共需13*31=403分钟。假设一个工作日是8小时，这样每辆卡车工作时间不超过480分钟。因此，路线1用一辆卡
30、车就足够。,67,小卡车运输费用：13（次）*2（英里/次）*20（美元/英里）=520美元 如果线路1用大卡车，运一次需要30+5+6=41分钟，为运走125立方码的土，需要7次，共需7*41=287分钟，因此一辆大卡车足够。 大卡车运输费用为420美元，比用小卡车节省100美元。,68,类似计算其他路线上的情况,路线2：需要大卡车1辆，节约费用360美元 路线3：需要大卡车2辆，节约费用400美元 路线4：需要大卡车1辆，节约费用200美元 路线5：需要大卡车2辆，节约费用640美元,69,变量及假设,变量： xi=1 如果在路线i上使用大卡车 xi=0 如果在路线i上使用小卡车 T=用的
31、大卡车总数 y=节约的总费用（美元）,70,假设 T=1x1+1x2+2x3+1x4+2x5 y=100 x1+360 x2+400 x3+200 x4+640 x5 T=3 目标：求y的最大值,71,第二步，选择建模方法,二值整数规划-BIP,72,第三步，将问题表为标准形式,MAX y=100 x1+360 x2+400 x3+200 x4+640 x5 s.t. 1x1+1x2+2x3+1x4+2x5=3 xi取0或1，i=1，2，3，4，5.,73,第四步，模型求解,MAX 100 x1+360 x2+400 x3+200 x4+640 x5 subject to 1x1+1x2+2x
32、3+1x4+2x5=3 end int 5,74,Report,OBJECTIVE FUNCTION VALUE 1) 1000.000 VARIABLE VALUE REDUCED COST X1 0.000000 -100.000000 X2 1.000000 -360.000000 X3 0.000000 -400.000000 X4 0.000000 -200.000000 X5 1.000000 -640.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 0.000000 NO. ITERATIONS= 5 BRANCHES= 0
33、 DETERM.= 1.000E 0,75,灵敏性分析,可能节约的资金与大卡车数量的关系 公司可能有额外的大卡车，或可以租用大卡车，这里需要考虑的是是否值得的问题。,76,可用大卡车数量的灵敏性,77,分析：线路上节省的费用变化对最优解的影响,T=1x1+1x2+2x3+1x4+2x5 y=100 x1+360 x2+400 x3+200 x4+640 x5 路线1：一辆大卡车一天节约100美元；路线2：360美元；路线3，4：200美元；路线5：320美元 路线5节约的费用的小改变，不会影响我们的最优决策：在2，5使用大卡车。实际上，任何大于400的数（每辆大卡车节约200）都会得到同样的最有决策，小于400的值会使我们将大卡车安排到线路2，3上。,78,稳健性分析,二值约束可用来限制可能的决策。 情形一：由于政治原因，大卡车不能用在线路2上。 情形二：由于类似的政治原因，管理层决定在线路4上使用大卡车，那么在线路3上也要使用大卡车。 作业：习题3.5 6，7，10，12，15，21，22,