建立优化模型专题练习题.docx

《建立优化模型专题练习题.docx》由会员分享，可在线阅读，更多相关《建立优化模型专题练习题.docx（39页珍藏版）》请在课桌文档上搜索。

1、练习题一1、建立优化模型应考虑哪些要素？答：决策变量、目标函数和约束条件。2、讨论优化模型最优解的存在性、迭代算法的收敛性及停止准则。min/(x)答：针对一般优化模型s.gj(x)0,i=l,2,m,讨论解的可行域。，若存在一点7(x)=OJ=1,pXO,对于VXO均有/(X*)/(X)则称X为优化模型最优解，最优解存在；迭代算法的收敛性是指迭代所得到的序列X,X,，(Q,满足“(*D)(%,则迭代法收敛；收敛的停止准则制产D卜 ,ft+-,(I)-“叫ji+2j210s.l.,2y1+3y2+5y318yvy29y30*2、研究线性规划的对偶理论和方法(包括对偶规划模型形式、对偶理论和对偶

2、单纯形法)。答：略。3、用单纯形法求解下列线性规划问题:min(1)s.,Z = X - 工2 + x3 Xj + X2 2与2 2x + 工2 + V 3 . 7+X34工,孙13 (2)min z = 4- X2 + 3x1 - 2x2 + X3 =2X2 2工3 += 2s.t.X? + X3 + X5 = 5xi0 = l,2,5)解：（1）引入松弛变量X4,心，X6minz=xi-x2+x3+0*x4+0*x5+0*x6X1+X2-2工3+.V4=2s.”2x,+x2+x3+x5=3-Jd+x3+6=4xl,x2,x3,x5,x60CL1-11OO0Cb基bXlX2X3XAXSX6O

3、Xi21I-21OOOxs3211O10OX64-101OO1Cj-Zj1-11OOO因检验数20,故确定X2为换入非基变量，以X2的系数列的正分量对应去除常数列，最小比值所在行对应的基变量X4作为换出的基变量。CL1-11OO0Cb基bxX4X3X4XSX6-1Xl211-21O0OXS11O网-110OXG4-IO1OO1CJ-ZJ2O-11O0因检验数G30,表明已求得最优解：X*=(O,83,l3,O,O,ll3),去除添加的松弛变量,原问题的最优解为：X*=(O,83,l3)o(2)根据题意选取XI,X4,minz=4-x2+Mx-2x2+工3=2%22x-+2s,t.%2+工3+工

4、5=5xi0(i=l,2,5)X5,为基变量：Cj0-1100CB基。XlX2X3X4XS0Xi20Xi20X551-210001-21001101Q-ZjO-IlOO因检验数O20最小，故确定X2为换入非基变量，以X2的系数列的正分量对应去除常数列，最小比值所在行对应的基变量X4作为换出的基变量。Cj0-1100Cb基bxX2X3XAX50Xi6I0320-1Xl201-2100XS3003.I1CJ-ZJ00-110因检验数G30,表明已求得最优解：X*=(9,4J,0,0)o4、分别用大M法、两阶段法和MatIab软件求解下列线性规划问题:minz=4%+X2maxZ=IOXI+152+

5、123x+x2=35x1+32+x39(1)l9rl+3x26.(2),5x+6-2+15x315WnC-CSTX+2%2W32x+%2+X3N5X,20X1,%2，r3解：(1)大M法根据题意约束条件1和2可以合并为1,引入松弛变量X3,X4,构造新问题。minz=4x1+x2+Mx3+0*x43x1x2+x3=35.f.0,表明已求得最优解：X*=(3/5,6/5).Matlab调用代码：f=4;l;A=l-9,-3U,2;b=-6;3;Aeq=3,l;beq=3;lb=O;O;x,fval=IinPrOg(f,A,b,Aeq,beq,lb)输出结果：Optimizationtermina

6、ted.X=0.60001.2000fval=3.6000(2)大M法引入松弛变量X4,X6,乃构造新问题。maxZ=IOX+15x2+12x3+Ox4+Ox5+Ox6-Mx15x1+3x2+x4=9-5x1+6x2+15+x5=152xl+x2+x3-x6+x7=5x1,x70单纯形表计算略；当所有非基变量为负数，人工变量5=05所以原问题无可行解。请同学们自己求解。Matlab调用代码：f=-10;-15;-12;A=5,3,l；-5,6,15;-2,-l,-l;b=9;15;-5;lb=0;0;0;x=linrog(f,A,b,lb)输出结果：原题无可行解。5、用内点法和Matlab软件

7、求解下列线性规划问题：minz=2x+打3x+2x2+2x3=6s.(2x+2=5和孙巧之。解：用内点法的过程自己书写，参考答案：最优解X=437/30；最优值5Matlab调用代码：Aeq=1,2,221,0;beq=6;5;lb=O;O;O;x,fval=linprog(f,Aeq,beq,lb)输出结果：Optimizationterminated.x=1.33332.33330.0000fval=5.00006、用分支定界法求解下列问题：max z - 7x1 + 9x2一x 312 4 6s.tA7 Xj + x2 35X, 2 0且X为整数maxz=5x+8x2x+X2V6(1)5

8、./5%+9x245；Xl,%20且均为整数解：(1)调用matlab编译程序bbmelhodf=-5;-8;G=l1;59;h=6;45x,y=bbmethod(f,Gh,0;0,l;i,l)x=33y=-39最优解33；最优值39(2)调用matlab编译程序bbm&hodf=-7;-9;G=-13;7l;h=6;35x,y=bbmethod(f,G,h,0;0,l;0,l)x=50y=-35最优解50；最优值357、用隐枚举法和Matlab软件求解下列问题:(1)min Z = 4x + 3肛 + 2xS.t.2x1 - 5x2 + 3叼-44x + X2 + 3町-3M + 43 Nl

9、Xz=O或 1(/= 1,2,3)max z = 3x + 2x2 - 5与 - 2x4 + 3心Xj + X? + %3 + 214 + 15 W 47x 3叼4a?4 + 3为5 8Il X 6工2 + 314 3有之 1Xj = 0或1 CZ = 1,2,5)(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)(0,0,1,0,0).(1,1

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

11、b=4;8;-1;x,fval=bintprog(f,A,b,);%不等式约束右端常数向量力%调用函数bintprog。注意两个空数组的占位作用。输出结果X=最优值5。8、某地区有A、B、C三个化肥厂，供应本地甲、乙、丙、丁四个产粮区。已知各化肥厂可供应化肥的数量和各产粮区对化肥的需要量，以及各厂到各区每吨化肥的运价如表2-28所示。试制定一个使总运费最少的化肥调拨方案。表2-1运价/粮化肥厂甲乙丙T各厂供应量/万吨Ai58737A2491078A384293各区需要量/万吨6633解：设A、B、C三个化肥厂为Ai、A2、A3,甲、乙、丙、丁四个产粮区为Bi、B2、B3、B4;CU为由Ai运化

12、肥至Bj的运价，单位是元/吨；殉为由Ai运往Bj的化肥数量(i=l,23j=l,2,3,4)单位是吨；Z表示总运费，单位为元，依题意问题的数学模型为:34minz=c/=17=1x11+x21+x31=6.V+工22+尢32=6+x23+=3S,t.12611O3524323351687、24322528,M=40J681512;行约简(2106(0)、f21090126Ii0列约简12680+IZO11UN01132I，(0)110*2所画O0元素少于nC八r标号I8074J(8(0)44,(n=4),未得到最优解，需要继续变换矩阵(求能覆盖所有O元素的最少数直线集合)：(2106(V)12

13、68()(0)110ZQ/八、A4_I8(0)44J未被直线覆盖的最小元素为Cij=2,在未被直线覆盖处减去2,在直线交叉处加上2。(084OA(O)840*、10460标号,TK1046(0)004011(0)411IZ18046；100得最优解：:010，使总利润为最大的分配任务方案为：11,24,33,42此时总利润W=35+40+32+32=139练习题三1、用0.618法求解问题min(t)=t3-2t-r0的近似最优解，已知夕的单谷区间为0,3,要求最后区间精度=0.5。答：t=0.8115;最小值-0.0886.(调用golds.”】函数)2、求无约束非线性规划问题minf(xl

14、,x2,x3)=xj2+4.+xj-2xi的最优解解一：由极值存在的必要条件求出稳定点：=2x1-2,)=1令搜索方向d=-W()=再从x()出发，沿d方向作一维寻解一：目标函数/3的梯度Wa) =bf(x) 3(%)*2)1 + 4x1 + 2x2-1 2x + 2x211优，令步长变量为4,最优步长为4,则有X+4=+故/()=/(X(s+4d)=(-4)-+2(-)2+2(-)+2=2-2=,(2)ol一11一令例(4)=2l-2=0可得4=1X=X+4=0+=求出X点之后,与上类似地，进行第二次迭代：v,(x)=令d=-(X)=1令步长变量为2,最优步长为4,则有X+2d=故/(x)=

15、F(X+)=(2-1)-(2+1)+2(-I)2+2(4-1)(2+1)+(2+1)2=52-2-1=2()令/(团=1042=0可得=X=X+;l2d=1+1n2WXX)=02此时所达到的精度Iw(X)|卜0.2828本题最优解X*=j5,/(X*)=-1,25解二：利用matlab程序求解首先建立目标函数及其梯度函数的M文件functionf=fun(x)f=x(1)-x(2)+2*x(1)*x(1)+2*x(1)*x(2)+x(2)*x(2);functiong=gfun(x)g=1+4*x(1)+2*x(2),-1+2*x(1)+2*x(2);调用grad.m文件x0=0,0;x,va

16、l,k=grad(fun,gfun,x)结果x=-1.0000,1.5000val=-1.2500k=33即迭代33次的到最优解x=-1.0000,1.5000；最优值val=-1.2500o4、试用Newton法求解第3题。解一：计算目标函数的梯度和HeSSe阵目标函数/(X)的梯度VnX)=a(不)1+4x12x2行()1+2X2x2V2(X)=42I=G,其逆矩阵为G05_22J-0.51X=X(。)G-Iw(X0)=0,0_5l,-l=-l,L5r计算历(X)|卜0。本题最优解X=；,/(X*)=-1,25解二：除了第3题建立两个M文件外，还需建立HeSSe矩阵的M文件利用matlab

17、程序求解首先建立目标函数及其梯度函数的M文件functionf=fun(x)f=x(1)-x(2)+2*x(1)*x(1)+2*x(1)*x(2)+x(2)*x(2);functiong=gfun(x)g=1+4*x(1)+2*x(2),-1+2*x(1)+2*x(2);functionh=hess(x)g=42;22;调用newton.m文件XO=O,O;x,val,k=11ewton(,fun,gfun,hess,xO)结果x=-1.0000,1.5000val=-1.2500k=l5、用Fleiche，ReeyeS法求解问题min/(X)=x12+25其中X=(xpx2),要求选取初始点

18、X0=(2,2)t,6=IO-6O解一:/(x) = -(x1,x2)0 5 G =2 00 50r = Vf() = (2x1,50x2)7.第一次迭代：令PO=F=(-4,-IoO)丁,Hro(4,100)；00PJGPO 4,700)-41500 50-100即，Xt = Xcaopo=(1.92,O)r第二次迭代:4=(3.84,0) BO= t p rr p (-3.846,-0.15)|尼2000，0(3.84,0)4 r(Xj = j =Pl GPl (-3.846,-0.15)3.84 0 F0 50-3.846-0.150.4802X=X +% Pi = (0.0732,-0

19、.072)7第三次迭代：弓=(0.1464,-3.6)7(建议同学们自己做下去，注意判别限e)解二：利用matlab程序求解首先建立目标函数及其梯度函数的M文件function f=fun(x)f=x(l)2+25* x(2)*x(2);function g=gfun(x)g=2*x(l), 50* x(2);调用frcg.m文件x=2,2 ;epsilon= 1 e-6;x,val,k=frcg(fun,gfun,x,epsilon)结果x=1.0e-006*l0.2651,0.0088val=7.2182e-014k=616、试用外点法(二次罚函数方法)求解非线性规划问题min/(X)=(

20、3-2)2+工；s.t.g(X)=x2-l0其中X=(x“2)R2解：设计罚函数尸(XM)=/(X)+M*g(X)八2采用MaHab编程计算，结果x=10;最优结果为1(调用Waidianfa.m)7、用内点法(内点障碍罚函数法)求解非线性规划问题：min(玉+1)3+x2ts.t.x1-10x20解：容易看出此问题最优解为X=U0；最优值为8.给出罚函数为P(x,r)=(xl+1)3+x2+r(l/(x,-l)lx2)令理22一J=。；2=-4=oX1(X1-I)2X2从而当r0+时，x(r)=n=x(建议同学自己编程序计算)8、用乘子法求解下列问题min/(X)=X：+x；1(X)=xl+

21、x2-2=0解：建立乘子法的增广目标函数:x,)=x12+j-内+a:2-2)+y(xl+x2-2)2人(xy,OAn:=2xi-Z+(xl+x2-2)=0X1w(x,九,)3zc、八=2x,-Z+Cr(XIX2-2)=0X解上述关于X的二元一次方程组得到稳定点2b+4-2+2x=2（+,-2+2.当乘子4取2时，或发参数。趋于无穷时，得到H=1=x*即最优解。1（建议同学自己编程序计算）练习题四1、石油输送管道铺设最优方案的选择问题：考察网络图4-6,设A为出发地，F为目的地，B,C,D,E分别为四个必须建立油泵加压站的地区。图中的线段表示管道可铺设的位置，线段旁的数字表示铺设这些管线所需的

22、费用。问如何铺设管道才能使总费用最小？解：第五阶段：El-F4；E2F3；第四阶段：Dl-El-F7；D2E2F5；D3El-F5；第三阶段：Cl-Dl-El-F12；C2D2E2F10；C3D2E2F8；C4-D3El-F9；第二阶段：Bl-C2D2E2F13；B2C3D2E2F15；第一阶段：A-B1C2D2E2F17；最优解：A-B1C2D2E2F最优值：172、用动态规划方法求解非线性规划max/(幻=喜+人+嘉xl+x2+x3=27x1,x2,x30解：=9,w=9,X3=9,最优值为9。3、用动态规划方法求解非线性规划maxZ=7x；+6x1+5考s.l.x1+2x2IOxl-3x

23、29xpx2O解：用顺序算法阶段：分成两个阶段，且阶段1、2分别对应不声。决策变量：,2状态变量：吗分别为第，阶段第一、第二约束条件可供分配的右段数值。(v1,vv1)=max7x12+6x1=min7vjz+6v1,7m?6wiOx0.rlhiX=minv1,w1,(v2,w2)=max5xJ+f(y1-2x2,w2+3x2).0x25=max5x?+min7(v2-2x2)2+6(v2-2x2),7(w2+3x2)2+6(w2+3x2)Og45由于彩=10,W2=9,于;(v2,w2)=*(10,9)=maxmin33x；-292x2+760,68x；+396x2+621可解的=9.6,w

24、=02,最优值为702.92。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个销售点，根据市场部门估计，在不同地区设置不同数量的销售点每月可得到的利润如表4-19所示。试问在各地区如何设置销售点可使每月总利润最大。表4-1地区销售点01234101625303220121721223010141617解：将问题分为3个阶段，k=T,2,3；决策变量

25、勺表示分配给第k个地区的销售点数；状态变量为sk表示分配给第k个至第3个地区的销售点总数；状态转移方程：sk+skxk9其中”二4；允许决策集合：Dk(SP=间OWqwSP阶段指标函数：gjXk)表示。个销售点分配给第Z个地区所获得的利润；最优指标函数(Sk)表示将数量为Sk的销售点分配给第k个至第3个地区所得到的最大利润，动态规划基本方程为：)=躁期(小加)=3,2,1力)=。=3时，5)=maxg3(M)Ij=i3g3(x3)力($3)x3*O1234OOOO110101214142316163417174后2时，(52)=max(x2)+(-x)0x2g2(2)+f3(s2x2)上G2)

26、X2*O1234OOOO10+1012+012120+1412+1017+022130+1612141710210272401712+1617+142110220312,341时，/(M)=maxg()+八(SI-M)，/(51)=maxg1(x1)+(4-)Ox15lOxl4修。1)力SLl)X(SI)x1*O123440+31162725+2230+1232+0472最优解为：x1*=2,x2*=l,3*=l,1(4)=47,即在第1个地区设置2个销售点，第2个地区设置1个销售点，第3个地区设置1个销售点，每月可获利润47。6、设某厂计划全年生产某种产品Ao其四个季度的订货量分别为600公

27、斤，700公斤，500公斤和1200公斤。已知生产产品A的生产费用与产品的平方成正比，系数为0.005。厂内有仓库可存放产品，存储费为每公斤每季度1元。求最佳的生产安排使年总成本最小。解：四个季度为四个阶段，采用阶段编号与季度顺序一致。设Sk为第季初的库存量，则边界条件为51=55=0设Xk为第季的生产量，设yk为第季的订货量；q,4,yk都取实数，状态转移方程为sk+i=sk+xk-yk仍采用反向递推，但注意阶段编号是正向的目标函数为:4j(X)=minV(0.005xj2+si)用多用，白M第一步：(第四季度)总效果启(s4K4)=05口2+%由边界条件有：$5=$4+工4-)4=0，解得

28、：工4*=1200-54将“*代入为($4，工4)得：必*($4尸0005(1200-S4)2+s4=7200-11,40.00554第二步：(第三、四季度)总效果(533)=0.005x32+53+74*(4)将$4=$3+3-500代入力($3白)得：f3(s3,xi)=0.005xj+53+7200-1l(x3+s3-500)+O.OO5(X3+*500)2=0.0lX3+0.0lx353-16&+0.005s；-15s313950纸(七)=002七+0.0k3-16=0xi解得石=800-0.5*,代入外邑，七)得小工)=7550-753+0.0025s；第三步：(第二、三、四季度)总

29、效果力62小2)二605X22+52+*(y3)将$3=$2+工2-700代入力(S2，工2)得：f2(s2,x2)=0.005x2+s2+7550-7(/+52-700)+0.0025*2+%-700)2=0.015x2+0.005(52-700)-7=0解得xJ=700-(13)2,代入以电,)得*(52)=l0000-Gs2+(0.005/3)学第四步：(第一、二、三、四季度)总效果力(SLI)=O.005xi2+51+力*g)将52=5I+1-600=X-600代入j(SlUl)得：j(s1,x1)=O.OO5x12+51+10000-6(x1-600)+(0.0053)(x1-600

30、)2Cx)=(0.043)x1-8=0xx解得x；=600,代入/；(51,%)得f；(s2)=USOO由此回溯：得最优生产-库存方案XI*=600,52*=0;冗2*=700,53*=O;x3*=8OO,54*=3(X);工4*=900。7、某种机器可在高低两种不同的负荷下进行生产。设机器在高负荷下生产的产量函数为g=8如，其中如为投入生产的机器数量，年完好率近0.7；在低负荷下生产的产量函数为F5y,其中y为投入生产的机器数量，年完好率为尻0.9。假定开始生产时完好机器的数量S产1000。试问每年如何安排机器在高、低负荷下的生产，使在5年内生产的产品总产量最高。解：构造这个问题的动态规划模

31、型：设阶段序数k表示年度。状态变量sk为第k年度初拥有的完好机器数量，同时也是第k-1年度末时的完好机器数量。决策变量uk为第k年度中分配高负荷下生产的机器数量，于是sk-uk为该年度中分配在低负荷下生产的机器数量。这里Sk和Uk均取连续变量，它们的非整数值可以这样理解，如Sk=O6就表示一台机器在k年度中正常工作时间只占6/10；uk=0.3,就表示一台机器在该年度只有3/10的时间能在高负荷下工作。状态转移方程为：SN=叫+砥-以)=07%+0.9(-以)，Z=1,2,5k段允许决策集合为：2)=以0%4设以)为第k年度的产量，则为=8%+5(与-以)故指标函数为：Vlt5=Yvk(Sk9

32、Uk)JM令最优值函数fk(sQ表示由资源量Sk出发，从第k年开始到第5年结束时所生产的产品的总产量最大值。因而有逆推关系式：X(56)=)=三xSuk+5(sk-uk)+10.7wjt+0.9(.-以)Z=1,2,3,4,5从第5年度开始，向前逆推计算。当k=5时,有:5(55-w5)+0.7w50.9(.*-)maxOm555=maxOm558m5+5(55-i55)3u5+5s5因f5是U5的线性单调增函数，故得最大解K*,相应的有:当k=4时，有：f4(s4)=max84+5(%-%)+07%+09(n-w4)=jnax8w4+5(s4-m4)+80.7m4+0.9(%-114)=jn

33、ax13.6m4+12.2(54-w4)=max(1.4wd+2.2s0m4v4lJ故得最大解，*=S4,相应的有l(54)=13.654依此类推，可求得“；=,%,相应的人(%)=17.5$3；=0,相应的人($2)=20.8$2；=0,相应的-G)=23.7*因Sl=IoO0,故：G）=23700计算结果表明：最优策略为=0,W*=0,；=S3，；=54,w5=s5即前两年应把年初全部完好机器投入低负荷生产，后三年应把年初全部完好机器投入高负荷生产。这样所得的产量最高，其最高产量为23700台。在得到整个问题的最优指标函数值和最优策略后，还需反过来确定每年年初的状态，即从始端向终端递推计算

34、出每年年初完好机器数。已知Sl=100O台，于是可得：G=0.7：+0.9（5,-）=0.9Sl=900（台）$3=0.7”；+0.2（%-=0.9电=810（台）54=0.7；+0.9（邑-；）=0.753=567（台）$5=0.7w*+0.9（54-w*）=0.754=397（台）$6=0.7；+0.9（%-）=OJs5=278（台）8、有一辆最大货运量为IOt的卡车，用以装载3种货物，每种货物的单位重量及相应单位价值如表4-20所示。应如何装载可使总价值最大？表4-2货物编号iI23单位重量（t）345单位价值Ci456解：建模设三种物品各装,与，七件max(4x1+5x2+6x3)3xl+4x2+5x310/NO,Xj7,=1,2,3利用动态规划的逆序解法求此问题。Si=c,D1(51)=x11