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

测试题目四一、名词解释（本题10分，每小题2分）1、可行解；2、二人有限零和对策：3、影子价格；4、0-1规划问题；5、最小费用最大流问题。二、（本题15分）某纺织厂生产A、B两种布料，平均生产能力均为1千米/小时，工厂正常生产能力是80小时/周。又A布料每千米获利2500元，B布料每千米获利1500元。已知A、B两种布料每周的市场需求量分别是70千米和45千米。现该厂确定一周内的目标为：第一优先级：避免生产开工不足：第二优先级：加班时间不超过10小时：第三优先级：根据市场需求达到最大销售量：第四优先级：尽可能减少加班时间。试建立该问题的目标规划数学模型（只建模，不求解）。三、（本题15分）已知线性规划问题：max z=10x, +5x2[3x, +4x, ≤9(1)s1J5x, +2x2 ≤8(2)X,x2≥0用单纯形法求得最终表如下XBbX1X2X3X403/215/14-3/14X21-0-1/72/7xi00-5/14-25/14cj-3j试用灵敏度分析的方法回答下列问题：①两种资源(1)、(2)的边际值各是多少？(x3，x4是资源(1)、(2)的松驰变量)；②目标函数系数c或c分别在什么范围内变动，上述最优解不变：③当约束条件右端项b,，b，中一个保持不变时，另一个在什么范围内变化上述最优基保持不变。四、（本题15分）设有三个煤矿供应四个电厂的发电用煤。假定各个煤矿的年产量、各个电厂的备用煤量以及单位运价如下表所示。试求运费最省的煤炭调拔方案。电厂1IIIIIIV产量煤矿A1613221750B14 13191560c20192350-0103070最低需要量507030不限最高需求量1

1 测试题目四 一、名词解释（本题 10 分，每小题 2 分） 1、可行解；2、二人有限零和对策；3、影子价格；4、0-1 规划问题；5、最小费用最 大流问题。 二、（本题 15 分）某纺织厂生产 A、B 两种布料，平均生产能力均为 1 千米/小时，工 厂正常生产能力是 80 小时/周。又 A 布料每千米获利 2500 元，B 布料每千米获利 1500 元。已知 A、B 两种布料每周的市场需求量分别是 70 千米和 45 千米。现该厂确定一 周内的目标为：第一优先级：避免生产开工不足；第二优先级：加班时间不超过 10 小 时；第三优先级：根据市场需求达到最大销售量；第四优先级：尽可能减少加班时间。 试建立该问题的目标规划数学模型（只建模，不求解）。 三、（本题 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 用单纯形法求得最终表如下 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中一个保持不变时，另一个在什么范围内变化， 上述最优基保持不变。 四、（本题 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 不限

五、（本题15分）根据下表所给的资料绘制网络计划图，并计算时间参数，最后确定关键路线。工序紧前工序工序时间/d工序紧前工序工序时间/d23AG、MGB、CBH4H5-7C12A、L-DL3K1F、IEc5L7B、CF5MC3A、E六、（本题20分）用割平面法求整数规划问题的最优解：maxz=7x+9x2[- X, + 3x2 ≤ 6s.7x +x, ≤35x,x≥0且为整数其中，下表为整数规划问题的松弛问题的最优表，7c,→900bXBCBxiX2X3X49011/227/27/22X21073/229/2-1/22xi0028/11-15/11c-"七、（本题10分）求下图顶点①到顶点③的最短路及最短路长。9②+?91206en61071?15452

2 五、（本题 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 六、（本题 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 其中，下表为整数规划问题的松弛问题的最优表。 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 七、（本题 10 分）求下图顶点①到顶点⑧的最短路及最短路长