重庆大学最优化方法习题答案.pdf

《重庆大学最优化方法习题答案.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、习题一1.1利用图解法求下列线性规划问题：（1）maxzx1x23x1x22s.t.x12x25x1,x20解：根据条件，可行域为下面图形中的阴影部分，，有图形可知，原问题在A点取得最优值，最优值z=5（2）minzx16x22x1x21s.t.x1x27x1,x20解：图中阴影部分表示可行域，由图可知原问题在点A处取得最优值，最优值z=-6.（3）maxz3x12x2x1x21s.t.x12x24x1,x20解：如图所示，可行域为图中阴影部分，易得原线

2、性规划问题为无界解。（4）minz2x15x2x12x26s.t.x1x22x1,x20解：由图可知该线性规划可行域为空，则原问题无可行解。1.2对下列线性规划问题，找出所有的基解，基可行解，并求出最优解和最优值。（1）minz5x12x23x36x4x12x23x34x47s.t.2x1x2x32x43x1,x2,x3,x40123解：易知x1的系数列向量p1，x2的系数列向量p2，x3的系数列向量p3，2114x4

3、的系数列向量p4。2x12x273x34x4①因为p1,p2线性无关，故有，令非基变量为x3x40，得2x1x23x32x41x13(1)111，所以得到一个基解x(,,0,0)是非基可行解；1133x23(2)21143②因为p1,p3线性无关，可得基解x(,0,,0)，z2；555(3)111③因为p1,p4线性无关，可得基解x(,0,0,)，是非基可行解；36(4)④因为p2,p3线性无关，可得基解x(0,2,1,0)，z41；⑤因为p2,p4线性相关，x

4、2,x4不能构成基变量；(6)⑥因为p3,p4线性无关，可得基解x(0,0,1,1)，z63；(2)(4)(6)(6)所以x,x,x是原问题的基可行解，x是最优解，最优值是z3。（2）maxzx1x22x3x4x5x1x2x3x41s.t.x12x2x54xi0,i1,2,3,4,511解：易知x1的系数列向量p1，x2的系数列向量p2，x3的系数列向量12110p，x的系数列向量p，x的系数列向量p。34455

5、001x1x21x3x4①因为p1,p2线性无关，故有，令非基变量为x3x4x50，得x12x24x52x13(1)25，所以得到一个基解x(,,0,0,0)，是非基可行解；533x23(2)②因为p1,p3线性无关，可得基解x(4,0,5,0,0)，是非基可行解；(3)③因为p1,p4线性无关，可得基解x(4,0,0,5,0)，是非基可行解；(4)④因为p1,p5线性无关，可得基解x(1,0,0,0,5)，z44；(5)⑤因为p2,p3线性相关，得基解x(

6、0,2,1.0,0)，是非基可行解；(6)⑥因为p2,p4线性无关，可得基解x(0,2,0,1,0)，是非基可行解；(7)⑦因为p2,p5线性无关，可得基解x(0,1,0,0,2)，z71；⑧因为p3,p4线性相关，x3,x4不能构成基变量；(9)⑨因为p3,p5线性无关，可得基解x(0,0,1,0,4)，z96；(10)⑩因为p4,p5线性无关，可得基解x(0,0,0,1,4)，z103；(4)(7)(9)(10)(7)所以原线性规划的基可行解是x,x,x,x，最优解是x，最优值是z1。1.3用单纯形法求解下列线

7、性规划问题；（1）maxz2x13x2x13x25s.t.x1x22x1,x20解：引入松弛变量x3，剩余变量x4和人工变量x5，把原问题化为规范式maxz2x13x2Mx5x13x2x35s.t.x1x2x4x52，其中M无限大，xi0,i1,2...5构造初始单纯形表并计算如下：x1x2x3x4x52+M3+M0-M0x1310053x110-1125以x2作为换入基，x3作为换成基，计算得x1x2x3x4x52M1+M0-1--M033x2111005333x5201-

8、111333以x1为换入基，x5作为换出基有x1x2x3x4x530013M-5.5222x2011111.5222x1101330.5222以x4换入