中国矿业大学：《运筹学》课程教学资源（作业习题）测试题四（答案）

测试题自四答案一、名词解释（本题10分，每小题2分）1、可行解：在线性规划问题中，凡满足所有约束条件的解称为线性规划问题可行解。2、二人有限零和对策：二人有限零和对策就是矩阵对策，是指只有两个参加对策的局中人，每个局中人都只有有限个策略可供选择。在任一局势下，两个局中人的赢得之和总是等于零，即双方的利益是激烈对抗的。3、影子价格：对偶变量Yi表示与原问题的第i个约束条件相对应的资源的影子价格在数量上表现为，当该约束条件的右端常数增加一个单位时（假设原问题的最优解不变2，原问题目标函数最优值增加的数量。4、0一1规划问题：在线性规划问题中，如果要求所有的决策变量只能取0或1，这样的问题称为0一1规划。5、最小费用最大流问题：最小费用最大流问题就是要求一个最大流f，使流的总输送费用b()=Zbif,取极小值。二、（本题15分）某纺织厂生产A、B两种布料，平均生产能力均为1千米/小时，工厂正常生产能力是80小时/周。又A布料每千米获利2500元，B布料每千米获利1500元。已知A、B两种布料每周的市场需求量分别是70千米和45千米。现该厂确定一周内的目标为：第一优先级：避免生产开工不足：第二优先级：加班时间不超过10小时：第三优先级：根据市场需求达到最大销售量：第四优先级：尽可能减少加班时间。试求该问题的最优方案。解：设x1,X2分别为生产甲、乙布料的小时数。对于第三优先级目标，根据A、B布料利润的比值2500:1500=5:3，取二者达到最大销量的权系数分别为5和3。该问题的目标规划模型为：minz=M,d,+M,d,+M,(5d,+3d)+Madx,+x+d-d=80x+x+d-=90x+d-=70s1.3+d -d=45,2d,d≥0i=1.4三、（本题15分）已知线性规划问题：maxz=10x, +5x2[3x, +4x,≤9(1)s1j5x, +2x2 ≤8 (2)X,X2≥01

1 测试题目四答案 一、名词解释（本题 10 分，每小题 2 分） 1、可行解：在线性规划问题中，凡满足所有约束条件的解称为线性规划问题可行解。 2、二人有限零和对策：二人有限零和对策就是矩阵对策，是指只有两个参加对策的局 中人，每个局中人都只有有限个策略可供选择。在任一局势下，两个局中人的赢得之 和总是等于零，即双方的利益是激烈对抗的。 3、影子价格：对偶变量 Yi 表示与原问题的第 i 个约束条件相对应的资源的影子价格， 在数量上表现为，当该约束条件的右端常数增加一个单位时（假设原问题的最优解不 变），原问题目标函数最优值增加的数量。 4、0—1 规划问题：在线性规划问题中，如果要求所有的决策变量只能取 0 或 1，这样 的问题称为 0—1 规划。 5、最小费用最大流问题：最小费用最大流问题就是要求一个最大流 f，使流的总输送 费用 b(f)=∑bijfij 取极小值。 二、（本题 15 分）某纺织厂生产 A、B 两种布料，平均生产能力均为 1 千米/小时，工 厂正常生产能力是 80 小时/周。又 A 布料每千米获利 2500 元，B 布料每千米获利 1500 元。已知 A、B 两种布料每周的市场需求量分别是 70 千米和 45 千米。现该厂确定一 周内的目标为：第一优先级：避免生产开工不足；第二优先级：加班时间不超过 10 小 时；第三优先级：根据市场需求达到最大销售量；第四优先级：尽可能减少加班时间。 试求该问题的最优方案。 解：设 x1,x2 分别为生产甲、乙布料的小时数。对于第三优先级目标，根据 A、B 布料 利润的比值 2500:1500=5:3，取二者达到最大销量的权系数分别为 5 和 3。该问题的目 标规划模型为： 1 1 2 2 3 3 4 4 1   1 2 1 1 1 2 2 2 1 3 3 2 4 4 1 2 min 5 3 80 90 . . 70 45 , , , 0 1, ,4. i i z M d M d M d d M d x x d d x x d d s t x d d x d d x x d d i                                              三、（本题 15 分）已知线性规划问题：             , 0 5 2 8 (2) 3 4 9 (1) . . max 10 5 1 2 1 2 1 2 1 2 x x x x x x st z x x

用单纯形法求得最终表如下bXBXi专X3X4013/25/14-3/14X21102/71/7Xi00-5/14-25/14cj-aj试用灵敏度分析的方法回答下列问题：①两种资源(1)、(2)的边际值各是多少？(x3，x4是资源(1)、(2)的松驰变量)：②目标函数系数c,或C分别在什么范围内变动，上述最优解不变；③当约束条件右端项b..b,中一个保持不变时，另一个在什么范围内变化上述最优基保持不变。解：（1)15/4≤c≤50,4/5≤c≤40/3,(2)24/5≤b,≤16,9/2≤b,≤15四、（本题15分）设有三个煤矿供应四个电厂的发电用煤。假定各个煤矿的年产量、各个电厂的备用煤量以及单位运价如下表所示。试求运费最省的煤炭调拔方案。电厂1IIIIV产量煤矿132217A1650B14 13151960c20231950-0最低需要量307010507030不限最高需求量解：由于各电厂的需求有两个部分，如电厂I，其最低需求30个单位不能由虚拟产地D供应，如要供应，其运价是一个任意大的正数M：而另一部分20个单位可以满足也可以不满足，因此可由虚拟产地D供应，其运价为0；其它电厂的需求量也可类似处理。从而可得到一个平衡的运输问题（单位运价表与产销平衡表）。电厂I’IVIV'1IIIII产量煤矿A17171616132250B15151414131960c19192023MM50D00050MMM203070301050销量利用表上作业法可以求出2

2 用单纯形法求得最终表如下 XB b x1 x2 x3 x4 x2 3/2 0 1 5/14 -3/14 x1 1 1 0 1/7 2/7 cj  zj 0 0 -5/14 -25/14 试用灵敏度分析的方法回答下列问题：①两种资源(1)、(2)的边际值各是多少？(x3，x4 是资源(1)、(2)的松驰变量)；②目标函数系数 c1 或 c2 分别在什么范围内变动，上述最 优解不变；③当约束条件右端项 b1,b2中一个保持不变时，另一个在什么范围内变化， 上述最优基保持不变。 解：(1) 15/ 4 50, 4 / 5 40 / 3,  c1   c2  (2) 24 / 5 16, 9 / 2 15.  b1   b2  四、（本题 15 分）设有三个煤矿供应四个电厂的发电用煤。假定各个煤矿的年产量、 各个电厂的备用煤量以及单位运价如下表所示。 试求运费最省的煤炭调拔方案。 电厂 煤矿 Ⅰ Ⅱ Ⅲ Ⅳ 产量 A 16 13 22 17 50 B 14 13 19 15 60 C 19 20 23 - 50 最低需要量 30 70 0 10 最高需求量 50 70 30 不限 解：由于各电厂的需求有两个部分，如电厂Ｉ，其最低需求 30 个单位不能由虚拟产地 D 供应，如要供应，其运价是一个任意大的正数 M；而另一部分 20 个单位可以满足也 可以不满足，因此可由虚拟产地 D 供应，其运价为 0；其它电厂的需求量也可类似处 理。从而可得到一个平衡的运输问题（单位运价表与产销平衡表）。 电厂 煤矿 Ⅰ Ⅰ’ Ⅱ Ⅲ Ⅳ Ⅳ’ 产量 A 16 16 13 22 17 17 50 B 14 14 13 19 15 15 60 C 19 19 20 23 M M 50 D M 0 M 0 M 0 50 销量 30 20 70 30 10 50 利用表上作业法可以求出

电厂IIIIIVIVII产量煤矿A5050B20103060c3020050D302050销量503020703010五、（本题15分）根据下表所给的资料绘制网络计划图，并计算时间参数，最后确定关键路线。工序紧前工序工序时间/d工序紧前工序工序时间/d3G2AB、CG、M5BH4H-7CI2A、L-VD3K1F、IEc5L7B、C3F5MCA、E解：网络图如下：CEI3nKQ01LD473关键路线为：1-3-4-5-6-7-10-11。六、（本题20分）用割平面法求整数规划问题的最优解：maxz=7x,+9x- X +3x, ≤6s.137x, +x,≤35X，x≥0且为整数其中，下表为整数规划问题的松弛问题的最优表。3

3 电厂 煤矿 Ⅰ Ⅰ’ Ⅱ Ⅲ Ⅳ Ⅳ’ 产量 A 50 50 B 20 10 30 60 C 30 20 0 50 D 30 20 50 销量 30 20 70 30 10 50 五、（本题 15 分）根据下表所给的资料绘制网络计划图，并计算时间参数，最后确定 关键路线。 工序 紧前工序 工序时间/d 工序 紧前工序 工序时间/d A G、M 3 G B、C 2 B H 4 H - 5 C - 7 I A、L 2 D L 3 K F、I 1 E C 5 L B、C 7 F A、E 5 M C 3 解：网络图如下： 关键路线为：1-3-4-5-6-7-10-11。 六、（本题 20 分）用割平面法求整数规划问题的最优解：              , 0且为整数 7 35 3 6 . max 7 9 1 2 1 2 1 2 1 2 x x x x x x st z x x 其中，下表为整数规划问题的松弛问题的最优表

790c→0bXBCBxiX2x3x49017/27/221/22X2710-1/223/229/2XI00-28/11-15/11cj解：线性规划的最优解为：Xi=9/2,x2=7/2,X3=x4=0,maxz=63由最终表中得：717④ +X+XA=22222将系数和常数项分解成整数和非负真分式之和，上式化为；71x =3+-X2 +X+22222移项后得：711711即：X4≥X≤225+X22222222只要把增加的约束条件加到B问题的最优单纯形表中。表4-379000c,→bXBCBXIX2X3X4Xs9017/221/2207/2X27103/2209/2-1/22xi000-7/2211/22-1/2Xs0028/1115/110-c-j这时得到的为非可行解，用对偶单纯形法进行求解。进行迭代得到：表4-479000C,→bXBCBXIX2X3XXs9010013X271001/7-1/732/XI00011/722/711/7X3000-1-8ci-4

4 c j  7 9 0 0 b CB XB x1 x2 x3 x4 9 x2 0 1 7/22 1/22 7/2 7 x1 1 0 －1/22 3/22 9/2 cj－zj 0 0 －28/11 －15/11 解： 线性规划的最优解为： x1  9/ 2, x2  7 / 2, x3  x4  0,max z  63 由最终表中得： 2 7 22 1 22 7 x2  x3  x4  ④ 将系数和常数项分解成整数和非负真分式之和，上式化为； 2 1 3 22 1 22 7 x2  x3  x4   移项后得： 即： 2 1 22 1 22 7 2 1 22 1 22 7 x3  x4    x3  x4   只要把增加的约束条件加到 B 问题的最优单纯形表中。 表 4－3 c j  7 9 0 0 0 b CB XB x1 x2 x3 x4 x5 9 x2 0 1 7/22 1/22 0 7/2 7 x1 1 0 －1/22 3/22 0 9/2 0 x5 0 0 －7/22* －1/22 1 －1/2 cj－zj 0 0 －28/11 －15/11 0 这时得到的为非可行解，用对偶单纯形法进行求解。进行迭代得到： 表 4－4 c j  7 9 0 0 0 b CB XB x1 x2 x3 x4 x5 9 x2 0 1 0 0 1 3 7 x1 1 0 0 1/7 －1/7 32/7 0 x3 0 0 1 1/7 －22/7 11/7 cj－zj 0 0 0 －1 －8

由计算结果知还没有得到整数解，重新再寻找割平面方程。由X行得：1132X,+=×4-74s:7将系数和常数项分解成整数和非负真分数之和：16XXs =4+X4-Xs+X, +77-64得到新的约束条件：X5-744-7641Xs+X6=1在的最优单纯形表中加上此约束，用对偶单纯形法求解：79c,→0000bCBXBX1X2X3X4XsX691001003X271001/7032/7-17Xi00011/7011/7-22/7X30-1/7"000-671-4/7X6000-10-8c9010.0103X270001-114XI010001-41X3000016-74X40000-2-7c-j则最优解为x，=4,x，=3，最优目标函数值为z=55。七、（本题10分）求下图顶点①到顶点的最短路及最短路长。9F9126610748D福15455

5 由计算结果知还没有得到整数解，重新再寻找割平面方程。 由 x1行得： 7 32 7 1 7 1 x1  x4  x5  将系数和常数项分解成整数和非负真分数之和： 7 4 4 7 6 7 1 x1  x4  x5  x5   得到新的约束条件： 7 4 7 6 7 1  x4  x5   7 4 7 6 7 1  x4  x5  x6   在的最优单纯形表中加上此约束，用对偶单纯形法求解： c j  7 9 0 0 0 0 b CB XB x1 x2 x3 x4 x5 x6 9 x2 0 1 0 0 1 0 3 7 x1 1 0 0 1/7 －1/7 0 32/7 0 x3 0 0 1 1/7 －22/7 0 11/7 0 x6 0 0 0 －1/7* －6/7 1 －4/7 cj－zj 0 0 0 －1 －8 0 9 x2 0 1 0 0 1 0 3 7 x1 1 0 0 0 －1 1 4 0 x3 0 0 1 0 －4 1 1 0 x4 0 0 0 1 6 －7 4 cj－zj 0 0 0 0 －2 －7 则最优解为 4, 3 * 2 * x1  x  ，最优目标函数值为 z * =55。 七、（本题 10 分）求下图顶点①到顶点⑧的最短路及最短路长

解：回g9 (15)②?9 (15)12(6)00(22)n66(10)回14 (4)7(11)10(21)??X+3)54 (11)25(5)(9)(22)15+福5 (10)(7分)v1到v8的最短路有两条：P18=(v1v3,v6,v8)及P18=vl,v3v7,v6,v8),最短路长为21。(3 分)6

6 解： (7 分) v1 到 v8 的最短路有两条：P18={v1,v3,v6,v8}及 P18={v1,v3,v7,v6,v8},最短路长为 21。 (3 分)