2020年硕士研究生招生考试初试考试大纲

科目代码：809

科目名称： 运筹学

适用专业： 交通运输工程、交通运输规划与管理、交通安全与工程管理

考试时间：3小时

考试方式： 笔试

总　　分： 150分

考试范围：

一、线性规划与单纯形法

线性规划问题和数学模型、线性规划图解法、线性规划解的性质、单纯形法及人工变量单纯形法。

二、对偶理论与灵敏度分析

线性规划问题的对偶及其变换、线性规划的对偶定理、对偶单纯形法、 线性规划的灵敏度分析、参数规划。

三、运输问题

运输问题的数学模型的特点及其求解、不平衡的运输问题的求解、运输问题的应用。

四、整数规划

整数规划问题数学模型的特点及其求解思路、整数规划问题的求解方法、 指派问题及其求解方法

五、动态规划

动态规划模型的最优性原理及其算法基本思路、离散型动态规划模型特点及其求解、连续型动态规划模型特点及其求解。

六、图与网络分析

图和网络的基本概念、 树和最小生成树、最短路径问题的求解、 网络最大流及最小截集的求解、最小费用最大流的求解。

七、 随机服务理论概述

随机服务系统的基本组成、 生灭过程的概念及其稳态解、泊松输入--指数服务排队系统特点及其计算、 排队系统的优化设计。

样 题：

一、(54分)已知一个工厂利用三种原材料生产两个产品，设两个产品的产量分别为x1，x2，利用单纯形法求解最优生产方案。求解过程中一个单纯形表如下：

XBB-1bx1x2x3x4x5

x31505100

x1211/301/60

x5102/30-1/61

Zj-Cj 0-1/301/30

试回答如下问题：

1、求第一个产品x1的售价以及第一个产品的售价在什么范围内工厂不改变其最优生产方案?(14分)

2、利用对偶性质给出原材料最低售价模型中的目标函数。(6分)

3、若x1的技术系数变为[1,3,1]T，利用所给单纯形表求解新生产方案。(14分)

4、第二种原材料拥有量在什么范围内变化时，第二个产品不能生产?(10分)

5、若对产品产量有整数要求，利用最优单纯形表求解新的生产方案。(10分)

二、(22分)道路施工需要碎石，两个施工段B1、B2需要从A1、A2两地采购碎石，其中B1因有存货，至少需要10吨，缺货费为3百元/吨;而B2无存货，为了保证工期不允许缺货。供应量、需要量及运价见下表，试进行下列分析：

1、建立表式运输平衡模型。(8分)

2、利用表上作业法求解最优方案。(10分)

3、A2找到新的运输路线运输到B1、B2，取代原有的路线后运价将会下降。若运到B1、B2的运价下降幅度相同，利用最优运输方案探讨运价变化对运输方案的影响。(4分)

运价(百元/吨)B1B2供应量(吨)

A11540

A22440

需求量(吨)[10,40]50

三、(24分)某种机器由三种设备装配而成，其价格和可靠性如下表，设备2损坏率最高，因此设备2至少配备2台。目前采购费用为12万元。试回答下列问题：

1、建立动态规划模型，明确第二阶段状态变量及其允许集合。(8分)

2、利用动态规划进行设备采购使装配后的机器可靠性最大?(16分)

设备i123

价格Ci(万元/台)321

可靠性Di(%)907080

四、(28分)有一区域单向交通网络如下所示，图中弧上权重为(通行能力，距离)。

试进行以下分析：

1、求出(vs,v3)，(v3,v2)为饱和流且网络流量为8的流量图。(8分)

2、根据距离求vs到vt的最短路径(不得使用枚举法且保留解题过程)。(6分)

3、在网络流量为8的流量图基础上求得最小费用最大流。(8分)

4、找出道路网瓶颈;若只能增加一条路的通行能力，试给出改善建议。(6分)

五、(10分)设有两个工人维修M1、M2、M3三台机器，不同工人维修费用见下表。因三台机器必须修理完毕，每个工人均可以维修两台机器。试求总费用最小的维修方案。

工人A工人B

M168

M21012

M3714

六、(12分)某小型机场只有一个跑道，飞机到达间隔与跑道服务时间均为指数分布，平均每小时到达3架飞机，目前跑道平均每小时服务4架飞机。如果飞机逗留一个小时费用为4万元，跑道服务成本为一个小时一架飞机3万元。试进行以下分析：

1、通过提高跑道服务率改善运营，计算最优的服务率以及此时系统中大于4架飞机的概率。(6分)

2、若使现在飞机平均等待时间降低，增加一条跑道但不改变原服务强度(即每个小时每个跑道服务2架飞机)，此方案是否可行。(6分)

参考公式：

参考书目

《运筹学》教材编写组. 运筹学. 清华大学出版社. 2007.4,第三版

韩大卫.管理运筹学--模型与方法.清华大学出版社.2014.6,第二版