x5 x 6 17 x1 4 x 2 8x 3 2x3 2x4 x 6 3x 7 2 x 4x 10x 4 2 x 7 9 1 2 x j 0 j 1, ,7
max z x1 (1 x2 ) x3 x1 x2 x3 1 xj 0 j 1,2,3
四．用隐枚举法求解下列 0-1 规划问题（20 分）

五．用动态规划方法求解下列问题（25 分）

六． 今有三个仓库运送某种产品到四个市场上去， 仓库的供应量是 20， 20 和 100， 市场需求量是 20，20，60 和 20，仓库与市场之间的路线上的容量如下表（容量 零表示两点间无直接的路线可通） 。用图论方法确定现有路线容量能否满足市场 的需求，若不能，应修改哪条线路的容量。 （20 分）
max z 5x1 7 x2 10 x3 3x4 x5 x1 3x2 5x3 x4 4 x5 2 2 x1 6 x2 3x3 2 x4 2 x5 0 2 x2 2 x3 x4 x5 1 1 j 1, ,5 xj 0
四．从甲, 乙, 丙, 丁, 戊五人中挑选四人去完成四项工作，已知每人完成各项工 作的时间如下表所示。规定每项工作只能由一个人去单独完成，每个人最多承担 一项工作，假定甲必须保证分配到工作，丁因某种原因不同意承担第四项工作。 在满足上述条件下， 如何分配工作， 使完成四项工作总的花费时间最少。 （20 分） 人 一 二 三 四 工作 甲 10 5 15 20 乙 2 10 5 15 丙 3 15 14 13 丁 15 2 7 6 戊 9 4 15 8 五．求 V1 到各点的最短路及最短路径。 （20 分）
副 正
B1 * *
B2
B3 *
B4
B5 *
A1 A2 A3 A4 A5
*
* *
* *
七．填空： （20 分） 1．某工程公司拟从四个项目中选择若干项目，若令 1，第i个项目被选中； i 1,2,3,4 xi 0，第i个项目未被选中；
=
用 i 的线性表达式表示下列要求： （1）从 1，2，3 项目中至少选 2 个： （2）只有项目 2 被选中，项目 4 才能被选中：
一．用单纯形法求解下述线性规划问题（20 分）

max z 4 x1 x 2 x1 x 2 2 x1 4 x 2 4 x1 2 x 2 8 x1 , x 2 0
二．设一线性规划问题为（25 分）
max z 2 x1 7 x2 x3 x1 x2 x3 6 x 2x 4 2 x 1 j 0 j 1, ,3
西南交通大学 2008 年硕士研究生入学考试试卷 1
试题代码：453 试题名称：运筹学
考生注意∶
１．本试题共 七 题，共 3 页，请考生认真检查； ２．请务必将答案写在答卷纸上，写在试卷上的答案无效。
题号 得分 签字 一 二 三 四 五 六 七 总分
一．某炼油厂生产三种牌号的汽油，70#，80#和 85#汽油。每种汽油有不同的辛 烷值和含硫量的质量要求并由三种原料油调和而成。 每种原料也有不同的质量指 标。每种原料每日可用数量、质量指标和生产成本见表 1，每种汽油的质量要求 和销售价格见表 2。问该炼油厂如何安排生产才能使其利润最大？假定在调和中 辛烷值和含硫量指标都符合线性相加关系。试建立数学模型。 （25 分) 表 1 序号 i 原料 辛烷值 含硫量（％） 成本（元/吨） 可用量（吨/日） 1 直馏汽油 62 1.5 600 2000 2 催化汽油 78 0.8 900 1000 3 重整汽油 90 0.2 1400 500 表2 序号 j 产品 辛烷值 含硫量（％） 销售价（元/吨） 1 70＃汽油 ≥70 ≤1 900 2 80＃汽油 ≥80 ≤1 1200 3 85＃汽油 ≥85 ≤0.6 1500 二．用对偶单纯形法求解下列线性规划问题： （25 分）
1 0 0
x3
-1/5 7/5 -3/5
x4
2/5 1/5
x5
-1/5 2/5
B b
-1
x2
x1
8/5 9/5
cj z j
-29/5 -M+2/5
X4 为松弛变量，X5 为人工变量， 1．上述模型的对偶模型为：
； 2．对偶模型的最优解为： 3．当两种资源分别单独增加一个单位时，目标函数值分别增加 ； ；
4 增加一个约束条件
x1 2x3 2
三．某种产品今后四周的需求量分别为 300，700，900，600 件，必须得到满足。ห้องสมุดไป่ตู้已知每件产品的成本在起初两周是 10 元，以后两周是 15 元。工厂每周能生产这 种产品 700 件，且在第二、三周能加班生产。加班后，每周可增产 200 件产品， 但成本每件增加 5 元。产品如不能在本周交货，则每件每周存贮费是 3 元。问如 何安排生产计划，使总成本最小，要求建立运输问题数学模型求解。 （25 分） 四．某校蓝球队准备从以下 6 名预备队员中选拔 3 名为正式队员，并使平均身高 尽可能高，这 6 名预备队员情况如下表所示，试建立数学模型。 （20 分） 队员的挑选要满足下列条件： 2 3 4 5 少补充一名后卫队员； 大李或小田中间只能入选一名； 最多补充一名中锋； 如果大李或小赵入选，小周就不能入选。
市场 仓库
1 30 0 20 20
2 10 0 10 20
3 0 10 40 60
4 40 50 5 20
供应量 20 20 100
1 2 3 需求量
七．下列叙述中正确的是 （ ） （20 分） 4 图解法与单纯形法，虽然求解的形式不同，但从几何上理解，两者是一致的； 5 若线性规划的原问题有多重最优解，则其对偶问题也一定具有多重最优解； 6 如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数 k， 最优调运方案将不会发生变化； 7 对于极大化问题 max Z =
max z 5 x1 12 x 2 4 x3 x 2x x 5 2 3 1 2 x1 x 2 3 x3 2 x1 , x 2 , x3 0 用单纯形法求解，得其终表如下： 5 12 c
j
4
0
-M
CB X B
12 5
x1
0 1 0
x2
x
； ；
2．用表上作业法求解某运输问题，若已计算出某空格的检验数为-2，则其经 济意义是 该空格出发进行调整，设调整量为 2，则调后可使总运费下降 10 动态规划中的 Bellman 最优性原理是 。 ，若从 ；
西南交通大学 2008 年硕士研究生入学考试试卷 4
试题代码：453 试题名称：运筹学
min W bij xij
n
n
重复部分后，恰好构成该图的最小支撑树。
西南交通大学 2008 年硕士研究生入学考试试卷 3
试题代码：453 试题名称：运筹学
考生注意∶
１．本试题共 七 题，共 3 页，请考生认真检查； ２．请务必将答案写在答卷纸上，写在试卷上的答案无效。
题号 得分 签字 一 二 三 四 五 六 七 总分
和
-1 4．最优基的逆矩阵 B =

5．如果原问题增加一个变量，则对偶问题的可行域将可能变大还是变小？ . 三．求解下列各题（解题方法自选）（20 分）
min z 5x11 6x12 10x13 8x21 10x22 12x23

预备队员 大张 大李 小王 小赵 小田 小周
号码 4 5 6 7 8 9
身高（厘米） 193 191 187 186 180 185
位置 中锋 中锋 前锋 前锋 后卫 后卫
五．某高校拟开设文学、艺术、音乐、美术四个学术讲座。每个讲座每周下午举 行一次。 经调查知， 每周星期一至星期五不能出席某一讲座的学生数如下表： （20 分） 星期 讲座 一 二 三 四 五
max z 2 x1 x2

x1 x2 x3 5 2 x2 x3 5 4 x2 6 x3 9 x1 , x2 , x3 0
三．已知某运输问题的产销平衡表与单位运价表如下表所示，B2 地区需要的 115 单位必须满足，试确定最优调拨方案。 （20 分） Bj Ai B1 B2 B3 A1 10 15 20 A2 20 40 15 A3 30 35 40 销量 25 115 60 B4 20 30 55 30 B5 40 30 25 70 产量 50 100 130
4 66 66 76
七．用单纯形法解线性规划问题，如何判断下列问题： （15 分） 1. 无可行解； 2. 有多重解； 3. 有无界解。
西南交通大学 2008 年硕士研究生入学考试试卷 2
试题代码：453 试题名称：运筹学
考生注意∶
１．本试题共 七 题，共 3 页，请考生认真检查； ２．请务必将答案写在答卷纸上，写在试卷上的答案无效。
六．某公司有资金 4 百万元向 A，B，C 三个项目追加投资，各个项目可以有不 同的投资额（以百万元为单位） ，相应的效益值如下表。问怎样分派资金，使总 效益值最大，试用动态规划方法求解。 （25 分） 项目 A B C 0 38 40 38 1 41 42 64 投资额 2 48 50 68
3 60 60 78
考生注意∶
１．本试题共 七 题，共 3 页，请考生认真检查； ２．请务必将答案写在答卷纸上，写在试卷上的答案无效。
题号 得分 签字 一．对约束条件（20 分） 一 二 三 四 五 六 七 总分
说明解 X=（1,2,1,0,0,0,0）T 是不是基可行解，假定不是，试找出一个基可 行解。 二．已知线性规划问题（20 分）