大连交通大学809运筹学考研大纲及样题

2018 年硕士研究生入学考试初试考研大纲
科目代码：809
科目名称： 运筹学
适用专业： 交通运输工程、交通运输规划与管理
考试时间：3 小时
考试方式： 笔试
总 分： 150 分
考试范围：
一、线线规划与单纯形法
线性规划问题和数学模型、线性规划图解法、线性规划解的性质、单纯形法
及人工变量单纯形法
二、对偶理论与灵敏度分析
线性规划问题的对偶及其变换、线性规划的对偶定理、对偶单纯形法、 线
性规划的灵敏度分析、参数规划
三、运输问题
运输问题的数学模型的特点及其求解、不平衡的运输问题的求解、运输问题
的应用
四、整数规划
整数规划问题数学模型的特点及其求解思路、整数规划问题的求解方法、
指派问题及其求解方法
五、动态规划
动态规划模型的最优性原理及其算法基本思路、离散型动态规划模型特点及
其求解、连续型动态规划模型特点及其求解
六、图与网络分析
图和网络的基本概念、 树和最小生成树、最短路径问题的求解、 网络最
大流及最小截集的求解、最小费用最大流的求解
七、 随机服务理论概述
随机服务系统的基本组成、 生灭过程的概念及其稳态解、泊松输入--指数
服务排队系统特点及其计算、 排队系统的优化设计
样 题：
一、（32 分）已知线性规划问题：









2,1,0
334
1852
.
3max
21
21
21
jx
xx
xx
ts
xxz
j
利用单纯形法求解，最优单纯形表如下：
XB B-1
b x1 x2 x3 x4
x1 3/2 1 0 3/26 -5/26
x2 3 0 1 2/13 1/13
Zj-Cj 0 0 15/26 1/26
试分别进行下面的计算：
1、第一约束资源系数在什么范围内变化上述最优基不变？（8 分）
2、x2 的价值系数在什么范围内变化时，最优基变量变为 x1 和 x4？（10 分）
3、若 x1 取大于 1 的整数，最优解如何？（14 分）
二、（18 分）已知最大化具有“≤”约束的线性规划问题，利用单纯形法求解，
其中一个单纯形表如下：
YB B-1
b y1 y2 y3 y4 y5
y1 3 1 2 3 0 0
y4 4 0 3 -2 1 0
y5 2 0 2 -1 0 1
Zj-Cj 0 -2 3 0 0
1、求出其对偶问题的资源系数。（8 分）
2、利用对偶理论给出对偶问题的最优解。（10 分）
三、（28 分）根据下面的运输供应量与需求量及运价表，试进行下列分析
1、建立表式运输平衡模型。（8 分）
2、利用表上作业法求解最优方案，判断最优方案的多重性。（14 分）
3、若 B1 的缺货费为 3，B2、B3 均无缺货费时，最优方案有何变化？（6 分）
运价 B1 B2 B3 供应量
A1 1 4 3 4
A2 1 5 2 6
四、（24 分）某厂计划用 6 万元购买一批机器，现有三种型号的机器可供选购，
其价格和生产能力如下表，要求至少需要一台 2 型机器。
试回答如下问题：
1、确定状态转移方程和第二阶段状态变量的允许集合。（8 分）
2、如何投资才能使总生产能力最大（利用动态规划求解）。（16 分）
五、（26 分）有如下网络图，图中弧上权重为(容量，费用，流量)。
1、判断所给网络流的可行性和最优性，说明原因。（8 分）
2、求此网络图的最小费用最大流量。（12 分）
3、找出最小截集，若只增加最小截集上一条弧的容量使得流量增加，流量最大
会增加多少？（6 分）
六、（10 分) 设有 M1、M2、M3 三台机器可以安装在 ABCD 四个不同位置，各种
不同安装费用见下表。M2 不能安装在 C 处，试求使总费用最小的安装方案。
A B C D
M1 6 8 10 12
M2 8 12 - 11
M3 7 14 13 8
四、七、（12 分）某质检处只有一位质检员，产品到达间隔与检测服务时间均为
指数分布，平均每小时到达 3 个产品。如果产品逗留 1 小时费用为 4 元，缩短质
检时间的成本为每小时为 3 元；那么总费用最小时，每个产品的质检时间为多
少？此时，质检员的服务强度、产品的等待队长、产品逗留时间为多少？
需求量 4 5 4
机器型号 i 1 2 3
价格 Ci（万元/台） 3 2 1
生产能力 Di（吨/台） 7 5 3.5
VS
V1
V2
VT
(3,3,2)
(4,2,3)
(3,3,2)
(6,5,1)
(5,4,3)