《[理学]最优化方法实验指导书16课时.doc》由会员分享，可在线阅读，更多相关《[理学]最优化方法实验指导书16课时.doc（34页珍藏版）》请在三一办公上搜索。
1、 最优化方法实验指导书（第一版）覃 义 编桂林电子科技大学数学与计算科学学院2011年9月20日实验一 线性规划算法及实现一、实验目的1. 掌握单纯形法在计算机上的实现，熟悉单纯形法的求解步骤。2. 掌握目标函数系数和约束右端项在什么范围内变化时，最优基保持不变。3. 读懂Lingo灵敏度分析报告和求解报告。4. 培养编程与上机调试能力。二、实验课时：4个课时三、实验准备1、熟悉线性规划的图解法及单纯形法解线性规划的原理；2、熟悉两阶段方法（两步法）及大M方法的基本思想及求解步骤；3、了解灵敏度分析的内容，熟悉灵敏度分析步骤；4、熟悉lingo软件的基本操作。5、熟悉Matlab软件的基本命令
2、及其数值计算中的基本命令和函数。四、实验内容课堂实验演示（1）用lingo软件求解线性规划例1：在模型窗口输入：model:max=2*x+3*y;4*x+3*y=10;3*x+5*y12;! the optimal value is :7.454545 ;End如图所示：运行结果如下（点击 工具栏上的solve或点击菜单lingo下的solve即可）：Global optimal solution found. Objective value: 7.454545（最优解函数值） Total solver iterations: 2（迭代次数） Variable （最优解） Value Red
3、uced Cost X 1.272727 0.000000 Y 1.636364 0.000000 Row Slack or Surplus Dual Price 1 7.454545 1.000000 2 0.000000 0.9090909E-01 3 0.000000 0.5454545例2：在模型窗口输入：model:max=5*x1+4*x2;x1+3*x2+x3=90;2*x1+x2+x4=80;x1+x2+x5=45;end运行（solve）结果如下：Global optimal solution found. Objective value: 215.0000 Total so
4、lver iterations: 2 Variable Value Reduced Cost X1 35.00000 0.000000 X2 10.00000 0.000000 X3 25.00000 0.000000 X4 0.000000 1.000000 X5 0.000000 3.000000 Row Slack or Surplus Dual Price 1 215.0000 1.000000 2 0.000000 0.000000 3 0.000000 1.000000 4 0.000000 3.000000例3在模型窗口输入：model:min=-x2+2*x3;x1-2*x2+
5、x3=2;x2-3*x3+x4=1;x2-x3+x5=2;end运行结果如下： Global optimal solution found. Objective value: -1.500000 Total solver iterations: 2 Variable Value Reduced Cost X2 2.500000 0.000000 X3 0.5000000 0.000000 X1 6.500000 0.000000 X4 0.000000 0.5000000 X5 0.000000 0.5000000 Row Slack or Surplus Dual Price 1 -1.50
6、0000 -1.000000 2 0.000000 0.000000 3 0.000000 0.5000000 4 0.000000 0.5000000例4：（此例不能用lingo试用版求解）在模型窗口输入：model:min=abs(x)+abs(y)+abs(z);x+y1;2*x+z=4;free(x);free(y);free(z);End求解器状态如下：可看出是非线性模型！运行结果为：（2）用lingo软件进行灵敏度分析实例在模型窗口输入：Lingo模型：model:max=60*x+30*y+20*z;8*x+6*y+z48;4*x+2*y+1.5*z20;2*x+1.5*y+0.
7、5*z8;y5;end求解报告如下(LingoSolve)：Global optimal solution found at iteration: 0 Objective value: 280.0000 Variable Value Reduced Cost X 2.000000 0.000000 Y 0.000000 5.000000 Z 8.000000 0.000000 Row Slack or Surplus Dual Price 1 280.0000 1.000000 2 24.00000 0.000000 3 0.000000 10.00000 4 0.000000 10.0000
8、0 5 5.000000 0.000000分析Value,Reduced Cost，Slack or Surplus，Dual Price的意义1、 由Value所在列可知x,y是基变量（因为取值不为0）2、 Reduced Cost（i.e. test indicator）所在列的三个数值表示当变量有微小变化时，目标函数的变化率。例如：第2个数5表示当变量y增加一个单位时，最优目标函数值减少的量。例如：当y=1时，最优目标函数值为280-5=275。可通过如下模型可检验：model:max=60*x+30*y+20*z;8*x+6*y+z48;4*x+2*y+1.5*z20;2*x+1.5*
9、y+0.5*z8;y5;y=1;end注：基变量的Reduced Cost值为0，只有非基变量的Reduced Cost值才可能不为0；故由value,和Reduced Cost值分析可知y为非基变量；3、 Slack or Surplus所在列的各数表示各行的松弛变量的取值。目标函数行的Slack or Surplus值没啥意义，不用考虑。可通过如下模型检验：model:max=60*x+30*y+20*z;8*x+6*y+z+s1=48;4*x+2*y+1.5*z+s2=20;2*x+1.5*y+0.5*z+s3=8;y+s4=5;end4、 Dual Price（对偶价格，影子价格）所在
10、列的各数表示约束右端项有微小变化时，最优目标函数值的变化率。注，只有紧约束行的Dual Price值不为0。例如：要检验第二行约束，可通过如下模型：model:max=60*x+30*y+20*z;8*x+6*y+z48;4*x+2*y+1.5*z21;2*x+1.5*y+0.5*z8;y5;end灵敏度分析报告如下(打开LingoRange即可，但必须先设置：LingoOptionsGeneral solverDual computationsPrices and Range)Ranges in which the basis is unchanged: Objective Coeffici
11、ent Ranges Current Allowable Allowable Variable Coefficient Increase Decrease X 60.00000 20.00000 4.000000 Y 30.00000 5.000000 INFINITY Z 20.00000 2.500000 5.000000 Righthand Side Ranges Row Current Allowable Allowable RHS Increase Decrease 2 48.00000 INFINITY 24.00000 3 20.00000 4.000000 4.000000 4
12、 8.000000 2.000000 1.333333 5 5.000000 INFINITY 5.000000分析Objective Coefficient Ranges，Righthand Side Ranges的意义5、 Objective Coefficient Ranges表示目标函数行各系数在某个范围内变化时，最优基保持不变。以变量x的系数为例：当x的系数在内取值时，最优基保持不变。此时，最优解不变，最优目标函数值变了。例如：可通过如下模型检验：model:max=56.0001*x+30*y+20*z;8*x+6*y+z48;4*x+2*y+1.5*z20;2*x+1.5*y+0
13、.5*z8;y5;end6、 Righthand Side Ranges表示约束右端项各数在某个范围内变化时，最优基保持不变。以第一个约束行为例：当右端项在内取值时，最优基保持不变。此时，最优解，目标函数的最优值变化了。例如：可通过如下模型检验：model:max=60*x+30*y+20*z;8*x+6*y+z4800;4*x+2*y+1.5*z20;2*x+1.5*y+0.5*z8;y=0)bnd(a,x,b)Axb（3）用Matlab软件求解实例常用命令如下；1、 若模型为则可使用命令2、若模型为则可使用命令，或，或其它，以下同3、若模型为则可使用命令若设置初始点即可使用命令Linpro
14、g的使用说明如下：LINPROG Linear programming. X=LINPROG(f,A,b) solves the linear programming problem: min f*x subject to: A*x = b x X=LINPROG(f,A,b,Aeq,beq) solves the problem above while additionally satisfying the equality constraints Aeq*x = beq. X=LINPROG(f,A,b,Aeq,beq,LB,UB) defines a set of lower and u
15、pper bounds on the design variables, X, so that the solution is in the range LB = X 0 then LINPROG converged with a solution X. 0 then LINPROG reached the maximum number of iterations without converging. = 0. The dual problem is max b*y such that A*y + s = f, s = 0.例6：用matlab求下列LP问题在命令行输入（也可建立m文件）C=
16、-2 -1;A=1 1; -1 1; 6 2;-1 0;0 -1;b=5 0 21 0 0;x,y,k=linprog(C,A,b)或C=-2 -1;A=1 1; -1 1; 6 2;b=5 0 21;LB=0 0;UB=inf inf;x,y,k=linprog(C,A,b,LB,UB)输出：x = 2.7500 2.2500y = -7.7500k = 1故原目标函数的最大值为 max(x0)= 7.7500 课堂实验任务1、用lingo软件或Matlab软件优化工具箱求解下列线性规划问题。（必做, 任选三个问题）实例1 某工厂生产甲、乙两种产品。已知生产甲种产品需耗种矿石、种矿石、煤；生
17、产乙种产品需耗种矿石、种矿石、煤。每甲种产品的利润是元，每乙种产品的利润是元。工厂在生产这两种产品的计划中要求消耗种矿石不超过、种矿石不超过、煤不超过。甲、乙两种产品应各生产多少，能使利润总额达到最大？实例2设有A1，A2两个香蕉基地，产量分别为60吨和80吨，联合供应B1，B2，B3三个销地的销售量经预测分别为50吨、50吨和40吨。两个产地到三个销地的单位运价如下表所示：表1（单位运费：元/吨）问每个产地向每个销地各发货多少，才能使总的运费最少？2、用Lingo软件对下列线性规划问题进行灵敏度分析。（必做, 任选三个问题） 3 某工厂用甲，乙两种原料生产A,B,C,D 四种产品，每种产品的
18、利润、现有原料数量及每种产品消耗原料定额如下表：每万件产品所耗原料（千克）ABCD现有原料（千克）甲3210418乙0022.53每万件产品利润（万元）985019问题：（1）怎样组织生产才能使总利润最大？（2）如果产品A的利润有波动，波动范围应限制在什么范围内，才能使得原生产计划不变？（3）若原料甲的数量发生变化，在什么范围内变化时才能使得原生产计划不变？（4）若工厂引进新产品E， 已知生产1万件E消耗原料甲3千克，材料乙1千克，问E的利润为多少时候（即，应满足什么条件），投资才有利？要求：建立相应的数学模型，用Lingo进行分析。4、用Matlab软件编写求解一类线性规划问题的程序，算法自
19、选。五、实验主要步骤1、安装Matlab7.0（或以上版本）及lingo9.0；2、至少用半小时认真阅读实验指导书，特别是实例介绍；3、用lingo软件求解上述LP问题，记录实验结果，即实验报告数据，将这些数据（数学模型，lingo模型，运行结果）暂时保存在word文档里，写实验报告时再复制即可）；4、试用Matlab的线性规划命令函数求解上述问题。5、试着自己动手用Matlab编写求解一类线性规划程序。6、撰写实验报告。（正文部分格式不作统一要求，但要求简单明了）六、实验报告的撰写要求1. 根据实验报告模板撰写实验报告；2. 写出实验目的、实验内容；3. 写出求解程序及实验结果（包括所建立的
20、数学模型、lingo模型、求解报告及灵敏度分析报告）4. 写出心得体会（主要包括实验中碰到什么的困难，解决问题的方法，及通过实验学到什么东西）；实验二 一维搜索 一、实验目的1、熟悉一维无约束优化问题的二分法与0.618算法。2、培养matlab编程与上机调试能力。二、实验课时：2个课时三、实验准备1、预习一维无约束优化问题的二分法与0.618算法。2、熟悉matlab软件的基本操作。四、实验内容课堂实验演示1、根据二分法算法编写程序，求函数在区间上的极小值。二分法如下：（1）给定区间以及；（2）若，则停，输出；（3）计算；（4）若，令，返回（2）；否则若，令；否则若，则停输出；functio
21、n val,x,iter = f_12(a,b,delt) iter = 0; while abs(b-a)delt iter = iter+1; y,dy = fun(a+b)/2); if dy=0 x = (a+b)/2; val = y; return elseif dy val,x,iter = f_12(-2,1,eps)val = 1x = -1iter = 542、根据0.618算法编写程序，求函数在区间上的极大值。0.618算法如下：（1）给定区间，及；（2）计算；（3）若，转（4），否则转（5）（4）若，则停，输出否则令，转（3）（5）若，则停，输出否则令，转（3）令，求运
22、行结果，如下：a=0,b=1,eps=10(-5)t = 23optx = 0.9707opty =-4.1086e+010则为 4.1086e+010其程序如下：function optx,opty=f_0618(a,b,eps)%see page 88, :% format: optx,opty=f_0618(a,b,eps)%a=0;b=1;eps=10(-5); eps10(-6)%a=-1;b=1;eps=10(-5); % a=0; b=105; eps=10(-2); %p111_5r=a; u=b;t=0;while 1 t=t+1; if f(r)=f(u) if u-rep
23、s optx=u; opty=f(u); u-r break end a=r; r=a+0.382*(b-a); u=a+0.618*(b-a); else if u-rdelt d = -dy; % 方向 temp = inf; lamda = 0; k = 1; while 1 % 步长 y,dy,hy = fun_1(x0+d*lamda); if tempy temp = y; else break end lamda = lamda+0.1*k; k = 0.5*k; end x0 = x0+d*lamda; y,dy,hy = fun_1(x0); iter = iter + 1;
24、end x = x0;val = y;function y,dy,hy = fun_1(x) y = (x(1)-2)4+(x(1)-2)2*x(2)2+(x(2)+1)2;dy = 4*(x(1)-2)3+2*(x(1)-2)*x(2)2;2*(x(1)-2)2*x(2)+2*(x(2)+1);hy = 12*(x(1)-2)2+2*x(2)2 4*(x(1)-2)*x(2);. 4*(x(1)-2)*x(2) 2*(x(1)-2)2+2; val,x,iter = steepest(1 1,0.001)val = 1.6924e-007x = 2.0003 -0.9997iter = 17课堂实验任务编写函数文件，实现最速下降法，并求解下列问题1) ， 2) ， 五、实验主要步骤1、安装matlab7.0及以上版本软件；2、编写m文件以创建和保存各函数；3、运行程序，保存结果；4、撰写实验报告。六、实验报告的撰写要求7. 写出实验课程名称、课号，任课老师；8.
