北京交通大学交通运输学院《942管理运筹学》历年考研真题汇编（含部分答案）

目录

2015年北京交通大学交通运输学院942

管理运筹学考研真题

2014年北京交通大学交通运输学院942

管理运筹学考研真题

2013年北京交通大学交通运输学院942

管理运筹学考研真题

2012年北京交通大学交通运输学院942

管理运筹学考研真题

2011年北京交通大学交通运输学院942

管理运筹学考研真题

2010年北京交通大学交通运输学院942

管理运筹学考研真题

2010年北京交通大学交通运输学院942

管理运筹学考研真题及详解

2009年北京交通大学交通运输学院942

管理运筹学考研真题

2009年北京交通大学交通运输学院942

管理运筹学考研真题及详解

2008年北京交通大学交通运输学院942

管理运筹学考研真题

2008年北京交通大学交通运输学院942

管理运筹学考研真题（含部分答案）

2007年北京交通大学交通运输学院417

管理运筹学考研真题

2007年北京交通大学交通运输学院417

管理运筹学考研真题及详解

2006年北京交通大学交通运输学院417

管理运筹学考研真题

2006年北京交通大学交通运输学院417

管理运筹学考研真题及详解

2005年北京交通大学交通运输学院417

管理运筹学考研真题

2005年北京交通大学交通运输学院417

管理运筹学考研真题及详解

2004年北京交通大学交通运输学院管

理运筹学考研真题

2004年北京交通大学交通运输学院管

理运筹学考研真题及详解

2003年北方交通大学交通运输学院管

理运筹学考研真题

2003年北方交通大学交通运输学院管

理运筹学考研真题及详解

2002年北方交通大学交通运输学院管

理运筹学考研真题

2002年北方交通大学交通运输学院管

理运筹学考研真题及详解

2001年北方交通大学交通运输学院管

理运筹学考研真题

2001年北方交通大学交通运输学院管

理运筹学考研真题及详解

2000年北方交通大学交通运输学院管

理运筹学考研真题

2015年北京交通大学交通运输学院942管理运筹学考研真题

2014年北京交通大学交通运输学院942管理运筹学考研真题

2013年北京交通大学交通运输学院942管理运筹学考研真题

2012年北京交通大学交通运输学院942管理运筹学考研真题

2011年北京交通大学交通运输学院942管理运筹学考研真题

2010年北京交通大学交通运输学院942管理运筹学考研真题

2010年北京交通大学交通运输学院942管理运筹学考研真题及详解

北京交通大学2010年硕士研究生入学考试

科目代码：942科目名称：管理运筹学

一、判断（正确的打“∨”，错误的打“×”）

1．线性规划问题的每一个基解对应可行域的一个顶点；（北京交通大

学2010年研）

【答案】×

【解析】基解不一定是可行解，基可行解对应着可行域的顶点。

2．若、分别是某一线性规划问题的最优解，则也是

该线性规划问题的最优解，其中、为正的实数；（北京交通大学

2010年研）

【答案】×

【解析】必须规定，当一线性规划问题存在两个最优

解时，则它一定存在无数个最优解，

3．已知为线性规划问题的对偶问题的最优解，若，则说明在最

优生产计划中第种资源已经完全耗尽；（北京交通大学2010年研）

【答案】∨

【解析】对偶问题互补松弛性质中；当时，有，

表明在最优生产计划中第种资源已经完全耗尽。

4．整数规划问题最优解的目标函数值一定优于其相应线性规划问题最

优解的目标函数值；（北京交通大学2010年研）

【答案】×

【解析】因为附加了整数条件，其可行域比其相应线性规划问题的可行

域减小，故整数规划问题最优解的目标函数值一定不优于其相应线性规

划问题最优解的目标函数值。

5．指派问题效率矩阵的每个元素乘以同一大于0的常数，将不影响最

优指派方案；（北京交通大学2010年研）

【答案】∨

【解析】效率矩阵每个元素乘以同一大于0的常数，即目标函数的系数

同时增大k倍，不会影响最优基的变化，故不影响最优指派方案。

6．如果图T是树，则T中一定存在两个顶点，它们之间存在两条不同的

链；（北京交通大学2010年研）

【答案】×

【解析】连通且不含圈的无向图称为树。因此任意两点间必定只有一条

链。

7．任一图都存在支撑子图和支撑树；（北京交通大学2010年

研）

【答案】×

【解析】当图中存在一个顶点，其次为0时，则该图不存在支撑树。

8．网络图中任何一个结点都表示前一工序的结束和后一工序的开始；

（北京交通大学2010年研）

【答案】×

【解析】网络图的起始点只表示一工序的开始，结束点只表示一工序的

结束。

9．结点最早时间同最迟时间相等的点连接的线路就是关键路线；（北

京交通大学2010年研）

【答案】∨

【解析】关键路线是指总时差为零的工作链，而该工作链是由一系列最

早时间同最迟时间相等的点连接而成的。

10．假如到达排队系统的顾客为普阿松流，则依次到达的两名顾客之间

的间隔时间服从负指数分布；（北京交通大学2010年研）

【答案】∨

【解析】设N（t）为时间[0，t]内到达系统的顾客数，则为参

数为的普阿松流的充要条件是：相继到达时间间隔服从相互独立的参

数为的负指数分布。

11．运输问题是一种特殊的线性规划模型，因而其求解结果也可能出现

四种情况之一：有唯一最优解，有无穷多最优解，无界解，无可行解；

（北京交通大学2010年研）

【答案】×

【解析】运输问题是一种特殊的线性规划模型，它总存在可行解，或是

存在唯一最优解，或是有无穷最优解。

12．单纯形法计算中，选取最大正检验数对应的变量作为换入变

量，将使目标函数值得到最快的增长。

【答案】∨

【解析】选择任何一个大于零的都可以，

由上式可以看出，将最大正检验数对应的变量作为换入变量，将使

目标函数值得到最快的增长。

二、简答

1．试简述求解整数规划模型的分枝定界法剪枝的几种情况；（北京交

通大学2010年研）

答：（1）某枝已经达到其范围内的最优解；

（2）某枝域内没有可行解时，即是不可行域；

（3）某枝所得数据不优于当前最优解时。

2．试写出标准指派问题的线性规划问题；（北京交通大学2010年研）

答：设，

则得线性规划模型

3．试写出求解最短径路的Dijkstra算法的步骤；（北京交通大学2010年

研）

答：步骤：

（1）给

（2）若vi点为刚得到P标号的点，考虑这样的点vj，（vi，vj）属于E，

且vj为T标号。对vj的T标号进行如下修改：

（3）比较所有具有T标号的点，把最小者改为P标号，即：

当存在两个以上最小者时，可同时改为P标号。若全部点均为P标号时停

止。否则用代转回（2）。

4．试写出M/M/1排队系统的Little公式；（北京交通大学2010年研）

答：

三、（40分）某厂生产Ⅰ、Ⅱ、Ⅲ三种产品，其所需劳动力、原材料等

有关数据如下：每件产品Ⅰ分别需要劳动力和原材料6个小时和3公斤，

每件产品Ⅱ分别需要劳动力和原材料为3小时和4公斤，每件产品Ⅲ分别

需要劳动力和原材料为5小时和5公斤；拥有的劳动力和原材料总数分别

为45小时和30公斤；又知Ⅰ、Ⅱ、Ⅲ三种产品的单件利润分别为3、1、

4元。（北京交通大学2010年研）

要求：

1．写出该厂获得最大的生产计划问题的线性规划模型并求出最优解；

答：设三种产品的产量分别为x1、x2、x3，则得模型：

将上述问题改写为标准形式为：

用单纯形法计算如下：

cj31400

CBXBbx1x2x3x4x5

0x44563510

0x53034[5]01

31400

0x415[3]－101－1

4x363/54/5101/5

3/5－11/500－4/5

3x151－1/301/3－1/3

4x33011－1/52/5

0－20－1/5－3/5

得到最优解，即生产Ⅰ、Ⅲ各5和3件。

2．写出该线性规划问题的对偶问题，并求对偶问题的最优解；

答：对偶问题：

由及上述最终单纯形表可知，。

3．产品Ⅰ的利润在什么范围内变化时，上述最优计划不变？

答：保持最优计划不变，即保持各非基变量检验数非正，则

解得。

4．如果设计一种新产品Ⅳ，单件产品消耗劳动力8小时，原材料2公

斤，每件可获利3元，问该产品是否值得生产？

答：新产品的产量为x6，则相对约束矩阵多一列向量，在最终

单纯形表中为

，其检验数为

，故值得生产。

5．如果劳动力数量不变，原材料可以从市场购买，每公斤0.4元，问该

厂是否购买原材料来扩大生产，以购买多少为宜？

答：设购买，则①

②，故可以购买原材料来扩大生产。

由①②两式得，即购买15公斤时可获得最大效益。

四、（16分）某公司有甲，乙，丙三个工厂和A，B，C三个客户，这三

个工厂在下一时期将分别生产某种产品300，500和400件，公司计划卖

给客户A，B，C的产品数量分别为400，300，100件，客户D想尽可能

多地购买剩下的商品。工厂卖给各客户单位产品的利润如下表。问如何

安排供应使该公司总利润最大。

答：该问题属于平衡运输问题，客户D将购买300＋500＋400－（400＋

300＋100）＝400（件）商品。则由沃格尔法得初始方案，并用位势法

得各空格检验数[]所示：

ABCD供给量行差

甲[－2]15[－3]13[－1]1230014300111

乙2001830017[1]15[－3]1250012

丙20013[－2]10100910010400322

需求量400300100400

3432

列差332

234

空格[乙C]检验数为正，故调整其所在回路，调整值为min[200，100]＝

100并检验得：

ABCD供给量

甲[－2]15[－3]13[－2]1230014300

乙100183001710015[－3]12500

丙30013[－2]10[－1]910010400

需求量400300100400

所有检验数均小于零，即得最优方案如下：

ABCD供给量

甲300300

乙100300100500

丙300100400

需求量4003001004001200

五、（20分）用动态规划方法求解下列整数规划问题：（北京交通大学

2010年研）

答：将该过程分为3个阶段，决策变量为，状态变量为，表示第k阶

段开始时候的状态（k＝1，2，3），其中，最优指标函数

，表示第k阶段状态为时，第k阶段至第3阶段

的最优值，且，表示每个阶段的指标函数。采用

逆推法。

k＝3时，

k＝2时，

k＝1时，。

***

所以得x1＝1，x2＝2，x3＝0，maxZ＝18。

六、（14分）某理发店只有一个理发员，来理发的顾客到达过程为

posson流，平均5人/小时；理发时间服从负指数分布，平均需要10分

钟；店内备有5把椅子供顾客等候，多余顾客将到其他理发店理发。

（北京交通大学2010年研）

求：

（1）该理发店忙的概率；

（2）该店内恰有2个顾客的概率；

（3）在该店内的平均顾客数；

（4）每位顾客在该店内的平均逗留时间；

（5）等待服务的平均顾客数；

（6）每位顾客平均等待时间；

（7）顾客损失的概率。

答：该问题属于M/M/1/N模型，，，N＝5。

（1），∴1－P0＝0.7494，即为理发店忙的概率。

（2）

∴。

（3）。

（4）。

（5）。

（6）顾客的平均等待时间是。

（7），即顾客损失的概率。

2009年北京交通大学交通运输学院942管理运筹学考研真题

2009年北京交通大学交通运输学院942管理运筹学考研真题及详解

北京交通大学2009年硕士研究生入学考试

科目代码：942科目名称：管理运筹学

一、（50分）已知线性规划问题如下：

1．求该问题的最优解；

答：用对偶单纯形法计算如下：

ci251/200

CBXBbx1x2x3x4x5

0x4－3－1－2－1/210

0x5－90－1[－3]01

251/200

0x4－2/3－1－11/601[－1/6]

1/2x3301/310－1/3

－2－29/600－1/6

0x696110－61

1/2x36241－20

13010

得最优解，X*＝（0，0，6）T，minz＝1/2×6＝3。

2．写出该线性规划问题的对偶问题，并求对偶问题的最优解；

答：

由上最终单纯形表可得，，maxw＝3

3．分别确定x2、x3的目标函数系数c2、c3在什么范围内变化，最优解不

变？

答：（1）c2变化，最优解不变，要保证，解得，即

。

（2）c3变化，最优解不变，要保证，，解得

，即。

4．求约束条件右端值由变为时的最优解；

答：代入最终单纯形表中，，因此不是最优解。

ci251/200

0x6－36110[－6]1

1/2x34241－20

13010

0x41/2－1－11/601－1/6

1/2x3401/310－1/3

029/6001/6

得新的最优解是X*＝[0，0，4]T，minz＝1/2×4＝2。

5．求增加新的约束条件x1＋2x2＋x3≤5时的最优解。

答：加入松弛变量x6得下表

cj251/2000

CBXBbx1x2x3x4x5x6

0x4－3－1－2－1/2100

0x5－90－1[－3]010

0x6－5－1－2－1001

251/2000

0x4－2/3－1－11/601－1/60

1/2x3301/310－1/30

0x6－2－1－5/300[－1/3]1

229/6001/60

0x41/3－1/2－1010－1/2

1/2x3512100－1

0x5635001－3

3/240001/2

得最优解X*＝[0，0，5]T，minz＝1/2×5＝5/2。

二、（25分）某铁路企业承担A、B、C三个城市之间的城际旅客列车运

输任务，列车的出发和到达时间如下表所示：

设旅客列车从到达某站到出发至少需要2个小时的准备时间，试制定一

个最佳的旅客列车车底接续方案，使该铁路企业所使用的车底数量最

少。

答：题中，将达到某城市的列车当成是要完成工作的工作人员，而在该

城市出发当成是要完成的工作，则3座城市的列车工作效率如下所示，

数据是执行任务需等待时间。

A城市：

到达出发T101T103T105T107T109

T1022381315

T10419202568

T10615162124

T10822234911

T110141520253

B城市

到达出发T102T104T106

T10116233

T10315222

T105101721

C城市

到达出发T108T110

T107715

T109513

则对于A城市，利用匈牙利算法指派任务如下：

初次指派为：，◎的个数少于54，故进行划线覆

盖所有的零元素

；

继续求解，，依然不符合，故继续划线覆盖所有

零元素，并最终求得最优解

，即A城市中

到达出发T101T103T105T107T109

T1023

T10419

T1062

T1084

T1103

所需车底数是3；

同理得B城市的指派为，所需车底数为2；

C城市指派为，需要车底数为2。

综上，该企业总的车底数最少需要是7个。

三、（20分）已知运输问题的运价及产销平衡表如下：

要求：

1．用最小元素法求该运输问题的初始解，并进一步求出最优解；

2.A3→B3的单位运价C33变为什么值时，有无穷多最优解？并进一步给

出两个新的最优方案。

答：（1）该运输问题的初始解是：

B1B2B3B4产量

A11010

A23101225

A3325

销量6101212

利用位势法计算个空格的检验数为：

产量

B1B2B3B4

A1[1][0]10[1]10

A2310[－2]1225

A33[13]2[7]5

销量6101212

空格A2B2检验数小于0，故调整其所在回路，调整量为min（2，3）＝

2，得新方案，并检验之，如表中所示：

B1B2B3B4产量

A1[－1][－2]10[－1]10

A211021225

A35[13][2][7]5

销量6101212

仍不是最优方案，故继续调整，最后得最终方案如下：

B1B2B3B4产量

A11010

A210121225

A355

销量6101212

（2）A3B3的检验数为C33－12＋10－6＝0时，即C33＝8时，有无穷多最

优解。

新方案一：

B1B2B3B4产量

A11010

A21.511.51225

4.50.55

A3

销量6101212

新方案二：

B1B2B3B4产量

A11010

A22111225

A3415

销量6101212

四、（21分）某公司生产并销售某产品。根据市场预测，今后四个月的

市场需求量如下表所示。已知生产一件产品的成本是1千元，每批产品

的生产准备成本是3千元，每月仅能生产一批，每批6件。每件存储成本

为0.5千元，且第一个月初无存货，第四个月末的存货要求为零。求最

优生产计划。（北京交通大学2009年研）

答：采用动态规划方法求解。设每个月生产xk件产品，xk小于等于6；sk

为每个月开始的存货量，则s1＝0，s5＝0，

，表示在k月初存货量是sk是从第

k个月开始至第4个月的最优指标函数。表示第k个月生产xk个产品

时所需要的生产费用，，表示第k个月生产xk个产

品时，剩余产品所需要的存储费用，

（1）k＝4时，

（2）k＝3时，

（3）k＝2时，

（4）k＝1时，

∴为最优生产计划。

五、（20分）在下图中，分别求v1至v6，v1至v4，v6至v2和v2至v5的最短

路和最短距离。（北京交通大学2009年研）

答：用Floyd方法求解：

令网络的权矩阵为

k＝0，，由表示从vi到vj点

或直接有边或借v1点为中间点是的最短路长，括弧中元素为更新元素，

得D（1）

k＝1，；表示从vi到vj点最多经v1，v2的

最短路长，得D（2）

k＝2，，依次类推，

k＝3，；k＝4，；

k＝5，；k＝6，

。

∴v1至v6的最短路是v1－v3－v5－v6，最短距离是－1。

v1至v4的最短路是v1－v3－v5－v4，最短距离是0。

v6至v2的最短路是v6－v4－v2，最短距离是3。

v2至v5的最短路是v2－v3－v5，最短距离1。

六、（14分）某汽车加油站只有一个加油设备，汽车到达加油站的过程

服从泊松分布，汽车平均到达时间间隔为5分钟，加油站平均1个小时能

加24辆车。

试求：

（1）加油站的空闲的概率；

（2）加油站有三辆车的概率；

（3）加油站有两辆车以上的概率；

（4）加油站内的平均车辆数；

（5）车辆在加油站内的平均逗留时间；

（6）加油站内的平均等待车数；

（7）车辆的平均等待时间。

答：属于M/M/1/∞模型，。

（1）加油站的空闲的概率。

（2）加油站有三辆车的概率。

（3）加油站有两辆车以上的概率。

（4）加油站内的平均车辆数即（辆）。

（5）车辆在加油站内的平均逗留时间。

（6）加油站内的平均等待车数即（辆）。

（7）车辆的平均等待时间。

2008年北京交通大学交通运输学院942管理运筹学考研真题

2008年北京交通大学交通运输学院942管理运筹学考研真题（含部分答

案）

北京交通大学2008年硕士研究生入学考试试卷

考试科目：942管理运筹学

注意事项：答案一律写在答题纸上，写在试卷上的不予装订和评分！

一、（35分）已知线性规划问题：

maxZ＝3x1＋4x2＋x3

（1）求线性规划问题的最优解：

（2）求对偶问题的最优解：

（3）求b1的灵敏度范围；

（4）求c2的灵敏度范围；

如果右端值[10，16]变为[12，10]求新问题的最优解。

答：

（1）由题意，用单纯形法计算。

Cj34100θi

CBXBb

0101[2]1105

016221018

34100

Cj－Zj

451/211/21/2010

06[1]00－116

Cj－Zj10－1－20

42011/21－1/2

36100－11

Cj－Zj00－1－1－1

此时，所有检验数为负，已得最优解XT＝（6，2，0），目标函数值为

Z＝26。

（2）对偶问题

Minw＝10y1＋16y2

s．ty1＋2y2≥3①

2y1＋2y2≥4②

y1＋y2≥1③

y1，y2≥0

由互补松弛条件YXs＝0，XYs＝0；

由X＝（6，2，0），得Y1s＝0Y2s＝0，即①②③为严格等式，

即y1＋2y2＝3，2y1＋2y2＝4；所以y1＝1，y2＝1。

即最优解y1＝1，y2＝1，minw＝26。

（3）灵敏度分析

当b1变化△b时，可计算

B－1b＋B－1

由，所以。

因此8≤b1≤16。

（4）记

即，得，所以。

（5）当右端值由[10，16]变为[12，10]时，

。

将其反映到最终单纯性表中，再用对偶单纯性法进行迭代，如下。

Cj34100

CBXBb

47011/21－1/2

3－2100[－1]1

Cj－Zj00－1－1－1

45111/201/2

02－1001－1

Cj－Zj－10－10－2

故新问题的最优解为X＊＝（0，5，0，2，0），最优值为z＊＝20。

二、（20）已知LP问题为

要求：

（1）设其偶变量为y1，y2，y3，y4，写出其对偶问题；

（2）已知原问题最优解（x1，x2，x3，x4，）＝（2，2，4，0），试根

据对偶性质直接求出对偶问题的最优解。（北京交通大学2008年研）

答：

（1）对偶问题

minW＝8y1＋6y2＋6y3＋9y4

s．t

（2）由互补松弛条件YXs＝0，XYs＝0；

（x1，x2，x3，x4，）＝（2，2，4，0），则X1s＝X2s＝X3s＝0，

X4s≠0，且＝0，Y1s＝Y2s＝Y3s＝0

所以，因此（y1，y2，y3，y4）＝（，1，0）。

三、（20）某公司有3个工厂和3个客户，这3个工厂在下一时期将分别

制造产品300，500和200件，公司答应卖给客户1，2，3的产品分别是

300，200，100件，客户4想尽可能多的购买剩下产品。工厂i卖给客户j

的单位产品利润如下表所示。问如何安排生产和供应才能使总利润最

大？

答：用18减去图中各个利润，将问题转化为运输问题，建立产销平衡

表。

产量

3564300

0136500

5898200

销量300200100400

用伏格尔法求解，（）内数据为解

产地销地产量行差

3564（300）300112

0（300）1（200）3（0）650013

589（100）8（100）200331

销量300200100400

列差3432

332

34

用位势法计算所有空格的检验数，计算结果如下图所示。

1210

4－2

－114

2354

表中有负检验数，选择（1，3）为调入格，调入量为100，得新的解

300

200200100

100100

再用位势法检验，得检验数

2320

3－1

214

1244

此时，所有检验数都非负，故上表中的解为最优解。

即安排A1生产300提供给B4，A2生产200提供给B1，A2生产200提供给

B2，A3生产100提供给B3，A3生产100提供给B1，A3生产100提供给

B4，故总利润为15000。

四、（25）某工厂有1000台机器，拟分四个阶段使用。已知在每个阶段

有两种生产任务，进行第一种生产时每台机器可收益9千元，其机器报

废率0.3，而进行第二种生产时每台机器可收益6千元，其机器报废率为

0.1．文怎样分配机器，使收益最大？（要求写出动态规划模型的基本

要素并求解）（北京交通大学2008年研）

答：将此题看成一个4个阶段决策问题。令为状态变量，它表示第k阶

段初拥有的完好机器数量，决策变量为第k阶段分配给第一种生产的

机器数量，于是为该阶段分配给第二种生产的机器数量。

状态转移方程为，设为第k阶段的

收益，则

令最优值函数表示由机器数量出发，从第k阶段开始到第4阶段结

束时所获得的收益最大值，故有递推关系式：

（1）k＝4时，

因f4是u4的线性单调增函数，故得最大解，相应的。

（2）k＝3时，

故得最大解，相应的有。

（3）k＝2时，

当

，相应的有。

（4）k＝1时，

当

，相应的有。

因s1＝1000，所以＝23793千元。

计算结果表明，第1阶段将1000台机器投入第二种生产，第2阶段将900

台机器投入到第二种生产，第3阶段将810台机器投入到第一种生产，第

4阶段将567台机器投入到第一种生产。可得最大收益为23793千元。

五、（10）为解决污水河流的污染问题，某城市拟修建污水处理站。备

选的站址有A、B、C三个，其投资等技术经济参数见下表：

按环保部门要求，每年至少要从污水中清除8万吨污染物1和6万吨污染

物2。

请构造一个整数规划模型，在满足环保要求的前提下使投资和运行费用

最小。（北京交通大学2008年研）

答：

设表示处理的万吨数，，被采用时为1，未采用时为0。

建立整数规划模型minz＝500＋500x1＋400＋800x2＋300＋1000x3

六、（20）某修理店只有一个修理工，来修理的顾客到达过程为poisson

流，平均5人／小时。分别计算在下列修理时间分布的情况下系统的

Ls，Lq，Ws与Wq的值。

（1）修理时间为常数，每次修理需10分钟；

（2）修理时间为负指数分布，平均修理需10分钟；

（3）修理时间为正态分布，μ＝9分钟，δ＝4。

答：（1）当修理时间为常数

（2）当修理时间为负指数分布

（3）当修理时间为正态分布

2007年北京交通大学交通运输学院417管理运筹学考研真题

2007年北京交通大学交通运输学院417管理运筹学考研真题及详解

北京交通大学2007年硕士研究生入学考试试卷

考试科目：417管理运筹学

注意事项：答案一律写在答题纸上，写在试卷上的不予装订和评分！

一、（20分）某工厂准备生产甲、乙、丙三种产品，它们都消耗A、B

两种原材料，有关数据如下表所示：

要求：构造使该厂利润最大的线性规划模型，并用单纯型法求解。

答：设三种产品的产量分别为x1、x2、x3，则得以下线性规划模型：

用单纯形法计算如下：

cj31400

CBXBbx1x2x3x4x5

0x44563510

0x53034[5]01

314

0x415[3]－101－1

4x363/54/5101/5

3/5－11/500－4/5

3x151－1/301/3－1/3

4x33011－1/52/5

0－20－1/5－3/5

得到最优解，即生产甲和丙各5和3单位。

二、（40分）已知线性规划模型

Maxz＝2x1＋x2

求：

（1）写出原问题的对偶线性规划模型；

（2）用对偶单纯型法求解原问题的最优解；

（3）增加约束条件3x1＋2x2≤12，最优解会有什么变化？

（4）若C1由2降至1.5，C2由1升至2，最优解会有什么变化？

（5）资源b3由现在的5变成4，最优解是否发生变化。

答：（1）

（2）对原问题的对偶问题利用对偶单纯形法

cj1524500

CBYBby1y2y3y4y5

0y4－20[－6]－110

0y5－1－5－2－101

1524500

24y21/3011/6－1/60

0y5－1/3－50[－2/3]－1/31

150140

24y21/4－5/410－1/41/4

5y31/215/2011/2－3/2

15/2007/23/2

得最优解，X*＝[7/2，3/2]，maxz＝8.5。

T

（3）即对偶问题增加了一变量y6，其约束变量为a＝[3，2]，目标函数

变量为12，在最终单纯形表中的

，，因此不是最优解，

继续计算如下：

cj152450012

CBYBby1y2y3y4y5y6

24y21/4－5/410－1/41/41/4

5y31/215/2011/2－3/2[3/2]

15/2007/23/2－3/2

24y21/6－5/21－1/6－1/31/20

12y61/3502/31/3－11

1501400

得原问题最优解X*＝[4，0]，maxz＝8。

（4）在其对偶问题中，即资源变量变化，最终单纯形表中

，继继续利用对偶单纯形法计算如下：

cj1524500

CBYBby1y2y3y4y5

24y2－1/8[－5/4]10－1/41/4

5y39/415/2011/2－3/2

15/2007/23/2

15y11/101－4/501/5－1/5

5y33/2061－10

06023

得原问题最优解X*＝（2，3）T，maxz＝7。

（5）即对偶问题c3＝4，y3是基变量，因此检查各非基变量的检验数

，因此最优解不发生变化。

三、（15分）求出下面运输问题的所有最优解。

答：本题为运输平衡问题，用沃格尔法计算如下：（）内数据为解。

产地销地B1B2B3B4产量行差

A19（6）8（2）13（5）14（5）1811411

A2101012（24）14240022

A38911（6）13611122

A4107（12）1112123

销量61435560

列差1101

1111

111

11

21

用位势法检验，各空格检验数[]内数据，存在检验数小于零的空格。

产地销地B1B2B3B4产量

A19（6）8（2）13（5）14（5）18

A210[2]10[3]12（24）14[1]24

A38[1]9[3]11（6）13[1]6

A410[2]7（12）11[－1]12[－1]12

销量61435560

在相应回路调整，如空格A1B3所在回路，调整量为5，最后得新方案，

并检验如下：

不存在检验数小于0的空格，得最优解，∵A3B1检验数为0，∴最优解不

唯一。

产地销地B1B2B3B4产量

A19（6）8（12）13[1]14[1]18

A210[1]10[2]12（24）14[1]24

A38[0]9[2]11（6）13[1]6

A410[2]7（2）11（5）12（5）12

销量61435560

由A3B1所在回路，任意变化可得所有最优解如下：

产地销地B1B2B3B4产量

A16－c12＋c18

A22424

A3c6－c6

A42－c5＋c512

销量61435560

C的取值范围是[0，2]。

四、（15分）用分支定界法求整数规划问题的最优解

Maxz＝X1＋x2

答：利用单纯形法先解相应的线性规划，得最优解如下：

cj1100

CBXBbx1x2x3x4

1x13/2107/16－9/32

1x210/3017/87/16

00－21/16－5/32

*

不是整数，故用分支定界法继续求解，z0＝29/6是问题最优解z的上

界，z＝0是一个下界，则。

将问题分成问题B1和B2

问题B1问题B2

z1＝10/3z1＝41/9

x1＝1x1＝2

x2＝7/3x2＝23/9

∵z1<z2，∴先将问题B2分解成B3和B4

问题B3问题B4

z1＝17/6z1＝14/3

x1＝5/6x1＝5/3

x2＝2x2＝3

接着讲B4分解成问题B5和B6，

问题B5问题B6

z1＝17/6z1＝4

x1＝2x1＝3

x2＝23/9x2＝1

T

得到一整数解z＝4，X＝[3，1]，比较个z值，发现B6的解即为最优

解。

五、（20分）某部门拟将某种新设备5台分配给甲、乙、丙3个工厂，各

工厂获得这些设备后可盈利如下表所示，这5台设备应如何分配，使其

利润最大？用动态规划方法求解（要求写出状态转移方程和递推方

程）。

答：将该问题分成3个阶段，xk（k＝1，2，3，4）为决策变量即在第K

阶段分给k工厂xk台设备，sk（k＝1，2，3，4）为第k阶段开始时候的状

态变量，为最优策略的指标函数，表示第k阶段状态为sk时第k阶段

至第三阶段的最优值，且，用加法方式。s1＝5，s2＝s1－x1，s3

＝s2－x2＝x3。

模型为：

∴0≤x1≤5，0≤x2≤s2，0≤x3＝s3

其中，a（x1），b（x2），c（x3）分别表示三家工厂获得这种设备后将

能为集团提供的盈利，如上表所示，采用逆推法，计算如下：

k＝3时，

，即

*

S3x3x3

0000

1141

2262

33113

44124

55125

k＝2时，

，即

*

x2S2012345x2

0000

14551

265＋410102

3115＋610＋411142

4125＋1110＋611＋411161、2

5125＋1210＋1111＋611＋411212

k＝1时，

，即

*

x1s1012345x1

5213＋167＋149＋1012＋513210、2

∴分配给各厂的设备分别为2、2、1或者0、2、3．获得最大利益21。

六、（20分）在下图中，分别求v1至v6，v4至v5，v6至V2的最短路和最

短距离。

答：用Floyd方法求解：

k

令网络的权矩阵为，D表示至少经过vk时的距

离，括号内数字即变动的距离。

，

，

∴可得v1至v6的没有通路，最短距离是∞。

v4至v5的最短路是v4—v2—v3—v5，最短距离是－3。

v6至V2的最短路是v6—v4—v2，最短距离－1。

七、排队论（20分）

假设到达一个公用电话间的顾客数服从普阿松分布，有两个公用电话间

同时使用。两个顾客相继到达的平均间隔时间为3分钟，通话时间服从

平均数为3分钟的普阿松分布。公用电话间内最多只能容纳5人。假设到

达的顾客见到电话间里已有5个人时就离开这个公用电话间去别处打电

话。

求：

（1）一位到达的顾客只得离开这个电话间去别处打电话的概率；

（2）平均队长；

（3）电话局打算只要顾客在队伍中的平均等待时间不超过1分钟，就搬

走一台电话。但如果因为减少一台电话会使顾客排队等待时间超过5分

钟，那么电话局就会放弃原来的打算。问这个公用电话间的服务设施是

否需要改变？

答：（1）

即去别处打电话的概率是0.3276。

（2）。

（3）当撤走一台电话时，此问题变成M/M/1/5排队模型。

∴电话设施不会改变。

2006年北京交通大学交通运输学院417管理运筹学考研真题

2006年北京交通大学交通运输学院417管理运筹学考研真题及详解

北京交通大学2006年硕士研究生入学考试试卷

考试科目：417管理运筹学

注意事项：答案一律写在答题纸上，写在试卷上的不予装订和评分！

一、（25分）设有如下的线性规划问题：

（1）写出该线性规划的标准型；（10分）

答：

（2）求原规划的最优解和最优目标函数值。（15分）

答：加入一个人工变量x7，利用单纯形法计算如下：

cj－123－30000

’’’’’

CBXBbx1x2x3x3x4x5x7x6

0x47211－11000

0x56－3－1－2[2]0100

0x74423－30010

0x6401000001

－123－30000

0x410[1/2]1/20011/200

’’

－3x33－3/2－1/2－1101/200

0x7131/21/20003/210

0x6401000001

－11/21/20003/200

’

－1x12011002100

’’

－3x31301－113200

0x730000－1110

0x6401000001

060011700

’’’’’

∴x1＝－x1＝－20，x2＝x2＋2＝2，x3＝x3－x3＝－13；

得到最优解X*＝[－20，2，－13]T，minz＝－55。

二、（25分）标准型线性规划问题（minZ＝CX，AX＝b，X≥0）的最

优单纯型表为：

其中：x4，x5是对应于初始单位矩阵的松弛变量。

试求：

（1）求该标准型线性规划目标函数的系数c1－c5；

答：松弛变量x4，x5的目标函数为0，，且由最终单纯形表可知：

解得

。

（2）设该标准型线性规划的右端常数项为b，△b1，△b2分别为b的两

个分量的增量，试分别对两个增量进行灵敏度分析，即求出△b1，△b2

分别变化时的取值范围；

答：

当，解得；

当，解得。

（3）假定用b＋λ△b代替b，其中△b＝，－∞＜λ＜＋∞，要使现行

的最优基B*不变，求λ的变化范围，并求当时的最优解；

答：保持最优基B*不变，则要求

解得，当时，最优解不发生变化，。

所以X*＝[3，1]T，minz＝－9。

（4）要使现行的最优基不变，求目标函数系数c1变化范围；

答：保持最优基不变，各非基变量检验数认识非负，则：

解得，。

∴c1变化范围是[－3，－1]。

（5）求两个约束的影子价格。

答：由最终单纯形表可知，两个影子价格即两个松弛变量的检验数，即

分别为3和1。

三、（25分）某工厂安排某种生活必需品在以后四个月的生产计划。该

产品可以在以后四个月的任一个月生产，不过受用工和原料价格的影

响，不同的月份其生产成本不同，该产品在以后四个月的生产成本分别

是12，10，15，18元，件。该产品以后四个月需要量分别是400，700，

900和800件，考虑到生活必需品的要求，产品需要量必须加以满足。该

工厂平常每月最多能生产700件，但在第二个月农闲时期工厂可以聘用

临时工加班，加班后可增产300件，但生产成本每件增加3元。过剩产品

每件存储费用是每月3元。试完成：

（1）仿照运输问题建立使总成本最小的生产计划线性规划数学模型；

（10分）

‘

答：设xij是第i个月生产供第j个月消费的产品数量，i＝1，2，2，3，

4，j＝1，2，3，4，其中x2’表示第2个月加班完成的产品数量。z表示总

成本。则由题意得线性规划数学模型：

（2）用运输问题表上作业法求解。（10分）

答：总供给量为700×4＋300＝3100；总需求量是400＋700＋900＋800＝

2800，故设一虚拟消费月份5，需求量是300，成本是0，其他如

xij（i<j），成本是∞。则化成产销平衡问题，利用沃格尔法得初始解如

下：（括号内为分配量，[]内为检验数）

消费月份12345产量

生产月份

1（400）12[5]15[2]18[2]21（300）0700

2[∞]∞（700）10[0]13[0]16[3]0700

2‘[∞]∞（0）13（200）16（100）19（0）0300

3[∞]∞[∞]∞（700）15[0]18[1]0700

4[∞]∞[∞]∞[∞]∞（700）18[1]0700

需求量4007009008003003100

所有空格检验数均为非负，故得最优解。

即4个月份分别生产400件、1000件、700件和700件。

（3）理论上讲该问题有几个最优基本可行解？（5分）

答：因为存在检验数为0，故有无数个最优基本可行解。

四、（25分）某城市公共交通公司共有公交客车1000辆，可投入超负荷

和正常负荷两种状态运营，如果当年投入高负荷状态运营，年运量为20

万人／台，且第一年投入高负荷运营时汽车年完好率为0.8，以后各年

投入高负荷运营时每年完好率随车龄每年以0.1递减，如果投入正常负

荷状态运营，年运量为15万人／台，第一年汽车年完好率为0.95，以后

各年投入正常负荷运营时每年完好率随车龄以O．O5递减，试安排5年

运量最大的运营方案。

答：设第k年有xk（k＝1，2，3，4，5）辆车超负荷状运营，年初有sk辆

完好车，则，s1＝1000辆，s2＝0.8x1

＋0.9（s1－x1），sk＋1＝sk－xk*0.01－（sk－xk）*0.05（k＝2，3，

4）。最优指标函数

表示k年初状态为sk时，从第k

年至第5年末的最大运量，。采用逆推方法计算如下：

K＝5时，

K＝4时，

k＝3时，

K＝2时，

K＝1时，

∴可知，第1年全部车辆正常运行，从第2年开始至第5年，所有车辆超

负荷运营，可获得最大运营量为80341万人次。

五、（15分）用割平面法求解下列IP问题：

MaxZ＝8x1十5x2

st．2x1＋3x2≤12

x1－x2≤6

x1，x2≥0且为整数

答：首先用单纯形法计算其相应的线性规划问题

cj8500

CBXBbx1x2x3x4

0x312[2]3106

0x461－1016

8500

8x1613/21/20

0x400－5/2－1/21

0－7－40

从上表中可以看出，已求得整数解XT＝[6，0]T，，maxz＝48。无需在

用割平面法进行求解。

六、（15分）试证明定理：可行流f*是最大流的充分必要条件是不存在

关于f*的增广链。

答：（1）充分性

不存在关于f*的增广链，则对f*的任意一条弧都不能再进行调整，故现

在的可行流流量已达到最大值，故可行流f*是最大流。

（2）必要性（用反证法）

可行流f*是最大流，假设存在关于f*的增广链，则总可以对f进行调整，

调整量。则增广链上，正向弧，则整个可行流

流量都增加，得到的新的可行流大于原可行流，则可知原可行流f*不

是最大流，与题意相悖。

七、（20分）某理发店只有一个理发师，来理发的顾客到达过程为

Poisson流，平均到达间隔为20分钟。理发时间服从负指数分布，平均需

要15分钟。试求：

（1）理发店空闲的概率

答：该问题属于M/M/1模型，

理发店空闲的概率。

（2）店内恰有3个顾客的概率

答：店内恰有3个顾客的概率。

（3）店内至少有1个顾客的概率

答：店内至少有1个顾客的概率。

（4）在店内的平均顾客数

答：在店内的平均顾客数。

（5）每位顾客在店内的平均逗留时间

答：每位顾客在店内的平均逗留时间。

（6）等待服务的平均顾客数

答：等待服务的平均顾客数。

（7）每位顾客平均等待时间

答：每位顾客平均等待时间。

（8）顾客在店内逗留超过10分钟的概率

答：顾客在店内逗留超过10分钟的概率。

2005年北京交通大学交通运输学院417管理运筹学考研真题

2005年北京交通大学交通运输学院417管理运筹学考研真题及详解

北京交通大学2005年硕士研究生入学考试试卷

考试科目：417管理运筹学

注意事项：答案一律写在答题纸上，写在试卷上的不予装订和评分！

一、（40分）已知线性规划问题

（1）求线性规划问题的最优解（20分）：

答：

Cj1534000θi

CBb

08002312100800/3

012005434010300

010003[4]53001250

Cj－Zj1534000

050－1/40－1/4－1/410－3/4

020020－2[1]011/4200

52503/415/43/40001000/3

Cj－Zj－11/40－13/41/400－5/4

01001/40－13/4011/4－1

420020－2101－1

5100－3/4111/400－3/41

Cj－Zj－13/40－11/400－1/4－1

所以最优解，最优值＝800＋500＝1300。

（2）求对偶问题的最优解（5分）；

答：由最终单纯性表可得y1＝0，y2＝1/4，y3＝1。

（3）当△b3＝－150时最优基是否发生变化？为什么？（5分）；

答：

出现了负值，所以最优解会发生变化。

（4）求c2的灵敏度范围（5分）；

答：

Cj134000

CBb

01001/40－13/4011/4－1

420020－2101－1

100－3/4111/400－3/41

Cj－Zj3/4－7011－11/4003/4－44－

所以，得。

（5）如果x3的系数由[1，3，5]变为[1，3，2]最优基是否改变？若改变

求新的最优解（5分）。

答：

Cj1534000

CBb

01001/40－1/4011/4－1

420020[1]101－1

5100－3/41－1/400－3/41

Cj－Zj－13/401/400－1/4－1

01503/4001/411/2－5/4

3200201101－1

5150－1/4101/40－1/23/4

Cj－Zj－15/400－1/40－1/2－3/4

所以最优解，最优值＝600＋750＝1350。

二、（20分）

已知某运输问题其供需关系及单位运价表如下表所示：

要求：用表上作业法找出最优调运方案。

答：由于产销不平衡，虚拟一个销地B4，运费为O。

即

B1B2B3B4产量

A142508

A235307

A313204

销量4852

首先，用伏格尔法求初始解，如下所示：

（）内数据为解

产地销地B1B2B3B4产量行差

A142（8）508223

A2353（5）0（2）7302

A31（4）3（0）2（0）0411

销量4852