北京交通大学期中考试试题答案
课程名称：管理运筹学 2006~2007学年第二学期 出题教师：胡天军
所在学院：交通运输 班级 姓名 学号
（请考生注意本试卷共有7道大题） 题号 得分 一 二 三 四 五 六 七
一、判断下面说法是否正确（10分）
1． 线性规划问题的每一个基解对应可行域的一个顶点；
2． 用单纯形求解标准型式的线性规划问题时，与σj>0对应的变量都可以被选做换入
变量，而选择最大正检验数σk对应的变量xk作为换入变量，将使目标函数值得到最快的增长。
3． 单纯形法计算中，如不按最小比值原则选取换出变量，则在下一个解中至少有一个
基变量的值为负；
4． 单纯形法的迭代计算是从一个可行解转换到目标值更大的另一个可行解；
5． 根据对偶问题的性质，当原问题为无界解时，对偶问题无可行解，反之，当对偶问
题无可行解时，其原问题具有无界解；
6． 若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优解； 7． 已知yi为线性规划的对偶问题的最优解，若yi>0，说明在最优生产计划中第i种
资源已完全耗尽；若某种资源的影子价格等于k,在其他条件不变的情况下，当该种资源增加5个单位时，相应的目标函数值将增大5k； 8． 运输问题是一种特殊的线性规划模型，因而其求解结果也可能出现下列四种情况之
一：有唯一最优解，有无穷多最优解，无界解，无可行解； 9． 如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数k，最优调
运方案将不会发生变化； 10．
二、某公司制造三种产品A、B、C，需要两种资源（劳动力和原材料），现要确定总利润最
大的生产计划，列出下述线性规划(35分)
maxz?3x1＋x2＋5x3（劳动力）?6x1＋3x2＋5x3?45 ?3x＋4x＋5x?30（原材料）?123?x，x，x?023?1*
*
指派问题效率矩阵的每个元素都乘上一个相同的常数k,将不影响最优指派方
案。
求：（1）线性规划问题的最优解；
（2）求对偶问题的数学模型及其最优解；
(3) 最优解不变的情况下，求产品A的利润允许变化范围；最优解不变的情况下， （4）假定能以10元的价格购进15单位的材料，这样做是否有利，为什么？ （5）当可利用的资源增加到60单位时，求最优解。 （6）当产品B的原材料消耗减少为2个单位时，是否影响当前的最优解，为什么？ （7）增加约束条件2x1+x2+3x3≤20，对原最优解有何影响，对对偶解有何影响？
三、某钻井队要从8个可供选择的井位中确定4个钻井探油，使总的钻探费用最省。若8
个井位的代号是s1、s2、…、s8，相应的钻探费用为c1、c2、…、c8，并且井位满足下列条件限制：（10分）
i. 或选择s1和s7，或选择s8； ii. s6和s7中选一个； iii. iv.
s2和s5不能同时选；
选择了s1的话就不能选择s4；
v. 选择了s2的话必须选择s3
试用：整数规划方法建模。
四、A、B两个煤矿负责供应甲、乙、丙三个城市煤炭。已知A、B两矿年产量、三个城市的需求量以及从两煤矿至各城市煤炭运价如下表。由于供不应求，经协商，甲城市必要时可少供应0－30万吨，乙城市需求须全部满足，丙城市需求不少于270万吨。试求：将甲、乙两矿煤炭全部分配出去，满足上述条件又使总运费最低的调运方案。（15分） 产 销 A B 销量（T） 甲 15 21 320 乙 18 25 250 丙 22 16 350 产量 400 450
五、分配甲、乙、丙、丁四人去完成5项任务。每人完成各项任务时间如下表所示。由于任务数多于人数，故规定其中有一人可兼完成两项任务，其余三人每人完成一项，试确定总花费时间最少的指派方案。（15分）
甲 乙 丙 丁 A 25 39 34 24 B 29 38 27 42 C 31 26 28 36 D 42 20 40 23 E 37 33 32 45 六、某公司打算将3千万元资金用于改造扩建所属的3个工厂，每个工厂的利润增长额与所分配的投资有关。各工厂在获得不同的投资额时所能增加的利润如下表所示，问应如何分配资金，使公司总的利润为最大（15分） 利润 投资 0 1千万 2千万 3千万 工厂 1 2 3
0 0 0 2.5 3 2 4 5 6 10 8.5 9 答案：
一、1.错 2.对 3.对 4.错 5.错
6.错 7.错 8.错 9.对 10.错 二、解：（1）首先将问题标准化：
maxz?3x1＋x2＋5x3?6x1＋3x2＋5x3?x4?45 ?3x＋4x＋5x?x?30?1235?x，x，x,x,x?02345?1cj CB 0 0 0 5 （2）
3 b 45 30 15 6 x1 6 3 3 3 3/5 0 3 1 x2 4 1 -1 4/5 -3 5 x3 5 【5】 5 0 1 0 0 x4 1 0 0 1 0 0 0 x5 0 1 0 -1 1/5 -1 XB x4 x5 x4 x3 ?i 9 6 最优解为X*=(x1,x2,x3,x4,x5)T=(0,0,6,15,0)T，最优目标值z*=30
minw?45y1?30y2?6y1?3y2??3y1?4y2??5y1?5y2?y?0,y2?1?3?1?5?0
y1*=0,y2*=1 （3）?c1?0,c1?3
（4）有利。因为单位材料的影子价格是1元，10元钱购进15单位的材料的单位价格
为2/3元，低于影子价格。同时，在保持最优基不变的情况下?30?b2?15
购进15吨的原材料，最优基不变。该材料的影子价格仍为1元。
（5）
b?Bb?1??0???1??45???15?
1???????60??12???5?'?1cj CB 0 XB x4 b -15 3 x1 3 1 x2 -1 5 x3 0 0 x4 1 0 x5 【-1】 5 0 5 x3 x5 x3 12 15 9 3/5 0 -3 6/5 -3 4/5 -3 1 3/5 -2 1 0 0 1 0 0 0 -1 1/5 -1 1/5 -1 1 0 0 最优解为X*=(x1,x2,x3,x4,x5)T=(0,0,9,0,15)T，最优目标值z*=45 （6）x2在最有表是非基变量，该产品的原材料消耗只影响x2的检验数。
P2?B'?1P2?1??3??1? 1??2?????25??????5???1?1??0???2?c2?CBB?1??0P2'?1?5??2???1???5??2?0
所以最优解不变（7）增加的约束条件，相当于增加了一个约束方程
2x1?x2?3x3?x6?20
cj CB 0 5 0 0 5 0 三、解：
2 b 15 6 20 15 6 2 x1 3 3/5 2 0 3 3/5 4/5 0 4 x2 -1 4/5 1 -3 -1 4/5 -7/5 -3 1 x3 0 1 3 0 0 1 0 0 0 x4 1 0 0 0 1 0 0 0 0 x5 -1 1/5 0 -1 -1 1/5 -3/5 -1 0 x6 0 0 1 0 0 0 1 0 XB x4 x3 x6 x4 x3 x6 对原问题的最优解无影响，对对偶问题的最优解也无影响。 ?1令：xi???0?x1?x7?x8?1?x?x7?1?6??x2?x5?1??x1?x4?1?x?x?023???xi?0或1当选择si当不选择simaxz?c1x1?c2x2?c3x3?c4x4?c5x5?c6x6?c7x7?c8x8
四、
解：(1)依题意得产销平衡表如下： 产 甲’ 甲’’ 销 A B C 销量（T） 15 21 M 290 15 21 0 30 18 25 M 250 22 16 M 270 22 16 0 80 400 450 70 乙 丙’ 丙’’ 产量
(2)做初始的调运方案（伏格尔法） 产 甲’ 销 A B C 15 150 140 M 21 30 0 250 乙 0 1 0 21 M-8 24 M 18 25 15 21 M 270 丙’ 12 0 16 22 16 M 12 0 0 16 250 18 25 270 M 22 16 10 70 80 丙’’ 22 16 0 U -6 0 -16 0 70 22 16 450 400 甲’’ 乙 丙’ 丙’’ 产量 销量（T） 290 30 （3）用位势法进行检验 产 甲’ 销 A B C V 0 M-5 21
(4) 做闭回路调整
0 15 21 0 15 21 甲’’ 0 M -5