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

《管理运筹学》习题2一、分别用图解法和单纯形法（用大M法和两阶段法都可以）求解下列线性规划问题：二、以下各模型目标函数都是求最大值，根据各自的最优表下结论（要判断解的类型）：（1）cj→-2-3-100-M-MCBXBB-1bx1x2x3x4x5x6x7-3-2x2x19/54/501103/5-2/5-3/101/51/10-2/53/10-1/5-1/102/5σj=cj-zj000-1/21/2-M+1/2-M+1/2（2）cj→101512000-MCBXBB-1bx1x2x3x4x5x6x7100-Mx1x3x73/23/31/210039/809/16-43/800103/161/16-7/16-1/801/16-3/8000-1001σj=cj-zj0-43M/80+31/80-30/16-7M/16-3M/80+1/8-M0（3）cj→2-120-M0-M0-MCBXBB-1bx1x2x3x4x5x6x7x8x922-1x1x3x23/47/27/4100001010-1/4-1/2-1/41/41/21/43/8-1/4-1/8-3/81/41/81/81/4-3/8-1/8-1/43/8σj=cj-zj0005/4-M-3/4-3/8-M+3/8-9/8-M+9/8三、有三个发电站产地B1，B2，B3需要从两个煤矿A1，A2购买煤炭，各自的产量、需求量以及每万吨煤炭的运价（千元）如表1所示。问如何调运煤炭，使得总运输费用最小？表1产销平衡表和单位运价表发电站Bj煤矿AiB1B2B3产量（万吨）A12362236A21577212每月对煤的需求量（万吨）315要求：（1）请建立该问题的线性规划模型，如果有必要再化为标准问题。（2）用表上作业法求解：用最小元素法确定初始方案；用闭回路法或者位势法验证初始方案是否最优？如果非最优，请用闭回路法调整，直至求出最优方案。四、某工厂生产两种产品。甲、乙两种产品每件生产工时分别为6小时，2小时，总生产工时计划定为24小时。甲产品和乙产品每生产一件对A原料消耗量都为1单位，原料A计划购买量为5单位。乙产品每生产品一件对B原料的消耗为5单位，甲产品生产不需要B原料，该原料计划购买量为5单位。要求依次满足下列目标：（1）计划工时数尽可能充分利用但最好不要超过；（2）原料A购买量最好不超过计划规定量；（3）原料B购买量最好也不要超过计划购买量。请建立该问题的线性目标规划模型并用图解法或单纯型法求解。《管理运筹学》习题2解答一.分别用图解法和单纯形法求解下列线性规划问题：x1≤2x1≤2x24321-1解：（一）用图解法求解，过程如下：4321-11.各种约束条件如图1所示，其中线段AB为x1-x2=1可行域。A点和B点坐标分别为(4/3,1/3)x1-x2=12.画出目标函数的一条等值线：-2x1+4x2=0,如图-2x1+4x2=0所示。它沿法线向下平移-2x1+4x2=0B3.当目标函数平移到A(4/3,1/3)点时，z→minz。BA所以本题有唯一最优解X*＝(4/3,1/3)T，最优目标Ax101234函数值z*=-2×4/3+4×1/3=-4/3。x101234(二)用单纯形法求解（用大M法和两阶段法都可）4x14x1+2x2≥6[大M法求解]1.将原模型化为标准型（1）令y1=2-x1≥0，………③x2=y2-y3(其中y2,y3≥0)………③………④则x1＝2-y1………④将①、②代入原约束条件，并化简整理得到：（2）在③式左边加入松弛变量y4,化为：2y1-y2+y3+y4=1④式不用标准化,已经是标准形式。（3）将①、②代入目标函数得：minz=-4+2y1+4y2-4y3+0·y4令w＝-z，则目标函数化为：maxw=4-2y1-4y2+4y3+0·y4所以，标准型即：………⑤………⑤2.在⑤式左边加入人工变量y5，并在目标函数中加入罚因子M(M为很大的正数)，则标准型化为规范型，如下所示：3.列单纯形表求解，过程如下：cj→-2-440-MθiCBXBB-1by1y2y3y4y50-My4y511[2]1-111-110011/21σj=cj-zj-M-2+M-4+M4-M00-2-My1y51/21/210-1/2[3/2]1/2-3/21/2-1/201—1/3σj=cj-zj-1-1/2M0-5+3/2M5-3/2M1-1/2M0-2-4y1y22/31/310010-11/3-1/31/32/3——σj=cj-zj-8/3000-2/3-M+11/34.结论：因为所有非基变量检验数σj≤0(j=3,4,5)，且σ3=0,人工变量y5=0，所以上述规范型模型有无穷多最优解，当前基可行解(2/3,1/3,0,0,0)T为最优解（其他最优解不能通过单纯形法求出，∵）。相应的x*1＝2-y*1=2-2/3=4/3；x*2=y*2-y*3=1/3-0=1/3；minz=-maxw=-(-8/3+4)=-4/3。[用两阶段法求解]（接大M法第2步以后）第一阶段：先列单纯形表求解如下模型：cj→0000-1θiCBXBB-1by1y2y3y4y50-1y4y511[2]1-111-110011/21σj=cj-zj11-1000-1y1y51/21/210-1/2[3/2]1/2-3/21/2-1/201—1/3σj=cj-zj03/2-3/2-1/2000y1y22/31/310010-11/3-1/31/32/3——σj=cj-zj00000-1因为所有非基变量检验数σj≤0(j=3,4,5)，所以停止迭代，w=0，进入第二阶段继续求解。第二阶段，去掉人工变量y5，恢复非人工变量目标系数，在以上最后一步基础上继续求解：cj→-2-440θiCBXBB-1by1y2y3y4-2-4y1y22/31/310010-11/3-1/3——σj=cj-zj-8/3000-2/34.结论同大M法第4步。二.以下各模型目标函数都是求最大值，根据各自的最优表下结论（要判断解的类型）：（1）cj→-2-3-100-M-MCBXBB-1bx1x2x3x4x5x6x7-3-2x2x19/54/501103/5-2/5-3/101/51/10-2/53/10-1/5-1/102/5σj=cj-zj000-1/21/2-M+1/2-M+1/2（2）cj→101512000-MCBXBB-1bx1x2x3x4x5x6x7100-Mx1x3x73/23/31/210039/809/16-43/800103/161/16-7/16-1/801/16-3/8000-1001σj=cj-zj0-43M/80+31/80-30/16-7M/16-3M/80+1/8-M0（3）cj→2-120-M0-M0-MCBXBB-1bx1x2x3x4x5x6x7x8x922-1x1x3x23/47/27/4100001010-1/4-1/2-1/41/41/21/43/8-1/4-1/8-3/81/41/81/81/4-3/8-1/8-1/43/8σj=cj-zj0005/4-M-3/4-3/8-M+3/8-9/8-M+9/8解：（1）结论：因为所有非基变量检验数σj≤0(j=3,4,5,6,7)，σ3＝0且、人工变量x6＝x7＝0，所以有无穷多最优解。以x3为进基变量继续迭代，可求出另外一个最优解。cj→-2-3-100-M-MθiCBXBB-1bx1x2x3x4x5x6x7-3-2x2x19/54/50110[3/5]-2/5-3/101/51/10-2/53/10-1/5-1/102/53—σj=cj-zj000-1/21/2-M+1/2-M+1/2-1-2x3x132015/32/310-1/201/6-1/31/20-1/61/3σj=cj-zj000-1/2-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；maxz=-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，而a/i4≤0(i=1,2,3)，故此问题无有限最优解（或为无界解）。三、有三个发电站产地B1，B2，B3需要从两个煤矿A1，A2购买煤炭，各自的产量、需求量以及每万吨煤炭的运价（千元）如表1所示。问如何调运煤炭，使得总运输费用最小？表1产销平衡表和单位运价表发电站Bj煤矿AiB1B2B3产量（万吨）A12362236A21577212每月对煤的需求量（万吨）315要求：（1）请建立该问题的线性规划模型，如果有必要再化为标准问题。（2）用表上作业法求解：用最小元素法确定初始方案；用闭回路法或者位势法验证初始方案是否最优？如果非最优，请用闭回路法调整，直至求出最优方案。解：（1）设产地Ai（i=1,2）调运到销地Bj（j=1,2,3）的煤炭为xij万吨，可建立以下模型：（2）因为总产量8万吨（=6+2）小于总需求量9万吨（=3+1+5），所以本问题不是标准运输问题。增加一个虚拟产地A3，它的单位运价c31=c32=c33=0，产量为9-8=1（万吨）。（3）第一步：用最小元素法确定初始方案（方案可能有以下三种，随着添加0位置不同而不同）。或或方法二：伏格尔法（本题用此法求出的初始基可行解就是最优解）方法三：西北角法第二步：求非基变量检验数，验证初始方案(最小元素法求得的第一种初始方案)是否最优。法一：用位势法求检验数。求解见下表所示：销地产地B1B2B3UiA10230620230A20152377621-8A300-39000-23Vj236223因为min(σ22,σ23,σ32,σ33|σij<0)=σ32=-39<0，所以初始方案并非最优方案，需进一步调整，x32为进基变量。法二：用闭回路法求检验数σ22=77-15+23-62=23;σ23=21-15+23-23=6;σ33=0-0+23-23=0；σ32=0-0+23-62=-39（注：图中画出了非基变量x32的闭回路）；因为min(σ22,σ23,σ32,σ33|σij<0)＝σ32=-39<0，，所以初始方案并非最优方案，需进一步调整，x32为进基变量。第三步：求θ值，调整初始方案。过程如下：以X32作为进基变量。调整量θ＝min(1,1)=1，按照左图所示进行调整，选择x31作为出基变量。方案调整后为方案二（注：另一个基可行解），如下：用位势法可求出方案二非基变量检验数：销地产地B1B2B3UiA10230620230A20152377621-8A339000390-62Vj236223因为非基变量检验数σ22,σ23,σ31,σ33>0，所以方案二就是唯一最优方案。决策结论：产地A1向销地B1调运煤炭1万吨，向销地B3调运煤炭5万吨；产地A2向销地B1调运煤炭2万吨；销地B2的需求量由虚拟产地A3来满足，实际上它的需求量1万吨完全未得到满足。最小总运费=23×1+0×62+23×5+15×2+0×1=168（千元）。四、某工厂生产两种产品。甲、乙两种产品每件生产工时分别为6小时，2小时，总生产工时计划定为24小时。甲产品和乙产品每生产一件对A原料消耗量都为1单位，原料A计划购买量为5单位。乙产品每生产品一件对B原料的消耗为5单位，甲产品生产不需要B原料，该原料计划购买量为5单位。要求依次满足下列目标：（1）计划工时数尽可能充分利用但最好不要超过；（2）原料A购买量最好不超过计划规定量；（3）原料B购买量最好也不要超过计划购买量。请建立该问题的线性目标规划模型并用图解法或单纯型法求解。解：首先，建立该问题的线性目标规划模型，如下：设甲、乙两种产品的产量分别为x1、x2件。图解法求解，如下图所示：6x1+2x2=24D012345d+36x1+2x2=24D012345d+3d-3Cd-1d+1d-2d+2BA12108642x1x2x1+x2=55x2=5x2取值范围、各约束条件表示在坐标系中，并用箭头标出正负偏差变量增大方向。在各级目标实现之前，可行域为第一象限及及x1、x2的非负半轴。(2)对于第一级目标P1，要求min(d1-+d1+)，在线段AD上任一点都可满足。(3)第二级目标P2，要求mind2+，可行域由线段AD缩小为线段BD。(4)第三级目标P3，要求mind3+，可行域由线段BD缩小为线段CD。即线段CD上任一点的坐标都可以全部满足三级目标。C、D两点坐标分别为（11/3,1）、（4,0）。但C点两种原料的利用率最高，都尽可能接近计划规定量（14/3,5）。因此，最优解X*=λ(11/3,1)T+(1-λ)(4,0)T（注解：所有级别的目标都完全实现时，可以称为最