运筹学作业-王程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 考虑线性规划问题

maxz??x1?2x2?x3?4x4? x1?x2 ?x4?4?2? (i)? s.t.?2x1?x2?3x3?2x4?5?7? (ii)

?x,x,x,x?0?1234模型中?，?为参数，要求：

⑴ 组成两个新的约束(i)'=(i)+(ii),(ii)'=(ii)-2(i)，根据式(i)'和式(ii)'，以

x1,x2为基变量，列出初始单纯形表；

(i) x1?x3?x4?3?2?解：

(ii) x2?x3?1??Cj→ CB 基 b α x1 3+2β2 x2 1-βcj-zj

α 2 1 -4 x1 x2 x3 x4 1 0 1 -10 1 -1 00 0 3-α α-4

⑵ 在表中，假定?=0 ，则? 为何值时，x1,x2为问题的最优基； 解：如果?=0，则当3???4时，x1,x2为问题的最优基变量。 ⑶ 在表中，假定?=3 ，则? 为何值时，x1,x2为问题的最优基。 解：如果?=3，则当-1???1时，x1,x2为问题的最优基变量。 1.10 试述线性规划模型中“线性”二字的含义，并用实例说明什么情况下线性的假设将被违背。

答：线性的含义：一是严格的比例性，如生产某产品对资源的消耗量和可获取的利润，同其生产数量严格成比例；二是可叠加性，如生产多种产品时，可获取的总利润使各项产品的利润之和，对某项资源的消耗量应等于各产品对该资源的消耗量之和；三是可分性，即模型中的变量可以取值为小数、分数或某一实数；四是确定性，指模型中的参数cj,aij,bi 均为确定的常数。

很多实际问题往往不符合上述条件，例如每件产品售价3元，但成批购买就可以得到折扣优惠。

1.11 判断下列说法是否正确，为什么？

m ⑴ 含n个变量m个约束的标准型的线性规划问题，基解数恰好为Cn个；

m?C 答：错误。基本解的个数=基的个数n

⑵ 线性规划问题的可行解如为最优解，则该可行解一定为基可行解；

答：错误。当有唯一最优解时，最优解是可行域顶点，对应基本可行解；当

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库运筹学作业-王程130404026(3)在线全文阅读。