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

1、 练习题一? 、建立优化模型应考虑哪些要素1 答：决策变量、目标函数和约束条件。 、讨论优化模型最优解的存在性、迭代算法的收敛性及停止准则。2)xminf(?*L.msi?tg1,x2,?0,答：针对一般优化模型，对，讨论解的可行域，若存在一点D?XDi?Lp1,?0,h jx?j*为优化模型最优解，最优解存在；迭代算法的收敛性是指迭代则称于 均有)?f(f(XX)XD?X)(K?1)K(1)(2)(K)，则迭代法收敛；收敛的停止准则有所得到的序列 ，满足)XfL)X?,Xf,L,X(X(?)(?1)k(k)(k(k?1)xx?ffx?x? )k(k(k?1)1)(k?(k?f?fxfx?x等

2、，?xx?)(kx)(kxf 等。练习题二 1、某公司看中了例2.1中厂家所拥有的3种资源R、R、和R，欲出价收购（可能用于生产附321加值更高的产品）。如果你是该公司的决策者，对这3种资源的收购报价是多少？（该问题称为例2.1的对偶问题）。 y,y,y作为本问题的决策变量。种资源报价 解：确定决策变量 对3321确定目标函数 问题的目标很清楚“收购价最小”。 确定约束条件 资源的报价至少应该高于原生产产品的利润，这样原厂家才可能卖。 min w?170y?100y?150y 因此有如下线性规划问题：3125y?2y?y?10?312?s.t2y?3y?5y?18 ?312?y,y,y?0?1

3、23*2、研究线性规划的对偶理论和方法（包括对偶规划模型形式、对偶理论和对偶单纯形法）。 答：略。 3、用单纯形法求解下列线性规划问题： z?4?x?xminx?x?xminz?32321x?2x2x?2?2?xx?x?312321?2?xx?2?x32x?xx?423123）（2；） 1 （.ts.ts.?5?xx?x?4x?x?52313?)5?21i0?x(?,0x,x,x?i312 解：（1）引入松弛变量x，x，x6 54 x?0*x?0*xx?x?x?0*min z?613425x?x?2x?x =2?4213?2x?x?x ?x5 =3?123 ts.?x1?x3 ?x6=4?x1

4、,x2,x3,x4,x5,x6?0? 0 0 0 1 -1 1 c j xx x C 基 b xxx 36B4125-2 0 1 1 x 2 1 0 0 41 0 x2 0 1 3 0 1 51 1 0 4 -1 0 0 0 x 60 0 1 1 c-z0 -1 jj因检验数0，故确定x为换入非基变量，以x的系数列的正分量对应去除常数列，最小比值222所在行对应的基变量x作为换出的基变量。 4 0 0 1 0 -1 c 1 j xx x x x b C 基 x36441B5-2 0 1 1 1 x 2 0 -1 23 0 x-1 1 1 0 0 1 51 1 -1 x 0 0 0 4 0 60

5、 0 1 c-z0 2 -1 jj因检验数0，表明已求得最优解：j*?(0,8/X3,1/3)。最优解为： （2）根据题意选取x，x，x，为基变量： 541minz?4?x?x32?2x?2x?x?312?x?2x?x?2?234 s.t.?x?x?x?5?532?x?0(i?1,2,?,5)?i 0 0 1 -1 c0 j x x x b x x C 基3521B41 0 x 2 1 0 -2 0 1-2 0 x0 1 2 0 1 41 1 0 5 1 0 0 x50 0 -1 0 1 c-zjj因检验数0最小，故确定x为换入非基变量，以x的系数列的正分量对应去除常数列，最小222比值所在行

6、对应的基变量x作为换出的基变量。 4 0 0 1 0 -1 c j xx b 基 x xx C3542B1-3 0 6 2 0 1 0 x1-2 0 1 0 -1 x1 2 23 1 -1 x 0 0 0 3 50 1 0 0 zc- -1 jj因检验数0，表明已求得最优解：因检验数j8、某地区有A、B、C三个化肥厂，供应本地甲、乙、丙、丁四个产粮区。已知各化肥厂可供应化肥的数量和各产粮区对化肥的需要量，以及各厂到各区每吨化肥的运价如表2-28所示。试制定一个使总运费最少的化肥调拨方案。 表2- 1 运/产)各厂供应万化肥737851891074348923 3 6 6 /各区需要量万吨 3

7、解：设A、B、C三个化肥厂为A、A、A，甲、乙、丙、丁四个产粮区为B、B、B、B；4121233c为由A运化肥至B的运价，单位是元/吨；x为由A运往B）单位i=1,2,3;j=1,2,3,4的化肥数量（jiijjiij 是吨；z表示总运费，单位为元，依题意问题的数学模型为：43?xminz?c ijij1?i?1j6?x?x?x?311121?6?x?x?x?321222?3x?x?x?332313? .3s?x?x?tx?342414?7x?x?x?x?14121311?8x?x?x?x?24222321?7?x?xx?x?34333132 matlab自带工具箱命令（linprog）求解。

8、该题可以用单纯形法或，框外右侧的一列数为求解下列不平衡运输问题（各数据表中，方框内的数字为单位价格*9、cij ：各发点的供应量，框底下一行数是各收点的需求量）baji1 7 10 5 要求收点3的需求必须正好满足。 （1） 6 4 6 80 3 2 5 15 75 20 50 （2） 5 1 0 20 要求收点1的需求必须由发点4供应。 3 2 4 10 7 5 2 15 9 6 0 15 5 10 15 解答略。 练习题三 1、用0.618法求解问题 3?2t?1(t)?tmin t?0?0.5。的单谷区间为 ，要求最后区间精度的近似最优解，已知3,0)t(答：t=0.8115；最小值-0

9、.0886.（调用golds.m函数） 、求无约束非线性规划问题2 222=min ?2x4xx?x?)x,xf(x,2311321的最优解 解一：由极值存在的必要条件求出稳定点： ?f?f?f?得，则由 x2x?2?8x2?1?x0?xx?00x?f 131232x?xx321再用充分条件进行检验： 222222f?f?f?ff?f， ，0?008?22? 222x?x?xxxx?xx?x331223121200?2T00?8f?，最优值为-1。即为正定矩阵得极小点为 (1,0,0)?x*?200?解二：目标函数改写成 222?4xx?1)?x?1(=min )x,xf(x,321213易知

10、最优解为（1,0,0），最优值为-1。 3、用最速下降法求解无约束非线性规划问题。 22 x?2xx?2xx?minf(X)?x?221211T0T。，给定初始点 其中),X0?X?(x,x)(021?f(x)? )(x?x2x?1?4?121?)(?x?f 的梯度解一：目标函数)(fx?x2x?1?2)xf(?21? )(x?21?1?(0)(1)(0)(1)(0)d方向作一维寻优，令步长变再从出发，沿令搜索方向X?)f?f(X?)?(dX?11?10?(1)(0)? ，最优步长为量为，则有?d?X?1?10?(0)(1)222?)?2?)d?)(?)?2(?()?2(xf()?fX? 故1

11、0?1?1?(1)(1)(0)(1)?1?02(?)?2?点之后，与上类似地， 可得求出令X?X?X?d?111011?11?(2)(1)(1) 进行第二次迭代：令?(X)X?f()?d?f?1?1? 令步长变量为，最优步长为，则有2?1?11?(2)(1)? ?Xd?111?2(1)(2)22?令故)?1)?2(?1)(2?1)?2(?(?1)?(fx)?f(X?5d1)?(?1)?(?1)20.81?1?11(2)(2)(1)? 可得0210)?(?X?X?d?2221.21155?0.2?(2)(2) 此时所达到的精度 ?)(X?f0.2828(X)?f?0.2?1? ，本题最优解25f

12、(X1,)?X?1.5? 练习题四，F为目的地，B1、石油输送管道铺设最优方案的选择问题：考察网络图4-6，设A为出发地，分别为四个必须建立油泵加压站的地区。图中的线段表示管道可铺设的位置，线段旁的数，EC，D 字表示铺设这些管线所需的费用。问如何铺设管道才能使总费用最小？ 4- 1 图 解： 3；E2F 第五阶段：E1F 4；E2F 5；D3E1F 7；D2F 5； 第四阶段：D1E1 第三阶段：C1D1E1 F 12；C2D2E2F 10；C3D2E2F 8；C4D3E1F 9； 第二阶段：B1C2D2E2F 13； B2C3D2E2F 15； 第一阶段：AB1C2D2E2F 17； 最优

13、解：AB1C2D2E2F 最优值：17 2、 用动态规划方法求解非线性规划 maxf(x)?x?x?x321 27x?xx?312?0x,xx?321 。9解：，最优值为9?9,x?9,xx312 、用动态规划方法求解非线性规划322?x56xz?7x?max211?.sx?10tx?2?21 ?9?3xx?21?0?x,x?21 用顺序算法解： 。、2 分别对应阶段：分成两个阶段，且阶段1 x,x21 决策变量：xx,21 阶段第一、第二约束条件可供分配的右段数值。j 状态变量：分别为第wv,ii22*2 ww?min7v6?6vfw(v,)?max7x,7?6x111111111vx?0?

14、11wx?0?11* minv,wx?111*2*)3x,wf?(v?2xf(v,w)?max5x?2122222225?0x2 222)xw?3)v?2x),7(w?3x?6()x ?max5?min7(v?2x?6(2222222225?x?02*22 ，由于9?10,wv?396x621?292x?760,68x?f,(vw)?f(10,9)?maxmin33x22222222225?0?x20.2?9.6,xx 。，最优值为702.92可解的21 使用迭代法求各地两点连线旁的数字表示两地间的距离。4-7。4、设四个城市之间的公路网如图 4的最短路线及相应的最短距离。到城市5128673

15、44 图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 表 销售点地区42130321613025022211217021716141030 解： 3；=1，2，将问题分为3个阶段，k k个地区的销售点数；决策变量x表示分配给第k 3个地区的销售点总数；s表示分配给第k个至第状态变量为k =4；x，其中s状态转移方程：s=

16、s1k+1kk xs|0s）=x允许决策集合：D（kkkkk 个地区所获得的利润；x个销售点分配给第k阶段指标函数：g（x）表示kkk动态个地区所得到的最大利润，个至第3的销售点分配给第s）表示将数量为sk最优指标函数f（kkk 规划基本方程为：max)?f?3,2,1(s?x)f(s?x) kg(?kk?k1kkkksx0? ?kk0)?f(s?44)xmaxg(fs)? 时，k=33333x?s33g（x）33f(s) x*33342130000010111014221416316317 4 4 17 f(s)?maxg(x)?f(s?x) 时，=2k2232222s?0?x22g(x)+

17、f(sx) 23222f(s) x*222423010000112+00+1011212220+1412+1017+00+1612+1432717+10221+00+17 12+16 4 31 17+14 21+10 2,3 22+0 k=1时， )x(4?x)?ff(s)?maxg(?)f(s?maxg(x)?f(sx)11111121211114x?0?xs0111 *12个地区设置1个地区设置2，x个销售点，第=1，f(4)=47最优解为：x=2，x，即在第=11321 。 个地区设置1个销售点，每月可获利润47个销售点，第3 公斤公斤，500600公斤，7006、设某厂计划全年生产某种

18、产品A。其四个季度的订货量分别为。厂内有仓库可存放的生产费用与产品的平方成正比，系数为0.0051200公斤。已知生产产品A和 1元。求最佳的生产安排使年总成本最小。产品，存储费为每公斤每季度 解：四个季度为四个阶段，采用阶段编号与季度顺序一致。=0 s s=为第设 s k季初的库存量，则边界条件为 5k1 都取实数，状态转移方程为y x为第k季的订货量；s，x 设 为第k季的生产量，设 y kk ，k kk 仍采用反向递推，但注意阶段编号是正向的目标函数为：y =s+x - skk+1kk4?2)(0.005x?sf(x)?min ii1x,x,xx43211?i2s)=0.005 x+(

19、fs,x(第一步：第四季度) 总效果4 4444y s，解得：x + 由边界条件有： s= sx*=1200 =04 4 4544 得：x)s*代入 f(,x将44 44 2 2ss=7200 )s)=0.005(1200 *(f s +s11 +0.005 4444442) s+ f*(f(s,x)=0.005 xs+第二步：(第三、四季度) 总效果 4333334f 500 代入 ,xx) 得：(s 将 s= s + 343 3332500)x?s?0.005x?s?7200?11(f(s,x)?33333332500)s?0.005(x332213950?15ss?16x?0.005s?

20、0.01x?0.01x333333)xs,?f( 333016?0.02x?0.01s? 33x?3?得x,)代入f(s,解得0.5x?800?s33333?2s?0.0025s)?7550?7fs(3333 ) 总效果第三步：(第二、三、四季度2) sx+s+ f*( f(s,x)=0.005 3222223 得：f(s,x) 将 s= s + x?700 代入 22322 22700)s?7(?7550?x?f(s,x)?0.005x?s22222222700)?0.0025(x?s22),x?f(s22207?s?700)?0.015x0.005( 22x?2?得),f(sx?700?(

21、13)s,代入解得x22222?2s3)6s?f(0.005(s)?10000?2222 总效果第四步：(第一、二、三、四季度) 2) s+ fx)=0.005 x*(+s, f(s 2111121f代入 600= x 600 x) 得：(= ss + xs, 将 11111 21 2?s?10000?6(x?f(s,x)0.005x600)1111112600)x?(0.0053)(1?f(s,x)111?(0.043)x?8?0 1x?1?得)s,xx?600,代入f(解得1111?11800?s)f(21 库存方案由此回溯：得最优生产。*=900； x*=800； x，s*=300*=0

22、*=700；， x*=600s*=0 x，s 1423342 ，=8ug7、某种机器可在高低两种不同的负荷下进行生产。设机器在高负荷下生产的产量函数为1为投入其中yy；=0.7在低负荷下生产的产量函数为h=5，a为投入生产的机器数量，u其中年完好率1试问每年如何安排机。假定开始生产时完好机器的数量=0.9年完好率为生产的机器数量，b。s=10001器在高、低负荷下的生产，使在5年内生产的产品总产量最高。 解： 构造这个问题的动态规划模型： 设阶段序数k表示年度。 状态变量s为第k年度初拥有的完好机器数量，同时也是第k?1年度末时的完好机器数量。 k?u为该年度中分配在低负荷下生k年度中分配高负

23、荷下生产的机器数量，于是s决策变量u为第kkk产的机器数量。 这里s和u均取连续变量，它们的非整数值可以这样理解，如s=0.6，就表示一台机器在k年度中kkk正常工作时间只占6/10；u=0.3，就表示一台机器在该年度只有3/10的时间能在高负荷下工作。 ks?au?b(s?u)?0.7u?0.9(s?u), k?1,2,L,5 状态转移方程为：kkkkk?1kk? 段允许决策集合为：ksu?u0?D(s)?kkkkkv(s,u)v?8u?5(s?u) 年度的产量，则为第k设kkkkkkk5? 故指标函数为：)u(s?V,vkk1,5k1k?令最优值函数f(s)表示由资源量s出发，从第k年开始

24、到第5年结束时所生产的产品的总产量最kkk大值。因而有逆推关系式： ?f(s)?066?f()s)?maxu)?f?0.7u0.9(s?u?8u5(s? ?kk?1kkkkkkk?D(su)?kkk k?1,2,3,4,5?从第5年度开始，向前逆推计算。 当k=5时，有： ?)s?fu0.7u?0.9(?f(s)?max8u?5(su)?5565555550?u5?s5?)5s?u?max?8u5( 555s?u50?5?s5?max?3u55s5?0u?5 ，相应的有：的线性单调增函数，故得最大解u*是因fu555s8sf()? 555 时，有：k=4当?)u0.9(s?f?0.7u?(s)

25、?maxs8u?5(?u)f4444444540?u?s44?)s?u0.7u?0.9(max)8u?5(s?u?8?444444s0?u? 44?)s?u13.6u?12.2(?max444s?0?u44?s?max12.21.4u44s0?u?44故得最大解，u*=s，相应的有 44 s13.6)?f(s444依此类推，可求得 *?u?s, 相应的 f(s)?17.5s33333?*u?0, 相应的 f(s)?20.8s ?2222?*u?0, 相应的 f(s)?23.7s?1111因s=1000，故： 23700)?f(s111计算结果表明：最优策略为 *u?0,u?0,u?s,u?s,

26、u?s 54134523即前两年应把年初全部完好机器投入低负荷生产，后三年应把年初全部完好机器投入高负荷生产。这样所得的产量最高，其最高产量为23700台。 在得到整个问题的最优指标函数值和最优策略后，还需反过来确定每年年初的状态，即从始端向终端递推计算出每年年初完好机器数。已知s=1000台，于是可得： 1*s?0.7u?0.9(s?u)?0.9s?900(台)11211*s?0.7u?0.2(s?u)?0.9s?810(台)22322* )台?0.7s567(?0.9(s?u)?s0.7u34333*s?0.7u?0.9(s?u)?0.7s?397(台)44454*s?0.7u?0.9(s

27、?u)?0.7s?278(台)55556 8、有一辆最大货运量为10t 的卡车，用以装载3种货物，每种货物的单位重量及相应单位价值如表4-20所示。应如何装载可使总价值最大？ 表4- 2 货物编号i 1 2 3 5 3 4 单位重量（t）6 4 单位价值ci 5 建模设三种物品各装x,x,x件 解：321max(4x?5x?6x)3123x?4x?5x?10 ?312?x?0,x?I,j?1,2,3?jj利用动态规划的逆序解法求此问题。 s?c,D(s)?x|0?x?s 111111s?s?x,D(s)?x|0?x?s 22122221s?s?x,D(s)?x|0?x?s 32333233状态

28、转移方程为： 2,13,k?s?x,)s?T(s,x?kkk?1kkk该题是三阶段决策过程，故可假想存在第四个阶段，而，于是动态规划的基本方程为： 0x?4x,f(s),k?3,2,1f(s)?max?kkkkk?1?1?D(xs) ?kkKf(s)?0?44 3,k? x?max6f(s)333L/5,?0,1,sx33 2,?kf(s)?max5x?f(s)32223s2L,0,1,x?2 4 )x?4?f(sx ?max52223s2L,?0,1,x2 4 1,?kf(s)?max4x?f(s)21121x?0,1,2,31 )xs?3(?max4x?f 11120,1,2,3?x1?2

29、,xx?1,x?0计算最终结果为 ，最大价值为13 。2319、设有 A，B，C 三部机器串联生产某种产品，由于工艺技术问题，产品常出现次品。统计结果表明，机器 A，B，C产生次品的概率分别为 p=30%, P=40%, P=20%, 而产品必须经过三部机CBA器顺序加工才能完成。为了降低产品的次品率，决定拨款 5 万元进行技术改造，以便最大限度地提高产品的成品率指标。现提出如下四种改进方案： 方案1：不拨款，机器保持原状； 方案2：加装监视设备，每部机器需款 1 万元； 方案3：加装设备，每部机器需款 2 万元； 方案4：同时加装监视及控制设备，每部机器需款 3 万元； 。4-21采用各方案

30、后，各部机器的次品率如表 表4- 3 A B C 20% 30% 40% 不拨款 10% 30% 万元 20% 拨款 1 10% 20% 拨款 2 万元 10% 6% 5% 10% 拨款 3 万元问如何配置拨款才能使串联系统的可靠性最大？ 解：为三台机器分配改造拨款，设拨款顺序为A, B, C，阶段序号反向编号为 k，即第一阶段计算给机器 C 拨款的效果。 设 s 为第 k 阶段剩余款，则边界条件为 s=5； 3k 设 x 为第 k 阶段的拨款额； k 状态转移方程为 s=s-x； kkk-1 目标函数为 max R=(1-P)(1-P)(1-P) CBA 仍采用反向递推 第一阶段 ：对机器 C 拨款的效果 R(s,x)=d(s,x)? R(s,x)= d(s,x) 111101111010 x0 1 2 3 x* R 11