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

练习题一1、建立优化模型应考虑哪些要素?答：决策变量、目标函数和约束条件。2、讨论优化模型最优解的存在性、迭代算法的收敛性及停止准则。答：针对一般优化模型 ，讨论解的可行域 ，若存在一点 ，对min().0,12, ijfxstgimhjp D*XD于 均有 则称 为优化模型最优解，最优解存在；迭代算法的收敛性是指迭代XD*()(ffX*所得到的序列 ，满足 ，则迭代法收敛；收敛的停止准则有12),K (1)()KKfXf， ， ， ，(1)()kkx()()kkx(1)()kkfxf(1)()(kkfxf等等。 ()kf练习题二1、某公司看中了例 2.1 中厂家所拥有的 3 种资源 R1、R 2、和 R3，欲出价收购（可能用于生产附加值更高的产品） 。如果你是该公司的决策者，对这 3 种资源的收购报价是多少？（该问题称为例2.1 的对偶问题） 。解：确定决策变量 对 3 种资源报价 作为本问题的决策变量。123,y确定目标函数 问题的目标很清楚“收购价最小” 。确定约束条件 资源的报价至少应该高于原生产产品的利润，这样原厂家才可能卖。因此有如下线性规划问题： 123min 7050wyy1231. 8,0sty*2、研究线性规划的对偶理论和方法（包括对偶规划模型形式、对偶理论和对偶单纯形法） 。答：略。3、用单纯形法求解下列线性规划问题：（1） 0,4322.min11xxxtsz； （2） )5,21(0.4min324132ixxxtszi解：（1）引入松弛变量 x4，x 5，x 6123456min 0*0*zxxx4123 =2. ,5,60stxxcj 1 -1 1 0 0 0CB 基 b x1 x2 x3 x4 x5 x60 x4 2 1 1 -2 1 0 00 x5 3 2 1 1 0 1 00 x6 4 -1 0 1 0 0 1cj-zj 1 -1 1 0 0 0因检验数 20，表明已求得最优解： ，去除添加的松弛变量，原问题*(,8/1,/)X的最优解为： 。*(0,8/31)X（2）根据题意选取 x1，x 4，x 5，为基变量：)5,21(0.4min324132ixxxtszicj 0 -1 1 0 0CB 基 b x1 x2 x3 x4 x50 x1 2 1 -2 1 0 00 x4 2 0 1 -2 1 00 x5 5 0 1 1 0 1cj-zj 0 -1 1 0 0因检验数 20，表明已求得最优解： 。*(9,4)X8、某地区有 A、B、C 三个化肥厂，供应本地甲、乙、丙、丁四个产粮区。已知各化肥厂可供应化肥的数量和各产粮区对化肥的需要量，以及各厂到各区每吨化肥的运价如表 2-28 所示。试制定一个使总运费最少的化肥调拨方案。表 2- 1运价/ 产粮 (元/吨) 区化肥厂甲 乙 丙 丁 各厂供应量/万吨A1 5 8 7 3 7A2 4 9 10 7 8A3 8 4 2 9 3各区需要量/万吨 6 6 3 3解：设 A、B、C 三个化肥厂为 A1、A 2、A 3，甲、乙、丙、丁四个产粮区为B1、B 2、B 3、B 4；c ij 为由 Ai 运化肥至 Bj 的运价，单位是元/ 吨；x ij 为由 Ai 运往 Bj 的化肥数量（i=1,2,3;j=1,2,3,4）单位是吨；z 表示总运费，单位为元，依题意问题的数学模型为： 341minijizcx12331423412312346. 78xstxx该题可以用单纯形法或 matlab 自带工具箱命令（linprog）求解。 *9、求解下列不平衡运输问题（各数据表中，方框内的数字为单位价格 ijc，框外右侧的一列数为各发点的供应量 ia，框底下一行数是各收点的需求量 jb）：（1） 5 1 7 10 要求收点 3 的需求必须正好满足。6 4 6 803 2 5 1575 20 50（2） 5 1 0 20 要求收点 1 的需求必须由发点 4 供应。3 2 4 107 5 2 159 6 0 155 10 15解答略。练习题三1、用 0.618 法求解问题 12)(min30ttt的近 似 最 优 解 ， 已 知 的 单 谷 区 间为 ， 要 求 最 后 区 间 精 度 。)(t3, 0.5答：t=0.8115 ；最小值-0.0886. （调用 golds.m 函数）2、求无约束非线性规划问题min =),(321xf 123214x的最优解解一：由极值存在的必要条件求出稳定点：， ， ，则由 0fx得 ， ， 12fx28fx3fx120x3再用充分条件进行检验：， ， ， ， ，21fx2f23fx21fx213fx23fx即 为正定矩阵得极小点为 ，最优值为-1。2082f T*(,0)解二：目标函数改写成min =),(321xf2213(41x易知最优解为（1,0,0） ，最优值为-1。3、用最速下降法求解无约束非线性规划问题。 2121)(minxxXf 其中 ，给定初始点 。TxX),(21T0,解一：目标函数 的梯度()fx1122()4()fxxf令搜索方向 再从 出发，沿 方向作一维寻优，令步长变(0)1fX(1)(0)1dfX(0)X(1)d量为 ，最优步长为 ，则有1(0)(1) 故 (0)() 221() ()()()fxXd 令 可得 求出 点之后，与上类似地，121(1)(0)(1)Xd(1)X进行第二次迭代： 令(1)f(2)(1)fX令步长变量为 ，最优步长为 ，则有2(1)(2)11Xd故 令(1)(2) 2 22()(1)()1()51()fx 可得 20215(2)()(2) 0.85Xd此时所达到的精度(2).fX(2)0.8f本题最优解 ，1.5()1,5fX练习题四1、石油输送管道铺设最优方案的选择问题：考察网络图 4-6，设 A 为出发地，F 为目的地，B，C，D，E 分别为四个必须建立油泵加压站的地区。图中的线段表示管道可铺设的位置，线段旁的数字表示铺设这些管线所需的费用。问如何铺设管道才能使总费用最小？图 4- 1解： 第五阶段：E1F 4；E2F 3；第四阶段：D1E1 F 7；D2E2F 5；D3 E1F 5；第三阶段：C1D1E1 F 12；C2D2E2F 10；C3D2E2F 8；C4D3 E1F 9；第二阶段：B1C2 D2E2F 13； B2C3D2E2F 15； 第一阶段：AB1C2 D2E2F 17；最优解：AB1C2 D2E2F 最优值：172、 用动态规划方法求解非线性规划 123123max()7,0fx解： ，最优值为 9。1239,9xx3、用动态规划方法求解非线性规划 22121max765.039,zxst解：用顺序算法阶段：分成两个阶段，且阶段 1 、2 分别对应 。12,x决策变量： 12,x状态变量： 分别为第 j 阶段第一、第二约束条件可供分配的右段数值。,ivw1*2221 1110(,)ma76in76,xf vw*1in,xv2*2 12205 22 2(,)ax(,3) in76(,7(3)6(3)fwfvxvxwxx由于 ，221,9v 2*22 22205(,),9)main970,8961xfvwf 可解的 ，最优值为 702.92。1.6,0.x4、设四个城市之间的公路网如图 4-7。两点连线旁的数字表示两地间的距离。使用迭代法求各地到城市 4 的最短路线及相应的最短距离。 2 14358 674图 4- 2 城市公路网解：城市 1 到城市 4 路线1-3-4 距离 10；城市 2 到城市 4 路线2-4 距离 8；城市 3 到城市 4 路线3-4 距离 4。5、某公司打算在 3 个不同的地区设置 4 个销售点，根据市场部门估计，在不同地区设置不同数量的销售点每月可得到的利润如表 4-19 所示。试问在各地区如何设置销售点可使每月总利润最大。表 4- 1地区 销 售 点0123412306120517402163217地区地区 销 售 点销 售 点解：将问题分为 3 个阶段，k =1，2，3；决策变量 xk 表示分配给第 k 个地区的销售点数；状态变量为 sk 表示分配给第 k 个至第 3 个地区的销售点总数；状态转移方程：s k+1=skx k，其中 s1=4；允许决策集合：D k（s k）= x k|0x ks k阶段指标函数：g k（x k）表示 xk 个销售点分配给第 k 个地区所获得的利润；最优指标函数 fk（s k）表示将数量为 sk 的销售点分配给第 k 个至第 3 个地区所得到的最大利润，动态规划基本方程为： 104()max()() 3,21kkkksfgfxk=3 时， 333()()xsf4 17 174 316163 214142110101 0000 43210 x3*f3(s3) g3（ x3）（ ）k=2 时， 222320()max()sfgfsx2,3 31 2+0 21+10 17+14 12+16 0+17 4 22721+017+1012+140+163 1217+012+100+14211212+00+101 0000 43210x2*f2(s2) g2(x2)+f3(s2 x2) k=1 时， ，1()max()sfgfsx124()max()fsgfx最优解为：x 1*=2，x 2*=1，x 3*=1，f 1(4)=47，即在第 1 个地区设置 2 个销售点，第 2 个地区设置 1个销售点，第 3 个地区设置 1 个销售点，每月可获利润 47。 6、设某厂计划全年生产某种产品 A。其四个季度的订货量分别为 600 公斤，700 公斤，500 公斤和 1200 公斤。已知生产产品 A 的生产费用与产品的平方成正比，系数为 0.005。厂内有仓库可存放产品，存储费为每公斤每季度 1 元。求最佳的生产安排使年总成本最小。解：四个季度为四个阶段，采用阶段编号与季度顺序一致。设 sk 为第 k 季初的库存量，则边界条件为 s1=s5=0设 xk 为第 k 季的生产量，设 yk 为第 k 季的订货量； sk ， xk ，y k 都取实数，状态转移方程为 sk+1=sk+xk - yk 仍采用反向递推，但注意阶段编号是正向的目标函数为：12342,1()min(0.5)iixf s第一步：(第四季度) 总效果 f4(s4,x4)=0.005 x42+s4由边界条件有： s5= s4 + x4 y4=0，解得： x4*=1200 s4将 x4*代入 f4(s4,x4)得：f4*(s4)=0.005(1200 s4)2+s4=7200 11 s4+0.005 s42第二步：(第三、四季度) 总效果 f3(s3,x3)=0.005 x32+s3+ f4*(s4)将 s4= s3 + x3 500 代入 f3(s3,x3) 得：233322 2333333323(,)0.5701(50)().1.6.19,)0108.5,(,)()7fsxsxsxfssxfsxfs解 得 代 入 得第三步：(第二、三、四季度) 总效果f2(s2,x2)=0.005 x22+s2+ f3*(s3)将 s3= s2 + x2 700 代入 f2(s2,x2) 得：222 22 222(,)0.57070(),).1.5()70(3),(,()6.f sfsxsfxfss 解 得 代 入 得第四步：(第一、二、三、四季度) 总效果f1(s1,x1)=0.005 x12+s1+ f2*(s2)将 s2= s1 + x1 600= x1 600 代入 f1(s1,x1) 得：21 2111112(,)0.506(0)(3)(),.4860,(,)()fxfsxfsfs解 得 代 入 得由此回溯：得最优生产库存