班级： 学号： X X ：
XX 学院2021 年成人学士学位主干课程考试卷
专业：信息与计算科学 科目：运筹学
题 号
一 二 三 四 五 六 七 八 九 总 分 得 分 阅卷人
一、选择题〔共5小题，每题4分〕
1、如果一个线性规划问题有n 个变量，m 个约束方程(m<n)，系数矩阵的数为m ，那么基可行解的个数最为〔 C 〕。

A ．m 个
B ．n 个
C ．m n C
D ．n m C 个
2、在 求 最 大 流 量 的问 题 中，已 知 与 起 点 相 邻 的 三 节 点 单 位 时 间 的 流 量 分 别 为 10,12,15，那么 终 点 单 位 时 间 输 出 的 最 大 流 量 为〔 D 〕 A. 等 于 27 B.大 于 或 等 于 37
C.小 于37
D.小 于 或 等 于 37
3、如下列图中每条有向边上的数字为该边的容量限制，那么从发点到收点的最大流是〔 C 〕
A 、18
B 、11
C 、12
D 、16 解析：用最大流标记法可得：
4、用最小元素法求初始调运方案是，运输表中数字格的个数为〔D 〕个。

A 、m*n
B 、m+n
C 、m*n-1
D 、m+n-1
5、假设用ES i 表示结点i 的最早开场时间，ES j 表示结点j 的最早开场时间，T i ，j 表示活动i →j 的作业时间，LF i 表示结点i 的最迟完成时间，LF j 表示结点j 的最迟完成时间，那么下述公式中正确的选项是〔 A 〕 A.ES j =}{max ,i j i i j
T ES +<
B.ES j =}{min ,i j i i j
T ES +<
C.LF j =}{max ,i j i i j
T LF -<
D.LF j =}{min ,i j i i j
T LF +<
二、填空题〔共5小题，每题4分〕
1、求解运输问题时，常用的判断运输方案是否最优的方法，一个是闭合回路，另一个是____位势法____。

2、假设用三种时间估计法计算作业时间，那么应先估计出最乐观时间、____悲观____时间和最可能时间。

3、 Max z=3x 1+8x 2+5x 3 4x 1+2x 2≤15 S.t 3x 1+x 3≤9
线性规划问题 x 1、x 2、x 3≥0 的标准形式是_______________
答案： Max z=3x 1+8x 2+5x 3+0*x 4+0*x 5 4x 1+2x 2+x 4=15 S.t 3x 1+x 3+x 5=9
x 1、x 2、x 3、x 4、x 5≥0
4、写出线性规划问题⎪⎪
⎭
⎪⎪⎬
⎫⎪⎪⎩⎪⎪⎨⎧≥≤++≤+-≥-+++=0,5643732532.422min 3,213213213213
21x x x x x x x x x x x x t s x x x Z 的对偶问题_______________
答案：⎪⎪⎭
⎪⎪
⎬⎫⎪⎪⎩⎪⎪⎨⎧≤≤≥≤++-≤+-≤++++=0,0,04675243232.532max 3213213213213
21y y y y y y y y y y y y t s y y y u
5、下表是制定生产方案问题的一XLP 最优单纯形表〔极大化问题，约束条件均为“≤〞型不
x1x2x3x4 x23/2 0 1 5/14 -3/14 x1 1 1 0 -1/7 2/5 -z -35/2 0 0 -5/14 -25/14 ∴最优解x = (1,3/2,0,0)T
∴目标函数的最大值z = 35/2
2、用动态规划的方法求出A→D的最短路径。

答案：最短路径为A→B3→C1→D为21
3、线性规划问题
Max z=2x1+x2+5x3+6x4 对偶变量
其对偶问题的最优解为y 1*
=4， y 2*
=1，试应用对偶问题的性质，求原问题的最优解。

4、用标号法求如图下所示网络的最大流和最小截集(割集)，每弧旁的数字是〔ij ij f c ,〕。

V 1 (4,2) V 3
(6,6) (6,4)
V S (3,1) (3,0) (4,1) Vt
(5,3) (7,5)
V 2 (4,4) V 4
解：
（1）标号过程
①首先给Vs 标上〔0，+∞〕。

②检查Vs ，
在弧〔Vs,V1〕上，fs1=Cs1=6，不满足标号条件。

在弧〔Vs,V2〕上，fs2<Cs2,给V2标号〔Vs ，l 〔V2〕〕
2x 1 +x3 +x4≤8 y1 2x1+2x2 + x3 +2x4≤12 y2 X j ≥0， j=1,2.。

4
v j v1=0 v2=0 v3=4 v4=8 v5=1
得出(u i+v j):
B1B2B3B4B5u i
销地
产地
A10 0 4 8 1 u1=0
A20 0 4 8 1 u2=0
A3 5 5 9 13 6 u3=5
A4 2 2 6 10 3 u4=2
v j v1=0 v2=0 v3=4 v4=8 v5=1
检验数C ij - (u i+v j)都大于0，所以为最优解。

C ij - (u i+v j)：
销地
B1B2B3B4B5u i
产地
A1 6 9 0 0 4 u1=0
A210 6 8 0 6 u2=0
A3 1 0 0 7 3 u3=5
A40 11 0 4 0 u4=2
v j v1=0 v2=0 v3=4 v4=8 v5=1
因此最有方案为：x13=5, x14=15, x24=30, x32=15, x33=25, x41=25, x43=5, x45=30, 最少运费为=850万元。

6、某工程的有关资料如表，画出其工程网络方案图。

答案：〔做题关键：了解网络方案根本元素紧前工作、紧后工作、虚工作和平行工作的定义〕。