最优化-刘志斌-练习题一和二参考答案.doc

练习题一1、建立优化模型应考虑哪些要素?答：决策变量、目标函数和约束条件。2、讨论优化模型最优解的存在性、迭代算法的收敛性及停止准则。答：针对一般优化模型，讨论解的可行域，若存在一点，对于 均有则称为优化模型最优解，最优解存在；迭代算法的收敛性是指迭代所得到的序列 ，满足，则迭代法收敛；收敛的停止准则有，等等。 练习题二1、某公司看中了例2.1中厂家所拥有的3种资源R1、R2、和R3，欲出价收购（可能用于生产附加值更高的产品）。如果你是该公司的决策者，对这3种资源的收购报价是多少？（该问题称为例2.1的对偶问题）。解：确定决策变量 对3种资源报价作为本问题的决策变量。确定目标函数 问题的目标很清楚“收购价最小”。确定约束条件 资源的报价至少应该高于原生产产品的利润，这样原厂家才可能卖。因此有如下线性规划问题：*2、研究线性规划的对偶理论和方法（包括对偶规划模型形式、对偶理论和对偶单纯形法）。答：略。3、用单纯形法求解下列线性规划问题： （1）； （2）解：（1）引入松弛变量x4，x5，x6cj1-11000CB基bx1x2x3x4x5x60x4211-21000x532110100x64-101001cj-zj1-11000因检验数20，故确定x2为换入非基变量，以x2的系数列的正分量对应去除常数列，最小比值所在行对应的基变量x4作为换出的基变量。cj1-11000CB基bx1x4x3x4x5x6-1x2211-21000x51103-1100x64-101001cj-zj20-1100因检验数30，表明已求得最优解：，去除添加的松弛变量，原问题的最优解为：。（2）根据题意选取x1，x4，x5，为基变量：cj0-1100CB基bx1x2x3x4x50x121-21000x4201-2100x5501101cj-zj0-1100因检验数20最小，故确定x2为换入非基变量，以x2的系数列的正分量对应去除常数列，最小比值所在行对应的基变量x4作为换出的基变量。cj0-1100CB基bx1x2x3x4x50x1610-320-1x2201-2100x53003-11cj-zj00-110因检验数30，表明已求得最优解：。4、分别用大法、两阶段法和Matlab软件求解下列线性规划问题：（1）； （2）解：（1）大M法根据题意约束条件1和2可以合并为1，引入松弛变量x3，x4，构造新问题。cj41M0CB基bx1x2x3x4Mx3331100x431201cj-zj4-3M1-M004x1111/31/300x4205/3-1/31cj-zj0-1/3M -4/304x13/5102/5-1/51x26/501-1/53/5cj-zj00M-7/51/5因检验数j0，表明已求得最优解：。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 terminated.x = 0.6000 1.2000fval = 3.6000（2）大M法引入松弛变量x4，x5，x6，x7构造新问题。单纯形表计算略；当所有非基变量为负数，人工变量=0.5，所以原问题无可行解。请同学们自己求解。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软件求解下列线性规划问题： 解：用内点法的过程自己书写，参考答案：最优解；最优值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.x = 1.3333 2.3333 0.0000fval = 5.00006、用分支定界法求解下列问题： （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；最优值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）（0，0，1，0，0）. （1，1，1，1，1）分别带入到约束条件中，可以得到：原问题的最优解是（1，1，0，0，0），目标函数最优值-5。Matlab软件求解：（1）调用代码：f=4; 3;2;% 价值向量fA=2,-5,3; -4,-1,-3;0,-1,-1;% 不等式约束系数矩阵A， 中的分号“；”% 为行分隔符b=4; -3;-1;% 不等式约束右端常数向量bx, fval=bintprog(f, A, b, , );%调用函数bintprog。注意两个空数组的占位作用。输出结果 x=001fval=2（2）调用代码：f=-3; -2;5;2;3;% 价值向量fA=1,1,1,2,1; 7,0,3,-4,3;-11, 6,0,-3, 3;% 不等式约束系数矩阵A， 中的分号“；”% 为行分隔符b=4; 8;-1;% 不等式约束右端常数向量bx, fval=bintprog(f, A, b, , );%调用函数bintprog。注意两个空数组的占位作用。输出结果 x=11000fval=-5最优值5。8、某地区有A、B、C三个化肥厂，供应本地甲、乙、丙、丁四个产粮区。已知各化肥厂可供应化肥的数量和各产粮区对化肥的需要量，以及各厂到各区每吨化肥的运价如表2-28所示。试制定一个使总运费最少的化肥调拨方案。表2- 1运价/ 产粮 (元/吨) 区化肥厂甲乙丙丁各厂供应量/万吨A158737A2491078A384293各区需要量/万吨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表示总运费，单位为元，依题意问题的数学模型为：该题可以用单纯形法或matlab自带工具箱命令（linprog）求解。 *9、求解下列不平衡运输问题（各数据表中，方框内的数字为单位价格，框外右侧的一列数为各发点的供应量，框底下一行数是各收点的需求量）：（1） 5 1 7 10 要求收点3的需求必须正好满足。 6 4 6 80 3 2 5 15 75 20 50（2） 5 1 0 20 要求收点1的需求必须由发点4供应。 3 2 4 10 7 5 2 15 9 6 0 15 5 10 15解答略。10、一公司经理要分派4位推销员去4个地区推销某种商品。推销员各有不同的经验和能力，因而他们在不同地区能获得的利润不同，其获利估计值如表2-29所示。公司经理应怎样分派才使总利润最大？表2- 2 地区推销员1234135272837228342940335243233424322528解：用求极大值的“匈牙利法”求解。效率