运筹学 2015 年学年第二学期
期末考试题（ a 卷）
注意事项：
1、答题前，考生务必将自己的姓名、班级填写在答题卡上。 2、答案用钢笔或圆珠笔写在答题卡上，答在试卷上不给分。 3、考试结束，将试卷和答题卡一并交回。
一、 单项选择题 ( 每小题 1 分，共 10 分 )
1：在下面的数学模型中，属于线性规划模型的为（
max S A . s.t .
4X XY X,Y 0
Y 3
）
min B. s.t.
S 3X 2X
Y
Y 1 C.
ma x S s.t.
X 2 X
Y X,Y 0
Y 2 2D.
min s.t.
S 2XY X
Y 3 X,Y 0
X,Y 0
2．线性规划问题若有最优解，则一定可以在可行域的 A．内点 A．多余变量 解为（ A. 两个 A ．解
）
B. 零个 B ．目标值
C.无穷多个 ）相同。
C． 解结构
B
（ D （
D
）上达到。 ．几何点
．顶点 B ．松弛变量
C
C.
．外点
3：在线性规划模型中，没有非负约束的变量称为
）
自由变量 ．人工变量
4：若线性规划问题的最优解同时在可行解域的两个顶点处达到，那么该线性规划问题最优
D.有限多个
5：原问题与对偶问题的最优（
D．解的分量个数
6：若原问题中 xi 为自由变量，那么对偶问题中的第 A．等式约束 A ．小于或等于零
B． “≤”型约束
B ．大于零
i 个约束一定为 （
D
．无法确定
）
)
）
C ． “≥”约束 C．小于零
7：若运输问题已求得最优解，此时所求出的检验数一定是全部（
D．大于或等于零
8：对于 m 个发点、 n 个收点的运输问题，叙述错误的是( A ．该问题的系数矩阵有 m× n 列
B．该问题的系数矩阵有 m+n 行
C．该问题的系数矩阵的秩必为 m+n-1
）
D．该问题的最优解必唯一
9：关于动态规划问题的下列命题中错误的是（ A 、动态规划分阶段顺序不同，则结果不同 B、状态对决策有影响
C、动态规划中，定义状态时应保证在各个阶段中所做决策的相对独立性 D、动态规划的求解过程都可以用列表形式实现
10：若 P 为网络 G 的一条流量增广链，则
P 中所有正向弧都为
G 的（ D．不饱和边
）
A ．对边
B ．饱和边
C．邻边
二、 判断题（每小题
1 分，共 10 分）
1：图解法和单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的。
2：单纯形法的迭代计算过程是从一个可行解转换到目标函数值更大的另一个可行解。
（√）
（× ）
3：一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果。 （√ ）
4：若线性规划问题中的
bi , c j 值同时发生改变，反映到最终单纯形表中，不会出现原问题
（×）
与对偶问题均为非可行基的情况。
5：若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优解。 6：运输问题的表上作业法实质上就是求解运输问题的单纯形法。
（√ ）
（√ ）
（× ）
7：对于动态规划问题，应用顺推或逆推解法可能会得出不同的最优解。 决策问题。（√ ）
8：动态规划的基本方程是将一个多阶段的决策问题转化为一系列具有递推关系的单阶段的 9：图论中的图不仅反映了研究对象之间的关系，而且是真实图形的写照，因而对图中点与 点的相对位置、点与点连线的长短曲直等都要严格注意。 （× ） 10：网络最短路线问题和最短树问题实质上是一个问题。 三、 填空题（每空 1 分，共 15 分）
1：线性规划中， 满足非负条件的基本解称为
_____。
（× ）
___基本可行解 _____，对应的基称为 ___可行基
2：线性规划的目标函数的系数是其对偶问题的 问题，则对偶问题为 ___最小化问题 _____。 3：在运输问题模型中，
__右端常数 ______；而若线性规划为最大化
m n 1个变量构成基变量的充要条件是
__不含闭回路 ______。
4：动态规划方法的步骤可以总结为：逆序求解 ____最优目标函数 ____，顺序求 ____最优策
略、 ____、___最优路线 _____和 ___最优目标函数值 _____。
5：工程路线问题也称为最短路问题，根据问题的不同分为定步数问题和不定步数问题；对
____函数 ____迭代法和 ____策略 ____迭代法两种方法。 不定步数问题，用迭代法求解，有 6：在图论方法中，通常用
____点 ____表示人们研究的对象，用
___边 _____表示对象之间的
某种联系。
7：一个 _____无圈 ___且 ____连通 ____的图称为树。 四、计算题（每小题
15 分， 45 分）
1：考虑线性规划问题：
C．该问题的系数矩阵的秩必为 m+n-1
）
D．该问题的最优解必唯一
9：关于动态规划问题的下列命题中错误的是（ A 、动态规划分阶段顺序不同，则结果不同 B、状态对决策有影响
C、动态规划中，定义状态时应保证在各个阶段中所做决策的相对独立性
D、动态规划的求解过程都可以用列表形式实现
10：若 P 为网络 G 的一条流量增广链，则
P 中所有正向弧都为 G 的（
）
A ．对边
B ．饱和边
C．邻边
二、 判断题（每小题 1 分，共
1：图解法和单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的。
2：单纯形法的迭代计算过程是从一个可行解转换到目标函数值更大的另一个可行解。
（√）
（× ）
3：一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中 删除，而不影响计算结果。 （√ ） 4：若线性规划问题中的
bi , c j 值同时发生改变，反映到最终单纯形表中，不会出现原问题
（×）
与对偶问题均为非可行基的情况。
5：若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优解。 6：运输问题的表上作业法实质上就是求解运输问题的单纯形法。
（√ ）
（√ ）
（× ）
7：对于动态规划问题，应用顺推或逆推解法可能会得出不同的最优解。 决策问题。（√ ）
8：动态规划的基本方程是将一个多阶段的决策问题转化为一系列具有递推关系的单阶段的 9：图论中的图不仅反映了研究对象之间的关系，而且是真实图形的写照，因而对图中点与 点的相对位置、点与点连线的长短曲直等都要严格注意。 （× ） 10：网络最短路线问题和最短树问题实质上是一个问题。 三、 填空题（每空 1 分，共 15 分）
1：线性规划中， 满足非负条件的基本解称为
_____。
（× ）
___基本可行解 _____，对应的基称为 ___可行基
2：线性规划的目标函数的系数是其对偶问题的 问题，则对偶问题为 ___最小化问题 _____。 3：在运输问题模型中，
__右端常数 ______；而若线性规划为最大化
m n 1个变量构成基变量的充要条件是
__不含闭回路 ______。
4：动态规划方法的步骤可以总结为：逆序求解 ____最优目标函数 ____，顺序求 ____最优策
略、 ____、___最优路线 _____和 ___最优目标函数值 _____。
5：工程路线问题也称为最短路问题，根据问题的不同分为定步数问题和不定步数问题；对
____函数 ____迭代法和 ____策略 ____迭代法两种方法。 不定步数问题，用迭代法求解，有 6：在图论方法中，通常用
____点 ____表示人们研究的对象，用
___边 _____表示对象之间的
某种联系。
7：一个 _____无圈 ___且 ____连通 ____的图称为树。 四、计算题（每小题
15 分， 45 分）
1：考虑线性规划问题：
C．该问题的系数矩阵的秩必为 m+n-1
）
D．该问题的最优解必唯一
9：关于动态规划问题的下列命题中错误的是（ A 、动态规划分阶段顺序不同，则结果不同 B、状态对决策有影响
C、动态规划中，定义状态时应保证在各个阶段中所做决策的相对独立性
D、动态规划的求解过程都可以用列表形式实现
10：若 P 为网络 G 的一条流量增广链，则
P 中所有正向弧都为 G 的（
）
A ．对边
B ．饱和边
C．邻边
二、 判断题（每小题 1 分，共
1：图解法和单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的。
2：单纯形法的迭代计算过程是从一个可行解转换到目标函数值更大的另一个可行解。
（√）
（× ）
3：一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中 删除，而不影响计算结果。 （√ ） 4：若线性规划问题中的
bi , c j 值同时发生改变，反映到最终单纯形表中，不会出现原问题
（×）
与对偶问题均为非可行基的情况。
5：若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优解。 6：运输问题的表上作业法实质上就是求解运输问题的单纯形法。
（√ ）
（√ ）
（× ）
7：对于动态规划问题，应用顺推或逆推解法可能会得出不同的最优解。 决策问题。（√ ）
8：动态规划的基本方程是将一个多阶段的决策问题转化为一系列具有递推关系的单阶段的 9：图论中的图不仅反映了研究对象之间的关系，而且是真实图形的写照，因而对图中点与 点的相对位置、点与点连线的长短曲直等都要严格注意。 （× ） 10：网络最短路线问题和最短树问题实质上是一个问题。 三、 填空题（每空 1 分，共 15 分）
1：线性规划中， 满足非负条件的基本解称为
_____。
（× ）
___基本可行解 _____，对应的基称为 ___可行基
2：线性规划的目标函数的系数是其对偶问题的 问题，则对偶问题为 ___最小化问题 _____。 3：在运输问题模型中，
__右端常数 ______；而若线性规划为最大化
m n 1个变量构成基变量的充要条件是
__不含闭回路 ______。
4：动态规划方法的步骤可以总结为：逆序求解 ____最优目标函数 ____，顺序求 ____最优策
略、 ____、___最优路线 _____和 ___最优目标函数值 _____。
5：工程路线问题也称为最短路问题，根据问题的不同分为定步数问题和不定步数问题；对
____函数 ____迭代法和 ____策略 ____迭代法两种方法。 不定步数问题，用迭代法求解，有 6：在图论方法中，通常用
____点 ____表示人们研究的对象，用
___边 _____表示对象之间的
某种联系。
7：一个 _____无圈 ___且 ____连通 ____的图称为树。 四、计算题（每小题
15 分， 45 分）
1：考虑线性规划问题：
C．该问题的系数矩阵的秩必为 m+n-1
）
D．该问题的最优解必唯一
9：关于动态规划问题的下列命题中错误的是（ A 、动态规划分阶段顺序不同，则结果不同 B、状态对决策有影响
C、动态规划中，定义状态时应保证在各个阶段中所做决策的相对独立性
D、动态规划的求解过程都可以用列表形式实现
10：若 P 为网络 G 的一条流量增广链，则
P 中所有正向弧都为 G 的（
）
A ．对边
B ．饱和边
C．邻边
二、 判断题（每小题 1 分，共
1：图解法和单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的。
2：单纯形法的迭代计算过程是从一个可行解转换到目标函数值更大的另一个可行解。
（√）
（× ）
3：一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中 删除，而不影响计算结果。 （√ ） 4：若线性规划问题中的
bi , c j 值同时发生改变，反映到最终单纯形表中，不会出现原问题
（×）
与对偶问题均为非可行基的情况。
5：若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优解。 6：运输问题的表上作业法实质上就是求解运输问题的单纯形法。
（√ ）
（√ ）
（× ）
7：对于动态规划问题，应用顺推或逆推解法可能会得出不同的最优解。 决策问题。（√ ）
8：动态规划的基本方程是将一个多阶段的决策问题转化为一系列具有递推关系的单阶段的 9：图论中的图不仅反映了研究对象之间的关系，而且是真实图形的写照，因而对图中点与 点的相对位置、点与点连线的长短曲直等都要严格注意。 （× ） 10：网络最短路线问题和最短树问题实质上是一个问题。 三、 填空题（每空 1 分，共 15 分）
1：线性规划中， 满足非负条件的基本解称为
_____。
（× ）
___基本可行解 _____，对应的基称为 ___可行基
2：线性规划的目标函数的系数是其对偶问题的 问题，则对偶问题为 ___最小化问题 _____。 3：在运输问题模型中，
__右端常数 ______；而若线性规划为最大化
m n 1个变量构成基变量的充要条件是
__不含闭回路 ______。
4：动态规划方法的步骤可以总结为：逆序求解 ____最优目标函数 ____，顺序求 ____最优策
略、 ____、___最优路线 _____和 ___最优目标函数值 _____。
5：工程路线问题也称为最短路问题，根据问题的不同分为定步数问题和不定步数问题；对
____函数 ____迭代法和 ____策略 ____迭代法两种方法。 不定步数问题，用迭代法求解，有 6：在图论方法中，通常用
____点 ____表示人们研究的对象，用
___边 _____表示对象之间的
某种联系。
7：一个 _____无圈 ___且 ____连通 ____的图称为树。 四、计算题（每小题
15 分， 45 分）
1：考虑线性规划问题：
C．该问题的系数矩阵的秩必为 m+n-1
）
D．该问题的最优解必唯一
9：关于动态规划问题的下列命题中错误的是（ A 、动态规划分阶段顺序不同，则结果不同 B、状态对决策有影响
C、动态规划中，定义状态时应保证在各个阶段中所做决策的相对独立性
D、动态规划的求解过程都可以用列表形式实现
10：若 P 为网络 G 的一条流量增广链，则
P 中所有正向弧都为 G 的（
）
A ．对边
B ．饱和边
C．邻边
二、 判断题（每小题 1 分，共
1：图解法和单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的。
2：单纯形法的迭代计算过程是从一个可行解转换到目标函数值更大的另一个可行解。
（√）
（× ）
3：一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中 删除，而不影响计算结果。 （√ ） 4：若线性规划问题中的
bi , c j 值同时发生改变，反映到最终单纯形表中，不会出现原问题
（×）
与对偶问题均为非可行基的情况。
5：若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优解。 6：运输问题的表上作业法实质上就是求解运输问题的单纯形法。
（√ ）
（√ ）
（× ）
7：对于动态规划问题，应用顺推或逆推解法可能会得出不同的最优解。 决策问题。（√ ）
8：动态规划的基本方程是将一个多阶段的决策问题转化为一系列具有递推关系的单阶段的 9：图论中的图不仅反映了研究对象之间的关系，而且是真实图形的写照，因而对图中点与 点的相对位置、点与点连线的长短曲直等都要严格注意。 （× ） 10：网络最短路线问题和最短树问题实质上是一个问题。 三、 填空题（每空 1 分，共 15 分）
1：线性规划中， 满足非负条件的基本解称为
_____。
（× ）
___基本可行解 _____，对应的基称为 ___可行基
2：线性规划的目标函数的系数是其对偶问题的 问题，则对偶问题为 ___最小化问题 _____。 3：在运输问题模型中，
__右端常数 ______；而若线性规划为最大化
m n 1个变量构成基变量的充要条件是
__不含闭回路 ______。
4：动态规划方法的步骤可以总结为：逆序求解 ____最优目标函数 ____，顺序求 ____最优策
略、 ____、___最优路线 _____和 ___最优目标函数值 _____。
5：工程路线问题也称为最短路问题，根据问题的不同分为定步数问题和不定步数问题；对
____函数 ____迭代法和 ____策略 ____迭代法两种方法。 不定步数问题，用迭代法求解，有 6：在图论方法中，通常用
____点 ____表示人们研究的对象，用
___边 _____表示对象之间的
某种联系。
7：一个 _____无圈 ___且 ____连通 ____的图称为树。 四、计算题（每小题
15 分， 45 分）
1：考虑线性规划问题：
C．该问题的系数矩阵的秩必为 m+n-1
）
D．该问题的最优解必唯一
9：关于动态规划问题的下列命题中错误的是（ A 、动态规划分阶段顺序不同，则结果不同 B、状态对决策有影响
C、动态规划中，定义状态时应保证在各个阶段中所做决策的相对独立性
D、动态规划的求解过程都可以用列表形式实现
10：若 P 为网络 G 的一条流量增广链，则
P 中所有正向弧都为 G 的（
）
A ．对边
B ．饱和边
C．邻边
二、 判断题（每小题 1 分，共
1：图解法和单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的。
2：单纯形法的迭代计算过程是从一个可行解转换到目标函数值更大的另一个可行解。
（√）
（× ）
3：一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中 删除，而不影响计算结果。 （√ ） 4：若线性规划问题中的
bi , c j 值同时发生改变，反映到最终单纯形表中，不会出现原问题
（×）
与对偶问题均为非可行基的情况。
5：若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优解。 6：运输问题的表上作业法实质上就是求解运输问题的单纯形法。
（√ ）
（√ ）
（× ）
7：对于动态规划问题，应用顺推或逆推解法可能会得出不同的最优解。 决策问题。（√ ）
8：动态规划的基本方程是将一个多阶段的决策问题转化为一系列具有递推关系的单阶段的 9：图论中的图不仅反映了研究对象之间的关系，而且是真实图形的写照，因而对图中点与 点的相对位置、点与点连线的长短曲直等都要严格注意。 （× ） 10：网络最短路线问题和最短树问题实质上是一个问题。 三、 填空题（每空 1 分，共 15 分）
1：线性规划中， 满足非负条件的基本解称为
_____。
（× ）
___基本可行解 _____，对应的基称为 ___可行基
2：线性规划的目标函数的系数是其对偶问题的 问题，则对偶问题为 ___最小化问题 _____。 3：在运输问题模型中，
__右端常数 ______；而若线性规划为最大化
m n 1个变量构成基变量的充要条件是
__不含闭回路 ______。
4：动态规划方法的步骤可以总结为：逆序求解 ____最优目标函数 ____，顺序求 ____最优策
略、 ____、___最优路线 _____和 ___最优目标函数值 _____。
5：工程路线问题也称为最短路问题，根据问题的不同分为定步数问题和不定步数问题；对
____函数 ____迭代法和 ____策略 ____迭代法两种方法。 不定步数问题，用迭代法求解，有 6：在图论方法中，通常用
____点 ____表示人们研究的对象，用
___边 _____表示对象之间的
某种联系。
7：一个 _____无圈 ___且 ____连通 ____的图称为树。 四、计算题（每小题
15 分， 45 分）
1：考虑线性规划问题：
C．该问题的系数矩阵的秩必为 m+n-1
）
D．该问题的最优解必唯一
9：关于动态规划问题的下列命题中错误的是（ A 、动态规划分阶段顺序不同，则结果不同 B、状态对决策有影响
C、动态规划中，定义状态时应保证在各个阶段中所做决策的相对独立性
D、动态规划的求解过程都可以用列表形式实现
10：若 P 为网络 G 的一条流量增广链，则
P 中所有正向弧都为 G 的（
）
A ．对边
B ．饱和边
C．邻边
二、 判断题（每小题 1 分，共
1：图解法和单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的。
2：单纯形法的迭代计算过程是从一个可行解转换到目标函数值更大的另一个可行解。
（√）
（× ）
4：若线性规划问题中的
bi , c j 值同时发生改变，反映到最终单纯形表中，不会出现原问题
（×）
与对偶问题均为非可行基的情况。
5：若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优解。 6：运输问题的表上作业法实质上就是求解运输问题的单纯形法。
（√ ）
（√ ）
（× ）
7：对于动态规划问题，应用顺推或逆推解法可能会得出不同的最优解。 决策问题。（√ ）
8：动态规划的基本方程是将一个多阶段的决策问题转化为一系列具有递推关系的单阶段的 9：图论中的图不仅反映了研究对象之间的关系，而且是真实图形的写照，因而对图中点与 点的相对位置、点与点连线的长短曲直等都要严格注意。 （× ） 10：网络最短路线问题和最短树问题实质上是一个问题。 三、 填空题（每空 1 分，共 15 分）
1：线性规划中， 满足非负条件的基本解称为
_____。
（× ）
___基本可行解 _____，对应的基称为 ___可行基
2：线性规划的目标函数的系数是其对偶问题的 问题，则对偶问题为 ___最小化问题 _____。 3：在运输问题模型中，
__右端常数 ______；而若线性规划为最大化
m n 1个变量构成基变量的充要条件是
__不含闭回路 ______。
4：动态规划方法的步骤可以总结为：逆序求解 ____最优目标函数 ____，顺序求 ____最优策
略、 ____、___最优路线 _____和 ___最优目标函数值 _____。
5：工程路线问题也称为最短路问题，根据问题的不同分为定步数问题和不定步数问题；对
____函数 ____迭代法和 ____策略 ____迭代法两种方法。 不定步数问题，用迭代法求解，有 6：在图论方法中，通常用
某种联系。
____点 ____表示人们研究的对象，用
___边 _____表示对象之间的
因篇幅问题不能全部显示，请点此查看更多更全内容