《数学建模课件。线性规划。》由会员分享，可在线阅读，更多相关《数学建模课件。线性规划。（77页珍藏版）》请在金锄头文库上搜索。
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,40); grid on,ezplot(y,18,22); grid on,ezplot(y,19,20); grid on,数值方法求解-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,灵敏性分析,考虑最优售猪时间关于小猪增长率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 更新消防站的位置。对响应时间数据的统计分析给出：对离救火站r英里打来的求救电话，需要的响应时间估计为 。下图给出了从消防管员处得到的从城区不同区域打来的求救电话频率的估计数据。求新的消防站的最佳位置。,3.2 多变量最优化,设(x,y)为新消防站的位置，对
5、求救电话的平均响应时间为： 问题为在区域0=x=6, 0=y=6上求z=f(x,y)的最小值。,绘制目标函数图形,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,随机搜索算法,算法：随机搜索算法 变量：a=x的下限，b=x的上限 c=y的下限，d=y的上限 xmin,ymin,zmin 输入：a,b,c,d,N 过程：开始 x=randoma,b,y=randomc,d zmin=f(x,y) 对n=1到N循环 开始 x=randoma,b
7、 y=randomc,d z=f(x,y) 若zzmin,则 xmin=x,ymin=y,zmin=z 结束 结束 输出：xmin,ymin,zmin,代码实现,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 一家草坪家俱厂商生产两种草坪椅。一种是木架的，一种是铝管架的。木架椅的生产价格为每把18美元，铝管椅为每把10美元。在产品出售的市场上，可以售出的数量依赖于价格。据估计，若每天售出x把木架椅，y把铝管椅，木架椅和铝管椅的出售价格分别不能超过 ，求最优生产量。,问题,在生产量的可
10、行域x=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=5,y=6,随机搜索求近似最优值,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、近似值,牛顿法见书p.56 x=x1;x2; F=diff(z,x1); G=diff(z,x2); Dz=F;G; % the gradient vector of z 即求方程组Dz=0的解。,牛顿法代码实现,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 线性规划,例3.4 一个家庭农场有625英亩的土地可用来种植农作物。这个家庭可考虑种植的农作物有玉米、小麦、燕麦。预计有1000英亩-英尺的灌溉用水，农场工人每周可以投入的工作时间为300小时。其他数据如下表。为获得最大收益，每种作物应各种植多少？,农场问题的有关数据,变量：x1,x2,x3=种植玉米、小麦、燕麦的亩数 w=需要的灌溉用水（英亩-英尺） l=需要的劳力（人-小时/周） t=种植作物的总英亩数 y=总收益（美元）,假设：w=3.0x1+1.0x2+1
15、.5x3=0 目标：求y的最大值,建模方法线性规划,线性规划简介见书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值表示当该非基变量增加一个单位时（其他非基变量保持不变）目标函数减少的量(对max型问题) 也可理解为：为了使该非基变量变成基变量，目标函数中对应系数应增加的量,灵敏性分析,增加1英亩-英尺灌溉水量对最优解的影
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,玉米收益的少量提高对最优解的影响,农作物每英亩收益会随气候及市场变化 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,燕麦收益的少量提高对最优解的影响,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,
