运筹学2015年学年第二学期期末考试题（a 卷）注意事项:1、答题前，考生务必将自己的姓名、班级填写在答题卡上。

2、答案用钢笔或圆珠笔写在答题卡上，答在试卷上不给分。

3、考试结束，将试卷和答题卡一并交回。

、单项选择题（每小题1分，共10分）1：在下面的数学模型中，属于线性规划模型的为（[max S=4X +Y [min S=3X+Y[maxS =X 2+Y 2A 」st. XY <3B.{s .t. 2X —丫 >一1 C .{ s.t. i X,Y >0I X, Y >0 j [min X -丫 <2 D.f st. X,Y >0S = 2XYX + 丫 >3X,Y >02. A . 3:线性规划问题若有最优解，则一定可以在可行域的 内点B .顶点C .外点 在线性规划模型中，没有非负约束的变量称为 多余变量 B .松弛变量C. 自由变量(D)D）上达到。

.几何点.人工变量若线性规划问题的最优解同时在可行解域的两个顶点处达到，那么该线性规划问题最优 ）4: 解为（A.两个B.零个5:原问题与对偶问题的最优（A .解B .目标值 C.无穷多个）相同。

C .解结构D.有限多个 D .解的分量个数6: 若原问题中 X i 为自由变量，那么对偶问题中的第 i 个约束一定为（ ）A. B . “W 型约束 C . 约束 D 若运输问题已求得最优解，此时所求出的检验数一定是全部（ A .小于或等于零B .大于零C .小于零&对于m 个发点、n 个收点的运输问题，叙述错误的是（等式约束 .无法确定7: ）D .大于或等于零 ）A .该问题的系数矩阵有m x n列B .该问题的系数矩阵有m+n行C .该问题的系数矩阵的秩必为 m+n-19:关于动态规划问题的下列命题中错误的是（ A 、 动态规划分阶段顺序不同，则结果不同 B 、 状态对决策有影响 C 、 动态规划中，定义状态时应保证在各个阶段中所做决策的相对独立性 D •该问题的最优解必唯一）D 、动态规划的求解过程都可以用列表形式实现 10：若P 为网络G 的一条流量增广链，则 P 中所有正向弧都为 G 的（ ） A .对边 B .饱和边 C .邻边 D .不饱和边 二、判断题（每小题1分，共10分） 1:图解法和单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的。

2:单纯形法的迭代计算过程是从一个可行解转换到目标函数值更大的另一个可行解。

(V)(X )3: —旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中 删除，而不影响计算结果。

（V ） 4:若线性规划问题中的 b i ,C j 值同时发生改变，反映到最终单纯形表中，不会出现原问题 与对偶问题均为非可行基的情况。

（X ） 5:若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优解。

6:运输问题的表上作业法实质上就是求解运输问题的单纯形法。

（V ） 7:对于动态规划问题，应用顺推或逆推解法可能会得出不同的最优解。

（X ） &动态规划的基本方程是将一个多阶段的决策问题转化为一系列具有递推关系的单阶段的 决策问题。

（V ） 9:图论中的图不仅反映了研究对象之间的关系，而且是真实图形的写照，因而对图中点与 点的相对位置、点与点连线的长短曲直等都要严格注意。

10:网络最短路线问题和最短树问题实质上是一个问题。

(X ) (X )1： 填空题（每空1分，共15分） 线性规划中，满足非负条件的基本解称为基本可行解 (V ),对应的基称为—可行基 。

线性规划的目标函数的系数是其对偶问题的 .最小化问题 _______ 。

m + n -1个变量构成基变量的充要条件是 __不含闭回路 __________ 。

最优目标函数 ________ ，顺序求 _______ 最优策 最优目标函数值 2: 问题，则对偶问题为 3:在运输问题模型中， 4:动态规划方法的步骤可以总结为：逆序求解 略、 _____ 、 最优路线 ___________ 禾n 最优目标函数值 ___________ 。

5: 工程路线问题也称为最短路问题，根据问题的不同分为定步数问题和不定步数问题；对 不定步数问题，用迭代法求解，有 _____________ 函数 ____ 迭代法和 _______ 策略 _____ 迭代法两种方法。

6:在图论方法中，通常用 ___________ 点 _表示人们研究的对象，用 —边 ________________ 表示对象之间的 某种联系。

7: 一个 ______ 无圈 且 连通 的图称为树。

右端常数 ；而若线性规划为最大化 四、计算题（每小题 15分，45 分） 1:考虑线性规划问题：max Z =2x 1 +4x 2 +3x 33x 1 +4x 2 + 2x 3 < 60 2音 + X 2 +2x 3 < 40 X j + 3冷 + 2x 3 <80 为，X 2,x 3 >0 s. t. 2 （a ） :写出其对偶问题； （b ） ：用单纯形方法求解原问题； （C ）：用对偶单纯形方法求解其对偶问题; （d ）:比较（b ）（ C ）计算结果。

1:解 a ）：其对偶问题为 min Z =60% +40y 2 +80y 3 3y<H2y^ y^2 4y 1 + y 2+ 3y^4 s. t. 4|2y 1 +2y 2 +2y 3 >3 原问题解 第一步 （0， 0， 0， 60， 40， 80） 第二步（0， 15， 0， 0， 25, 35） 第三步 （0, 20/3, 50/3, 0, 0, 80/3） （3分）b ）：用单纯形方法求解原问题时每步迭代结果: （5分）c ）:用对偶单纯形方法求解对偶问题时每步迭代结果: 緒_-j_b 第 步 第-二*步 第三步对偶问题问题解（0，0, 0, -2，-4，-3） （1，0，0，1, 0, -1） （5/6，2/3，0，11/6，0，0）d ）:对偶问题的实质是将单纯形法应用于对偶问题的求解, 此（b ）、（C ）的计算结果完全相同。

-------------------------- （5 分） 又对偶问题的对偶即原问题， 因 ——（2分） 2:某公司打算在三个不同的地区设置 4个销售点，根据市场预测部门的估计，在不同的地区设置不同数量的销售店，每月可得到的利润如下表所示。

试问各个地区应如何设置销2:解该问题可以作为三段决策问题，对1，2，3地区分别设置销售店形成1，2, 3三个阶段。

X k表示给地区k设置销售店时拥有分配的数量，U k表示给地区k设置销售店的数量。

状态转移方程为：Xk41=X k-U k ；阶段效应题中表所示；目标函数：3max R =2：gk（Uk）；其中gjuj表示在k地区设置Uk个销售店时的收益;k£---- （3 分）首先逆序求解条件最有目标函数值集合和条件最有决策集合:k =3时，O<X3<4, 0<U3<X3, £3（X3）于是有:f3（2） 7 （2） =14, u'3 （2） =2f3（3）〜（3） =16, u'3（3） =3,f3（4） =g3（4） =17, u'3 （4） =4（3 分）k =2时，0<X2 兰4, 0<U2 兰X2, f2（X2）= 0吧惡｛92（氏）+f3（X3）｝,0 16 25 30 32 0 12 172122 0 10 141617弋xQWJfg｝，其中f3（0） =g3（0） =0, U3（0） =0,f3（i）=g3（i）=io, U3（1）=1,f 2（0） =0maX{g 2（U 2） + f 3（X 3）} =0, U 2（0） = 0,f 2（1）=max{g 2（U 2）+ f 3（x 3）} =12, U 2（1）=1, f 2（2） =max{ g 2（U 2）+ f 3（X 3）} =22, U 2（2） =1 , f 2（3） =max{g 2（u 2）+ f 3（X 3）} =27, U 2（3） = 2, f 2（4^m^ax{ g 2（U 2） + £3（X 3）} =31, U 2（4） =2 or 3.（3 分）k =3时，X , =4, 0<5 <x , =4,于是有:f 1⑷=0max{g 1（U 1）+ f 2（X 2）} =47, U 1（4） =2.因此，最优的分配方案所能得到的最大利润位 47,分配方案可由计算结果反向查出得：U i （4）=2, u 2（2） =1, U 3（1）=1。

即为地区1设置两个销售店,地区2设置1各销售店，地区 3设置1个销售店。

3:对下图中的网络,3:解破圈法（1）：取圈，去掉边［V1,3】。

（2）：取圈 V 2,V 4,V 3,V 2，去掉边［V 2,V 4］。

（3）:取圈 V2,V3,V5,V2，去掉边［V2,V5］。

（ 4）:取圈 V3,V4,V5,V5,V3，去掉边［WM ］。

在图中已无圈，此时，p=6，而q = P"1=5，因此所得的是最短树。

结果如下图,其树的总长度为12。

分）于是有:（3 分）（6分别用破圈法和生长法求最短树。

生长法根据生长法的基本原理，得以下计算表五、简答题（每小题10分，共20分）1 .试述单纯形法的计算步骤，并说明如何在单纯形表上判断问题是具有唯一最优解、无 穷多最优解和无有限最优解。

解：1:单纯形法的计算步骤第一步：找出初始可行解，建立初始单纯形表。

若所有的b j 兰0，则基B 为最优基，相应的基可行解即为基本最优解，计算停止。

V 2V 3V 4V 5vS i{2}6 □c□c □c V 23 8 9 □c S2{3}8 9 □c V 35 3□c S35{3}□cv□c1S 45{1}V 63S 5{3}据此也得到与破圈法相同的最短树。

（6分）（3 分）第二步：判断最优，检验各非基变量X j 的检验数 b j "C B B P j —C j 。

若所有的检验数 W 兰0，又存在某个非基变量的检验数所有的 b k =0，则线性规划问题有无穷多最优解。

若有某个非基变量的检验数W >0，并且所对应的列向量的全部分量都非正，则该线性规划问题的目标函数值无上界，既无界解，停止计算。

第三步：换基迭代当存在b k 》0，选Xk进基来改善目标函数。

若检验数大于0的非基变量不止一个，则可以任选其中之一来作为进基变量。

进基变量Xk确定后，按最小比值原则选择出基变量Xr 。