最优化计算方法ppt课件

第三章最优化计算方法,单变量优化多变量优化线性规划离散最优化,1,单变量优化,例3.1再来考虑售猪问题。但现在考虑到猪的生长率不是常数的事实。假设现在猪还小，生长率是增加的。什么时候将猪售出从而获得最大收益？,2,求解模型图像法,clearall;closeall;symsxy=(0.65-0.01*x)*200*exp(0.025*x)-0.45*x;ezplot(y,0,20);gridon,3,ezplot(y,0,20),4,ezplot(y,0,40),5,ezplot(y,18,22);gridon,6,ezplot(y,19,20);gridon,7,数值方法求解-Matlab,dydx=diff(y,x)xmax=solve(dydx);xmax=double(xmax)xmax=xmax(1)ymax=subs(y,x,xmax),8,Newton法,求方程F(x)=0的根.牛顿法：x(n)=x(n-1)-F(x(n-1)/F(x(n-1),9,F=dydx;F1=diff(F,x);formatlongN=10;%numberofiterationsx0=19%initialguessfprintf(iterationxvaluenn);fori=1:Nx1=x0-subs(F,x,x0)/subs(F1,x,x0);fprintf(%5.0f%1.16fn,i,x1);x0=x1;enddisplay(Hence,thecriticalpoint(solutionofF=0)is(approx),x1,10,灵敏性分析,考虑最优售猪时间关于小猪增长率c=0.025的灵敏性。,11,xvalues=0;forc=0.022:0.001:0.028y=(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=xvalues;xmaxc;endxvalues=xvalues(2:end);,12,cvalues=0.022:0.001:0.028;cvalues=cvalues;%transposestherowintoacolumnformatshort;display(cvalues,xvalues),13,例3.2更新消防站的位置。对响应时间数据的统计分析给出：对离救火站r英里打来的求救电话，需要的响应时间估计为。下图给出了从消防管员处得到的从城区不同区域打来的求救电话频率的估计数据。求新的消防站的最佳位置。,3.2多变量最优化,14,15,设(x,y)为新消防站的位置，对求救电话的平均响应时间为：问题为在区域0=x=6,0=y=6上求z=f(x,y)的最小值。,16,绘制目标函数图形,clearallsymsxyr1=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)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),17,18,绘制等值线图,ezcontourf(z,0606)colorbar,gridon,19,随机搜索算法,算法：随机搜索算法变量：a=x的下限，b=x的上限c=y的下限，d=y的上限xmin,ymin,zmin输入：a,b,c,d,N过程：开始x=randoma,b,20,y=randomc,dzmin=f(x,y)对n=1到N循环开始x=randoma,by=randomc,dz=f(x,y)若zzmin,则xmin=x,ymin=y,zmin=z结束结束输出：xmin,ymin,zmin,21,代码实现,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(Iterationxminyminzminvaluenn);forn=1:Nxnew=a+(b-a)*rand(1);ynew=c+(d-c)*rand(1);znew=subs(z,x,y,xnew,ynew);ifznew=0上求利润函数z=f(x,y)的最大值。,25,绘制目标函数及等值线图,clearall,closeallsymsx1x2z=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.1100.110);title(ObjectiveFunctionz);,26,最优值点大致位于x=5,y=6,27,随机搜索求近似最优值,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(Iterationx1minx2minzminvaluenn);forn=1:Nx1new=a+(b-a)*rand(1);x2new=c+(d-c)*rand(1);znew=subs(-z,x1,x2,x1new,x2new);ifznewzminx1min=x1new;x2min=x2new;zmin=znew;fprintf(%4.0f%1.6f%1.6f%1.6fn,n,x1min,x2min,zmin);endend,28,牛顿法求较精确的近似值,牛顿法见书p.56x=x1;x2;F=diff(z,x1);G=diff(z,x2);Dz=F;G;%thegradientvectorofz即求方程组Dz=0的解。,29,牛顿法代码实现,dFdx1=diff(F,x1);dFdx2=diff(F,x2);dGdx1=diff(G,x1);dGdx2=diff(G,x2);D2z=dFdx1dFdx2;dGdx1dGdx2;%JacobianofDz(sameasHessianofD2z)x0=5;5;%initialguessN=10;%numberofiterationsfori=1:NDz0=subs(Dz,x1,x2,x0(1),x0(2);D2z0=subs(D2z,x1,x2,x0(1),x0(2);xnew=x0-inv(D2z0)*Dz0;x0=xnew;endxmax=xnewzmax=subs(z,x1,x2,xmax(1),xmax(2),30,xmaxfigure,ezcontourf(z,0.1100.110)holdonplot3(xmax(1),xmax(2),zmax,mo,LineWidth,2,.MarkerEdgeColor,k,MarkerFaceColor,.491.63,.MarkerSize,12);title(Countourplotandoptimalvalue);,31,3.3线性规划,例3.4一个家庭农场有625英亩的土地可用来种植农作物。这个家庭可考虑种植的农作物有玉米、小麦、燕麦。预计有1000英亩-英尺的灌溉用水，农场工人每周可以投入的工作时间为300小时。其他数据如下表。为获得最大收益，每种作物应各种植多少？,32,农场问题的有关数据,33,变量：x1,x2,x3=种植玉米、小麦、燕麦的亩数w=需要的灌溉用水（英亩-英尺）l=需要的劳力（人-小时/周）t=种植作物的总英亩数y=总收益（美元）,34,假设：w=3.0 x1+1.0 x2+1.5x3=0目标：求y的最大值,35,建模方法线性规划,线性规划简介见书p.59可以用lindo/lingo软件求解,36,模型求解,MAX400X1+200X2+250X3SUBJECTTO3X1+X2+1.5X3=10000.8X1+0.2X2+0.3X3=300X1+X2+X3=625END,37,reducedcost值表示当该非基变量增加一个单位时（其他非基变量保持不变）目标函数减少的量(对max型问题)也可理解为：为了使该非基变量变成基变量，目标函数中对应系数应增加的量,38,灵敏性分析,增加1英亩-英尺灌溉水量对最优解的影响MAX400X1+200X2+250X3SUBJECTTO3X1+X2+1.5X3=10010.8X1+0.2X2+0.3X3=300X1+X2+X3=625END,39,玉米收益的少量提高对最优解的影响,农作物每英亩收益会随气候及市场变化MAX450X1+200X2+250X3SUBJECTTO3X1+X2+1.5X3=10000.8X1+0.2X2+0.3X3=300X1+X2+X3=625END,40,燕麦收益的少量提高对最优解的影响,MAX400X1+200X2+260X3SUBJECTTO3X1+X2+1.5X3=10000.8X1+0.2X2+0.3X3=300X1+X2+X3=625END,41,新品种玉米,这种玉米新品种需要较少的灌溉用水2.5英亩-英尺（而不是3.0）。MAX400X1+200X2+250X3SUBJECTTO2.5X1+X2+1.5X3=10000.8X1+0.2X2+0.3X3=300X1+X2+X3=625END,42,新增另一新的作物大麦,一英亩大麦需要1.5英亩-英尺的水和0.25人-小时的劳力，预期可获得200美元的收益。用一个新的决策变量x4表示种植大麦的英亩数。MAX400X1+200X2+250X3+200 x4SUBJECTTO3X1+X2+1.5X3+1.5x4=10000.8X1+0.2X2+0.3X3+0.25x4=225,rD=450;cij=2dij,i=1,2,3cij=2dij+5,i=4C=c1Ax1A+c1Bx1B+c1Cx1C+c1Dx1D+c2Ax2A+c2Bx2B+c2Cx2C+c2Dx2D+c3Ax3A+c3Bx3B+c3Cx3C+c3Dx3D+c4Ax4A+c4Bx4B+c4Cx4C+c4Dx4D目标：求C的最小值。,48,线性规划的标准形式,Miny=10 x1A+4x1B+12x1C+20 x1D+8x2A+10 x2B+14x2C+10 x2D+14x3A+12x3B+8x3C+8x3D+23x4A+25x4B+17x4C+9x4D约束条件：,49,x1A+x1B+x1C+x1D=175x1B+x2B+x3B+x4B=125x1C+x2C+x3C+x4C=225x1D+x2D+x3D+x4D=450 xij=0,i=1,2,3,4;j=A,B,C,D.,50,问题求解,MIN10 x1A+4x1B+12x1C+20 x1D+8x2A+10 x2B+14x2C+10 x2D+14x3A+12x3B+8x3C+8x3D+23x4A+25x4B+17x4C+9x4DSUBJECTTOx1A+x1B+x1C+x1D=175x1B+x2B+x3B+x4B=125x1C+x2C+x3C+x4C=225x1D+x2D+x3D+x4D=450END,51,稳健性分析,MIN10 x1A+4x1B+12x1C+20 x1D+8x2A+10 x2B+14x2C+10 x2D+14x3A+12x3B+8x3C+8x3D+23x4A+25x4B+17x4C+9x4DSUBJECTTOx1A+x1B+x1C+x1D=150 x2A+x2B+x2C+x2D=400 x3A+x3B+x3C+x3D=325x1A+x2A+x3A+x4A=175x1B+x2B+x3B+x4B=125x1C+x2C+x3C+x4C=225x1D+x2D+x3D+x4D=450END,52,3.4离散最优化,例3.6仍考虑农场问题。这个家庭有625英亩的土地用来种植。有5块每块120英亩的土地和另一块25英亩的土地。这家人想在每块地上种植一种作物：玉米、小麦或燕麦。与前面一样，有1000英亩-英尺可用的灌溉用水，每周农场工人可提供300小时的劳力。其他数据下表给出。求应在每块地中种哪种植物，从而使总收益达最大。,53,农场问题的有关数据,54,变量,x1=种植玉米的120英亩地块数x2=种植小麦的120英亩地块数x3=种植燕麦的120英亩地块数x4=种植玉米的25英亩地块数x5=种植小麦的25英亩地块数x6=种植燕麦的25英亩地块数w=需要的灌溉用水（英亩-英尺）l=需要的劳力（人-小时/周）t=种植作物的总英亩数y=总收益（美元）,55,假设,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=625x1+x2+x3=5,x4+x5+x6=1,x1,x6为非负整数。目标：求y最大值。,56,整数规划的标准形式：,maxy=48000 x1+24000 x2+30000 x3+10000 x4+5000 x5+6250 x6s.t.375x1+125x2+187.5x3+75x4+25x5+37.5x6=1000100 x1+25x2+37.5x3+20 x4+5x5+7.5x6=300 x1+x2+x3=5x4+x5+x6=1x1,x6为非负整数.,57,问题求解,MAX48000 x1+24000 x2+30000 x3+10000 x4+5000 x5+6250 x6SUBJECTTO375x1+125x2+187.5x3+75x4+25x5+37.5x6=1000100 x1+25x2+37.5x3+20 x4+5x5+7.5x6=300 x1+x2+x3=5x4+x5+x6=1ENDGIN6,58,灵敏性分析,有100英亩-英尺的额外灌溉水量可用。只要灌溉水量不低于1000-25=975，最优解不会改变。可用水量只有950时，又如何？以上灵敏性分析显示，IP问题解的不可预期的特点。,59,稳健性分析,60,例如最小地块为2时，问题为：,Maxy=800 x1+400 x2+500 x3s.t.6.0 x1+2.0 x2+3.0 x3=10001.6x1+0.4x2+0.6x3=300 x1+x2+x3=312x1,x2,x3为非负整数。,61,问题求解,MAX800 x1+400 x2+500 x3SUBJECTTO6.0 x1+2.0 x2+3.0 x3=10001.6x1+0.4x2+0.6x3=300 x1+x2+x3=312ENDGIN3,62,例3.7,仍考虑例3.5中的土方问题。在使用10立方码载重量的卡车运输的情况下，公司已经确定了最优的运输方案。公司又有3辆更大的卡车可用于运输，载重量为20立方码。使用这些车辆可能会在运输中节省一些资金。载重10立方码的卡车平均用20分钟装车，5分钟卸车，每小时平均开20英里，费用为每英里单位重量20美元。载重量20立方码的卡车30分钟装车，5分钟卸车，每小时平均开20英里，费用为每英里单位重量30美元，为最大限度地节省运输费用，应如何安排车辆的使用？,63,第一步，提出问题,64,哪条路上使用哪种卡车？,假设每条路上只使用一种类型的卡车。由于大卡车运量是小卡车的2倍，而费用却不到小卡车的2倍，因此，我们希望将这些卡车安排到能节约资金最多的路线上。计算每条路上使用不同类型的卡车能节约的费用。,65,例如路线1：从1到B运125立方码，距离2英里。小卡车一次装车20分钟，卸车5分钟，每小时20英里要开6分钟，因此运一次需要31分钟。125立方码的土需要运13次，共需13*31=403分钟。假设一个工作日是8小时，这样每辆卡车工作时间不超过480分钟。因此，路线1用一辆卡车就足够。,66,小卡车运输费用：13（次）*2（英里/次）*20（美元/英里）=520美元如果线路1用大卡车，运一次需要30+5+6=41分钟，为运走125立方码的土，需要7次，共需7*41=287分钟，因此一辆大卡车足够。大卡车运输费用为420美元，比用小卡车节省100美元。,67,类似计算其他路线上的情况,路线2：需要大卡车1辆，节约费用360美元路线3：需要大卡车2辆，节约费用400美元路线4：需要大卡车1辆，节约费用200美元路线5：需要大卡车2辆，节约费用640美元,68,变量及假设,变量：xi=1如果在路线i上使用大卡车xi=0如果在路线i上使用小卡车T=用的大卡车总数y=节约的总费用（美元）,69,假设T=1x1+1x2+2x3+1x4+2x5y=100 x1+360 x2+400 x3+200 x4+640 x5T=3目标：求y的最大值,70,第二步，选择建模方法,二值整数规划-BIP,71,第三步，将问题表为标准形式,MAXy=100 x1+360 x2+400 x3+200 x4+640 x5s.t.