最优化方法练习题答案.docx
练习题一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)<£，练习题二1、某公司看中了例2.1中厂家所拥有的3种资源Ri、R2、和R3,欲出价收购(可能用于生产附加值更高的产品)。如果你是该公司的决策者，对这3种资源的收购报价是多少？(该问题称为例2.1的对偶问题)。解：确定决策变量对3种资源报价,%，为作为本问题的决策变量。确定目标函数问题的目标很清楚一一“收购价最小二确定约束条件资源的报价至少应该高于原生产产品的利润，这样原厂家才可能卖。因此有如下线性规划问题：minw=170>f1+1OOj2+150y3*2、研究线性规划的对偶理论和方法(包括对偶规划模型形式、对偶理论和对偶单纯形法)。答：略。3、用单纯形法求解以下线性规划问题：Z = X-X2 +X3Aj ÷ %2 2冷22町 +12 +冗3 43 ；(2)z = 4-X2 ÷ x3×2 - 2x3 + 工4 =2%2 + ×3+= 5Xj0=l,2,5)解：(1)引入松弛变量X4,X5,X6CL1-11000CB基bXlX2XyXlX5X60X4211-2100OX532110100X64-101001Cf-Zj1-11000因检验数。2<0,故确定X2为换入非基变量，以X2的系数列的正分量对应去除常数列最小比值所在行对应的基变量X4作为换出的基变量。CL1-11000CB基bXlX4X3XlXSX6-12211-21000XS110-1100X64-101001Cj-Zj20-1100因检验数O3<0,故确定X3为换入非基变量，以X3的系数列的正分量对应去除常数列最小比值所在行对应的基变量X5作为换出的基变量。CjT1-11000CB基XiXlX5X4X5X6-I-V28/35/3101/32/301X31/31/301-1/31/300X611/3-4/3001/3-1/31G;7/3032/31/30因检验数5>0,说明已求得最优解: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因检验数G2<0最小，故确定X2为换入非基变量，以及的系数列的正分量对应去除常数列，最小比值所在行对应的基变量g作为换出的基变量。，一*0-1100CB基。XlXlXyX4X5OXi610-320-IA"2201-210Oxs3OO.11CfZjOO-ll因检验数。3<0最小，故确定X3为换入非基变量，以即的系数列的正分量对应去除常数列，最小比值所在行对应的基变量X5作为换出的基变量。O-11OOCb基bXlX2XyX4XSOXl91OO11-1X24O1O1/32/31X3IOO1-1/31/3CfZjOOO2/31/3因检验数j>O,说明已求得最优解：X*=(9,4,1,0,0)。min z = 4x + x24、分别用大M法、两阶段法和Matlab软件求解以下线性规划问题:maxz=1Ox1+15x2÷12x33b+= 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/3OOX42O15/3-1/31Cj-ZjO-1/3M-4/3O4Xl3/51O2/5-1/51X26/5O1-1/53/5Cj-ZjOOM-7/51/5因检验数5>0,说明已求得最优解：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,所以原问题无可行解。请同学们自己求解。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.00(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最优解50；最优值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)分别带入到约束条件中，可以得到：原问题的最优解是(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=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½)化肥厂甲乙丙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、求
