运筹学作业-王程130404026(3)

以进行第二阶段计算，将第一阶段的最终表中的人工变量取消，并填入原问题的目标函数的系数，如下表： cj 2 3 1 0 0 θi CB XB b x1 x2 x3 x4 x5 3 2 x2 x1 9/5 4/5 0 1 0 1 0 0 3/5 -2/5 0 -3/10 1/5 1/2 1/10 -2/5 1/2 Tcj-zj ?49?由表中计算可知，原线性规划问题的最优解X*??，，0，0，0，0，0?，目标函数的

?55?49最优值z*?2??3??7，由于存在非基变量检验数?3=0，故该线性规划问题

55有无穷多最优解。

（2）解：大M法： 在上述线性规划问题的约束条件中加上松弛变量x4,x5,减去剩余变量x6,再加上 人工变量x7,得 maxz?10x1+15x2?12x3?0x4?0x5?0x6?Mx7?5x1?3x2?x3?x4?9??5x?6x?15x?x?15?1235 s.t.??2x1?x2?x3?x6?x7?5??x1,x2,x3,x4,x5,x6,x7?0 其中M是一个任意大的正数，据此可列出单纯形表如下： cj 10 15 12 0 CB XB b x1 x2 x3 x4 0 x4 9 0 x5 15 -M x7 5 cj-zj 10 x1 9/5 0 x5 24 -M x7 7/5 cj-zj [5] -5 2 10+2M 1 0 0 0 0 x5 0 1 0 0 0 1 0 0 0 x6 0 0 -1 -M 0 0 -1 -M x7 θi 3 6 1 15+M 3/5 9 -1/5 M9? 51 15 1 12+M 1/5 [16] 3/5 310+M5 1 0 0 0 1/5 1 -2/5 2?2?M 50 9/5 0 - 1 5/2 0 0 9 0 3/2 1 7/3 ?M 0 10 x1 3/2 12 x3 3/2 -M x7 1/2 cj-zj 1 0 0 0 39/80 9/16 -43/80 2743?M 8800 1 0 0 3/16 1/16 -7/16 ?-1/80 1/16 -3/80 0 0 -1 0 0 1 21753?M ??M ?M 0 816880 由单纯性表的最终表可以看出，所有非基变量检验数?j?0 ，且存在人工变量

x7?1 ，故原线性规划问题无可行解。 2两阶段法：在上述线性规划问题的约束条件中加上松弛变量x4,x5,减去剩余变量x6,再加上人工变量x7,得第一阶段的数学模型 min w=x7?5x1?3x2?x3?x4?9??5x?6x?15x?x?15?1235 s.t.??2x1?x2?x3?x6?x7?5??x1,x2,x3,x4,x5,x6,x7?0据此可列出单纯初始形表如下： cj 0 0 CB XB b x1 x2 0 0 1 x4 x5 x7 9 15 5 [5] -5 2 -2 1 0 0 0 1 0 0 0 *0 x3 1 15 1 -1 1/5 [16] 3/5 3/5 0 1 0 0 T0 x4 1 0 0 0 1/5 1 -2/5 -2/5 3/16 1/16 -7/16 7/16 0 x5 0 1 0 0 0 1 0 0 -1/80 1/16 -3/80 3/80 0 x6 0 0 -1 1 0 0 -1 1 0 0 -1 1 1 x7 0 0 1 0 0 0 1 0 0 0 1 0 θi 9/5 - 5/2 9 3/2 7/3 3 6 1 -1 3/5 9 -1/5 -1/5 39/80 9/16 -43/80 43 80cj-zj 10 x1 9/5 0 x5 24 1 x7 7/5 cj-zj 0 0 1 x1 x3 x7 cj-zj 3/2 3/2 1/2 11??33第一阶段求得最优解X??，0，0，0，0，?，因人工变量x7??0 ，且非基变

22??22量检验数?j?0，所以原线性规划问题无可行解。 1.5 考虑下述线性规划问题：

maxz?c1x1?c2x2

?a11x1?a12x2?b1?s.t.?a21x1?a22x2?b2

? x,x?012?式中，1?c1?3,4?c2?6,?1?a11?3,2?a12?5,8?b1?12,2?a21?4,4?a22?6,10?b2?14，试确定目标函数最优值的下界和上界。解：（1）上界对应的模型如下（c，b取大，a取小）

maxz?3x1?6x2??1x1?2x2?12 s.t.?2x?4x?14

?12?x,x?0?12 最优值（上界）为：21；

（2）下界对应的模型如下（c，b取小，a取大）

maxz?x1?4x2?3x1?5x2?8 s.t.?4x?6x?10

?12?x,x?0?12 最优值（下界）为：6.4。

1.7 已知某线性规划问题的初始单纯形表和用单纯形法迭代后得到表1-21，试求括弧中未知数a?l的值。

表 1-21 项目 x1 x2 x3 x4 x5x4 6 (b) (c) (d) 1 0 x5 1 -1 3 (e) 0 1cj -zj (a) -1 2 0 0x1 (f) (g) 2 -1 1/2 0x5 4 (h) (i) 1 1/2 1cj -zj 0 -7 (j) (k) (l)

解：a b c d e f g h i j k l3 2 4 -2 2 3 1 0 5 -5 -3/2 01.8 若X⑴,X(2)均为某线性规划问题的最优解，证明在这两点连线上的所有点也是该问题的最优解。

证明：设X(1)和X(2)满足：maxz?CTX?AX?b ??X?0 对于任何0?a?1，两点连线上的点 X满足：X?aX(1)?(1?a)X(2)也是可行解，且 CTX?CTaX(1)?CT(1?a)X(2) ?CTaX(1)?aCTX(2)?CTX(2) ?CTX(2) 所以X也是最优解。 1.9 考虑线性规划问题 …… 此处隐藏：581字，全部文档内容请下载后查看。喜欢就下载吧 ……