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

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

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

一、 单项选择题(每小题1分，共10分)1：在下面的数学模型中，属于线性规划模型的为（ ） ⎪⎩⎪⎨⎧≥≤+=0Y ,X 3XY .t .s Y X 4S max .A ⎪⎩⎪⎨⎧≥-≥-+=0Y ,X 1Y X 2.t .s Y X 3S min .B ⎪⎩⎪⎨⎧≥≤-+=0Y ,X 2Y X .t .s Y X S max .C 22 ⎪⎩⎪⎨⎧≥≥+=0Y ,X 3Y X .t .s XY2S min.D 2．线性规划问题若有最优解，则一定可以在可行域的 （ ）上达到。

A ．内点 B ．顶点 C ．外点 D ．几何点3：在线性规划模型中，没有非负约束的变量称为 （ ） A ．多余变量 B ．松弛变量 C.自由变量 D ．人工变量4：若线性规划问题的最优解同时在可行解域的两个顶点处达到，那么该线性规划问题最优解为（ ）A.两个B.零个C.无穷多个D.有限多个5：原问题与对偶问题的最优（ ）相同。

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

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

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

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

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

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

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

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

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

（× ） 10：网络最短路线问题和最短树问题实质上是一个问题。

（× ） 三、 填空题（每空1分，共15分）1：线性规划中，满足非负条件的基本解称为___基本可行解_____，对应的基称为___可行基_____。

2：线性规划的目标函数的系数是其对偶问题的__右端常数______；而若线性规划为最大化问题，则对偶问题为___最小化问题_____。

3：在运输问题模型中，1m n +-个变量构成基变量的充要条件是__不含闭回路______。

4：动态规划方法的步骤可以总结为：逆序求解____最优目标函数____，顺序求____最优策略、____、___最优路线_____和___最优目标函数值_____。

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

6：在图论方法中，通常用____点____表示人们研究的对象，用___边_____表示对象之间的某种联系。

7：一个_____无圈___且____连通____的图称为树。

四、计算题（每小题15分，45分）1：考虑线性规划问题：1231231231231236max 2433420408022..32,0,z x x x x x x x x x s t x x x x x x =++++⎧⎪+ ≤≤≤+ ⎪⎨++≥⎪⎪⎩ （a ）：写出其对偶问题；（b ）：用单纯形方法求解原问题；（c ）：用对偶单纯形方法求解其对偶问题； （d ）：比较（b ）（c ）计算结果。

1：解 a ）：其对偶问题为123123123123123min 604080324..2222,3,40z y y y y y y y y y s t y y y y y y =++++⎧⎪+ + 3⎪⎨++≥≥≥≥⎪⎪⎩------（3分）b ）：用单纯形方法求解原问题时每步迭代结果：原问题解 第一步 第二步 第三步 （0，0，0，60，40，80） （0，15，0，0，25，35） （0，20/3，50/3，0，0，80/3）------（5分） c ）：用对偶单纯形方法求解对偶问题时每步迭代结果：对偶问题问题解 第一步 第二步 第三步 （0，0，0，-2，-4，-3） （1，0，0，1，0，-1） （5/6，2/3，0，11/6，0，0）------（5分）d ）：对偶问题的实质是将单纯形法应用于对偶问题的求解，又对偶问题的对偶即原问题，因此（b ）、（c ）的计算结果完全相同。

--------(2分)2：某公司打算在三个不同的地区设置4个销售点，根据市场预测部门的估计，在不同的地区设置不同数量的销售店，每月可得到的利润如下表所示。

试问各个地区应如何设置销售店，才能使每月获得的总利润最大？其值是多少？0 1 2 3 4 12 30 16 25 30 320 12 17 21销售 店利 润地 区220 10 14 16 172：解 该问题可以作为三段决策问题，对1，2，3地区分别设置销售店形成1，2，3三个阶段。

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

状态转移方程为：1k k k x x u +=-；阶段效应题中表所示；目标函数：31max ()kk k R gu ==∑； 其中()k k g u 表示在k 地区设置k u 个销售店时的收益； ------（3分）首先逆序求解条件最有目标函数值集合和条件最有决策集合：3k =时，333333334400()max{(4,)(,)}u x g x f u x x u f =+≤≤≤≤，其中44()0f x =于是有：'333(0)(0)0,(0)0f g u ===, '333(1)(1)10,(1)1f g u ===,333(2)(2)14,'(2)2f g u ===,333(3)(3)16,'(3)3f g u ===,333(4)(4)17,'(4)4f g u === .------（3分）2k =时，22222222233000()max {(4)()},,u x x g x u x u f x f ≤≤=+≤≤≤≤,于是有：222'332020(0)max{()()}0,(0)0u f g u f x u ≤≤=+==,2'22022331(1)max{()()}12,(1)1u f g u f x u ≤≤=+==,2'22022332(2)max{()()}22,(2)1u f g u f x u ≤≤=+==,2'22022333(3)max{()()}27,(3)2u f g u f x u ≤≤=+==,2'22022334(4)max{()()}31,(4)23u f g u f x u or ≤≤=+==. ------（3分）3k =时，111,404,x u x ≤=≤=于是有：1'11122014(4)max{()()}47,(4) 2.u g u f x u f ≤≤=+== .------（3分）因此，最优的分配方案所能得到的最大利润位47，分配方案可由计算结果反向查出得：123***(4)2,(2)1,(1)1u u u ===。

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

3：对下图中的网络，分别用破圈法和生长法求最短树。

3：解 破圈法 （1）：取圈3121,,,v v v v ，去掉边13[,]v v 。

（2）：取圈2432,,,v v v v ，去掉边24[,]v v 。

（3）：取圈2352,,,v v v v ，去掉边25[,]v v 。

（4）：取圈34553,,,,v v v v v ，去掉边34[,]v v 。

在图中已无圈，此时，6p =，而15q p =-=，因此所得的是最短树。

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

.------（6分）.------（3分）生长法根据生长法的基本原理，得以下计算表2v 3v 4v 5v 6v1S {2} 6 ∞∞∞ 2v 3 8 9 ∞ 2S {3} 8 9 ∞ 3v 5 3 ∞3S 5{3} ∞5v ∞1 4S 5 {1} 6v 3 5S{3}据此也得到与破圈法相同的最短树。

.------（6分）五、简答题(每小题10分，共20分)1．试述单纯形法的计算步骤，并说明如何在单纯形表上判断问题是具有唯一最优解、无穷多最优解和无有限最优解。

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

第二步：判断最优，检验各非基变量jx 的检验数1j B j jC B P C σ-=-。

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

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

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

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