运筹学期末考试题（b 卷）
注意事项：
1、答题前，考生务必将自己的姓名、班级填写在答题卡上。
2、答案用钢笔或圆珠笔写在答题卡上，答在试卷上不给分。
3、考试结束，将试卷和答题卡一并交回。
一、 单项选择题(每小题1分，共10分)
1：下列关于运筹学的缺点中，不正确的是( )
A.在建立数学模型时，若简化不慎，用运筹学求得的最优解会因与实际相差大而失去意义
B.运筹学模型只能用借助计算机来处理
C.有时运筹学模型并不能描述现实世界
D.由于运筹学方法的复杂性使一些决策人员难以接受这些解决问题的方法 2：在下面的数学模型中，属于线性规划模型的为（ ） ⎪⎩
⎪⎨⎧≥≤+=0Y ,X 3XY .t .s Y X 4S m ax .A ⎪⎩⎪⎨⎧≥-≥-+=0Y ,X 1Y X 2.t .s Y
X 3S mi n .B ⎪⎩
⎪⎨⎧≥≤-+=0Y ,X 2Y X .t .s Y X S ma x .C 22 ⎪⎩⎪
⎨⎧≥≥+=0
Y ,X 3Y X .
t .s XY
2S m in .D 3．线性规划一般模型中，自由变量可以用两个非负变量的 （ ）代换。 A ．和 B ．商 C ．积 D ．差 4：以下关系中，不是线性规划与其对偶问题的对应关系的是( )。 A.约束条件组的系数矩阵互为转置矩阵
B.一个约束条件组的常数列为另一个目标函数的系数行向量
C.两个约束条件组中的方程个数相等
D.约束条件组的不等式反向
5．对偶问题的对偶是 （ ）
A ．原问题
B ．解的问题
C ．其它问题
D ．基本问题 6：若原问题中0i x ≥，那么对偶问题中的第i 个约束一定为 （ ）
A ．等式约束
B ．“≤”型约束
C ．“≥”约束
D ．无法确定
7：若运输问题已求得最优解，此时所求出的检验数一定是全部（ ） A ．小于或等于零 B ．大于零
C ．小于零
D ．大于或等于零
8：考虑某运输问题，其需求量和供应量相等，且供应点的个数为m ，需求点的个数是n 。若以西北角法求得其初始运输方案，则该方案中数字格的数目应为（ ） A.（m+n ）个 B.（m+n-1）个 C.（m-n ）个 D.（m-n+1）个 9：关于动态规划问题的下列命题中错误的是（ ） A 、动态规划分阶段顺序不同，则结果不同 B 、状态对决策有影响
C 、动态规划中，定义状态时应保证在各个阶段中所做决策的相对独立性
D 、动态规划的求解过程都可以用列表形式实现
10：若P 为网络G 的一条流量增广链，则P 中所有逆向弧都为G 的（ ）
A ．非零流弧
B ．饱和边
C ．零流弧
D ．不饱和边 二、 判断题（每小题1分，共10分）
1：如线性规划问题存在最优解，则最优解一定对应可行域边界上的一个点。（ ） 2：线性规划问题的每一个基解对应可行域的一个顶点（ ） 3：若线性规划问题具有可行解，且其可行域有界，则该线性规划问题最多具有有限个数的最优解（ ） 4：对偶问题的对偶问题一定是原问题。（ ） 5：任何线性规划问题存在并具有唯一的对偶问题。（ ） 6：运输问题是一种特殊的线性规划模型，因而求解结果也可能出现下列四种情况之一：有唯一最优解，有无穷多最优解，无界解，无可行解。（ ） 7： 动态规划的最优性原理保证了从某一状态开始的未来决策独立于先前已做出的决策。（ ） 8： 一个线性规划问题若转化为动态规划方法求解时，应严格按变量的下标顺序来划分阶段， 如将决定1x 的值作为第一阶段，决定2x 的值作为第二阶段等。（ ）
9：在任意图中，当点集确定后，树是图中边数最少的连通图。（ ） 10：求网络最大流的问题可以归结为求解一个线性规划模型。（ ） 三、 填空题（每空1分，共15分）
1：满足所有约束条件的一组值称为线性规划的________，这些解中，使目标函数取得最大 或最小值的解称为线性规划问题的_______。
2：在单纯形法中，初始基可能由________、________和________三种类型的变量组成。 3：若原始问题可行，则其目标函数无界的充要条件是对偶问题________；若对偶问题为无
界解，其原问题为________。
4：在运输问题模型中，计算检验数的方法一般有________和________两种方法。
5：动态规划方法的步骤可以总结为：逆序求解________，顺序求________、________和
________。
6：树的任意两个顶点之间有且只有一条________。
7：网络中满足容量限制条件和中间点平衡条件的弧上的流称为_________。 四、计算题（每小题15分，45分）
1：已知线性规划：
121212121241max 322233..,0
z x x x x x x s t x x x x =+-+⎧⎪+ ≤≤≤2 ⎨
-≥⎪⎪⎪⎩ （a ）：用单纯形方法求解该线性规划问题的最优解和最优值；
（b ）：写出线性规划的对偶问题； （c ）：求解对偶问题的最优解和最优值。
2：今有1000台机床，要投放到A 、B 两个生产部门，计划连续使用3年。已知对A
部门投入A u 台机器时的年收益是2
()4A A g u u =（元），机器的完好率0.5a =，相应的B 部门的年收益是2()2B B h u u =（元），完好率0.9b =。试求3年间总收益最大的年度机器分配
方案。
3：用破圈法和生长法求下图的最短树。
五、问答题(每小题5分，共10分)
1．简述动态规划建模的一般过程和最优性原理。
2．网络最短路线问题的求解有多种方法，一般有狄克斯拉算法、海斯算法和福德算法。试分析各自适用的范围和优缺点。
期末考试参考答案及评分标准（b 卷）
单项选择题(每小题1分，共10分)
1.B
2.B
3.D
4.C
5.A
6.C
7.D
8.B
9.A 10.A 判断题（每小题1分，共10分）
1.T
2.F
3.F
4.T
5.T
6.F
7.T
8.F
9.T 10.T 填空题（每空1分，共15分）
1：可行解、最优解；2：决策变量、松弛变量、人工变量；3：没有可行解、无可行解；4：闭回路法、位势法；5：最优目标函数、最优策略、最优路线、最优目标函数值；6：初等链；7：可行流。
计算题（每小题15分，45分） 1：解 a):
*[]
max 18332
,,,0,05355
183
212
55
X z ⨯+⨯===
------（5分）
b ）：其对偶问题为
123123123123min 41233..2,3
22
,w y y y y y y s t y y y y y y =++≥≥≥-++⎧⎪
+ -⎨⎪⎩
------（5分） c ）：
*[0,1,0]Y =，
*
*
012130124w z ⨯+⨯+⨯===。 ------（5分） 2：解 该问题可以作为三段资源分配问题，每个年度是一个阶段。 k 阶段状态变量k x 取为
