最优化方法习题答案.pdf

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

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

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

3、。442x12x273x34x4①因为p1,p2线性无关，故有，令非基变量为x3x40，得2xx3x2x12341x13(1)111，所以得到一个基解x(,,0,0)是非基可行解；1133x23(2)21143②因为p,p线性无关，可得基解x(,0,,0)，z；132555(3)111③因为p,p线性无关，可得基解x(,0,0,)，是非基可行解；1436(4)④因为p,p线性无关，可得基解x(0,2,1,0)，z1；234⑤因为p,p线性相关，x,x不能构成基变量；2

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

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

6、解；23(6)⑥因为p,p线性无关，可得基解x(0,2,0,1,0)，是非基可行解；24(7)⑦因为p,p线性无关，可得基解x(0,1,0,0,2)，z1；257⑧因为p,p线性相关，x,x不能构成基变量；3434(9)⑨因为p,p线性无关，可得基解x(0,0,1,0,4)，z6；359(10)⑩因为p,p线性无关，可得基解x(0,0,0,1,4)，z3；4510(4)(7)(9)(10)(7)所以原线性规划的基可行解是x,x,x,x，最优解是x，最优值是z1。1.3用单纯形法求解下列线性规划问题；（1）maxz2x3

7、x12x13x25s.t.x1x22x,x012解：引入松弛变量x，剩余变量x和人工变量x，把原问题化为规范式345maxz2x3xMx125x13x2x35s.t.x1x2x4x52，其中M无限大，x0,i1,2...5i构造初始单纯形表并计算如下：x1x2x3x4x52+M3+M0-M0131005x3110-112x5以x作为换入基，x作为换成基，计算得23x1x2x3x4x520M-M01+M-1-33111005x2333201-111x5333以x为换入基，x作为换出基有1

8、5x1x2x3x4x500133-5.5M222011111.5x2222101330.5x1222以x换入，