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

整理文档很辛苦,赏杯茶钱您下走!

免费阅读已结束,点击下载阅读编辑剩下 ...

阅读已结束,您可以下载文档离线阅读编辑

资源描述

练习题一1、建立优化模型应考虑哪些要素?答:决策变量、目标函数和约束条件。2、讨论优化模型最优解的存在性、迭代算法的收敛性及停止准则。答:针对一般优化模型min()..0,1,2,0,1,,ijfxstgximhxjp,讨论解的可行域D,若存在一点*XD,对于XD均有*()()fXfX则称*X为优化模型最优解,最优解存在;迭代算法的收敛性是指迭代所得到的序列(1)(2)(),,,KXXX,满足(1)()()()KKfXfX,则迭代法收敛;收敛的停止准则有(1)()kkxx,(1)()()kkkxxx,(1)()kkfxfx,(1)()()kkkfxfxfx,()kfx等等。练习题二1、某公司看中了例2.1中厂家所拥有的3种资源R1、R2、和R3,欲出价收购(可能用于生产附加值更高的产品)。如果你是该公司的决策者,对这3种资源的收购报价是多少?(该问题称为例2.1的对偶问题)。解:确定决策变量对3种资源报价123,,yyy作为本问题的决策变量。确定目标函数问题的目标很清楚——“收购价最小”。确定约束条件资源的报价至少应该高于原生产产品的利润,这样原厂家才可能卖。因此有如下线性规划问题:123min170100150wyyy1231231235210..23518,,0yyystyyyyyy*2、研究线性规划的对偶理论和方法(包括对偶规划模型形式、对偶理论和对偶单纯形法)。答:略。3、用单纯形法求解下列线性规划问题:(1)0,,43222..min32131321321321xxxxxxxxxxxtsxxxz;(2))5,,2,1(052222..4min53243232132ixxxxxxxxxxtsxxzi解:(1)引入松弛变量x4,x5,x6123456min0*0*0*zxxxxxx12341232=225=3..136=41,2,3,4,5,60xxxxxxxxstxxxxxxxxxcj→1-11000CB基bx1x2x3x4x5x60x421[1]-21000x532110100x64-101001cj-zj1-11000因检验数σ20,故确定x2为换入非基变量,以x2的系数列的正分量对应去除常数列,最小比值所在行对应的基变量x4作为换出的基变量。cj→1-11000CB基bx1x4x3x4x5x6-1x2211-21000x5110[3]-1100x64-101001cj-zj20-1100因检验数σ30,故确定x3为换入非基变量,以x3的系数列的正分量对应去除常数列,最小比值所在行对应的基变量x5作为换出的基变量。cj→1-11000CB基bx1x2x5x4x5x6-1x28/35/3101/32/301x31/31/301-1/31/300x611/3-4/3001/3-1/31cj-zj7/3032/31/30因检验数σj0,表明已求得最优解:*(0,8/3,1/3,0,0,11/3)X,去除添加的松弛变量,原问题的最优解为:*(0,8/3,1/3)X。(2)根据题意选取x1,x4,x5,为基变量:)5,,2,1(052222..4min53243232132ixxxxxxxxxxtsxxzicj→0-1100CB基bx1x2x3x4x50x121-21000x420[1]-2100x5501101cj-zj0-1100因检验数σ20最小,故确定x2为换入非基变量,以x2的系数列的正分量对应去除常数列,最小比值所在行对应的基变量x4作为换出的基变量。cj→0-1100CB基bx1x2x3x4x50x1610-320-1x2201-2100x5300[3]-11cj-zj00-110因检验数σ30最小,故确定x3为换入非基变量,以x1的系数列的正分量对应去除常数列,最小比值所在行对应的基变量x5作为换出的基变量。cj→0-1100CB基bx1x2x3x4x50x1910011-1x240101/32/31x31001-1/31/3cj-zj0002/31/3因检验数σj0,表明已求得最优解:*(9,4,1,0,0)X。4、分别用大M法、两阶段法和Matlab软件求解下列线性规划问题:(1)0,3263933..4min2121212121xxxxxxxxtsxxz;(2)0,,52151565935..121510max321321321321321xxxxxxxxxxxxtsxxxz解:(1)大M法根据题意约束条件1和2可以合并为1,引入松弛变量x3,x4,构造新问题。1234minz=4x+x+Mx+0*x1231241433..23,0xxxstxxxxxcj→41M0CB基bx1x2x3x4Mx33[3]1100x431201cj-zj4-3M1-M004x1111/31/300x420[5/3]-1/31cj-zj0-1/3M-4/304x13/5102/5-1/51x26/501-1/53/5cj-zj00M-7/51/5因检验数σj0,表明已求得最优解:*(3/5,6/5)X。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)输出结果:Optimizationterminated.x=0.60001.2000fval=3.6000(2)大M法引入松弛变量x4,x5,x6,x7构造新问题。1234567max101512000zxxxxxxMx123412351236717539561515..25,,0xxxxxxxxstxxxxxxx单纯形表计算略;当所有非基变量为负数,人工变量7x=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软件求解下列线性规划问题:0,,52622..2min32121321321xxxxxxxxtsxxxz解:用内点法的过程自己书写,参考答案:最优解[4/37/30]X;最优值5Matlab调用代码: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)输出结果:Optimizationterminated.x=1.33332.33330.0000fval=5.00006、用分支定界法求解下列问题:(1)且均为整数0,45956..85max21212121xxxxxxtsxxz;(2)为整数且1212121210,35763..97maxxxxxxxxtsxxz解:(1)调用matlab编译程序bbmethodf=[-5;-8];G=[11;59];h=[6;45][x,y]=bbmethod(f,G,h,[],[],[0;0],[],[1;1],1)x=33y=-39最优解[33];最优值39(2)调用matlab编译程序bbmethodf=[-7;-9];G=[-13;71];h=[6;35][x,y]=bbmethod(f,G,h,[],[],[0;0],[],[1;0],1)x=50y=-35最优解[50];最优值357、用隐枚举法和Matlab软件求解下列问题:(1))3,2,1(1013344352..234min32321321321jxxxxxxxxxtsxxxzj或;(2))5,,2,1(101336118343742..32523max542154315432154321jxxxxxxxxxxxxxxtsxxxxxzj或解:隐枚举法:(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];%不等式约束右端常数向量b[x,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];%不等式约束右端常数向量b[x,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表示总运费,单位为元,依题意问题的数学模型为:3411minijijijzcx112131122232132333142434111213142122232431323334663..3787xxxxxxxxxstxxxxxxxxxxxxxxx该题可以用单纯形法或matlab自带工具箱命令(linprog)求解。*9、求解下列不平衡运输问题(各数据表中,方框内的数字为单位价格ijc,框外右侧的一列数为各发点的供应量ia,框底下一行数是各收点的需求量jb):(1)51710要求收点3的需求必须正好满足。6468032515752050(2)51020要求收点1的需求必须由发点4供应。32410752159601551015解答略。10、一公司经理要分派4位推销员去4个地区推销某种商品。推销员各有不同的经验和能力,因而他们在不同地区能获得的利润不同,其获利估计值如表2-29所示。公司经理应怎样分派才使总利润最大?表2-2地区推销员1234135272837228342940335243233424322528解:用求极大值的“匈牙利法”求解。效率矩阵表示为:

1 / 11
下载文档,编辑使用

©2015-2020 m.777doc.com 三七文档.

备案号:鲁ICP备2024069028号-1 客服联系 QQ:2149211541

×
保存成功