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

1、练习题一1、建立优化模型应考虑哪些要素?答：决策变量、目标函数和约束条件。2、讨论优化模型最优解的存在性、迭代算法的收敛性及停止准则。minf(x)答：针对一般优化模型s.tg(x)0,i=1,2,.m，讨论解的可行域D,若存在一点X*gD，对h(x)=0,j=1,pj于VXgD均有f(X*)f(X)则称X*为优化模型最优解，最优解存在；迭代算法的收敛性是指迭代所得到的序列X(1),X，,X(K).，满足f(X(K+1)f(X(K)，则迭代法收敛；收敛的停止准则有f(X(k+1)-f(X(k)X(k+1)-X(k)X(k+1)-X(k)，10123s.t18123y,y,y0123*2、研究线

2、性规划的对偶理论和方法(包括对偶规划模型形式、对偶理论和对偶单纯形法)。答：略。3、用单纯形法求解下列线性规划问题：1)minz=Xx?+xX1+X2-2X322X+兀小+3s.#123；X+X302)minz=4x空+x3X1-2X2+X3x2-2x3+x4X2+X3+X5s.t.0(i=1,2,5)解：(1)引入松弛变量X4，X5，X6minz=x-x+x+0*x+0*x+0*x123456TOC o 1-5 h zx+x-2x+x=212342x+x+x+x5=3s.t123-x1+x3+x6=4x1,x2,x3,x4,x5,x60因检验数O20,故确定x2为换入非基变量，以x2的系数列

3、的正分量对应去除常数列,最小比值c1-11000/C基bx,x.xQx.xcx.B0 x4211-21000 x532110100 x64-101001Cj-Zj1-11000所在行对应的基变量x4作为换出的基变量。cfj1-11000CB基bx1x4x3x4亠x6-1x2211-21000 x51103-1100 x64-10100120-1100因检验数。30,表明已求得最优解：X*=(0,8/3,1/3,0,0,11/3)，去除添加的松弛变量,最优解为：X*=(0,8/3,1/3)。2)根据题意选取x1，x4，x5，为基变量:minz=4-x空+x3s.t.0(i=1,2,5)CB基bX

4、1X2X3X4X50X121-21000X4201-2100X5501101Cj-z0-1100因检验数o2v0最小，故确定x2为换入非基变量,以x2的系数列的正分量对应去除常数列，最小比值所在行对应的基变量x4作为换出的基变量。c.fjcb基b0X6-1x20 x530-1100X1XX3X4X510-32001-210003-1100-11因检验数a30，表明已求得最优解：X*(9,4丄0,0)。8、某地区有A、B、C三个化肥厂，供应本地甲、乙、丙、丁四个产粮区。已知各化肥厂可供应化肥的数量和各产粮区对化肥的需要量，以及各厂到各区每吨化肥的运价如表2-28所示。试制定一个使总运费最少的化肥

5、调拨方案。表2-1运价/、粮良化肥厂甲乙丙丁各厂供应量/万吨A58737A,491078a384293各区需要量/万吨6633解：设A、B、C三个化肥厂为A.A2、A3，甲、乙、丙、丁四个产粮区为B、B2、B3、B4；勺为由Ai运化肥至斗的运价，单位是元/吨；亓为由Ai运往斗的化肥数量(i=1,2,3;j=1,2,3,4)单位是吨；z表示总运费，单位为兀，依题意问题的数学模型为:minz=衣cxijiji=1j=1x+x+x=6112131x+x+x=6122232x+x+x=3132333x+x+x=3142434x+x+x+x:=711121314x+x+x+x=821222324x+x+

6、x+x=731323334该题可以用单纯形法或matlab自带工具箱命令（1inprog）求解。*9、求解下列不平衡运输问题（各数据表中方框内的数字为单位价格cj框外右侧的一列数为各发点的供应量a，框底下一行数是各收点的需求量b.）：aij108015要求收点3的需求必须正好满足。75205020要求收点1的需求必须由发点4供应10151551015解答略。练习题三1、用0.618法求解问题min9（t）=13一2t+1t0的近似最优解，已知P（t）的单谷区间为0,3，要求最后区间精度=0.5。答:t=0.8115；最小值-0.0886.（调用golds.m函数）2、求无约束非线性规划问题1m

7、inf(x,x,x)=x2+4x2+x2-2x1231231的最优解解一：由极值存在的必要条件求出稳定点：吋dfo=2x2，=8x，dx1dx212dx3=2x，则由Vf(x)=0得x=0，x=023再用充分条件进行检验：d2f=2，dx21竺=8,dx22d2fdx23也=0,dxdx12d2fdxdx13d2fdxdx230为正定矩阵得极小点为x*=(1,0,0)2丿解二：目标函数改写成T，最优值为-1。minf(x,x,x)=(x-1)2+4x2+x2-1123123易知最优解为(1,0,0)，最优值为-1。3、用最速下降法求解无约束非线性规划问题。minf(X)=xx+2x2+2xx+

8、x2其中X=(x,x)t，给定初始点X0=(0,0)t。12解一：目标函数f(x)的梯度Vf(x)二df(x)d(x)1df(x)d(x)21+4x+2x121+2x+2x12Vf(X(0)二令搜索方向d(i)=-Vf(X(o)二再从X(0)出发，沿d方向作一维寻优，令步长变-11-九九令Q(九)=2九一2=0可得九=1X(1)=X(0)+Xd(1)=11011+=011求出X(1)点之后，与上类似地，进行第二次迭代：Vf(X(i)二令d二-Vf(X)二量为九，最优步长为九，则有X(0)+Xd(1)=1故f(x)=f(X(0)+九d(1)=(九)一九+2(九)2+2(九)九+九2=九22X=p

9、(九)1令步长变量为X，最优步长为X,则有2-1九-1九+1故f（x）二f（X（1）+九d）二（九1）-（九+1）+2（九一1）2+2（九1）（九+1）+（九+1）2二5九2-2九1=9（九）令219（九）=10九一2=0可得九=225X（2=X（+I2-1d=（2）1-08Vf（X（2）=0.2-0.2此时所达到的精度IVf(X)卜0.2828本题最优解X*=,f(X*)=-1,25丄练习题四1、石油输送管道铺设最优方案的选择问题：考察网络图4-6,设A为出发地，F为目的地，B,C，D，E分别为四个必须建立油泵加压站的地区。图中的线段表示管道可铺设的位置，线段旁的数解：第五阶段：E1F4；E

10、2F3；第四阶段：D1E1F7；D2E2F5；D3E1F5；第三阶段：C1D1E1F12；C2D2E2F10；C3D2E2F8；C4D3E1F9第二阶段：B1C2D2E2F13；B2C3D2E2F15；第一阶段：AB1C2D2E2F17；最优解：AB1C2D2E2F最优值：172、用动态规划方法求解非线性规划maxx+x+x=270123解：x二9,x二9,x二9，最优值为9。1233、用动态规划方法求解非线性规划rmaxz=7x2+6x+5x212s.tx+2x1012x一3x012解：用顺序算法阶段：分成两个阶段，且阶段1、2分别对应x,x。12决策变量：x,x12状态变量：v,w分别为第

11、j阶段第一、第二约束条件可供分配的右段数值。iimax7x2+6x=min7v2+6v,7w2+6w0 x1v10 x11w11x*二minv,w11f*(v,w)=max5x2+f*(v-2x,w+3x)2220 x25212222=max5x2+min7(v一2x)2+6(v一2x),7(w+3x)2+6(w+3x)222222220 x52由于v=10,w=9，f*(v,w)=f*(10,9)=maxmin33x2一292x+760,68x2+396x+621222220 x252222可解的x=9.6,x=0.2，最优值为702.92。124、设四个城市之间的公路网如图4-7。两点连线

12、旁的数字表示两地间的距离。使用迭代法求各地到城市4的最短路线及相应的最短距离。解：城市1到城市4路线图4-2城市公路网1-3-4距离10；城市2到城市4路线2-4距离8；城市3到城市4路线3-4距离4。5、某公司打算在3个不同的地区设置4个销售点，根据市场部门估计，在不同地区设置不同数量的销售点每月可得到的利润如表4-19所示。试问在各地区如何设置销售点可使每月总利润最大。表4-1销售点01234101625303220121721223010141617解：将问题分为3个阶段，k=1,2,3；决策变量xk表示分配给第k个地区的销售点数；状态变量为sk表示分配给第k个至第3个地区的销售点总数;

13、状态转移方程：Sk+i=Sk_Xk，其中S=4；允许决策集合：Dk(sk)=x/OWxkWskfvAzAzfvAz阶段指标函数：gk(xk)表示xk个销售点分配给第k个地区所获得的利润;最优指标函数fk(sk)表示将数量为sk的销售点分配给第k个至第3个地区所得到的最大利润，动态规划基本方程为：kk)maxg(x)+skkkf(s-X)k+1kkk=3,2,1k=3时，f(s)=maxg(x)333X3=S3k=2时，f(s)=maxg(x)+f(s-1x)220 x2s22232122223101416101416g3(X3)f3(S3)X3*0123400L0017174畛户厶（丁x)2胆

14、）x*2012340000k=1时，fi(1)二max+1)+12S+01)，f(5!)二maxgi(x)+f(4x)丄20+1412+10场（17）+0（打-可）221X.*30+16012-卜1417410:21+04】24切+17+血卜16217r+142221+10222+023最优解为：x=2,兀2*=1,兀3*=1,f（4）=47,即在第1个地区设置2个销售点，第2个地区设置1个销售点，第3个地区设置1个销售点，每月可获利润47。6、设某厂计划全年生产某种产品A。其四个季度的订货量分别为600公斤，700公斤，500公斤和1200公斤。已知生产产品A的生产费用与产品的平方成正比,系

15、数为0.005。厂内有仓库可存放产品,存储费为每公斤每季度1元。求最佳的生产安排使年总成本最小。解：四个季度为四个阶段,采用阶段编号与季度顺序一致。设sk为第k季初的库存量，则边界条件为51=55=0设xk为第k季的生产量，设yk为第k季的订货量；sk，xk，yk都取实数，状态转移方程为sk+1=sk+xk-yk仍采用反向递推，但注意阶段编号是正向的目标函数为：f（x）=min（0.005x2+s）iix1,x2,x3,x4i=1第一步：（第四季度）总效果f4（s4,x4）=0.005x42+s4由边界条件有：$5=$4+兀4-歹4=0，解得：兀4*=1200-34将兀4*代入加血“）得：f4

16、*(s4)=0.005(1200-s4)2+s4=7200-11s4+0.005s42第二步：(第三、四季度)总效果f3(s3,x3)=0.005x32+s3+f4*(s4)将S4=S3+X3-500代入f3(s3，X3)得:f(s,x)=0.005x2+s+7200-ll(x+s-500)TOC o 1-5 h z333333+0.005(x+s-500)233=0.0lx2+0.0lxs-l6x+0.005s2-l5s+l3950333333fs3,X3)=0.02x+0.01s-16=0dx333解得x*=800-0.5s,代入f(s,x)得33333f*(s)=7550-7s+0.00

17、25s23333第三步:(第二、三、四季度)总效果f2(s2,x2)=0.005x22+s2+f3*(s3)将s3=s2+x2-700代入f2(s2,x2)得:f(s,x)=0.005x2+s+7550-7(x+s-700)222222+0.0025(x+s-700)222叭(s2,x2)=0.015x+0.005(s-700)-7=0dx222解得x*=700-(13)s,代入f(s,x)得22222f*(s)=10000-6s+(0.005s22222第四步:(第一、二、三、四季度)总效果f1(s1,x1)=0.005x12+s1+f2*(s2)将s2=s+x600=x600代入f1(s,

18、x)得:f(s,x)=0.005x2+s+10000-6(x-600)111111+(0.0053)(x-600)2fIx1)=(0.04,3)x-8=0dx11解得x*=600,代入f(s,x)得1111f*(s)=1180012由此回溯：得最优生产-库存方案x1*=600，s2*=0；x2*=700，s3*=0；x3*=800，s4*=300；x4*=900。7、某种机器可在高低两种不同的负荷下进行生产。设机器在高负荷下生产的产量函数为g=8u1，其中u1为投入生产的机器数量，年完好率a=0.7；在低负荷下生产的产量函数为h=5y,其中y为投入生产的机器数量，年完好率为b=0.9。假定开始

19、生产时完好机器的数量s1=1000o试问每年如何安排机器在高、低负荷下的生产，使在5年内生产的产品总产量最高。解：构造这个问题的动态规划模型：设阶段序数k表示年度。状态变量sk为第k年度初拥有的完好机器数量，同时也是第k-1年度末时的完好机器数量。决策变量Uk为第k年度中分配高负荷下生产的机器数量，于是Sk-Uk为该年度中分配在低负荷下生产的机器数量。这里sk和uk均取连续变量，它们的非整数值可以这样理解，如sk=0.6，就表示一台机器在k年度中正常工作时间只占6/10；uk=0.3,就表示一台机器在该年度只有3/10的时间能在高负荷下工作。状态转移方程为：s二au+b(su)二0.7u+0.

20、9(su),k二1,2,5k+1kkkkkkk段允许决策集合为：D(s)=b|0uskkkkk设v(s,u)为第k年度的产量，则v二8u+5(su)kkkkkkk故指标函数为：V=丈v(s,u)1,5kkkk=1令最优值函数fk(sk)表示由资源量sk出发，从第k年开始到第5年结束时所生产的产品的总产量最大值。因而有逆推关系式：f(s)=066rf(s)=max(8u+5(skkkkukeDk(sk)k=1,2,3,4,5u)+f0.7u+0.9(skk+1kku)k从第5年度开始，向前逆推计算。当k=5时，有：5)max0u5s5max0u5s5=max0u5s5Isu+5(su)+f【0.

21、7u+0.9(s555655I8u+5(su5)555I3u+5s55u)5因f5是u5的线性单调增函数，故得最大解u5*，相应的有:f5(s5)=8s5当k=4时，有：f(s)=maxu+5(s-u)+f【0.7u+0.9(s-u)440u?4445444=maxu+5(s-u)+8【0.7u+0.9(s-u)0us4444440u4s4=max(13.6u+12.2(s-u)j0u4s4444=max1.4u+12.2s440u4s4故得最大解，U4*二S4，相应的有f(s)二13.6s44依此类推，可求得u*二s,相应的f(s)二17.5s33333u*二0,相应的f(s)二20.8s2

22、222u*二0,相应的f(s)二23.7s1111因si=1000,故：f(s)二2370011计算结果表明：最优策略为u*=0,u*二0,u*=s,u*=s,u*=s12334455即前两年应把年初全部完好机器投入低负荷生产，后三年应把年初全部完好机器投入高负荷生产。这样所得的产量最高，其最高产量为23700台。在得到整个问题的最优指标函数值和最优策略后，还需反过来确定每年年初的状态，即从始端向终端递推计算出每年年初完好机器数。已知s1=1000台，于是可得：s=0.7u*+0.9(s-u*)=0.9s=900(台)21111s=0.7u*+0.2(s-u*)=0.9s=810(台)TOC o 1-5 h z2222s=0.7u*+0.9(s-u*)=0.7s=567(台)3333s=0.7u*+0.9(s-u*)=0.7s=397(台)4444s=0.7u*+0.9(s-u*)=0.7s=278(台)55558、有一辆最大货运量为10t的卡车，用以装载3种货物，每种货物的单位重量及相应单位价值如表4-20所示。应如何装载可使总价值最大？表4-2货物编号i123单