《最优化方法练习题答案.docx》由会员分享，可在线阅读，更多相关《最优化方法练习题答案.docx（28页珍藏版）》请在三一办公上搜索。
1、练习题一1、建立优化模型应考虑哪些要素？答：决策变量、目标函数和约束条件。2、讨论优化模型最优解的存在性、迭代算法的收敛性及停止准那么。minf(x)答：针对一般优化模型W.gj(x)0,i=l,2,m1讨论解的可行域。，假设存在一点y(x)=O,y=l,pX*O,对于VX。均有/(X*)f(X)那么称X*为优化模型最优解，最优解存在；迭代算法的收敛性是指迭代所得到的序列X,X,(K).,满足/(gD)f(K),那么迭代法收敛;收敛的停止准那么有卜MrRk,HH/H，(X(Z)f1+1OOj2+150y3*2、研究线性规划的对偶理论和方法(包括对偶规划模型形式、对偶理论和对偶单纯形法)。答：略
2、。3、用单纯形法求解以下线性规划问题：Z = X-X2 +X3Aj %2 2冷22町 +12 +冗3 43 ；(2)z = 4-X2 x32 - 2x3 + 工4 =2%2 + 3+= 5Xj0=l,2,5)解：(1)引入松弛变量X4,X5,X6CL1-11000CB基bXlX2XyXlX5X60X4211-2100OX532110100X64-101001Cf-Zj1-11000因检验数。20,故确定X2为换入非基变量，以X2的系数列的正分量对应去除常数列最小比值所在行对应的基变量X4作为换出的基变量。CL1-11000CB基bXlX4X3XlXSX6-12211-21000XS110-11
3、00X64-101001Cj-Zj20-1100因检验数O30,说明已求得最优解:X*=(0,8/3,1/3,0,0,11/3),去除添加的松弛变量,原问题的最优解为：X*=(),8/3,1/3)o(2)根据题意选取力，X4,X5,为基变量:CL0-1100Cb基bXlXlX3X4X50Xi21-21000X420Hl-2100XS501101Cj-Zj0-1100因检验数G20最小，故确定X2为换入非基变量，以及的系数列的正分量对应去除常数列，最小比值所在行对应的基变量g作为换出的基变量。，一*0-1100CB基。XlXlXyX4X5OXi610-320-IA2201-210Oxs3OO.1
4、1CfZjOO-ll因检验数。3O,说明已求得最优解：X*=(9,4,1,0,0)。min z = 4x + x24、分别用大M法、两阶段法和Matlab软件求解以下线性规划问题:maxz=1Ox1+15x212x33b+= 39x1 +32 6 ；Xj + 2x2 3x,%2 SJ/5x + 3x2 + 工3 W 95x + 62 + 15工3 W152x + v3 2 5X,%X3 解：(1)大M法根据题意约束条件1和2可以合并为1,引入松弛变量X3,X4,构造新问题。CjT41MOCb基bxX2X3X4MX33311OOX43I2OICJ-Zj4-3MI-MOO4Xl111/31/3OO
5、X42O15/3-1/31Cj-ZjO-1/3M-4/3O4Xl3/51O2/5-1/51X26/5O1-1/53/5Cj-ZjOOM-7/51/5因检验数50,说明已求得最优解：X*=(3/5,6/5)0Matlab调用代码：f=4；l；A=-9r3U,2;b=-6;3;Aeq=3,l;beq=3;lb=O;O;x,fval=linprog(f,A,b,Aeq,beq,lb)输出结果：Optimizationterminated,x=0.60001.2000fval=3.6000(2)大M法引入松弛变量X4,x5,X6,切构造新问题。单纯形表计算略；当所有非基变量为负数，人工变量占=0.5,
6、所以原问题无可行解。请同学们自己求解。Matlab调用代码：f=-10;-15;-12;A=5,3,l；-5,6,15;-2,-l,-U；b=9;15;-5;lb=0;0;0;X=linprog(f,A,b,lb)输出结果：原题无可行解。5、用内点法和MaUab软件求解以下线性规划问题：解：用内点法的过程自己书写，参考答案：最优解X=437/30；最优值5Matlab调用代码：f=2;l;l;Aeq=U,2,2;2,0;beq=6;5;lb=O;O;O;x,fval=linprog(f,Aeq,beq,lb)输出结果：Optimizationterminated.1.33332.33330.0
7、0(X)fval=5.00006、用分支定界法求解以下问题:max Z = 7x + 9电-x + 32 6s.t.1 7町 + X2 35x, X2 N。且R为整数maxz=5jq+8町町+冷K6s.“5x+9%245x2且均为整数解：(1)调用matlab编译程序bbmethodf=-5;-8;G=11;59;h=6;45x,y=bbmethod(f,Qh,0;0,l;l,l)x=33y=-39最优解33；最优值39(2)调用matlab编译程序bbmelhodf=-7;-9;G=-13;7l;h=6;35lx,y=bbmethod(f,G,h,l,lO;0,l;0,1)y=-35最优解5
8、0；最优值357、用隐枚举法和MatIab软件求解以下问题:min z = 4x + 3x2 + 2x31 1 ) S.f.v2x 52 + 3工3 44x1 + x2 3必 3 了2 +与NIXj =O或 1(/= 1,2,3)max z = 3x + 2x2 - 5与 一 2必 + 3巧X1 + X2 x3 2工4 + r5 K 47x + 3叼414 + 3町85. ,1 lx - 62 + 34 3和 N 1xy =0Wcl( = 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
9、)分别带入到约束条件中，可以得到：原问题的最优解是(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,1,1,1)分别带入到约束条件中，可以得到：原问题的最优解是(1,1,0,0,0),目标函数最优值5。Matlab软件求解：(1)调用代码:f=4;3;2;A=2,-5t3;-4,-I,-3;0,-1,-1;b=4;x,fval=bintprog(f,A,b,);%价值向量/%不等式约束系数矩阵A,中的分号“：”为行分隔符%不等式约束右端常数向量%调用函数bintprog。注意两个空数组的占位作用。输出结果X
10、=001fval=2调用代码:f=-3;-2;5;2;3;%价值向量fA=1,1,1,2,1；7A3,-4,3;-11,6,0,-3,3:%不等式约束系数矩阵A,中的分号“：%为行分隔符b=4;8;-1;x,fval=bintprog(f,A,b,);%不等式约束右端常数向量b%调用函数biniprog。注意两个空数组的占位作用。输出结果X=110Ofval=最优值5。8、某地区有A、B、C三个化肥厂，供给本地甲、乙、丙、丁四个产粮区。各化肥厂可供给化肥的数量和各产粮区对化肥的需要量，以及各厂到各区每吨化肥的运价如表2-28所示。试制定一个使总运费最少的化肥调拨方案。表2-1运价/弋粮7cV)
11、化肥厂甲乙丙T各厂供给量/万吨Ai58737A2491078A384293各区需要量/万吨6633解：设A、B、C三个化肥厂为Ai、A2、A3,甲、乙、丙、丁四个产粮区为Bi、B2、B3、B4;Cij为由Ai运化肥至Bj的运价，单位是元/吨；刈为由Ai运往Bj的化肥数量(i=l,23j=l,2,3,4)单位是吨；Z表示总运费，单位为元，依题意问题的数学模型为：该题可以用单纯形法或matlab自带工具箱命令(Iinprog)求解。*9、求解以下不平衡运输问题(各数据表中，方框内的数字为单位价格框外右侧的一列数为各发点的供给量勺，框底下一行数是各收点的需求量%)：要求收点3的需求必须正好满足。要求
12、收点1的需求必须由发点4供给。解答略。10、一公司经理要分派4位推销员去4个地区推销某种商品。推销员各有不同的经验和能力，因而他们在不同地区能获得的利润不同，其获利估计值如表2-29所示。公司经理应怎样分派才使总利润最大？表2-2区推磊、1234135272837228342940335243233424322528解：用求极大值的“匈牙利法”求解。效率矩阵表示为：35272837W7-123)283429401MYiO行约简E=O35243233J87、24322528八1(,M91512,(2106(0f21090、12611O2三8O1132(L2O748fc441/）、*所画（）。元素
13、少于n（n=4）,未得到h最优解，需要继续变换矩阵（求能覆盖所有O元素的最少数直线集合）：未被直线覆盖的最小元素为Cij=2,在未被直线覆盖处减去2,在直线交叉处加上2。得最优解:标号使总利润为最大的分配任务方案为:If1,2-4,3-*3,42此时总利润W=35+40+32+32=139练习题三1、用0.618法求解问题的近似最优解，伊的单谷区间为0,3,要求最后区间精度=0.5。答：t=0.8115;最小值-0.0886.(调用golds.m函数)2、求无约束非线性规划问题min/(x1,x2,3)=(2+4x?+x1-2xl的最优解解一：由极值存在的必要条件求出稳定点：=2xl2,旦=8
14、x,=2x3,那么由*(x)=0得X=1,x2=0,xj=0xix2x3再用充分条件进行检验：工2,空=8,江=2,旦=0,红=0,旦二0dx；X2Mxix2xlx3x2xi200、即力f=080为正定矩阵得极小点为X*=(l,0,0)1最优值为1。1002)解二：目标函数改写成min/(x1,x2,x3)=(x1-I)2+4xj+考-1易知最优解为(1,0,0),最优值为1。3、用最速下降法求解无约束非线性规划问题。其中x=,s)7,给定初始点=(0,0)定f()解一:目标函数/的梯度Vf(X)=犷=：竽2：qf(x)1-1+2+2工2d*2)_W(Xw)=P令搜索方向d=-W(X(O)=口
15、再从()出发，沿d方向作一维寻优,11o-l-11-令步长变量为,最优步长为4,那么有X()+Zd=+2=01故/()=/(X+4d=0+1=j求出X点之后，与上类似地，进行第二次迭代：WXXa)=T令户=_(X)=111令步长变量为X,最优步长为4,那么有故f(x)=/(X+Ad)=(-l)-(+l)+2(2-l)2+2(2-1)(2+1)+(2+1)2=52-2-1=2()令%(；I)=I(U一2=0可得&=X+3=1+1J=nO-Vf(x(2)=02此时所到达的精度IW(X)|卜0.2828此题最优解X*=,/(X*)=-1,25解二：利用matlab程序求解首先建立目标函数及其梯度函数
16、的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文件x=l,;x,vaLk=grad(,fun,gfun,xO)结果x=-1.0000,1.5000val=-1.2500k=33即迭代33次的到最优解x=-1.0000,1.5000；最优值VaI=-1.2500。4、试用NewfaI法求解第3题。解一：计算目标函数的梯度和HeSSe阵目标函数/(x)的梯度Wa)5()婀)f()1+4x1+Ix
17、2-12x2V(X)=G,其逆矩阵为GT=0.5-0.5-0.51计算Iw(X)=o此题最优解.=,/(X*) = -1,25解二：除了第3题建立两个M文件外，还需建立HeSSe矩阵的M文件利用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);functionh=hess(x)g=K2;22;调用newton.in文件x0=0,0;x,val,k=newton(f
18、un,gfun,hess,xO)结果x=-1.0000,1.50001val=-1.2500k=l5、用FIaCher-HeeyeS法求解问题其中X=(xpx2)r，要求选取初始点X0=(2,2)7m=K)Fo解一:,.1 f(x) = (xl9x2)0 5 G =2 00 50r = V(x) = (2x1 ,50x2 ) .第一次迭代：令PO=F=(-4,-100)即，X=X+0Po=(1.92,0)7第二次迭代：(二(3.84,0)7,用=叫二急，PLF+4%=(3.846,-0.15)tIl石Il2000第三次迭代：&=(0.1464,-3.6尸(建议同学们自己做下去，注意判别限g)解
19、二：利用matlab程序求解首先建立目标函数及其梯度函数的M文件functionf=fun(x)f=x(l)2+25*x(2)*x(2);functiong=gfun(x)g=2*x(l),50*x(2);调用frcg.m文件x=2,21,;epsilon=le-6;x,val=frcg(fun,gfun,xO,epsilon)结果x=1.0e-006*0.2651,0.0088val=7.2182e-014k=616、试用外点法(二次罚函数方法)求解非线性规划问题min/(X)=(x1-2)2+x1s.t.g(X)x2-10其中X=(%,%)wR2解：设计罚函数P(x,)=(X)+*(X)J
20、2采用MaHab编程计算,结果x=10;最优结果为1。(调用Waidianfa.m)7、用内点法(内点障碍罚函数法)求解非线性规划问题：解：容易看出此问题最优解为X=H0；最优值为8.给出罚函数为P(x,r)=(x1+1)3+x2+r(l/(x1-1)+1/X2)令2=3(%+l)2-=();2=i-4=oX(XI-I)X2X2从而当r(时，x(r)=1+J3),z21、(建议同学自己编程序计算)min/(X)=x12+x18、用乘子法求解以下问题,，二八IZi（八）=x1-Vx2-Z=O解：建立乘子法的增广目标函数：令：Zl=2T+b+x2-2)=0明解上述关于X的二元一次方程组得到稳定点当
21、乘子X取2时，或发参数趋于无穷时，得到了=1=x*即最优解。1(建议同学自己编程序计算)练习题四1、石油输送管道铺设最优方案的选择问题：考察网络图46,设A为出发地，F为目的地，B,C,D,E分别为四个必须建立油泵加压站的地区。图中的线段表示管道可铺设的位置，线段旁的数字表示铺设这些管线所需的费用。问如何铺设管道才能使总费用最小？图4-1解：第五阶段：El-F4；E2F3；第四阶段：Dl-El-F7；D2E2F5；D3ElF5；第三阶段：Cl-Dl-ElF12；C2D2E2F1O；C3D2E2F8；C4D3ElF9；第二阶段：B1C2D2E2Fl3；B2C3D2E2F15；第一阶段：A-B1C
22、2D2E2F17；最优解：A-Bl-C2D2E2F最优值：172、用动态规划方法求解非线性规划解：x1=9,x2=9,X3=9,最优值为9。3、用动态规划方法求解非线性规划解：用顺序算法阶段：分成两个阶段，且阶段1、2分别对应为“2。决策变量：XpX2状态变量：吗分别为第/阶段第一、第二约束条件可供分配的右段数值。由于%=10,卬2=9，(v2,W2)=(10,9)=maxmin33x?-292xo760,68x+396x2+621)0x25可解的3=9.6,=0.2,最优值为702.92。4、设四个城市之间的公路网如图4-7o两点连线旁的数字表示两地间的距离。使用迭代法求各地到城市4的最短路
23、线及相应的最短距离。图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解：将问题分为3个阶段，k=l,2,3；决策变量xk表示分配给第k个地区的销售点数；状态变量为sk表示分配给第k个至第3个地区的销售点总数；状态转移方程：s%+=%q,其中S=4;允许决策集合：Dk(%)=州IOWqWSJ阶段指标函数：gk(q)表示q个销售点分
24、配给第忆个地区所获得的利润；最优指标函数(Sk)表示将数量为4的销售点分配给第&个至第3个地区所得到的最大利润，动态规划根本方程为：:3时，力5)=maxg3(x3)F62时，)=m2(x2)-)时，/(M)=maxg(x)+A(S玉),工()=maxg(x)+,(4玉)0xMSl0.v14*=szp相应的有依此类推，可求得因Sl=1000,故：/GI)=23700计算结果说明：最优策略为即前两年应把年初全部完好机器投入低负荷生产，后三年应把年初全部完好机器投入高负荷生产。这样所得的产量最高，其最高产量为23700台。在得到整个问题的最优指标函数值和最优策略后，还需反过来确定每年年初的状态，即
25、从始端向终端递推计算出每年年初完好机器数。SI=100O台，于是可得：8、有一辆最大货运量为IOt的卡车，用以装载3种货物，每种货物的单位重量及相应单位价值如表4-20所示。应如何装载可使总价值最大？表4-2货物编号i123单位重量(t)345单位价值Ci456解：建模设三种物品各装冷号七件利用动态规划的逆序解法求此问题。状态转移方程为：+=(.,/)=4-七/=3,2该题是三阶段决策过程，故可假想存在第四个阶段，而儿=0,于是动态规划的根本方程为:计算最终结果为工；=2,石=1,石=0,最大价值为13o9、设有A,B,C三部机器串联生产某种产品，由于工艺技术问题，产品常出现次品。统计结果说明
26、，机器A,B,C产生次品的概率分别为pa=30%,Pb=40%,Pc=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%问如何配置拨款才能使串联系统的可靠性最大？解：为
27、三台机器分配改造拨款，设拨款顺序为A,B,C,阶段序号反向编号为k,即第一阶段计算给机器C拨款的效果。设Sk为第k阶段剩余款，那么边界条件为53=5；设Xk为第k阶段的拨款额；状态转移方程为ShI=Sk-X女；目标函数为maxR=(1-PA)(I-PB)(I-PC)仍采用反向递推第一阶段：对机器C拨款的效果Rl(SIul)二4(s口I)XRo(SOHo)=d(s9x)XSI0123Xi*RIGi,x*)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第二阶段：
28、对机器B,C拨款的效果由于机器A最多只需3万元，故522递推公式：2($242)=2(5242)XRl(SIRI*)例：R2(3,2)=d2(3,2)xR1(1,1)=(1-0.2)0.9=0.72得第二阶段最优决策表Sl.11*RI(Sl9Xl*)000.8110.921,20.9330.94430.94530.94S20123X2*R2(S2,X2*)20.540.630.6420.6430.5640.630.720.72230.7240.5640.6580.720.8130.8150.5640.6580.7520.8130.81第三阶段：对机器A,B,C拨款的效果边界条件：$3=5递推公
29、式:R3(s33)=d3(s343)xR2(s2K2*)例：(5,3)=d3(5,3)Q,2)=(1 0.05) 0.64=0.608Sl1：x3=l,2=3,町=1,/?3=0.80.90.9=0.648II：x3=2,也=2,町=1,/?3=0.90.80.9=0.648III：町=2,%2=3,X=0,/?3=0.90.90.8=0.648练习题五1、考察多目标规划问题X+2,2X1图形，并求出其中工(X)=X2/)=1,l2R,R”RmRPa,R“p，这里凡是min工(x)的最优解集。1l-2x4解：2、用线性加权法中的法求解下述多目标规划问题minj(x)=4x,+6x2maxf2(
30、x)=3x1+3x2。2x1+4x214s.t.6xl+3x224xl,x2O解：min/(X)=4%+65最优解为X=【00；max6(X)=3玉+3%最优解为X=32:利用。法得线性方程组：解得唯一加权系数4=3846,0.6154F原多目标规划加权后解得加权后的最优解为：x*=4Of,最优值为J.23123、用线性加权求和法求解下述多目标规划问题，取4=064=0.4。解：将问题转化为一个新的单目标规划问题。约束条件同上，该问题转化为线性规划问题，可用单纯形法求解，也可用Mauab命令求解(求解过程略)。解得加权后的最优解为：x*=0IJt,最优值为-1.4。4、用平方和加权法求解多目标
31、规划问题：xl-x24其中工(X)=玉，Z)：x1x28,l=-,2=Ox1,2033解：不难看出两个目标函数下界均为0,得平方和加权法后的新目标规划问题：利用matlab程序求解首先建立目标函数及其梯度函数的M文件functionf=fun(x)f=l3*x(l)2+23*x(2)*x(2);x,fval=fmincon(t,00,l-1;11,4;8,00)解得最优解为：x*=00,最优值为0。5、用极小极大法和Matlab软件求解下述多目标规划问题V-minF(x)=(xl-3)2+x；,x：+(x2-2)2)7Os.t.xl+x22解：取评价函数为M/(X)=max(再-3)2+X+(
32、2-2)2,再求iMatlab软件求解：编制M文件functionf=mnmax(x)f(l)=(x(l)-3)2+x(2)2;f(2)=x(l)2+(x(2)-2)2设初值x0=0;0;调用函数x,fval=fminimax(mnmax,xO,11,2)结果：X=1.30000.7000fval=3.38003.3800可得X*=11.3,0.7f；对应fi=f2=3.38从而X*=L3,0.7F为原问题的解。附习题中用过的Matlab程序1、bbmethodfunctionx,y=bbmethod(f,G,h,Geq,heq,lb,ub,x,id,options)%整数线性规划分支定界法，
33、可求解纯整数规划和混合整数规划。%y=minf,*xs.t.G*x=hGeq*x=heqX为全整数或混合整数列向量%用法%x,y=bbmethod(f,G,h,Geq,heq,lb,ub,x,id,options)%参数说明%lb:解的下界列向量(DefaulC-int)%ub:解的上界列向量(Defaultrint)%x：迭代初值列向量%id:整数变量指标列向量，1-整数，O-实数(DefaulCl)globalupperoptcxAbAeqbeqIDoptions;ifnargin10,options=optimset();options.Display-off;options.LargeScale=off;endifnargin9,id=ones(size(f);endifnargin8,x=；endifnargin7|isempty(ub),ub=inf*ones(size(f);endifnargin6IiSemPly(Ib)Jb=ZeroS(SiZe(f);endifnargin5,heq=jendifnargin4,Geq=;endupper=inf;c=f;A=G;b=h;Aeq=Geq;beq=heq;xO=x;ID=id;ftemp=IntLP(lb(:),ub(:);x=opt;y=upper;%下面是子函数functionftemp=IntLP(vlb,
