要设计和发射一个带有X射线望远镜和其他科学仪器的气球.doc

一、最速下降法的基本知识1、最速下降法基本原理无约束问题的最优解所要满足的必要条件和充分条件是我们设计算法的 依据，为此我们有以下几个定理：定理1 设 f : Rn R1在点x Rn处可微。若存在pRn，使f (x)T p 0，则向量p是f 在点x 处的下降方向。定理2 设 f : Rn R1在点x* Rn处可微。若x*是无约束问题的局部最优解，则f (x* ) = 0。由数学分析中我们已经知道，使f (x) = 0的点x为函数f 的驻点或平稳点。函数f 的一个驻点可以是极小点；也可以是极大点；甚至也可能既不是极小点也不是极大点，此时称它为函数f 的鞍点。以上定理告诉我们，x*是无约束问题的的局部最优解的必要条件是：x*是其目标函数f 的驻点。定理3（充分条件） 设 f : Rn R1在点x* Rn处的Hesse矩阵2 f (x* )存在。若f (x* ) = 0，并且2 f (x* )正定，则x*是无约束问题的严格局部最优解。一般而言，无约束问题的目标函数的驻点不一定是无约束问题的最优解。但对于其目标函数是凸函数的无约束凸规划，下面定理证明了，它的目标函数的驻点就是它的整体最优解。定理4 设 f : Rn R1，x* Rn， f 是Rn上的可微凸函数。若有f (x* ) = 0，则x*是无约束问题的整体最优解。2、最速下降法的基本思想 从当前点xk出发，取函数f (x)在点xk处下降最快的方向作为我们的搜索方 向pk .由f (x)的Taylor 展式知f (xk ) - f (xk + tpk ) = -tf (xk )T pk + o( tpk)略去t的高阶无穷小项不计，可见取pk = -f (xk )时，函数值下降得最多。于是，我们可以构造出最速下降法的迭代步骤。解无约束问题的的最速下降法计算步骤3、算法描述用最速下降法求无约束多维极值问题的算法步骤如下：（1）取初始点，精度，令（2）计算搜索方向，其中表示函数在点处的梯度；（3）若，则停止计算；否则，从出发，沿进行一维搜索，即求，使得。此处的一维搜索可以用黄金分割法等算法，当然也可以用MATLAB的函数；（4）令，转步骤2。如图，函数J（a）在某点ak的梯度 是一个向量，其方向J（a）增长最快的方向。显然，负梯度方向是J（a）减少最快的方向。在最速下降法中，求函数最大值时，沿着梯度方向走，可以最快达到极大点；反之，沿着负梯度方向走，则最快达到最小点。求函数J（a）极小值的问题，可以选择任意初始点a0，从a0出发沿着负梯度方向走，可使得J（a）下降最快。4、流程图：本程序在设计时加入了一个子程序，可以在子程序中输入要计算的线性方程，在主程序中进行运算。程序设计时用while循环语句查找最值，用求导函数的方法定义变量，并且将变量x1，x2写成矩阵的形式以便进行运算。二、炼油厂将A、B、C三种原料加工成甲乙丙三种汽油。一桶原油加工成汽油的费用为4元，每天至多能加工汽油14，000桶。原油的买入价、买入量、辛烷值、硫含量，及汽油的卖出价、需求量、辛烷值、硫含量由下表给出。问如何安排生产计划，在满足需求的条件下使利润最大？一般来说，作广告可以增加销售，估计一天向一种汽油投入一元广告费，可以使这种汽油日销量增加10桶。问如何安排生产计划和广告计划使利润最大？原油类别买入价（元/桶）买入量（桶/天）辛烷值（）硫含量（）A455000 120.5B35500062.0C25500083.0汽油类别卖出价（元/桶）需求量（桶/天）辛烷值（）硫含量（）甲703000101.0乙60200081丙50100061.0符号说明：X1,X2,X3分别为A类原油生产成甲，乙，丙三种汽油的量。Y1,Y2,Y3分别为B类原油生产成甲，乙，丙三种汽油的量Z1,Z2,Z3分别为C类原油生产成甲，乙，丙三种汽油的量PA,PB,PC分别为甲，乙，丙三种汽油中投入广告的花费一、 不考虑广告投入时的模型求解：由以上述条件可知：PA=PB=PC=0;总利润为：70*3000+60*2000+50*1000-45*(X1+X2+X3)-35*(Y1+Y2+Y3)-25*(Z1+Z2+Z3)-4*(X1+X2+X3+Y1+Y2+Y3+Z1+Z2+Z3)针对买入量与总产量得条件：X1+X2+X3+Y1+Y2+Y3+Z1+Z2+Z314000;X1+X2+X35000;Y1+Y2+Y35000;Z1+Z2+Z35000;针对需求量得条件：X1+Y1+Z13000;X2+Y2+Z22000;X3+Y3+Z31000;针对辛烷值得条件：12%*X1+6%*Y1+8%*Z110%*(X1+Y1+Z1);12%*X2+6%*Y2+8%*Z22%*(X2+Y2+Z2);12%*X3+6%*Y3+8%*Z36%*(X3+Y3+Z3);针对硫含量得条件：0.5%*X1+2.0%*Y1+3.0%*Z11.0%*(X1+Y1+Z1);0.5%*X2+2.0%*Y2+3.0%*Z20.8%*(X2+Y2+Z2);0.5%*X3+2.0%*Y3+3.0%*Z31.0%*(X3+Y3+Z3);X1,X2,X3，Y1,Y2,Y3,Z1,Z2,Z3均为非负整数；结果分析与检验利用LING0 9.0求解在上述四条件下利润的最大值得：不考虑广告投入时用LINGO 9.0求解利润最大值所用程序：max=70*3000+60*2000+50*1000-45*(X1+X2+X3)-35*(Y1+Y2+Y3)-25*(Z1+Z2+Z3)-4*(X1+X2+X3+Y1+Y2+Y3+Z1+Z2+Z3);X1+X2+X3+Y1+Y2+Y3+Z1+Z2+Z3=14000;X1+X2+X3=5000;Y1+Y2+Y3=5000;Z1+Z2+Z3=3000;X2+Y2+Z2=2000;X3+Y3+Z3=1000;0.12*X1+0.06*Y1+0.08*Z1=0.10*(X1+Y1+Z1);0.12*X2+0.06*Y2+0.08*Z2=0.02*(X2+Y2+Z2);0.12*X3+0.06*Y3+0.08*Z3=0.06*(X3+Y3+Z3);0.005*X1+0.02*Y1+0.03*Z1=0.01*(X1+Y1+Z1);0.005*X2+0.02*Y2+0.03*Z2=0.008*(X2+Y2+Z2);0.005*X3+0.02*Y3+0.03*Z3=0.01*(X3+Y3+Z3);gin(X1);gin(X2);gin(X3);gin(Y1);gin(Y2);gin(Y3);gin(Z1);gin(Z2);gin(Z3); 直接求解结果：Global optimal solution found.Objective value: 110000.0Total solver iterations: 6Variable Value Reduced Cost X1 2400.000 0.000000 X2 1600.000 0.000000 X3 800.0000 0.000000 Y1 0.000000 2.000000 Y2 0.000000 2.000000 Y3 0.000000 2.000000 Z1 600.0000 0.000000 Z2 400.0000 0.000000 Z3 200.0000 0.000000Row Slack or Surplus Dual Price 1 110000.0 1.000000 2 8000.000 0.000000 3 200.0000 0.000000 4 5000.000 0.000000 5 3800.000 0.000000 6 0.000000 -45.00000 7 0.000000 -45.00000 8 0.000000 -45.00000 9 36.00000 0.000000 10 184.0000 0.000000 11 52.00000 0.000000 12 0.000000 800.0000 13 0.000000 800.0000 14 0.000000 800.0000 当X1=2400,X2=1600, X3=800,Z1=600,Z2=400,Z3=200,其余变量值为0；即用A类原油生产2400桶甲类汽油，生产1600桶乙类石油，生产800桶丙类石油，用C类原油生产600桶甲类汽油，用C类原油生产400桶乙类汽油，用C类原油生产200桶丙类汽油时，总利润达到最大值为110000元。二、考虑广告投入时的模型求解：对甲、乙、丙三种汽油的广告投入分别设为PA、PB、PC.总利润变:70*(3000+10*PA)+60*(2000+10*PB)+50*(1000+10*PC)-45*(X1+X2+X3)-35*(Y1+Y2+Y3)-25*(Z1+Z2+Z3)- 4*(X1+X2+X3+Y1+Y2+Y3+Z1+Z2+Z3)-PA-PB-PC;针对需求量得到的条件变为：X1+Y1+Z13000+10*PA;X2+Y2+Z22000+10*PB;X3+Y3+Z31000+10*PC;其余条件与不考虑广告投入时相同.结果分析与检验利用LING0 9.0求解在上述条件下利润的最大值得：考虑广告投入时利用LINGO 9.0求解利润最大值所用程序：max=70*(3000+10*PA)+60*(2000+10*PB)+50*(1000+10*PC)-45*(X1+X2+X3)-35*(Y1+Y2+Y3)-25*(Z1+Z2+Z3)- 4*(X1+X2+X3+Y1+Y2+Y3+Z1+Z2+Z3)-PA-PB-PC;X1+X2+X3+Y1+Y2+Y3+Z1+Z2+Z3=14000;X1+X2+X3=5000;Y1+Y2+Y3=5000;Z1+Z2+Z3=3000+10*PA;X2+Y2+Z2=2000+10*PB;X3+Y3+Z3=1000+10*PC;0.12*X1+0.06*Y1+0.08*Z1=0.10*(X1+Y1+Z1);0.12*X2+0.06*Y2+0.08*Z2=0.02*(X2+Y2+Z2);0.12*X3+0.06*Y3+0.08*Z3=0.06*(X3+Y3+Z3);0.005*X1+0.02*Y1+0.03*Z1=0.01*(X1+Y1+Z1);0.005*X2+0.02*Y2+0.03*Z2=0.008*(X2+Y2+Z2);0.005*X3+0.02*Y3+0.03*Z3=0.01*(X3+Y3+Z3);gin(X1);gin(X2);gin(X3);gin(Y1);gin(Y2);gin(Y3);gin(Z1);gin(Z2);gin(Z3); 直接求解结果：Global optimal solution found.Objective value: 129959.1Extended solver steps: 0Total solver iterations: 18Variable Value Reduced Cost PA 109.9000 0.000000 PB 0.000000 0.000000 PC 0.000000 0.000000 X1 2733.000 -20.90000 X2 1600.000 -10.90000 X3 667.0000 -0.9000000 Y1 1366.000 -30.90000 Y2 400.0000 -20.90000 Y3 333.0000 -10.90000 Z1 0.000000 -40.90000 Z2 0.000000 -30.90000 Z3 0.000000 -20.90000Row Slack or Surplus Dual Price 1 129959.1 1.000000 2 6901.000 0.000000 3 0.000000 0.000000 4 2901.000 0.000000 5 5000.000 0.000000 6 0.000000 -69.90000当PA=109,PB=0,PC=0,X1=2733,X2=1600,X3=667,Y1=1366,Y2=400,Y3=333,即对甲类汽油投入广告费109元，对乙,丙类汽油不投入广告费，同时用A类原油生产甲类汽油2733桶，生产乙类汽油1600桶，生产丙汽油667桶，用B类原油生产甲类汽油1366桶，生产乙类汽油400桶，生产丙类汽油333桶，不用C类原油时，总利润可得最大为129959.1元.三、要设计和发射一个带有X射线望远镜和其他科学仪器的气球。对于性能的粗糙的度量方法是以气球所能到达的高度和所携带仪器的重量来表达，很清楚，高度本身是气球体积的一个函数。根据过去的经验作出的结论，是求极大满意性能函数，此处V是体积，w是仪器重量。承包项目的预算限额为1040美元，与体积v有关的费用是2v，与设备有关的费用是4W，为了保证在高度方面的性能与科学设备方面的性能之间合理平衡，设计者要满足约束条件80W100W，找出由体积和设备重量来表达的最优设计，并用线性化方法求解。解：由题意可以问题的V和W应满足的约束条件为 s.t.然后求解目标函数的最大值。我们可以用非线性规划的线性逼近的方法将目标函数转化成近似的线性函数然后用线性规划的求解的方法即可得出结果。根据题意建立模型：Max f = 100-0.3+80W-0.2s.t.设置变量为：体积V：x1 设备重量W：x2模型求解的Matlab程序如下：（1）建立非线性目标函数文件function f=qiqiu01(x) f=0.3*x(1)2-100*x(1)+0.2*x(2)2-80*x(2);(2) 建立主程序求解x0=1;1;A=1,2;5,-4;b=520;0;Aeq=;beq=;vlb=0;0; vub=;x,fval=fmincon(qiqiu01,x0,A,b,Aeq,beq,vlb,vub);xfval%求出的结果为：x = 148.5714 185.7143fval = 1.6194e+004由上可知体积V为148.5714，重量为185,7143时为最优的设计。四、某厂向用户提供发动机，合同规定，第一、二、三季度末分别交货40台、60台、80台每季度的生产费用为 （元），其中x是该季生产的台数若交货后有剩余，可用于下季度交货，但需支付存储费，每台每季度c元已知工厂每季度最大生产能力为100台，第一季度开始时无存货，设a=50、b=0.2、c=4，问工厂应如何安排生产计划，才能既满足合同又使总费用最低解：分析： 问题的关键在于由于工厂的生产能力足以满足每个季度用户的需求，但是为了使总费用最少，那么利用每个季度生产费用的不同，可用利用上个生产费用低的季度多生产来为下个季度进行准备，前提是本月节省下的费用减去总的发动机存储费用还有剩余，这样生产才有价值，才可能满足合同的同时又能使总费用最低。基本假设： 1、工厂的生产能力不受外界环境因素影响。 2、为使总费用最低，又能满足合同要求，各个季度之间的生产数量之间是有联系的。 3、第一季度开始时无存货。 4、工厂每季度的生关费用与本季度生产的发动机台数有关。 5、生产要按定单的数量来进行，生产的数量应和订单的数量相同，以避免生产出无用的机器。