《管理运筹学》历年模拟试卷（一）

一、

单选题（每题２分，共20分。）

1．目标函数取极小（minZ）的线性规划问题可以转化为目标函数取极

大的线性规划问题求解，原问题的目标

函数值等于（ ）。

A. maxZ B. max(-Z) C. –max(-Z)

D.-maxZ

2. 下列说法中正确的是（ ）。

Ａ．基本解一定是可行解 Ｂ．基本可行解的每个分量一定非负

Ｃ．若B是基，则B一定是可逆 Ｄ．非基变量的系数列向量一定是线性相关的

3．在线性规划模型中，没有非负约束的变量称为 （ ）

多余变量 B．松弛变量 C．人工变量 D．自由变量

4. 当满足最优解，且检验数为零的变量的个数大于基变量的个数时，可求得（ ）。

Ａ．多重解 Ｂ．无解 Ｃ．正则解 Ｄ．退化解

5．对偶单纯型法与标准单纯型法的主要区别是每次迭代的基变量都满

足最优检验但不完全满足 （ ）。 A．等式约束 B．“≤”型约束 C．“≥”约束 D．非负约束

6. 原问题的第ｉ个约束方程是“＝”型，则对偶问题的变量yi是（ ）。

Ａ．多余变量 Ｂ．自由变量 Ｃ．松弛变量 Ｄ．非负变量

7.在运输方案中出现退化现象，是指数字格的数目( )。

A.等于m+n B.大于m+n-1 C.小于m+n-1 D.等于m+n-1

8. 树Ｔ的任意两个顶点间恰好有一条（ ）。

Ａ．边 Ｂ．初等链 Ｃ．欧拉圈

Ｄ．回路

9．若G中不存在流f增流链，则f为G的 （ ）。

A．最小流 B．最大流 C．最小费用流 D．无法确定

10.对偶单纯型法与标准单纯型法的主要区别是每次迭代的基变量都满足最优检验但不完全满足（ ）

Ａ．等式约束 Ｂ．“≤”型约束 Ｃ．“≥”型约束 Ｄ．非负约束

二、多项选择题（每小题4分，共20分）

1．化一般规划模型为标准型时，可能引入的变量有 （ ）

1

A．松弛变量 B．剩余变量 C．非负变量 D．非正变量 E．自由变量

2．图解法求解线性规划问题的主要过程有 （ ）

A．画出可行域 B．求出顶点坐标 C．求最优目标值 D．选基本解 E．选最优解

3．表上作业法中确定换出变量的过程有 （ ）

A．判断检验数是否都非负 B．选最大检验数 C．确定换出变量

D．选最小检验数 E．确定换入变量

4．求解约束条件为“≥”型的线性规划、构造基本矩阵时，可用的变量有 （ ）

A．人工变量 B．松弛变量 C. 负变量 D．剩余变量 E．稳态变量

5．线性规划问题的主要特征有 （ ）

A．目标是线性的 B．约束是线性的 C．求目标最大值 D．求目标最小值 E．非线性

三、 计算题（共60分）

1. 下列线性规划问题化为标准型。(10分) minZ??x1+5x2-2x3

x1?x2?x3?6满足

2x1?x2?3x3?5x1?x2?10 x1?0,x2?0,x3符号不限

2. 写出下列问题的对偶问题 (10分)

minZ?4x1?2x2+3x3

4x1+5x2?6x3=7满足

8x1?9x2?10x3?1112x1?13x2?14 x1?0,x2无约束，x3?0

3. 用最小元素法求下列运输问题的一个初始基本可行解(10分)

4．某公司有资金10万元，若投资用于项目

2

i(i?1,2,3)的投资额为xi时，其收益分别为g1(x1)?4x1,g(x2)?9x2,

g(x3)?2x3,问应如何分配投资数额才能使总收益最大？(15分)

5． 求图中所示网络中的最短路。（15分）

《管理运筹学》历年模拟试卷（一）

参考答案

一、 单选题

1.C 2.B 3.D 4. A 5. D 6. B 7. C 8.B 9. B 10.D 二、 多选题

1. ABE 2. ABE 3. ACD 4. AD 5. AB 三、计算题

1、max(-z)=

x1?5x'2?2(x'3?x''3)

2、写出对偶问题

maxW=7y1?11y2?14y3

3

3、解： 4．解：状态变量sk为第k阶段初拥有的可以分配给第k到底3个项目的资金额；决策变量xk为决定给第k个项目的资金额；状态转移方程为sk?1?sk?xk；最优指标函数fk(sk)

表示第k阶段初始状态为sk时，从第k到第3个项目所获得的最大收益，fk(sk)即为所求的总收益。递推方程为：

fk(sk)?max?gk(xk)?fk?(sk?1)?(k?1,2,3)0?xk?sk f4(s4)?0 当k=3时有

0?x3?s3

2当x3?s3时，取得极大值2s3，即：

2f3(s3)?max?2x3??2x320?x3?s32f3(s3)?max?2x3? 当k=2时有：

2f2(s2)?max?9x2?f3(s3)?0?x2?s22

?max?9x0?x2?s20?x2?s2

2h(s,x)?9x?2(s?x)222222令 用经典解析方法求其极值点。 dh2?9?2(s2?x2)(?1)?0由 dx2 解得：

x2?s2?94

?max?9x2?2(s2?x2)?2?2s3?

d2h2?4?02dx2而

所以

x2?s2?94是极小值点。

极大值点可能在[0，s2]端点取得：

4

f2(0)?2s22， f2(s2)?9s2

当f2(0)?f2(s2)时，解得 s2?9/2

当s2?9/2时，f，此时，*2(0)?f2(s2)x2?0

当s2?9/2时，f2(0)?f2(s*2)，此时，x2?s2

f)?f当k=1时，

1(s1max?4x1?2(s2)?0?x1?s1

当 f1?9s1?9x1?2(s2)?9sfs1)?2时，

1(max?4x0?x1?s1

?max?9s1?5x 1??9s10?x1?s1

但此时 s2?s1?x1?10?0?10?9/2，与s2?9/2矛盾，所以舍去。

f当f21(10)?2(s2)?2s2时，

max?4x1?2(s1?x1)2?0?x1?10

令 h1(s1,x1)?4x1?2(s1?x21)

dh1?4?4(s由 dx2?x2)(?1)?01

解得： x2?s1?1 d2h2?1?0而 dx22 所以 x1?s1?1是极小值点。 比较[0,10]两个端点 x1?0时，f1(10)?200 x1?10时，f1(10)?40

x*1?0

所以

再由状态转移方程顺推：

s2?s1?x*1?10?0?10 因为 s2?9/2 所以 x*2?0，

s3?s*2?x2?10?0?10 因此 x*3?s3?10

最优投资方案为全部资金用于第3个项目，可获得最大收益200万元。

5. 解：用Dijkstra算法的步骤如下，

P（v1）＝0

T（vj）＝?（j＝2，3?7） 第一步：

因为?v1,v2?，?v1,v3??A

且v2，v3是T标号，则修改上个点的T标号分别为：

5