中国计量学院-运筹学期末试卷C试题及答案

中国计量学院200 ~200 学年第 学期《 运筹学 》课程试卷（C ）第 1 页 共 6 页 中国计量学院200 ~ 200 学年第 学期 《 运筹学 》课程考试试卷（ C ）

开课二级学院： 经管学院 ，考试时间： 年___月_ _日 时 考试形式：闭卷√、开卷，允许带 计算器、钢笔（圆珠笔）、学生证 入场

考生姓名： 学号： 专业： 班级：

一、单项选择题（共20分，每题2分） 1、当线性规划问题的可行解集合非空时一定（ ） A 、包含原点 B 、有界 C 、无界 D 、是凸集 2、线性规划具有无界解是指（ ） A 、可行解集合无界 B 、有相同的最小比值

C 、存在某个检验数ó≥0且a ik ≤0(i=1,2,…,m)

D 、最优表中所有非基变量的检验数非零 3. 对偶单纯形法的适用条件是（ ） A 、对偶可行 ，原始不可行 B 、对偶不可行 ，原始可行 C 、对偶可行 ，原始可行 D 、对偶不可行 ，原始不可行

4、当基变量Xi 的系数Ci 波动时，最优表中引起变化的是（ ） A 、基变量X B 的数值 B 、所有非基变量的检验数 C 、右端常数项b D 、系数矩阵A

5、具有m 个产地n 个销地的平衡运输问题模型具有特征为（ ） A 、有 mn 个约束条件 B 、有m+n 个非基变量 C 、有mn-m-n-1个变量 D 、有m+n-1个基变量

6、max Z =3x 1 + x 2 ,4x 1 + 3x 2 ≤7, x 1+ 2x 2 ≤4 x 1,x 2= 0或1，最优解是（ ） A 、（0，0） B 、（0，1） C 、（1，0） D 、（1，1）

7、连通图G 有n 个点，其生成树是T ，则有（ ） A 、T 有n 个点n 条边 B 、T 有n 个点n-1条边

C 、T 中有m 个点m-1条边(m

D 、T 的长度等于G 的每条边的长度之和 8、绘制网络图时，对引入的虚活动说法正确的是（ ）

装 订 线

A、虚活动是真实的活动

B、虚活动需要耗用一定时间

C、虚活动用实箭线表示

D、虚活动仅表示相邻活动之间的衔接关系，不需要时间

9、对于不确定型的决策，某人采用乐观主义准则进行决策，则应在收益表中（）

A、大中取大

B、大中取小

C、小中取大

D、小中取小

10、下列错误的结论是（）

A、容量不超过流量

B、流量非负

C、容量非负

D、发点的流出合流等于流入收点的合流

单项选择题答题表

二、判断及改错题，正确打√，错误打×，并将修改建议简写在对应题号下的改错栏。（共20分，每题2分）

1、任何线性规划一定有最优解。（）

2、线性规划问题减少一个变量，目标值不会比原来变差。（）

3、高莫雷约束是将可行域中一部分非整数解切割掉。( )

4、运输问题的检验数就是对偶问题松弛变量的值。（）

5、在指派问题的效率表的某行加上一个非零数最优解不变。（）

6、割集中弧的流量之和称为割量。（）

7、事件i的最迟时间等于以i为开工事件工序的最迟必须开工时间的最小值（）

8、在网络计划中，总时差为0的工序成为关键工序（）

9、在不确定型决策中，最小机会损失准则比等可能性准则保守性更强。（）

10、普通单纯形法最小比值规则失效说明问题无界。（）

判断及改错题答题表

中国计量学院200 ~200 学年第学期《运筹学》课程试卷（C ）第2页共 6 页

三、（20分）对于如下的线性规划问题

min z = 3x1 + 2x2 +x3

s.t. x

1 + x

2

+ x

3

≤ 15 (1)

2x

1 - x

2

+ x

3

≥ 9 (2)

-x

1 + 2x

2

+2x

3

≤ 8 (3)

x

1 x

2

x

3

≥ 0

1、（5分）写出题目中线性规划问题的对偶问题；

2、（10分）分别求出原始问题和对偶问题的最优解（求解的次序和方法不限）；

3、（5分）C3如何变化，使该问题的最优性保持不变。

中国计量学院200 ~200 学年第学期《运筹学》课程试卷（C ）第3页共 6 页

四、（15分）在一个3×3的运输问题中，已知供应量a1＝15，a2＝30，a3＝85；而需求量b1＝20，b2＝30，b3＝80，其最优解运输量如下表所示：

又设各位势为

u1＝-2，u2＝3，u3＝5，v1＝2，v2＝5，v3＝10，现问：

1、最优总运费是多少？（10分）

2、在保持上面解最优解的条件下，各个非基变量的C ij的最小值是什么？（5分）

中国计量学院200 ~200 学年第学期《运筹学》课程试卷（C ）第4页共 6 页

五、（10分）某项目网络图如下，英文字母表示工序，数字表示该工序需要的时间。

a ,7 e,10 g,35

②⑤

④⑥

C,12 f,24 i,17

③⑦ j,34 ⑧

1、指出项目的关键路线；（5分）

2、求项目的完工期。（5分）

中国计量学院200 ~200 学年第学期《运筹学》课程试卷（C ）第5页共 6 页

六、（15分））1、求以下网络的最小支撑树（5分）；

2、求以下网络从节点1到节点12的最短路径（10分）。

3 4 7

①②③④

6 2 5 1

1 9 8

⑤⑥⑦⑧

4 8 6 3

⑨⑩⑾⑿

7 2 4

中国计量学院200 ~200 学年第学期《运筹学》课程试卷（C ）第6页共 6 页

中国计量学院200 ~ 200 学年第学期

《运筹学》课程

试卷（ C ）参考答案及评分标准

开课二级学院：经管学院，学生班级：，教师：

一、单项选择题（20分，每题2分）

单项选择题答题表

二、判断及改错题（20分，每题2分）

判断及改错题答题表

三、（20分）对于如下的线性规划问题

min z = 3x1 + 2x2 +x3

s.t. x

1 + x

2

+ x

3

≤ 15 (1)

2x

1 - x

2

+ x

3

≥ 9 (2)

-x

1 + 2x

2

+2x

3

≤ 8 (3)

x

1 x

2

x

3

≥ 0

1、（5分，每个方程各1分）写出题目中线性规划问题的对偶问题；

解：max w = 15y1 + 9y2 + 8y3

s.t. y

1 + 2y

2

- y

3

≤ 3 (1)

y

1 - y

2

+ 2y

3

≤ 2 (2)

y

1 + y

2

+ 2y

3

≤ 1 (3)

y

1≤0、 y

2

≥0、y

3

≤0

2、（10分，步骤为6分，结果为4分）分别求出原始问题和对偶问题的最优解（求解的次序和方法不限）；

解：先将原问题化成以下形式，则有

mi n z = 3x1 + 2x2 + x3

s.t. x

1 + x

2

+ x

3

+ x

4

= 15 (1)

-2x

1 + x

2

- x

3

+ x

5

= -9 (2)

-x

1 + 2x

2

+2x

3

+x

6

= 8 (3)

中国计量学院200 ~200 学年第学期《运筹学》课程试卷（C ）第7页共 6 页

原始问题的最优解为（X1 X2 X3 X4 X5 X6）=（2，0，5，8，0，0），minz=11

对偶问题的最优解为（y1 y2 y3 y4 y5 y6）=（0，7/5，-1/5，0，19/5，0），maxw=11 3、（5分）C3如何变化，使该问题最优性不变。

解：设有C3+q,当C3=1时，取最优表变形为：

-19/5+3q/5 ≤0和 -7/5-q/5≤0和-1/5+2q/5≤0同时成立，则有-7≤q ≤1/2，即有-6≤1+q≤3/2

因此当C3在[-6，3/2]的范围内变化时，最优性不变。

中国计量学院200 ~200 学年第学期《运筹学》课程试卷（C ）第8页共 6 页

四、（15

最优总运费为0×15+5×5+25×5+10×5+80×15＝1475（结果6分，步骤4分）根据位势法原理非基变量σij＝cij-（ ui+vj）所有的σij满足大于零。

σ12＝c12-（-2+5）》0，所以c12》3，最小值为3

σ13＝c13-（-2+10）》0，所以c12》8，最小值为8

σ23＝c23-（3+10）》0，所以c12》13，最小值为13

σ11＝c11-（5+2）》0，所以c12》7，最小值为7

（结果3分，步骤2分）

五、（10分）求项目的完工期和关键路线。

a ,7 e,10 g,35

②⑤

④⑥⑨

C,12 f,24 i,17

③⑦⑧

j,34

T ES(1,2)= T ES(1,3)= T ES(1,4)=0

T ES(2,4)= T ES(1,2)+t12 =0+7=7= T ES(2,5)

T ES(3,4)= T ES(1,3)+t13 =0+12=12= T ES(3,7)

T ES(4,6)=max{T ES(2,4)+t24, T ES(1,4)+t14, T ES(3,4)+t34, } =12

T ES(5,9)= T ES(2,5)+t25 =7+10=17

T ES(6,9)= T ES(4,6)+t46 =12+17=29

T ES(7,8)= T ES(7,9) = T ES(3,7)+t37 =12+24=36

T ES(8,9)= T ES(7,8)+t78 =36+34=70

T EF(5,9)= T ES(5,9)+t59 =17+35=52

T EF(6,9)= T ES(6,9)+t69 =29+26=55

T EF(8,9)= T ES(8,9)+t89 =70+0=70

所以完工期为T=70天，结果为5分。

T LS(5,9)= T-t59 =70-35=35

T LS(6,9)= T-t69 =70-26=34

T LS(7,9)= T-t79 =70-17=53

中国计量学院200 ~200 学年第学期《运筹学》课程试卷（C ）第9页共 6 页

T LS(8,9)= T-t89 =70-0=70

T LS(7,8)= T LS(8,9)-t78 =70-34=36

T LS(2,5)= T LS(5,9)-t25 =35-10=25

T LS(4,6)= T LS(6,9)-t46 =34-17=17

T LS(3,7)= min{ T LS(7,9)-t37, T LS(7,8)-t37}=12

T LS(3,4)= T LS(3,7)-t34 =12-0=12

T LS(2,4)= T LS(2,5)-t24 =25-0=25

T LS(1,2)= min{ T LS(2,5)-t12, T LS(2,4)-t12}=8

T LS(1,3)= min{ T LS(3,7)-t13, T LS(3,4)-t13}=0

T LS(1,4)= T LS(4,6)-t14 =17-8=5

所以关键路线为：c f j，结果为5分。

六、（共15分）最小支撑树为下图所示，权值为35；（最小支撑树为3分，权值为2分）

3 4

①②③④

2 5 1

1

⑤⑥⑦⑧

4 6 3

⑨⑩⑾⑿

2 4

最短路径为1-2-3-4-8-12，路径为18。（其中最短路步骤为4分，结果为6分）

中国计量学院200 ~~200 学年第学期《运筹学》课程试卷（C ）第10页共 6 页