《最优化计算方法》由会员分享，可在线阅读，更多相关《最优化计算方法（78页珍藏版）》请在金锄头文库上搜索。
1、第三章 最优化计算方法 单变量优化 多变量优化 线性规划 离散最优化单变量优化 例3.1 再来考虑售猪问题。但现在考虑到猪 的生长率不是常数的事实。假设现在猪还 小，生长率是增加的。什么时候将猪售出 从而获得最大收益？求解模型图像法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 onezplot(y,0,20)ezplot(y,0,40)ezplot(y,18,22); grid onezplot(y,19,20); grid on数值方法求解-Matlab
2、dydx = diff(y,x) xmax = 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)/s
3、ubs(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 灵敏性分析 考虑最优售猪时间关于小猪增长率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); xmax
4、c = xmaxc(1); xvalues = 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 更新消防站的位置。对响应时间数 据的统计分析给出：对离救火站r英里打来 的求救电话，需要的响应时间估计为 。下图给出了从消防管员处得到的从城区 不同区域打来的求救电话频率的估计数据 。求新的消防站的最佳位置。3
5、.2 多变量最优化3014212112325330128521001063131023111 设(x,y)为新消防站的位置，对求救电话的平均响 应时间为： 问题为在区域0=0,y=0上求利润函数 z=f(x,y)的最大值。绘制目标函数及等值线图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); 最优值点大致位于x
6、=5,y=6随机搜索求近似最优值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 znew=0 目标：求y的最大值建模方法线性规划 线性规划简介见书p.59 可
7、以用lindo/lingo软件求解模型求解MAX 400 X1 + 200 X2 + 250 X3 SUBJECT TO 3 X1 + X2 + 1.5 X3 =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目标：求C的最小值。线性规划的标准形式Min y=10x1A+4x1B+12x1C+20x1D+
8、8x2A+10x2B+14x2C+10x2D+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.问题求解MIN 10x1A+4x1B+12x1C+20x1D+8x2A+10x2B+14x2C+10x2D+14x3A+12x3B+8x3C+8x3D+23x4A+25x4B+17x4C+9x4D SUBJECT TO x1A+x1B+x1C
9、+x1D=175 x1B+x2B+x3B+x4B=125 x1C+x2C+x3C+x4C=225 x1D+x2D+x3D+x4D=450 END稳健性分析MIN 10x1A+4x1B+12x1C+20x1D+8x2A+10x2B+14x2C+10x2D+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=2
10、25 x1D+x2D+x3D+x4D=450 END3.4 离散最优化例3.6 仍考虑农场问题。这个家庭有625英亩 的土地用来种植。有5块每块120英亩的土 地和另一块25英亩的土地。这家人想在每 块地上种植一种作物：玉米、小麦或燕麦 。与前面一样，有1000英亩-英尺可用的灌 溉用水，每周农场工人可提供300小时的劳 力。其他数据下表给出。求应在每块地中 种哪种植物，从而使总收益达最大。农场问题的有关数据条件（每英亩 ）作物玉米小麦燕麦灌溉用水（英 亩-英尺）3.01.01.5劳力（人-小时 /周）0.80.20.3收益（美元）400200250变量x1=种植玉米的120英亩地块数 x2=
11、种植小麦的120英亩地块数 x3=种植燕麦的120英亩地块数 x4=种植玉米的25英亩地块数 x5=种植小麦的25英亩地块数 x6=种植燕麦的25英亩地块数 w=需要的灌溉用水（英亩-英尺） l=需要的劳力（人-小时/周） t=种植作物的总英亩数 y=总收益（美元）假设w=120(3.0x1+1.0x2+1.5x3)+25(3.0x4+1.0x5+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(400x1+200x2+250x3)+25(400x4+200x5+25
12、0x6 ) w=1000,l=300,t=625 x1+x2+x3=5, x4+x5+x6=1,x1,x6为非负整数。 目标：求y最大值。整数规划的标准形式：max y=48000x1+24000x2+30000x3+10000x4+5000x5+6 250x6 s.t. 375x1+125x2+187.5x3+75x4+25x5+37.5x6=1000 100x1+ 25x2+ 37.5x3+ 20x4+ 5x5 +7.5x6 =300x1 +x2 +x3 =5x4 +x5 +x6 =1 x1,x6为非负整数.问题求解MAX 48000x1+24000x2+30000x3+10000x4+5
13、000x5 +6250x6 SUBJECT TO 375x1+125x2+187.5x3+75x4+25x5+37.5x6=100 0 100x1+25x2+37.5x3+20x4+5x5+7.5x6=300 x1+x2+x3=5 x4+x5+x6=1 END GIN 6灵敏性分析 有100英亩-英尺的额外灌溉水量可用。 只要灌溉水量不低于1000-25=975，最优 解不会改变。 可用水量只有950时，又如何？ 以上灵敏性分析显示，IP问题解的不可预 期的特点。稳健性分析最小 地块 尺寸0125102050100125150200250300500玉米 （英 亩）187. 542188451
14、906020020012515020025000小麦 （英 亩）437. 51436104304040040025030040025000燕麦 （英 亩）0582057005200025015000600500收益 （美 元）162 5001625 00162 400162 500162 000162 000160 000160 000162 500157 000160 000150 000150 000125 000例如最小地块为2时，问题为：Max y=800x1+400x2+500x3 s.t. 6.0x1+2.0x2+3.0x3=1000 1.6x1+0.4x2+0.6x3=300 x
15、1+x2+x3=312 x1,x2,x3为非负整数。问题求解MAX 800x1+400x2+500x3 SUBJECT TO 6.0x1+2.0x2+3.0x3=1000 1.6x1+0.4x2+0.6x3=300 x1+x2+x3=312 END GIN 3例3.7 仍考虑例3.5中的土方问题。在使用10立方码载 重量的卡车运输的情况下，公司已经确定了最优 的运输方案。公司又有3辆更大的卡车可用于运 输，载重量为20立方码。使用这些车辆可能会在 运输中节省一些资金。载重10立方码的卡车平均 用20分钟装车，5分钟卸车，每小时平均开20英 里，费用为每英里单位重量20美元。载重量20立 方码的卡车30分钟装车，5分钟卸车，每小时平 均开20英里，费用为每英里单位重量30美元，为 最大限度地节省运输费用，应如何安排车辆的使 用？第一步，提出问题路线从到英里数运量11B212522A417533C422543D410054D4350哪条路上使用哪种卡车？ 假设每条路上只使用一种类型的卡车。 由于大卡车运量是小卡车的2倍，而费用却 不到小卡车的2倍，因此，我们希
