运筹学复习题及参考答案.doc

《运筹学》

一、判断题：在下列各题中，你认为题中描述的内容为正确者，在题尾括号内写“T”，错误者写“F”。
1. T 2. F 3. T 4.T 5.T 6.T 7. F 8. T 9. F
10.T 11. F 12. F 13.T 14. T 15. F

1. 线性规划问题的每一个基本可行解对应可行域的一个顶点。 ( T )
2. 用单纯形法求解一般线性规划时，当目标函数求最小值时，若所有的检验数Cj-Zj≤0，则问题达到最优。 ( F )
3. 若线性规划的可行域非空有界，则其顶点中必存在最优解。 ( T )
4. 满足线性规划问题所有约束条件的解称为可行解。 ( T )
5. 在线性规划问题的求解过程中，基变量和非机变量的个数是固定的。 ( T )
6. 对偶问题的对偶是原问题。 ( T )
7. 在可行解的状态下，原问题与对偶问题的目标函数值是相等的。 ( F )
8. 运输问题的可行解中基变量的个数不一定遵循m＋n－1的规则。 ( T )
9. 指派问题的解中基变量的个数为m＋n。 ( F )
10. 网络最短路径是指从网络起点至终点的一条权和最小的路线。 ( T )
11. 网络最大流量是网络起点至终点的一条增流链上的最大流量。 ( F)
12. 工程计划网络中的关键路线上事项的最早时间和最迟时间往往是不相等。 ( F )
13. 在确定性存贮模型中不许缺货的条件下，当费用项目相同时，生产模型的间隔时间比订购模型的间隔时间长。 (T )
14. 单目标决策时，用不同方法确定的最佳方案往往是不一致的。 ( T )
15. 动态规则中运用图解法的顺推方法和网络最短路径的标号法上是一致的。 ( F )
二、单项选择题
1.A 2.B 3.D 4.B 5.A 6.C 7.B 8.C 9. D 10.B
11.A 12.D 13.C 14.C 15.B

1、对于线性规划问题标准型：maxZ=CX, AX=b, X≥0, 利用单纯形法求解时，每作一次迭代，都能保证它相应的目标函数值Z必为（ A ）。
A. 增大 B. 不减少 C. 减少 D. 不增大
2、若线性规划问题的最优解不唯一，则在最优单纯形表上（ B ）。
A. 非基变量的检验数都为零 B. 非基变量检验数必有为零
C. 非基变量检验数不必有为零者 D. 非基变量的检验数都小于零
3、线性规划问题的数学模型由目标函数、约束条件和（ D ）三个部分组成。
A. 非负条件 B. 顶点集合 C. 最优解 D. 决策变量

4、已知x1= ( 2, 4), x2=(4, 8)是某线性规划问题的两个最优解，则（ B ）也是该线性规划问题的最优解。
A. （4，4） B. (1,2) C. (2,3) D. 无法判断
5、下列数学模型中，（ A ）是线性规划模型。
MaxZ= 10x1+x2-3x3
x21+5x2≤15
x1-8x2+3x3≥22
xj≥0, j=1,2,3

A. MinZ=3x1+x2－2 x3 B.
2x1+3x2-4x3≤12
4x1+x2+2x3≥8
3x1-x2+3x3=6
x1≥ 0,x2无约束,x3≤ 0

MaxZ=x1+4x2-8x3+x24
x1+4x3-x4=29
x2-5x3+4x4≥40
x1+x2-6x4≤19
xj≥0,j=1,2,3,4

Z=5x1+6x2+8x3-9x4
x1+4x3-x4=19
x2-5x3+4x4≥30
x1+x2-6x4≤9
xj≥0,j=1,2,3,4
C. D.

6、线性规划问题最终解的情形有（ C ）。
A. 可行解、最优解、基本解和无解 B. 可行解、基本可行解、基本解和最优解
C. 最优解、退化解、多重最优解和无解 D. 最优解、退化解、多重解和无界解
7、若x是原问题maxZ=CX, AX≤b, X≥0的可行解，y是其对偶问题MinS=Yb, YA≥C, Y≥0的可行解，则有（ B ）。
A. CX≥Yb B. CX≤Yb C. CX=Yb D. 无法确定
8、下面关于运输问题与线性规划问题的关系，（ C ）是正确的。
A. 运输问题和线性规划问题是两类不同的优化问题；
B. 运输问题和线性规划问题是两类相同的优化问题，但不能用相同的方法求解；
C. 运输问题是一类特殊的线性规划问题；
D. 该两类问题的关系无法确定。
9、动态规划问题中的状态变量必须具有（ D ）性质。
A. 无后效性 B. 无后效性和决策性 C. 可知性和决策性 D. 无后效性和可知性
10、 图的组成要素有（ B ）。
A. 点 B. 点及点之间的连线 C. 点和权 D. 点、边和权
11、网络计划技术中关键路线法与计划评审技术两种方法的根本区别在于（ A ）。
A. 工序时间参数的确定 B. 计算原理与计算过程
C. 关键路线的确定方法 D. 最早时间与最迟时间的确定

12、下面关于网络图中的虚工序的描述，正确的是（ D ）。
A. 虚工序是技术上的等待，因而它不耗费人力、物力，只耗费时间；
B. 虚工序与实工序一样，包括技术上的等待，因而它既耗费人力、物力，又耗费时间；
C. 虚工序所描述的是一类实际上不存在的工序，只是为了作图的需要；
D. 虚工序是表示前后两道工序之间的逻辑关系，因而它既不耗费人力、物力，又不耗费时间。
13、决策的三要素是（ C ）。
A. 方案、状态和收益 B. 方案、状态和损失
C. 方案集、状态集和损益矩阵 D. 方案集、状态集和概率集
14、求解风险型决策问题的最大概率准则，一般适用于（ C ）。
A. 状态概率为已知的情形 B. 状态概率为相等的情形
C. 状态概率悬殊较大的情形 D. 既然作为决策准则，应该适用于任何情形
15、针对某一特定的不确定型的决策问题，分别采用五种决策准则（等可能准则、乐观准则、悲观准则、折衷准则和后悔值准则）进行决策，其决策结果（ B ）。
A. 相同 B. 一般不相同 C. 绝大多数相同 D. 不能确定

三、简述题
1. 用图解法说明一般线性规划问题的最优解一定在可行域的顶点上达到。
2. 运输问题是特殊的线性规划问题，但为什么不用单纯形法求解。
3. 建立动态规划模型时，应定义状态变量，请说明状态变量的特点。

四、下列表是三个不同模型的线性规划单纯形表，请根据单纯形法原理和算法，分别在表中括号中填上适当的数字。
1. 计算该规划的目标函数值
Cj → 20 15 20 0 0
Ci xB x1 x2 x3 x4 x5
20 x1 2 1 0 -1 0
20 x3 1 0 1 1 1/2 0
0 x5 3 0 -1 0 0 1
z j 20 30 20 -10 0
c j－z j 0 -15 0 10 0

2、确定上表中输入，输出变量

五、已知一个线性规划原问题如下，请写出对应的对偶模型

六、下图为动态规划的一个图示模型，边上的数字为两点间的距离，请用逆推法求出S至F点的最短路径及最短路长。
B1
S
A2
4
9
B3
8
C2
11
F
C1
9
5
A1
8
7
11
12
14
6
B2

10
5
5
8

七、自已选用适当的方法，对下图求最小(生成树)。
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
1

九、下图是某一工程施工网络图(统筹图)，图中边上的数字为工序时间(天)，请求出各事项的最早时间和最迟时间，求出关键路线，确定计划工期。

2
3
1
4
5
6
5
12
4
9
10
5
0
9
4

十、某企业生产三种产品A1、A2、A3。每种产品在销售时可能出现销路好(S1)，销路一般(S2)和销路差(S3)三种状态，每种产品在不同销售状态的获利情况(效益值)如表1所示，请按乐观法则进行决策，选取生产哪种产品最为合适。
状态
效益值
产品

S1

S2

S3
A1
50
40
-6
A2
20
15
9
A3
18
13
12

(表1)
十一、已知运输问题的运价表和发量和收量如表2所示，请用最小元素法求出运输问题的一组解。

B1
B2
B3
B4

A1
2
9
12
7
9
A2
1
3
5
2
4
A3
10
4
2
6
5

3
5
4
6

(表2)

十二、下列表3是一个指派问题的效率表(工作时间表)，其中A i为工作人员(i=1, 2, 3, 4)、Bj为工作项目(j=1, 2, 3, 4)，请作工作安排，使总的工作时间最小。

B1
B2
B3
B4
A1
4
1
7
4
A2
2
2
3
5
A3
5
6
4
3
A4
6
3
2
4

(表3)

十三、有一化肥厂用两种原料A,B生产C,D,E三种化肥，根据市场调查某地区各种化肥每天最少需求分别为100吨，60吨，130吨。该厂每天可供的原料分别为200吨和240吨。单位成品化肥所耗费的原料及销售利润如下表。问每天应生产多少各类化肥，使该厂利润最大。要求建立线性规划模型，不作具体计算。

化肥\原料
A
B
最低需要量
单位利润
C
1
2
100
10
D
1.5
1.2
26
15
E
4
1
130
11
供应量
200
240

《运筹学》参考答案

四、计算题
1.z=60
2. X4输入，X3输出
五、 Smin = 4y1＋3y2+4y3
y1+y3≥2
y2+y3≥5
y1, y2, y3≥0
六、
S=26

V1
V3
V2
V4
V5
V6
七、
V1
V3
V2
V4
V5
V6

L=13
L=13

八、最短路径：V1→V3→V5→V6→V7 L=10

22
22
5
13
九、
31
31
9
9
4
2

5
6

0
0
0
10
4
1

4
5

12
5
3

22
27
12
12

关键线①—③—④—⑥ 计划工期31

S1

S2

S3
A1
50
40
-6
A2
20
15
9
A3
18
13
12
选A1为最佳方案

50 √
20
18
十、

十一、

B1
B2
B3
B4

A1
2
⑨
12
⑦
9
A2
①
3
5
②
4
A3
10
④
②
6
5

3
5
4
6

3
1
6
5
1
4

B1
B2
B3
B4
A1
4
①
7
4
A2
②
2
3
5
A3
5
6
4
③
A4
6
3
②
4

十二、

L = 8

十三、解：设成品化肥的产量分别为x1、x2、x3吨，则线性规划模型为：

（注：专业文档是经验性极强的领域，无法思考和涵盖全面，素材和资料部分来自网络，供参考。可复制、编制，期待你的好评与关注）