最优化方法练习题答案

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

2、(K)，则迭代法收敛；收敛的停止准则有 x(k 1) x(k)练习题二1、某公司看中了例中厂家所拥有的 3种资源 R1、R2、和 R3，欲出价收购(可能用于 生产附加值更高的产品) 。如果你是该公司的决策者， 对这 3 种资源的收购报价是多少？ (该问题称为例的对偶问题) 。解：确定决策变量 确定目标函数 确定约束条件对 3 种资源报价 y1, y2, y3 作为本问题的决策变量。 问题的目标很清楚“收购价最小” 。 资源的报价至少应该高于原生产产品的利润，这样原厂家才可能因此有如下线性规划问题： min w 170 y1 100 y2 150 y35y1 2 y2 y3 10s.t. 2 y

3、1 3y2 5 y3 18y1, y2, y3 0*2、研究线性规划的对偶理论和方法(包括对偶规划模型形式、对偶理论和对偶单 纯形法)。答：略。3、用单纯形法求解下列线性规划问题：（1）；（2）解：（1）引入松弛变量 x4，x5， x6minzx1x2x30* x40* x5 0* x6x1x22x3x4=2s.t2x1x2x3x5=3x1x3x6=4x1,x2, x3, x4, x5, x6 0cj1-11000CB基 bx1x2x3x4x5x60x4211-21000x532110100x64-101001cj -zj1-11000因检验数 20，故确定 x2为换入非基变量，以 x2的系数

4、列的正分量对应去除常数 列，最小比值所在行对应的基变量 x4 作为换出的基变量。cj1-11000CB基 bx1x4x3x4x5x6-1x2211-21000x51103-1100x64-101001cj -zj20-1100因检验数 30，表明已求得最优解： X* （0,8/ 3,1/ 3,0,0,11/ 3） ，去除添加的松弛 变量，原问题的最优解为： X* （0,8 / 3,1/ 3）2）根据题意选取 x1，x4， x5，为基变量：cj 0-1100CB基bx1x2x3x4x50x121-21000x4 201-2100x5501101cj-zj0-1100因检验数 20 最小，故确定

5、x2 为换入非基变量，以x2的系数列的正分量对应去除常数列，最小比值所在行对应的基变量x4 作为换出的基变量。cj 0-1100CB基bx1x2x3x4x50x1610-320-1x2 201-2100x53003-11cj-zj00-110因检验数 30，表明已求得最优解： X* （9, 4,1,0,0） 。4、分别用大法、两阶段法和 Matlab 软件求解下列线性规划问题：（1）；（2）解：（1）大 M法根据题意约束条件 1和 2可以合并为 1，引入松弛变量 x3，x4，构造新问题min z=4x 1+x 2 +Mx 3+0*x 43x1x2 x3s.t x1 2x2x4 3x1,L x4

6、 0cj 41M0CB基 bx1x2x3x4Mx3331100 x4 31201cj- zj4-3M1-M004x1111/31/300 x4 205/3-1/31cj- zj0-1/3M -4/304x1 3/5102/5-1/51x2 6/501-1/53/5cj- zj00M-7/51/5因检验数 j 0，表明已求得最优解： X* (3/ 5,6 /5)Matlab 调用代码：f=4;1;A=-9,-3;1,2;b=-6;3;Aeq=3,1;beq=3;lb=0;0;x,fval = linprog(f,A,b,Aeq,beq,lb) 输出结果：Optimization terminat

7、ed.fval =(2)大 M法引入松弛变量 x4，x5，x6，x7 构造新问题。max z 10x1 15x2 12x3 0x4 0x5 0x6 Mx7s.t5x13x2x3x45x1 6x2 15x3x5152x1x2x3x6 x7 5x1,L ,x7 0单纯形表计算略；当所有非基变量为负数，人工变量 x7 =，所以原问题无可行解请同学们自己求解。Matlab 调用代码： f=-10;-15;-12;A=5,3,1;-5,6,15;-2,-1,-1;b=9;15;-5;lb=0;0;0;x = linprog(f,A,b,lb) 输出结果： 原题无可行解。5、用内点法和 Matlab 软件

8、求解下列线性规划问题：解：用内点法的过程自己书写，参考答案：最优解 X 4/3 7/3 0 ；最优值 5 Matlab 调用代码：f=2;1;1;Aeq=1,2,2;2,1,0;beq=6;5;lb=0;0;0;x,fval = linprog(f,Aeq,beq,lb)输出结果：Optimization terminated.fval =6、用分支定界法求解下列问题：（ 1） ；（2）解：（1）调用 matlab 编译程序 bbmethodf=-5; -8;G=1 1;5 9;h=6; 45x,y=bbmethod（f,G,h,0;0,1;1,1）x =3 3y =-39最优解 3 3 ；最

9、优值 39 （2）调用matlab编译程序 bbmethodf=-7; -9;G=-1 3; 7 1;h=6; 35x,y=bbmethod（f,G,h,0;0,1;0,1）x =5 0y =-35最优解 5 0 ；最优值 357、用隐枚举法和 Matlab 软件求解下列问题：（1）；（2）解： 隐枚举法：（1）将（ 0，0，0）（0，0，1）（0，1，0）（1，0，0）（0，1，1）（1，0，1）（1， 1，0）（ 1， 1， 1）分别带入到约束条件中，可以得到：原问题的最优解是（ 0，0，1）， 目标函数最优值 2.（2）将（0，0，0，0，0）（0，0，0，0，1）（0，0，0，1，0）

10、（0，0，1，0，0）（ 1，1，1，1，1）分别带入到约束条件中，可以得到：原问题的最优解是（1，1，0，0，0），目标函数最优值 -5 。Matlab 软件求解：（1）调用代码：f=4; 3;2;A=2,-5,3;-4,-1,-3;0,-1,-1;b=4; -3;-1;x, fval=bintprog(f, A, b, );% 价值向量 f% 不等式约束系数矩阵 A， 中的分号“；” % 为行分隔符% 不等式约束右端常数向量 b%调用函数 bintprog 。注意两个空数组的占位作用。输出结果x=001 fval=2（2）调用代码：f=-3; -2;5;2;3;A=1,1,1,2,1; 7

11、,0,3,-4,3;-11,6,0,-3, 3;b=4; 8;-1;x, fval=bintprog(f, A, b, , );% 价值向量 f% 不等式约束系数矩阵 A， 中的分号“；” % 为行分隔 符% 不等式约束右端常数向量 b%调用函数 bintprog 。注意两个空数组的占位作用。输出结果x=11000fval=-5最优值 5。8、某地区有 A、B、C 三个化肥厂，供应本地甲、乙、丙、丁四个产粮区。已知各化肥厂可供应化肥的数量和各产粮区对化肥的需要量， 以及各厂到各区每吨化肥的运价 如表 2-28 所示。试制定一个使总运费最少的化肥调拨方案区 化肥厂A158737A2491078A

12、384293各区需要量 / 万吨6633解：设 A、B、C 三个化肥厂为 A1、A2、A3，甲、乙、丙、丁四个产粮区为 B1、B2、B3、B4；cij 为由Ai运化肥至 Bj的运价，单位是元 /吨； xij 为由Ai运往Bj的化肥数量 (i=1,2,3;j=1,2,3,4 )单位是吨；z 表示总运费，单位为元， 依题意问题的数学模型为：34min zi1 j 1cij xijx11x21x316x12x22x326x13x23x333s.t. x14x24x343x11x12x13x147x21x22x23x248x31x32x33x347该题可以用单纯形法或 matlab 自带工具箱命令(

13、linprog )求解。*9 、求解下列不平衡运输问题(各数据表中，方框内的数字为单位价格，框外右侧的一列数为各发点的供应量，框底下一行数是各收点的需求量) ：要求收点 3 的需求必须正好满足75 20 50要求收点 1 的需求必须由发点 4 供应5 10 15解答略。10、一公司经理要分派 4位推销员去 4 个地区推销某种商品。推销员各有不同的经 验和能力，因而他们在不同地区能获得的利润不同，其获利估计值如表 2-29 所示。公 司经理应怎样分派才使总利润最大？表 2- 2地区推销员1234135272837228342940335243233424322528解：用求极大值的“匈牙利法”求

14、解。效率矩阵表示为：35272837528342940MCij1235243233M=4052432252816221090126110列约简12(0)081103724标号8n4），未得到最优解，需要继续变换矩阵131236110行约简16878 15 12106(0)680*110*2 所画（） 0 元素 少于 n(0)44求能覆盖所有 0元素的最少数直线集合） ：(0) 0* 2442 1012 6 (0) 118 (0)未被直线覆盖的最小元素为 cij =2，在未被直线覆盖处减去 2，在直线交叉处加上 2(0)840084010460 标号1046(0)011040*11(0)4804

15、68(0)46100得最优解：0000010100100使总利润为最大的分配任务方案为：1 1， 24，3 3， 42 此时总利润 W=35+40+32+32=139练习题三1、用法求解问题min (t) t3 2t 1 t0的近似最优解，已知 (t)的单谷区间为 0,3 ，要求最后区间精度 0.5 答： t= ；最小值. (调用函数)2 、求无约束非线性规划问题min f (x1,x2,x3)=x12 4x22 x32 2x1 的最优解解一： 由极值存在的必要条件求出稳定点：2x1 2 ，8x2，2x3 ，则由得 x1 1，x20 ， x3 0x1 x2x3再用充分条件进行检验：2f 2 f

16、 2f2f 2 f2f2 2， 2 8 ， 22，0，0，0x1x2x3x1 x2x1 x3x2 x3200即20 8 0 为正定矩阵得极小点为 x* (1,0,0) T ，最优值为 -1。 002解二： 目标函数改写成minf(x1,x2,x3)=(x1 1)2 4x22x32 1易知最优解为( 1,0,0 )，最优值为 -1 。3、用最速下降法求解无约束非线性规划问题。min f (X) x1其中 X (x1,x2)T ，给定初始点 X0x2(0,0)T。2x12 2x1x22x2解一：目标函数 f (x) 的梯度f (x)f(x) (x1) f(x) (x2)1 4x11 2x12x22

17、x2f (X (0) )11 令搜索方向 d(1)11f (X(0)11再从 X (0)出发，沿 d(1) 方向作一维寻优，令步长变量为，最优步长为1，则有 X (0)d(1)故 f (x) f(X(0)d (1) ( )2( )22( )1( )令 1( ) 2 20 可得 1 1X (1) X(0)1d(1)求出 X(1) 点之后，与上类似地，进行第二次迭代：f(X (1) )令 d(2)f(X (1) )令步长变量为，最优步长为2，则有X(1)d(2)1111f(x)f(X (1)d(2) ) (1)1) 2(1)22(1)(1) (221)2 5 2 2 1 2( )令 2 () 10

18、2 0 可得X(2)X(1)2d(2)11510.81.2f (X (2) )0.20.2此时所达到的精度f (X(2) ) 0.28281本题最优解 X 1.15 ， f(X ) 1,25解二： 利用 matlab 程序求解 首先建立目标函数及其梯度函数的 M文件 function f=fun(x) f=x(1)-x(2)+2*x(1)*x(1)+2*x(1)*x(2)+x(2)*x(2); function g=gfun(x) g=1+4*x(1)+2*x(2),-1+2*x(1) +2* x(2) ; 调用文件 x0=0,0;x,val,k=grad(fun,gfun,x0) 结果 x=

19、 , val= k=33即迭代 33 次的到最优解 x= , ；最优值 val=4、试用 Newton 法求解第 3 题。解一： 计算目标函数的梯度和 Hesse阵目标函数f (x)f (x)的梯度 f (x)(x1)f (x)(x2)1 4x11 2x12x22x22f(X)24 22 G，其逆矩阵为 G0.50.50.51X(1)X (0) G 1f (X (0)0,0 T0.50.50.5 1, 1 T1,1.5 T计算 f (X (1) 0。1本题最优解 X ， f(X ) 1,251.5解二： 除了第 3 题建立两个 M文件外，还需建立 Hesse 矩阵的 M文件 利用 matlab

20、 程序求解首先建立目标函数及其梯度函数的 M文件 function f=fun(x) f=x(1)-x(2)+2*x(1)*x(1)+2*x(1)*x(2)+x(2)*x(2); function g=gfun(x) g=1+4*x(1)+2*x(2),-1+2*x(1) +2* x(2) ; function h=hess(x) g=4 2;2 2 ;调用文件x0=0,0;x,val,k=newton(fun,gfun,hess,x0) 结果x= ,val=k=15、用 Fletcher Reeves 法求解问题22 min f (X) x12 25x22其中X (x1,x2)T，要求选取初

21、始点 X0 (2,2)T, 10 6。解一：Q f(x)120 x120T( x1 ,x2),G0，rf (x) (2x1,50x2 )T212050 x250第一次迭代：令p0 r0( 4, 100)T ，T(4,100)r0 r010010p0TGp0 (2 0 4504, 100)0 50 100即，X (1) X(0)0 p0 (1.92,0) T第二次迭代：r1(3.84,0) T ，| r1 |2 3 ， p 0 2， p1r10 |r0 |2 2000 13.84T(3.84,0)r1 r1043.8460.150 p0 ( 3.846, 0.15)T20( 3.846, 0.1

22、5) 20 5001Tp1T Gp10.4802X (2) X (1)1 p1 (0.0732, 0.072) T第三次迭代：r2 ( 0.1464,3.6)T建议同学们自己做下去，注意判别）解二： 利用 matlab 程序求解首先建立目标函数及其梯度函数的 M文件function f=fun(x)f=x(1)2+25* x(2)*x(2);function g=gfun(x)g=2*x(1), 50* x(2) ;调用文件x0=2,2 ;epsilon=1e-6;x,val,k=frcg(fun,gfun,x0, epsilon)结果x = * , val =k = 616、试用外点法（二次

23、罚函数方法）求解非线性规划问题min f (X) (x1 2)2 x22s.t. g(X) x2 1 0其中 X (x1,x2) R2解：设计罚函数 P(x,M) f(X) M* g(X) 2 采用 Matlab 编程计算，结果 x=1 0 ；最优结果为 1。(调用)7、用内点法(内点障碍罚函数法)求解非线性规划问题：min (x1 1)3 x2s.t. x1 1 0 x2 0解：容易看出此问题最优解为 x=1 0 ；最优值为 8.给出罚函数为 P(x,r) (x1 1)3 x2 r (1/( x11)1/ x2)令 P(x,r)x13(x1 1)2 (x1 r1)2 0；P(xx2,r)2x

24、2从而当 r 0 时，x(r) (1r/3)1/2r建议同学自己编程序计算)min f(X)8、用乘子法求解下列问题h1(X) x12x1x22 x2 2解：建立乘子法的增广目标函数：(x, , ) x12(x1 x2 2) 2(x1 x2 2) 2令： (x, , )2x1x1(x1 x2 2) 0(x, , ) 2x2x1(x1 x2 2) 0解上述关于 x 的二元一次方程组得到稳定点222x2221当乘子 取 2时，或发参数 趋于无穷时，得到 x 1 x* 即最优解1建议同学自己编程序计算）练习题四1、石油输送管道铺设最优方案的选择问题：考察网络图4-6，设 A为出发地，F为目的地， B

25、，C，D，E分别为四个必须建立油泵加压站的地区。图中的线段表示管道可铺 设的位置，线段旁的数字表示铺设这些管线所需的费用。问如何铺设管道才能使总费用 最小？图 4- 1解：?第五阶段： E1F 4 ；E2 F 3 ；第四阶段： D1E1?F? 7；D2E2F ?5；D3E1F? 5；第三阶段： C1D1E1?F? ?12；C2D2E2F? 10；C3D2E2F? ?8；C4D3 E1F ?9 ；第二阶段： B1C2D2E2F? ?13； B2C3D2E2F? 15； ?第一阶段： A B1C2D2 E2F? 17 ；最优解： AB1C2D2E2F?最优值： 172、用动态规划方法求解非线性规划

26、解： x1 9,x2 9,x3 9 ，最优值为 9。3、用动态规划方法求解非线性规划解：用顺序算法 阶段：分成两个阶段，且阶段 1 、2 分别对应 x1,x2 。决策变量：x1,x2状态变量：vi ,wi 分别为第 j阶段第一、第二约束条件可供分配的右段数值。*f1* (v1,w1)2 max7 x1 6x10 x1 w1min7 v1226v1,7 w1 6w1x1 min v1, w1f2* (v2,w2)max5 x220 x2 5max5 x220 x2 5f1* (v2 2x2,w2 3x2)22min7( v2 2x2)2 6(v2 2x2),7( w2 3x2)2 6(w2 3x

27、2 )由于 v2 10,w2 9 ，* 2 2f2 (v2,w2)f 2* (10,9) maxmin33 x22 292x2 760,68 x22 396x2 621可解的 x1 9.6, x2 0.2 ，最优值为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 个销售点，根据市场部门估计，在不同地

28、 区设置不同数量的销售点每月可得到的利润如表 4-19 所示。试问在各地区如何设置销 售点可使每月总利润最大。表 4- 1解：将问题分为 3 个阶段， k=1，2，3； 决策变量 xk 表示分配给第 k 个地区的销售点数；状态变量为 sk表示分配给第 k 个至第 3 个地区的销售点总数；状态转移方程：sk+1=skxk，其中 s1=4；允许决策集合：Dk(sk)=xk|0xksk阶段指标函数：gk（xk）表示 xk 个销售点分配给第 k 个地区所获得的利润；最优指标函数 fk（sk）表示将数量为 sk 的销售点分配给第 k个至第 3个地区所得到的最大利润，动态规划基本方程为：fk(sk) 0m

29、xaxs gk(xk) fk 1(sk xk)k 3,2,10 xk skf4(s4) 0 k=3 时， f3(s3) maxg3 ( x3 )x3 s3k=2时， f2 (s2) max g2( x2 ) f3(s2 x2)0 x2 s2k=1时，f1(s1)max g1(x1)0 x1 s1f2(s1 x1)， f1(s1) max g1( x1 ) f2(4 x1)0 x1 4最优解为：x1*=2，x2*=1，x3*=1，f1(4)=47，即在第 1 个地区设置 2 个销售点，第 2 个地区设置 1 个销售点，第 3 个地区设置 1 个销售点，每月可获利润 47。6、设某厂计划全年生产某

30、种产品 A。其四个季度的订货量分别为 600 公斤， 700公 斤，500 公斤和 1200 公斤。已知生产产品 A的生产费用与产品的平方成正比，系数为。 厂内有仓库可存放产品，存储费为每公斤每季度 1 元。求最佳的生产安排使年总成本最 小。解：四个季度为四个阶段，采用阶段编号与季度顺序一致。设 sk 为第 k 季初的库存量，则边界条件为 s1=s5=0设 xk 为第 k 季的生产量，设 yk 为第 k 季的订货量； sk ， xk ， yk 都取实数， 状态转移方程为 sk+1=sk+xk - yk 仍采用反向递推，但注意阶段编号是正向的目标函 数为：4f1(x) min(0.005 xi2

31、 si)x1,x2 ,x3,x4 i 1第一步： (第四季度 ) 总效果 f 4(s4, x4)= x42+s4由边界条件有： s5= s4 + x4 y4=0，解得： x4*=1200 s4将 x4*代入 f4(s4,x4)得：f4*( s4)=(1200 s4) 2+s4=7200 11 s4+ s42 第二步： (第三、四季度) 总效果 f3(s3,x3)= x32+s3+ f 4*( s4)将 s4= s3 + x3 500 代入 f 3(s3, x3) 得：2f3(s3,x3) 0.005 x32 s3 7200 11(x3 s3 500)0.005( x3 s3 500) 2220

32、.01x32 0.01 x3 s3 16x3 0.005s32 15s3 13950f3(s3,x3)x30.02 x3 0.01s3 16 0解得x3 800 0.5s3, 代入 f3(s3,x3)得2 f3 (s3) 7550 7s3 0.0025s32第三步： （ 第二、三、四季度 ） 总效果f 2( s2, x2)= x22+s2+ f 3*( s3)将 s3= s2 + x2 ?700 代入 f 2(s2, x2) 得：f2(s2,x2) 0.005x22 s2 7550 7(x2 s2 700)20.0025(x2 s2 700)2(s2,x2)x20.015x2 0.005(s2

33、 700) 7 0解得 x2 700 (1 3)s2, 代入f2(s2,x2)得 f2 (s2) 10000 6s2 (0.005 3)s22第四步： （第一、二、三、四季度 ） 总效果f 1( s1, x1)= x12+s1+ f 2*( s2)将 s2= s1 + x1 600= x1 600 代入 f1(s1,x1) 得：2f1(s1,x1) 0.005x12 s1 10000 6(x1 600) (0.005 3)(x1 600)2 f1(s1,x1) (0.04 3)x1 8 0 x1解得 x1 600, 代入f1 (s1, x1)得 f1 (s2) 11800由此回溯：得最优生产库

34、存方案x1*=600， s2*=0； x2*=700，s3*=0； x3*=800，s4*=300； x 4*=900。7、某种机器可在高低两种不同的负荷下进行生产。设机器在高负荷下生产的产量函数为 g=8u1，其中 u1 为投入生产的机器数量，年完好率 a=；在低负荷下生产的产量函 数为 h=5y，其中 y 为投入生产的机器数量，年完好率为 b=。假定开始生产时完好机器 的数量 s1=1000。试问每年如何安排机器在高、低负荷下的生产，使在5 年内生产的产 解： 构造这个问题的动态规划模型： 设阶段序数 k 表示年度。状态变量 sk 为第 k 年度初拥有的完好机器数量，同时也是第 k?1 年

35、度末时的完好机器 数量。决策变量 uk 为第 k 年度中分配高负荷下生产的机器数量，于是 sk?uk 为该年度中分配 在低负荷下生产的机器数量。这里 sk 和 uk 均取连续变量，它们的非整数值可以这样理解，如 sk=，就表示一台机器在 k 年度中正常工作时间只占6/10 ；uk=，就表示一台机器在该年度只有3/10 的时间能在高负荷下工作。状态转移方程为：sk 1 auk b(sk uk) 0.7uk 0.9(sk uk ), k 1,2,L ,5k 段允许决策集合为： Dk (sk ) uk 0 uk sk 设vk(sk,uk)为第 k 年度的产量，则 vk 8uk 5(sk uk)5故指

36、标函数为： V1,5vk(sk ,uk)k1令最优值函数 fk(sk)表示由资源量 sk 出发，从第 k年开始到第 5年结束时所生产的产 品的总产量最大值。因而有逆推关系式：f6(s6) 0fk(sk) ukmDak (xsk) 8uk 5(sk uk)fk 1 0.7uk 0.9( sk uk)k 1,2,3, 4,5从第 5 年度开始，向前逆推计算 当 k=5 时，有：f5(s5) max8u55(s5u5) f6 0.7u5 0.9(s5 u5)0 u5 s5max0 u5 s58u55(s5u55)max3u55s50 u5 s5因 f5 是 u5 的线性单调增函数，故得最大解 u5*

37、 ，相应的有：f5(s5) 8s5当 k=4 时，有：f4(s4) max 0 u4 s4max 0 u4 s4max 0 u4 s4max 0 u4 s4故得最大解， u4*=s4，相应的有8u4 5(s4 u4)f5 0.7u4 0.9(s4u4)8u4 5(s4 u4)8 0.7u4 0.9(s4u4)13.6u4 12.2(s4u4)1.4u4 12.2s4f4(s4) 13.6 s417.5s320.8s223.7s1依此类推，可求得u3* s3, 相应的 f3(s3) u2* 0, 相应的 f2(s2) u1* 0, 相应的 f1(s1)因 s1=1000，故： f1(s1) 23

38、700计算结果表明：最优策略为u1 0,u2 0,u3 s3,u4 s4,u5 s5即前两年应把年初全部完好机器投入低负荷生产， 后三年应把年初全部完好机器投入高 负荷生产。这样所得的产量最高，其最高产量为 23700 台。 在得到整个问题的最优指标函数值和最优策略后，还需反过来确定每年年初的状态，即8、有一辆最大货运量为从始端向终端递推计算出每年年初完好机器数。已知 s1=1000 台，于是可得：s20.7u1*0.9(s1u1*)0.9s1900(台)s30.7u2*0.2(s2*u2)0.9s2810(台)s40.7u*30.9(s3*u3)0.7s3567(台)s50.7u*40.9(

39、s4*u4*)0.7s4397(台)s60.7u*5 0.9(s5 u5* ) 0.7s5 278(台)10t 的卡车，用以装载 3 种货物，每种货物的单位重量及相应单位价值如表 4-20 所示。应如何装载可使总价值最大？表 4- 2货物编号 i123单位重量( t )345单位价值 ci456解： 建模设三种物品各装 x1,x2,x3件max(4 x1 5x2 6x3)3x1 4x2 5x3 10xj 0,xj I, j 1,2,3利用动态规划的逆序解法求此问题。s1c,D1(s1) x1 |0x1s1s2s1 x1,D2(s2)x2|0x2s3s2 x2,D3(s3)x3 |0x3状态转移

40、方程为：sk 1Tk (sk ,xk ) skxk,k3,2,1该题是三阶段决策过程，故可假想存在第四个阶段，而，于是动态规划的基本方程为：fk(sk) x mDa(xs ) xk, fk 1(sk 1),k 3,2,1xk DK(sk)f4(s4) 0k 3,f3(s3)max6x3x3 0,1,L ,s3 /53 k 2, f2(s2) maxs 5x2 f3 (s3 )x2 0,1,L ,s24maxs 5x2 f3(s2 4x2)x2 0,1,L , s2 4k 1,f1(s1) max 4x1 f2(s2)x1 0,1,2,3max 4x1 f2(s1 3x1) x1 0,1,2,3

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

42、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 拨款的效果。设 sk 为第 k 阶段剩余款，则边界条件为 s3=5；设 xk 为第 k 阶段的拨款额； 状态转移方程为 sk-1=sk-xk；目标函数为 max R=(1- PA)(1- PB)(1- PC)仍采用反向递推第一阶段 ：对机器 C 拨款

43、的效果R1( s1, x1)= d1( s1, x1)? R0( s0, x0)= d1( s1, x1)s 1x10123x1*R1 (s1, x 1*)001121, 2334353第二阶段 ：对机器 B, C 拨款的效果由于机器 A 最多只需 3 万元，故 s2 ? 2递推公式：2(s2, x2)= d2( s2, x2)?R1( s1, x1*)例： R2(3,2)= d2(3,2)? R1(1,1)= ?=sx1s 1x1*R1 (s1, x 1*)001121, 2334353得第二阶段最优决策表s 2x2s 20123x2*R2( s2, x 2*)2232,34353第三阶段

44、：对机器 A, B, C 拨款的效果边界条件： s3 = 5递推公式：R 3(s3, x3)= d3( s3, x3)? R2( s2, x2*)例： R3(5,3)= d3(5,3)? R2(2,2)= ?=得第三阶段最优决策表I ： x3=1, x2=3, x1=1, R3= ? ?=II ：x3=2, x2=2, x1=1, R3= ?=III ： x3=2, x2=3, x1=0, R3= ?=练习题五1、考察多目标规划问题 其中，试画出个目标函数的图形，并求出，这里是的最优解集 解：2、用线性加权法中的法求解下述多目标规划问题 。解： min f1(x) 4x1 6x2最优解为 x

45、(1) =0 0 T；max f2(x) 3x1 3x2最优解为 x(2) =3 2 T；利用 法得线性方程组：1 *0 2 *01 *24 2 *15解得唯一加权系数 0.3846,0.6154原多目标规划加权后min F(x) 0.3846 f1(x) 0.6154 f2(x)解得加权后的最优解为： x =4 0 T ，最优值为3、用线性加权求和法求解下述多目标规划问题，取。 解：将问题转化为一个新的单目标规划问题。Matlabminv(F(x) 0.6( x1 3x2) 0.4(2 x1 x2) 约束条件同上，该问题转化为线性规划问题，可用单纯形法求解，也可用 命令求解 (求解过程略)。

46、解得加权后的最优解为： x =0 1 T ，最优值为。4、用平方和加权法求解多目标规划问题：其中 ，。解：不难看出两个目标函数下界均为 0，得平方和加权法后的新目标规划问题：1 2 2 2min F(x) x1 x233利用 matlab 程序求解 首先建立目标函数及其梯度函数的 M文件 function f=fun(x)f=1/3*x(1)2+2/3* x(2)*x(2);x,fval=fmincon( f ,0 0,1 -1;1 1,4;8,0 0) 解得最优解为： x =0 0 T ，最优值为 0。5、用极小极大法和 Matlab 软件求解下述多目标规划问题。解：取评价函数为 v(F(x) max(x1 3)2 x22 , x12 (x2 2)2 ，再求i min v(F ( x) minmax( x1 3)2 x22 , x12 (x2 2)2DiMatlab 软件求解： 编制 M文件 function f=mnmax(x) f(1)=(x(