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

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

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

3、)答：略3、用单纯形法求解下列线性规划问题：(1)min z = x, - x2x3% +x2 _2x3 兰2 2x, +x2 +x3 兰3 ；s.t.X1X3 _ 4Xi，X2，X3 _0(2)min z = 4 - X2 X3V, -2X2 +X3 x2 - 2x3 + x4X2 +X3+s.t.=2=2X5 =5Xi _0 (i =1,2, ,5),最小比值,最小比值解：（1）引入松弛变量X4, X5, X6min z =X -x2 x3 0* x4 0* x5 0* x6x, +x2 2x3 +Xzt=22x,+x2+x3+ x5 =3s.t彳| -x1 + x3+ x6=4x1,x2

4、, x3,x4,x5,x6 _ 0q-1-11000Cb基bX1X2X3X4X5X60X4211-21000X532110100X64-101001Cj-Zj1-11000因检验数020 ,故确定X2为换入非基变量,以X2的系数列的正分量对应去除常数列 所在行对应的基变量X4作为换出的基变量。q-1-11000Cb基bX1X4X3X4X5X6-1X2211-21000X51103-1100X64-101001Cj-Zj20-1100因检验数030 ,表明已求得最优解：X* =(0,8/3,1/3,0,0,11/ 3),去除添加的松弛变量,的最优解为：X* =(0,8/3,1/3)。(2)根据题

5、意选取XI，X4, X5,为基变量:min z 二 4 - X2 X3x 2x? + X3 2X2 -2X3 +X4=2St.X2 +X3+X5 =5Xi _0 (i =1,2,5)c-0-1100Cb基bX1X2X3X4X50X121-21000X4201-2100X5501101q-Zj0-1100因检验数020最小，故确定X2为换入非基变量,以X2的系数列的正分量对应去除常数列 比值所在行对应的基变量X4作为换出的基变量。c-0-1100Cb基bX1X2X3X4X50X1610-320-1X2201-2100X53003-11Cj-Zj00-110原问题,最小,最小因检验数030 ,表明

6、已求得最优解：X* =(9,4,1,0,0)8、某地区有A、B、C三个化肥厂，供应本地甲、乙、丙、丁四个产粮区。已知各化肥厂可供 应化肥的数量和各产粮区对化肥的需要量，以及各厂到各区每吨化肥的运价如表 2-28所示。试制定 一个使总运费最少的化肥调拨方案。表2- 1运价/粮(元 吨)化肥厂甲乙丙丁各厂供应量/万吨A158737A2491078A384293各区需要量/万吨6633解：设A、B、C三个化肥厂为Ai、A、A3，甲、乙、丙、丁四个产粮区为Bi、B2、B3、B4； Cj为由Ai运化肥至Bj的运价，单位是元/吨；Xij为由Ai运往Bj的化肥数量(i=1,2,3;j=1,2,3,4)单位是

7、吨；z表示总运费，单位为元，依题意问题的数学模型为：34min z 二、qXjjy j wX11 * X21 + %1 6x12 + x22 + x32 = 6X13 +X23 +X33 =3s.t sgk(Xk) fk 16 卡) k =3,2,1.!0 3k _Sk4$) =0k=3 时，f3(S3)=maxg3(X3)X3 士g3（ X3）f3(S3)*X3012340000110101214142316163417174k=2时，仇疋摯区)3(2)g2（X2）+f3（S2 X2）f2（S2）*X201234000010+1012+012120+1412+1017+022130+1612

8、+1417+1021+027240+1712+1617+1421+1022+0312,3k=i 时，fi（siomaxgi（rhf2（s -），人（$）=摩91化）+f2（4 X!）gi（i）+/2（vr-叼)小1)0123440+3116+2725 卜2230+1232+0472最优解为：x1 =2 , x2 =1 , x3 =1 , f1=47 ,即在第1个地区设置2个销售点，第2个地区设置1 个销售点，第3个地区设置1个销售点，每月可获利润47。6、设某厂计划全年生产某种产品 A。其四个季度的订货量分别为600公斤，700公斤，500公 斤和1200公斤。已知生产产品A的生产费用与产品的

9、平方成正比，系数为0.005。厂内有仓库可存 放产品，存储费为每公斤每季度1元。求最佳的生产安排使年总成本最小。解：四个季度为四个阶段，采用阶段编号与季度顺序一致。设sk为第k季初的库存量，则边界条件为S1 = S5=0设xk为第k季的生产量，设yk为第k季的订货量；Sk，xk ，yk都取实数，状态转移方程 为sk+1=sk+xk - yk仍采用反向递推，但注意阶段编号是正向的目标函数为：4fi(x)min 、 (0.005x： s)X1，X2，X3，X4第一步：(第四季度)总效果f4(s4,x4)=0.005 x42+s4由边界条件有：S5= S4 + X4 -y4=0，解得：X4*=120

10、0 - S4将 x4*代入 f4(s4,x4)得:f4*(s4)=0.005(1200 -s4)2+s4=7200 -1 s4+0.005 s42第二步：(第三、四季度)总效果 f3(s3，x3)=0.005 x32+s3+ f4*(s4)将 S4= S3 + X3 -500 代入 f3(S3，X3)得：f3(s3, %) =0.005x2 s 7200 -11(x3-500)0.005(X3 s3 -500)22 2=0.01x3 0.01x3Sj -16x3 0.005s3 -15S5 13950十3(S3，X3)=0.02x30.01S3 -16=0X3解得x3： =800 -0.5&,

11、代入 f3 (S3,x3)得f3 (q) =7550 -7s3 0.0025sf第三步：(第二、三、四季度)总效果f2(S2，X2)=0.005 X22+S2+ f3*(S3)将 S3= S2 + X2 -700 代入 f2(S2，X2)得：2f2(S2, X2)=0.005x2 员 7550-7(x2 s - 700)0.0025(% s2 -700)2f2(S2，X2)=0.015x2 . 0.005(s2 _700) -7 = 0 .X2解得X2 =700 -(13)S2,代入 f2 (S2,X2)得f2(Ss) =10000 6S2 (0.005 3)s2第四步：(第一、二、三、四季度

12、)总效果fl (si ,xi)=0.005 xi2+si + f2*(S2)将S2= S +-600=-600 代入 片佝为)得：=0.005x； S|10000-6(% -600)(0.005 3)(x, -600)2fl(,Xl) =(0.04；3)xi -8 =0x1解得x| = 600,代入fi(Si,)得f1 (s,) =11800由此回溯：得最优生产d库存方案xi*=600 , s,*=0 ;x,*=700 , S3*=0 ;X3*=800 , S4*=300 ;“*=900。7、某种机器可在高低两种不同的负荷下进行生产。设机器在高负荷下生产的产量函数为g=8ui,其中ui为投入生

13、产的机器数量，年完好率a=0.7 ;在低负荷下生产的产量函数为h=5y,其 中y为投入生产的机器数量，年完好率为b=0.9。假定开始生产时完好机器的数量 S1=1000。试问每 年如何安排机器在高、低负荷下的生产，使在5年内生产的产品总产量最高。解：构造这个问题的动态规划模型：设阶段序数k表示年度。状态变量sk为第k年度初拥有的完好机器数量，同时也是第k- 1年度末时的完好机器数量。决策变量Uk为第k年度中分配高负荷下生产的机器数量，于是Sk- Uk为该年度中分配在低负荷下生 产的机器数量。这里sk和uk均取连续变量，它们的非整数值可以这样理解，如sk=0.6，就表示一台机器在k年度中正常工作

14、时间只占6/10 ； uk=0.3，就表示一台机器在该年度只有3/10的时间能在高负荷下工作。状态转移方程为：sk1=aukb(sk-uk) = 0.7uk0.9(s-uk),k = 1,2,|)(,5k段允许决策集合为：Dk(sQ Uk 0乞山乞s设Vk(Sk，Uk)为第k年度的产量，则Vk =8Uk 5(s - Uk)5故指标函数为：V,5=：Z Vk(sk,Uk)k幺令最优值函数fk(Sk)表示由资源量Sk出发，从第k年开始到第5年结束时所生产的产品的总产量最 大值。因而有逆推关系式：f6( s6 = 0fk(sk) = ma8Uk 5(sk -Uk) - fk0.7Uk 0.9(sk

15、-Uk) b|uk Dk(sk)k =1,2,3, 4,5从第5年度开始，向前逆推计算。当k=5时，有：f5(s0 = max &5 5(S5 -U5) f6 l-0.7u5 0.9($ -比)b0应5童5max ：8u5 5(s5 -u55)f0勺5浜因是U5的线性单调增函数，故得最大解U5*，相应的有：当k=4时，有:f4(s4)max ：8u4 5(s4-u4)f5 0.7u4 0.9(s4-u4) I?0虫4全4max 78u4 5(s4 - u4) 8 l.0.7u4 - 0.9(s4 -u4) .1?0空4空4max 713.6u4 - 12.2(s -u4)/0空4空4max d

16、.4u412.2s4 /0空4空4故得最大解，u4*=s4 ,相应的有f 4( s4) =13.6s4依此类推，可求得u； = % 相应的 f3(s3 17.5s3u；=0,相应的 f2(s220.8s,u；=0,相应的 ($)=；3.7$-因 s1=1000 ,故：人佝)=23700计算结果表明：最优策略为u； =0,u2 =0,u； =s；,u4 =S4,u； =S5即前两年应把年初全部完好机器投入低负荷生产，后三年应把年初全部完好机器投入高负荷生产。这样所得的产量最高，其最高产量为23700台。在得到整个问题的最优指标函数值和最优策略后，还需反过来确定每年年初的状态，即从始端向终端递推计

17、算出每年年初完好机器数。已知s；=1000台，于是可得：s2 = 0.7u； 0.9($ - u；) =0.9s； = 900(台)s = 0.7u2 0.2(s2 -氏)=0.9S2 = 810(台)s4 -0.7u； 0.9(s； -U；) = 0.7s； =567(台)s5 =0.7u4 0.9(s4 - u4) = 0.7s4 = 397(台)s6 =0.7比 0.9$ -比)=0.7s5 = 278(台)8、有一辆最大货运量为10t的卡车，用以装载3种货物，每种货物的单位重量及相应单位价值如表4-20所示。应如何装载可使总价值最大？表4- 2货物编号i123单位重量 （t）345单位

18、价值ci456解：建模设三种物品各装Xi,X2, X3件max（4x 5x2 6x3）3x4x2 5x3 _10Xj _0,Xj l,j =1,2,3利用动态规划的逆序解法求此问题。$ =c, D,s） =人 |0 兰Xi “52 = 3 - Xi, D2（S2） =X2 I 0 _ X2 - S2状态转移方程为：53 =S2 X2,D3（S3）=X30 乞 X3 乞 SsSk 1 = Tk（ Sk, xj = Sk- Xk, k= 3, 2,1该题是三阶段决策过程，故可假想存在第四个阶段，而X4=0,于是动态规划的基本方程为：fk（Sk）XkK （ Sk ）k k 卅 k 出f4 （S4）=

19、 0k =3,f3（S3）二 max 、6x3 /X3 ,1,辰/5k =2,f2（S2）= maxs 5X2f3（S3）X2 =0,1,川，吟二 max 5x2f3（S2 4x2）x2 =0,1,1，|,子k =1,fi（s）= max4xi +f2（q）xi y,i，2,3=max 4 x1 f2（3 -3xJXi 卫,1,2,3计算最终结果为xi = 2, X2 =1,X3 = 0 ,最大价值为13 。9、设有A, B, C三部机器串联生产某种产品，由于工艺技术问题，产品常出现次品。统计结 果表明，机器A，B，C产生次品的概率分别为 Pa=30%, Pb=40%, Pc=20%,而产品必

20、须经过三部机 器顺序加工才能完成。为了降低产品的次品率，决定拨款5万元进行技术改造，以便最大限度地提 高产品的成品率指标。现提出如下四种改进方案：方案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，即第一

21、阶段计算给 机器C拨款的效果。设s为第k阶段剩余款,则边界条件为s3=5 ;设xk为第k阶段的拨款额；状态转移方程为sk-1 =sk-xk ；目标函数为 max R=(1- Pa)(1-Pb)(1-PC)仍采用反向递推第一阶段：对机器C拨款的效果Rl(si，xi)=di(si，xi)Ro(so，xo)= di(si，xi)、S10123X1*R1(S1, X1*)00.800.810.80.910.920.80.90.91,20.930.80.90.90.9430.9440.80.90.90.9430.9450.80.90.90.9430.94第二阶段：对机器B, C拨款的效果由于机器A最多只需3万元，故s2