文档介绍：中南大学《运筹学》程试题及参考答案
一、判断题(在下列各题中,你认为题中描述的内容为正确者,在题尾括号内写“√”,错误者写“×”。)
1. 图解法提供了求解线性规划问题的通用方法。 ( )
2. 用单纯形法求解一般线性规划时,当目标函数求最小值时,若所有的检验数Cj-Zj≥0,则问题达到最优。 ( )
3. 在单纯形表中,基变量对应的系数矩阵往往为单位矩阵。 ( )
4. 满足线性规划问题所有约束条件的解称为基本可行解。 ( )
5. 在线性规划问题的求解过程中,基变量和非基变量的个数是固定的。 ( )
6. 对偶问题的目标函数总是与原问题目标函数相等。 ( )
7. 原问题与对偶问题是一一对应的。 ( )
8. 运输问题的可行解中基变量的个数一定遵循m+n-1的规则。 ( )
9. 指派问题的解中基变量的个数为m+n。 ( )
10. 网络最短路径是指从网络起点至终点的一条权和最小的路线。 ( )
11. 网络最大流量是网络起点至终点的一条增流链上的最大流量。 ( )
12. 工程计划网络中的关键路线上事项的最早时间和最迟时间往往不相等。 ( )
13. 在确定性存贮模型中不许缺货的条件下,当费用项目相同时,生产模型的间隔时间比订购模型的间隔时间长。 ( )
14. 单目标决策时,用不同方法确定的最佳方案往往是一致的。 ( )
15. 动态规划中运用图解法的顺推方法和网络最短路径的标号法上是一致的。
( )
二、简述题
1. 用图解法说明线性规划问题单纯形法的解题思想。
2. 运输问题是特殊的线性规划问题,但为什么不用单纯形法求解。
3. 建立动态规划模型时,应定义状态变量,请说明状态变量的特点。
三、填空题
1. 图的组成要素; 。
2. 求最小树的方法有、。
3. 线性规划解的情形有、、、。
4. 求解指派问题的方法是。
5. 按决策环境分类,将决策问题分为、、。
6. 树连通,但不存在。
四、下列表是线性规划单纯形表(求Zmax),请根据单纯形法原理和算法。
1. 计算该规划的检验数
Cj → 3 2 0 0 0
Ci xB x1 x2 x3 x4 x5
3 x1 3 1 0 -1 0
2 x3 4 0 1 1 1/2 0
z j 3 2 -2 0
c j-z j

2. 计算对偶问题的目标函数值
3. 确定上表中输入,输出变量
五、已知一个线性规划原问题如下,请写出对应的对偶模型
六、下图为动态规划的一个图示模型,边上的数字为两点间的距离,请用逆推法求出S至F点的最短路径及最短路长。
B1
10
7
10
6
11
A1
10
C1
8
B2
12
5
5
14
F
S
6
6
13
7
C2
10
A2
9
B3
七、自己选用适当的方法,对下图求最小(生成)树。
V1
2
3
3
5
2
3
3
5
6
V3
V2
V4
V5
V6
八、用标号法求下列网络V1→V7的最短路径及路长。
V1
V7
V5
V6
V4
V3
V2
5
4
3
5
3
1
7
6
1
7
3