《管理运筹学》习题2解答

《管理运筹学》习题2

一、分别用图解法和单纯形法（用大M法和两阶段法都可以）求解下列线性规划问题：

min z??2x1?4x2 ?4x1?2x2?6?s.t.?x1?x2?1?x?2,x自由2?1二、以下各模型目标函数都是求最大值，根据各自的最优表下结论（要判断解的类型）：

（1）

-2 -3 -1 0 0 -M -M cj→ -1CB XB Bb x1 x2 x3 x4 x5 x6 x7 -3 x2 9/5 0 1 3/5 -3/10 1/10 3/10 -1/10 -2 x1 4/5 1 0 -2/5 1/5 -2/5 -1/5 2/5 0 0 0 -1/2 1/2 -M+1/2 -M+1/2 σj=cj-zj （2） CB 10 0 -M σ（3） 2 -1 2 0 -M 0 -M 0 -M cj→ CB XB B-1b x1 x2 x3 x4 x5 x6 x7 x8 x9 2 x1 3/4 1 0 0 -1/4 1/4 3/8 -3/8 1/8 -1/8 2 x3 7/2 0 0 1 -1/2 1/2 -1/4 1/4 1/4 -1/4 -1 x2 7/4 0 1 0 -1/4 1/4 -1/8 1/8 -3/8 3/8 0 0 0 5/4 -M-3/4 -3/8 -M+3/8 -9/8 -M+9/8 σj=cj-zj 三、有三个发电站产地B1，B2，B3需要从两个煤矿A1，A2购买煤炭，各自的产量、需求量以及每万吨煤炭的运价（千元）如表1所示。问如何调运煤炭，使得总运输费用最小？

表1 产销平衡表和单位运价表

B1 B2 B3 发电站Bj 产量（万吨） 煤矿Ai A1 23 62 23 6 A2 15 77 21 2 3 1 5 每月对煤的需求量（万吨） 要求：（1）请建立该问题的线性规划模型，如果有必要再化为标准问题。（2）用表上作

业法求解：用最小元素法确定初始方案；用闭回路法或者位势法验证初始方案是否最优？如果非最优，请用闭回路法调整，直至求出最优方案。

四、某工厂生产两种产品。甲、乙两种产品每件生产工时分别为6小时，2小时，总生产工时计划定为24小时。甲产品和乙产品每生产一件对A原料消耗量都为1单位，原料A计划购买量为5单位。乙产品每生产品一件对B原料的消耗为5单位，甲产品生产不需要B原料，该原料计划购买量为5单位。要求依次满足下列目标：（1）计划工时数尽可能充分利用但最好不要超过；（2）原料A购买量最好不超过计划规定量；（3）原料B购买量最好也不要超过计划购买量。请建立该问题的线性目标规划模型并用图解法或单纯型法求解。

cj→ XB x1 x3 x7 j=cj-zj B-1b 3/2 3/3 1/2 10 x1 1 0 0 0 15 x2 39/80 9/16 -43/80 -43M/80 +31/8 12 x3 0 1 0 0 0 0 x4 x5 3/16 -1/80 1/16 1/16 -7/16 -3/80 -30/16 -3M/80 -7M/16 +1/8 0 x6 0 0 -1 -M -M x7 0 0 1 0

《管理运筹学》习题2解答

一.分别用图解法和单纯形法求解下列线性规划问题：

min z??2x1?4x2?4x1?2x2?6?s.t.?x1?x2?1?x?2,x自由2?1

x2 x1≤2 解：（一）用图解法求解，过程如下：

4 1.各种约束条件如图1所示，其中线段AB为

x1-x2=1 可行域。A点和B点坐标分别为(4/3,1/3)、（2,1） 3 2.画出目标函数的一条等值线：-2x1+4x2=0,如图

2 所示。它沿法线向下平移，目标函数值z越来越小。 -2x1+4x2=0 3.当目标函数平移到A(4/3,1/3)点时，z→min z。 1 B *T

所以本题有唯一最优解X＝(4/3,1/3)，最优目标

A x1 函数值z*=-2×4/3+4×1/3=-4/3。

0 1 2 3 4 (二)用单纯形法求解（用大M法和两阶段法都可）， -1 4x1+2x2≥6 [大M法求解]

1.将原模型化为标准型 （1）令y1=2-x1≥0，

?2y1?y2?y3?1 ………③ x2=y2-y3(其中y2,y3≥0)………①

?则x1＝2- y1………②

s.t.? y1?y2?y3?1………④

将①、②代入原约束条件，并化简整理得到：

?（2）在③式左边加入松弛变量y4,化为： ?yj?0j?1,2,32y1-y2+y3+y4=1

④式不用标准化,已经是标准形式。

（3）将①、②代入目标函数得：min z=-4+2y1+4y2-4y3+0·y4 令w＝-z，则目标函数化为：max w=4-2y1-4y2+4y3+0·y4 所以，标准型即：

??max w?4?2y1?4y2?4y3?0?y4 ?2y1?y2?y3?y4?1?s.t.?y1?y2?y3?1??yj?0?j?1,2,3?………⑤

2.在⑤式左边加入人工变量y5，并在目标函数中加入罚因子M(M为很大的正数)，则标准型

化为规范型，如下所示：

max w?4?2y1?4y2?4y3?0?y4?M?y5 ?2y1?y2?y3?y4 ?1?s.t.?y1?y2?y3 ?y5?1??yj?0?j?1,2,?,5?3.列单纯形表求解，过程如下： cj→ CB 0 -M -2 -M -2 -4 XB y4 y5 y1 y5 y1 y2 B-1b 1 1 -M 1/2 1/2 -1-1/2M 2/3 1/3 -8/3 -2 y1 [2] 1 -2+M 1 0 0 1 0 0 -4 y2 -1 1 -4+M -1/2 [3/2] 0 1 0 4 y3 1 -1 4-M 1/2 -3/2 0 -1 0 0 y4 1 0 0 1/2 -1/2 1-1/2M 1/3 -1/3 -2/3 -M y5 0 1 0 0 1 0 1/3 2/3 -M+11/3 θi 1/2 1 — 1/3 — — σj=cj-zj σj=cj-zj -5+3/2M 5-3/2M σj=cj-zj 4.结论：因为所有非基变量检验数σj≤0(j=3,4,5)，且σ3=0,人工变量y5=0，所以上述规范型模型有无穷多最优解，当前基可行解(2/3,1/3,0,0,0)T为最优解（其他最优解不能通过单纯形

*****

法求出，∵?）。相应的x＝2-yx=y- ymin 1=2-2/3=4/3 ；1223=1/3-0=1/3；a13?0?0,a?23??1?0z=-max w=-(-8/3+4)=-4/3。

[用两阶段法求解]

（接大M法第2步以后）第一阶段：先列单纯形表求解如下模型：

max w??1?y5?2y1?y2?y3?y4 ?1?s.t.?y1?y2?y3 ?y5?1??yj?0?j?1,2,?,5?cj→ CB 0 -1 0 -1 0 0 XB y4 y5 y1 y5 y1 y2 σj=cj-zj B-1b 1 1 1/2 1/2 2/3 1/3 0 0 y1 [2] 1 1 1 0 0 1 0 0 0 y2 -1 1 1 -1/2 [3/2] 3/2 0 1 0 0 y3 1 -1 -1 1/2 -3/2 -3/2 0 -1 0 0 y4 1 0 0 1/2 -1/2 -1/2 1/3 -1/3 0 -1 y5 0 1 0 0 1 0 1/3 2/3 -1 θi 1/2 1 — 1/3 — — σj=cj-zj σj=cj-zj 因为所有非基变量检验数σj≤0(j=3,4,5)，所以停止迭代，w=0，进入第二阶段继续求解。 第二阶段，去掉人工变量y5，恢复非人工变量目标系数，在以上最后一步基础上继续求解：

cj→ CB -2 -4 XB y1 y2 B-1b 2/3 1/3 -8/3 -2 y1 1 0 0 -4 y2 0 1 0 4 y3 0 -1 0 0 y4 1/3 -1/3 -2/3 θi — — σj=cj-zj 4.结论同大M法第4步。 二.以下各模型目标函数都是求最大值，根据各自的最优表下结论（要判断解的类型）： （1） cj→ CB -3 -2 （2） cj→ CB 10 0 -M XB x1 x3 x7 B-1b 3/2 3/3 1/2 10 x1 1 0 0 0 15 x2 39/80 9/16 -43/80 -43M/80 +31/8 2 x3 0 1 0 0 0 x4 -1/4 -1/2 -1/4 5/4 12 x3 0 1 0 0 0 x4 3/16 1/16 -7/16 0 x5 -1/80 1/16 -3/80 0 x6 0 0 -1 -M -M x7 0 0 1 0 XB x2 x1 B-1b 9/5 4/5 -2 x1 0 1 0 -3 x2 1 0 0 -1 x3 3/5 -2/5 0 0 x4 -3/10 1/5 -1/2 0 x5 1/10 -2/5 1/2 -M x6 3/10 -1/5 -M x7 -1/10 2/5 σj=cj-zj -M+1/2 -M+1/2 σj=cj-zj （3） cj→ CB 2 2 -1 解：

XB x1 x3 x2 B-1b 3/4 7/2 7/4 -30/16- -3M/80 7M/16 +1/8 -M x5 1/4 1/2 1/4 0 x6 3/8 -1/4 -1/8 -M x7 -3/8 1/4 1/8 2 x1 1 0 0 0 -1 x2 0 0 1 0 0 x8 1/8 1/4 -3/8 -M x9 -1/8 -1/4 3/8 σj=cj-zj -M-3/4 -3/8 -M+3/8 -9/8 -M+9/8 （1）结论：因为所有非基变量检验数σj≤0(j=3,4,5,6,7)，σ3＝0且a??13cj→ CB -3 -2 -1 -2 XB x2 x1 x3 x1 B-1b 9/5 4/5 3 2 -2 x1 0 1 0 0 1 0 -3 x2 1 0 0 5/3 2/3 0 -1 x3 [3/5] -2/5 0 1 0 0 0 x4 -3/10 1/5 -1/2 -1/2 0 -1/2 0 x5 -M x6 35?0、人工变

量x6＝x7＝0，所以有无穷多最优解。以x3为进基变量继续迭代，可求出另外一个最优解。

-M x7 -1/10 2/5 -1/6 1/3 θi 3 — 1/10 3/10 -2/5 -1/5 1/6 -1/3 1/2 0 σj=cj-zj 1/2 -M+1/2 -M+1/2 σj=cj-zj -1/2 -M+1/2 -M+1/2 所以，本题最优解其中一个为：X1*=(4/5,9/5,0,0,0,0,0)T；

另一个最优解为：X2*=(2,3,0,0,0,0,0)T； max z=-3×9/5-2×4/5=-1×3-2×2=-7

（2）结论：因为所有非基变量检验数σj≤0(j=2,4,5,6)但人工变量x7=1/2≠0，所以此问题无可行解。

（3）结论：非基变量检验数σ4＝5/4>0，而ai4≤0(i=1,2,3)，故此问题无有限最优解（或为无界解）。

三、有三个发电站产地B1，B2，B3需要从两个煤矿A1，A2购买煤炭，各自的产量、需求量以及每万吨煤炭的运价（千元）如表1所示。问如何调运煤炭，使得总运输费用最小？

表1 产销平衡表和单位运价表 B1 B2 B3 发电站Bj 产量（万吨） 煤矿Ai A1 23 62 23 6 A2 15 77 21 2 3 1 5 每月对煤的需求量（万吨） 要求：（1）请建立该问题的线性规划模型，如果有必要再化为标准问题。（2）用表上作业法求解：用最小元素法确定初始方案；用闭回路法或者位势法验证初始方案是否最优？如果非最优，请用闭回路法调整，直至求出最优方案。

解：（1）设产地Ai（i=1,2）调运到销地Bj（j=1,2,3）的煤炭为xij万吨，可建立以下模型：

/

min z???cij?xij?23x11?62x12?23x13?15x21?77x22?21x23i?1j?123?x11?x12?x13?6?x?x?x?223?2122??x11?x21?3s..t??x12?x22?1?x13?x23?5???xij?0(i?1,2;j?1,2,3)

（2）因为总产量8万吨（=6+2）小于总需求量9万吨（=3+1+5），所以本问题不是标准运输问题。增加一个虚拟产地A3，它的单位运价c31=c32=c33=0，产量为9-8=1（万吨）。 （3）第一步：用最小元素法确定初始方案（方案可能有以下三种，随着添加0位置不同而不同）。

?23(0)62(1)23(5)?6(1)(0)?(2)?157721??2(0)? 0(1) 0 0???1(0) 3 1 5 (2) (0) (0) (0)?015??15??15??2??20??2?0?????? ?????1?或??1?或??1?方法二：伏格尔法（本题用此法求出的初始基可行解就是最优解）

?23(1)62(0)23(5)?6[0](5)(0)?(2)?157721??2[6](0)(1)? 0 0 0???1[0](0) 3 1 5 [15] [77] [21] [ 8] (0) [ 2] (1) [ -] [ -] ( 0) (0)方法三：西北角法

?105??2??? ??1??

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库《管理运筹学》习题2解答在线全文阅读。