天津大学考研试题

天津大学研究生运筹学A 试题

学院班级_________ ___ 姓名_____ _______ 学号___ __ _______ 成绩____________ 一、填空(15%)

1. 设有线性规划问题[min]f =CX , X ∈D={X |AX =b , X ≥0}，有一可行基B (为A 中的前m 列)，记相应基变量为X B ，价格系数为C B ；相应于非基N 的非基变量为X N ，价格系数为C N ，则相应于B 的基本可行解为X =_____________，用非基变量来表示基变量的表达式为X B =___________，用非基变量表示目标函数的表达式为f =___________，B 为最优基的条件是_____________。

2. 某足球队要从1、2、3、4、5号五名队员中挑选若干名上场，令 ，

请用x i 的线性表达式表示下列要求：(1) 若5号上场，则2号不上场：______ ________⎩⎨⎧=号不上场第号上场

第i i x i 015,,1"=i ；(2) 只有3号上场，4号才上场：_________ __________。

3. 动态规划的研究对象是______ ______决策问题，其递推求解的理论基础是_____ _______最优性原理。

v 1

v 2 v 3

v 4 v 5

v 6

v 7

5

6

347 35 6

3241

4. 求右图网络的最小部分树 (用粗线在图上标 出)，最小权和为____________。

5. 运筹学中定量分析的一般过程用图示表示为：

___________________________________________________________________________________。

二 (30%)、某电冰箱厂生产单、双门两种冰箱，每台所需组装时间、调试时间、销售收入及该厂的组装、调试能力如下表，电机每月进货最多50个（每台冰箱用1台电机），令x 1、x 2分别为单、双门冰箱的月产量。现工厂需拟订使总收入Z 为最大的生产计划。

单门

双门

月生产能力(时)

组装时间(时) 10 15 1000 调试时间(时) 2 5 270 销售收入(元)

1000 1300

(1) 写出此问题的数学模型(约束条件依次为：组装时间、调试时间、电机数)。 (2) 下面是用单纯形法求解此问题过程中的一个不完全表，请将表完成。 C B

X B B -1b

1000 x 1

1300 x 2

0 x 3

0 x 4

0 x 5

x 3 –5 1 0 –15 x 4 –3 0 1 –5 x 2

1 0 0 1 σj

(3) 上表是否为终表？为什么？若是，请写出最优生产计划、最大销售收入和电机的影子价格，在执行这一最优计划后，哪种资源有剩余？余多少？ (4）写出上述规划的对偶规划模型及其最优解。

（5）若每月可再得到电机供货4台，每台购买价1150元，这种供货是否值得接受？说明原因。 （6）单门冰箱的价格提升至多少时才有可能生产？

（7）现又设计出三门冰箱，每台需要组装时间20小时，调试时间10小时，销售收入1600元，是否应考虑生产三门冰箱？

（8）试分析：若在（1）的模型的第3个约束（电机数）的两端同乘以2，记 表示这新的约束相应的影子价格，那么 与原 （即原电机影子价格）是否相等？若不相等，请给出二者

的关系式，并说明原因。 3y

3y

∗

3y

三 (15%)、证明线性规划中的互补松弛定理：设（P ）[max]z =CX , X ∈ {X |AX ≤b , X ≥0}，（D ）[min]w =Yb , Y ∈ {Y |YA ≥b , Y ≥0}，若Y X ,分别是（P ）、（D ）的可行解，则Y X ,是（P ）、（D ）的最优解的充要条件是 X Y X

Y s

s

=；并解释互补松弛定理的经济意义。

四（15%）、有一艘装运N 种货物的船，它的最大载重量是W ，其中第j 种货物每件重量为w j ，价值为r j (j =1, …, N )。在不超过船的最大载重条件下，拟确定每种货物各装多少件可使所载货物的总价值最大。试就以下两小题选答．．

一题： 1. (1) 写出此问题的数学规划模型；(2) 拟用动态规划方法求解，请写出此问题的阶段变量、状态变量、决策变量、状态转移、阶段指标、指标函数、基本方程(不解)。

j w j r j 2. 若最大载重量W =5，共有N =3种货物，每种货物每件重量w j 和价值r j 如右表所示。请用动态规划方法求解使总价值最大的装载方案。 1 1 30 2 3 80 3 2 65

五 (10%)、过纽约ALBANY 的北-南高速公路，路况通过能力如下图所示，图中弧上数字单位：千辆/小时，求（1）该路网能承受的北-

南向最大流量；（2）若要将整个路网的北-南向通过能力扩充2千辆/小时，并只能在一条路段上扩充，请指出一个路段选择方案，并说明原因。

六 (15%)、某项工程有关资料如右表，

工序紧前工序平均工序时间(周) 估计的工序时间方差2

σ

(1) 画出工程网络图，确定关键工序及期望工期； A — 1 0.67 (2) 求工程在30周内完成的概率。

B — 1 0.67

C A 1.4 3.00

D B 1 1.78

E A 、D

2 1.67 F A 、D

7 2.78

Z 0 1 2 3

)(z Φ 0.50 0.84 0.97 0.99

G E 、F

5 0.33 H F 4 1.11

(3) 若要压缩整个工程的工期，应当在什么工序上压缩？如果网络中有多条平行的关键路线时该怎样压缩？

I J

G 、H

I

12 2.66 0.00 1