最优化方法练习题答案修改建议版本--删减版

1、X(k1)x(k)x(k1 x(k)|x(k)|x(k1)x(k)f x(k fx(k)f x(k)x(k)练习题一1、建立优化模型应考虑哪些要素？答：决策变量、目标函数和约束条件。2、讨论优化模型最优解的存在性、迭代算法的收敛性及停止准那么。min f(x)答：针对一般优化模型s.t gi x 0,i 1,2,m，讨论解的可行域D，假设存在一点X* D，hj x 0, j 1,，p对于X D均有f(X*) f(X)那么称X*为优化模型最优解，最优解存在；迭代算法的收敛性是指迭f(X(K)，那么迭代法收敛；收敛的停止准那么有代所得到的序列X,X，,X(K)，满足f(X(K1)等。练习题二1、某

2、公司看中了例中厂家所拥有的3种资源R1、R2、和R3,欲出价收购可能用于生产附加值 更高的产品。如果你是该公司的决策者，对这 3种资源的收购报价是多少？该问题称为例的对偶 问题。解：确定决策变量对3种资源报价2匚3作为本问题的决策变量。确定目标函数问题的目标很清楚一一“收购价最小。确定约束条件资源的报价至少应该咼于原生产产品的利润，这样原厂家才可能卖。因此有如下线性规划问题：min w 170y1 100y2 150y35y1 2y2 y310s.t 2y1 3y2 5y3 18y1, y2, y302、研究线性规划的对偶理论和方法包括对偶规划模型形式、对偶理论和对偶单纯形法 答：略。3、用单

3、纯形法求解以下线性规划问题：minzx1x2x3minz 4 x2X3x1x22x32X2X2X321s.t.2x1 x2x33 ；2s.t.x2 2x3X42x1x34x2 X3x55X1,X2,X30Xi 0 (i1,2,5)解：1引入松弛变量X4，X5，X6min z x1 x2 x3 0* x4 0* x5 0* x6x1 x2 2x3 x4=2丄2x1X2X3x5=3s.tx1 x3x6=4x1,x2, x3,x4,x5,x6 0Cj1-11000Cb基bX1X2X3X4X5X60X4211-21000X532110100X64-101001Cj-zj1-11000因检验数020，故

4、确定X2为换入非基变量，以X2的系数列的正分量对应去除常数列，最小比值 所在行对应的基变量X4作为换出的基变量。Cj1-11000Cb基bX1X4X3X4X5X6-1X2211-21000X51103-1100X64-101001Cj-zj20-1100因检验数03Q,说明已求得最优解：X*(0,8/ 3,1/3,0,0,11/ 3)，去除添加的松弛变量，原问题的最优解为：X (0,8/3,1/3)2根据题意选取X1,X4，X5，为基变量:min z 4 X2X3x3X4X12x2x22x3st. 23x2x3Xi0 (i1,2,x5,5)Cj -1Cb基bX1X2X3X4X50X121-21

5、000X4201-2100X5501101cj-z0-1100因检验数020,说明已求得最优解：X* (9,4,1,0,0)8、某地区有A、B、C三个化肥厂，供应本地甲、乙、丙、丁四个产粮区。各化肥厂可供应 化肥的数量和各产粮区对化肥的需要量，以及各厂到各区每吨化肥的运价如表2-28所示。试制定个使总运费最少的化肥调拨方案。运价/ 产粮化肥厂甲乙丙丁各厂供应量/万吨A158737A2491078A384293各区需要量/万吨6633解：设A、B、C三个化肥厂为Ai、A2、A3,甲、乙、丙、丁四个产粮区为Bi、B2、B3、B4；cij为由Ai运化肥至Bj的运价，单位是元/吨；xij为由Ai运往B

6、j的化肥数量i=1,2,3;j=1,2,3,4单位是吨；z表示总运费，单位为元，依题意问题的数学模型为:34minzi1 j 1cijxijX11X21X316X12X22X326X13X23X333s.tx14X24X343X11X12X13X147X21X22X23X248X31X32X33X347该题可以用单纯形法或 matlab自带工具箱命令:linprog求解。9、求解以下不平衡运输问题各数据表中，方框内的数字为单位价格q,框外右侧的一列数为各发点的供应量ai，框底下一行数是各收点的需求量bj：108015要求收点3的需求必须正好满足75 20 5020101515要求收点1的需求必

7、须由发点4供应解答略练习题三1min (t) t3 2t 1 t 0的近似最优解，(t)的单谷区间为0,3，要求最后区间精度 0.5答：t=0.8115;最小值-0.0886.调用 golds.m 函数2、求无约束非线性规划问题的最优解解一：由极值存在的必要条件求出稳定点：2x-i2，丄8x2，丄2x3，那么由 f x0 得 x-i1 ,x20,x30XixX3再用充分条件进行检验：2 2 2 2 2 2f 2，厶f28，f cf cf牙 2，0，-0，f 0X1X2x3x1x-! x3X2X3200即2f080为正定矩阵得极小点为X*(1,0,0)T，最优值为-1002解二：目标函数改写成2

8、 2 2min f (Xi,X2X)= (Xi 1)4x? X3 1易知最优解为1,0,0最优值为-13、用最速下降法求解无约束非线性规划问题。2 2 min f(X) x1 x2 2X 2x-|X2 x2其中X (X1,X2)T，给定初始点X0(0,0)T。1 4x1 2x21 2x1 2x2f(x)解一：目标函数f (x)的梯度f(x)(X1)f (x)(X2)f(X(0)1令搜索方向d1f (X(0)再从X(0)出发，沿d方向作一维寻优，令步长变量为，最优步长为那么有X(0)故 f (x) f (X (0)d)2( )22(1()令 1( )220可得X(1) x(0)1d(1)求出X点

9、之后，与上类似地,进行第二次迭代:f(X)11 令 d(2)1f(X)令步长变量为，最优步长为2，那么有x(1)d(2)1 1 11 1 1故f(x)f(X d )(1)(1) 2(1)22()1012 0可得 2- XX(1)2d(2)52(1)(1) (1)2 5 2 212()令1 1 1 0.815 11.20 2f(X(2)02此时所到达的精度f (X )|0.28281此题最优解X, f(X )1,251.5练习题四1、石油输送管道铺设最优方案的选择问题：考察网络图4-6,设A为出发地，F为目的地，B,C, D，E分别为四个必须建立油泵加压站的地区。图中的线段表示管道可铺设的位置，

10、线段旁的数 字表示铺设这些管线所需的费用。问如何铺设管道才能使总费用最小？图4-1解：第五阶段:E1 F 4;E2 F:3；第四阶段:D1 E1 F7; D2 E2 F 5;D3E1 F 5;第三阶段:C1 D1 E1F 12;C2D2 E2 F 10; C3 D2 E2第二阶段:B1 C2 D2E2 F13; B2C3 D2 E2 F 15;第一阶段:AB1 C2 -D2 E2-F 17;最优解：AB1C2 D2 E2 F最优值：17F 8； C4 D3 E1 F2、用动态规划方法求解非线性规划9；maxf(x) . X| , x2x3x1 x2 x327X1,X2,X30解：x-i 9,x

11、2 9, x3 9，最优值为 9。3、用动态规划方法求解非线性规划2 2 max z 7x1 6x 5x2s.t x-i 2x210x-i 3x29x1, x20解：用顺序算法阶段：分成两个阶段，且阶段1、2分别对应Xi,X2。决策变量:Xi,X2状态变量:Vi, Wj分别为第j阶段第一、第二约束条件可供分配的右段数值。fl (Vi, Wi)。啊7 X0 x( W1min7 v； 6V| ,7 w 6w1x-imi nZw*2f2(v2,w2) max5 x22x2,w2 3x2)max5 x；由于 v210, w29，22min7( v2 2x2)6(v2 2x2),7( w2 3x2)6(

12、w2 3x2)* * 2 2f2 (v2, w2) f2 (10,9) maxmin33 x2 292x2 760,68 x2 396x2 621可解的X1 9.6, x； 0.2，最优值为702.92。4、设四个城市之间的公路网如图4-7。两点连线旁的数字表示两地间的距离。使用迭代法求各地到城市4的最短路线及相应的最短距离。图4- 2城市公路网解：城市1到城市4路线1-3-4 距离10；城市2到城市4路线2-4距离8;城市3到城市4路线3-4 距离4。5、某公司打算在3个不同的地区设置4个销售点，根据市场部门估计，在不同地区设置不同数量的销售点每月可得到的利润如表 4-19所示。试问在各地区

13、如何设置销售点可使每月总利润最大。表4-1地销售点区01234101625303220121721223010141617解：将问题分为3个阶段，k=1 , 2, 3;决策变量xk表示分配给第k个地区的销售点数；状态变量为Sk表示分配给第k个至第3个地区的销售点总数；状态转移方程：劭+1=孤乂丘，其中s=4;允许决策集合：DkSk= Xk|0S3S2X2, D3(s3) X3 1 0X3Ss状态转移方程为：Sk 1 Tk(Sk,Xk) Sk xk,k3,2,1该题是三阶段决策过程，故可假想存在第四个阶段，而 x4 0，于是动态规划的根本方程为:fk(Sk) XkmaxJseMk 咖f4() 0

14、k 3,f3(S3)max6x3X3 0,1, ,S3/5k 2,f2(S2)max 5x2X 0,1,邑4f3(S3)max 5x2X2 0,1,吟f3(S24X2)k 1,MG 頁ax戶 f2(s2)max34 fzg 3xjx1 U,l，2,3计算最终结果为Xi 2,X2 1,X3 0，最大价值为13。9、设有A，B，C三部机器串联生产某种产品，由于工艺技术问题，产品常出现次品。统计结 果说明，机器 A，B，C产生次品的概率分别为 Pa=30%, Pb=40%, Pc=20%,而产品必须经过三部机 器顺序加工才能完成。为了降低产品的次品率，决定拨款5万元进行技术改造，以便最大限度地提高产

15、品的成品率指标。现提出如下四种改进方案：方案1:不拨款，机器保持原状；方案2:加装监视设备，每部机器需款 1万元；方案3:加装设备，每部机器需款 2万元；方案4:同时加装监视及控制设备，每部机器需款 3万元；采用各方案后，各部机器的次品率如表 4-21。表4- 3ABC不拨款30%40%20%拨款1万元20%30%10%拨款2万元10%20%10%拨款3万元5%10%6%问如何配置拨款才能使串联系统的可靠性最大？解：为三台机器分配改造拨款，设拨款顺序为 A, B, C,阶段序号反向编号为k,即第一阶段计算给 机器C拨款的效果。设永为第k阶段剩余款，那么边界条件为 s3=5；设x为第k阶段的拨款

16、额；状态转移方程为 Sk-1=Sk-Xk；目标函数为max R=(1-Pa)(1-Pb)(1-Pc)仍采用反向递推第一阶段：对机器C拨款的效果Rl(si，x0=d i(si ,xi)Ro(S0,X0)= d*si，xi)S10123X1*R1(S1, X1*)001121,2334353第二阶段：对机器B, C拨款的效果由于机器A最多只需3万元，故s2 2 递推公式：R2(S2，X2)=d2(s2，X2)只1&“)例：R2(3,2)=d2(3,2) R1(1,1)=(1-0.2)得第二阶段最优决策表S1X1*R1(S1, X1*)001121,2334353S20123X2*R2(S2, X2*)2232,34353第三阶段：对机器A, B, C拨款的效果边界条件：S3 = 5递推公式：R3(s3,x3)=d3(s3,x3) R2