运筹学期末考试题〔a卷〕注意事项：1、答题前,考生务必将自己的##、班级填写在答题卡上.2、答案用钢笔或圆珠笔写在答题卡上,答在试卷上不给分.3、考试结束,将试卷和答题卡一并交回.一、单项选择题<每小题1分,共10分>1：在下面的数学模型中,属于线性规划模型的为〔〕2．线性规划问题若有最优解,则一定可以在可行域的〔〕上达到.A．内点 B．顶点 C．外点 D．几何点3：在线性规划模型中,没有非负约束的变量称为〔〕A．多余变量 B．松弛变量 C.自由变量D．人工变量4：若线性规划问题的最优解同时在可行解域的两个顶点处达到,那么该线性规划问题最优解为〔〕A.两个B.零个C.无穷多个D.有限多个5：原问题与对偶问题的最优〔〕相同.x为自由变量,那么对偶问A．解B．目标值C．解结构D．解的分量个数6：若原问题中i题中的第i个约束一定为〔〕A．等式约束B．"≤〞型约束C．"≥〞约束 D．无法确定7：若运输问题已求得最优解,此时所求出的检验数一定是全部〔〕A．小于或等于零B．大于零C．小于零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的〔〕A．对边B．饱和边C．邻边D．不饱和边二、判断题〔每小题1分,共10分〕1：图解法和单纯形法虽然求解的形式不同,但从几何上理解,两者是一致的.〔〕2：单纯形法的迭代计算过程是从一个可行解转换到目标函数值更大的另一个可行解.〔〕3：一旦一个人工变量在迭代中变为非基变量后,该变量与相应列的数字可以从单纯形表中删除,而不影响计算结果.〔〕b c值同时发生改变,反映到最终单纯形表中,不会出现原问题与对4：若线性规划问题中的,i j偶问题均为非可行基的情况.〔〕5：若线性规划的原问题有无穷多最优解,则其对偶问题也一定具有无穷多最优解.〔〕6：运输问题的表上作业法实质上就是求解运输问题的单纯形法.〔〕7：对于动态规划问题,应用顺推或逆推解法可能会得出不同的最优解.〔〕8：动态规划的基本方程是将一个多阶段的决策问题转化为一系列具有递推关系的单阶段的决策问题.〔 〕 9：图论中的图不仅反映了研究对象之间的关系,而且是真实图形的写照,因而对图中点与点的相对位置、点与点连线的长短曲直等都要严格注意.〔 〕10：网络最短路线问题和最短树问题实质上是一个问题.〔 〕 三、 填空题〔每空1分,共15分〕1：线性规划中,满足非负条件的基本解称为________,对应的基称为________. 2：线性规划的目标函数的系数是其对偶问题的________；而若线性规划为最大化问题,则对偶问题为________.3：在运输问题模型中,1m n +-个变量构成基变量的充要条件是________.4：动态规划方法的步骤可以总结为：逆序求解________,顺序求________、________和________.5：工程路线问题也称为最短路问题,根据问题的不同分为定步数问题和不定步数问题；对不定步数问题,用迭代法求解,有________迭代法和________迭代法两种方法.6：在图论方法中,通常用________表示人们研究的对象,用________表示对象之间的某 联系.7：一个________且________的图称为树. 四、计算题〔每小题15分,45分〕1：考虑线性规划问题： 〔a 〕：写出其对偶问题； 〔b 〕：用单纯形方法求解原问题； 〔c 〕：用对偶单纯形方法求解其对偶问题； 〔d 〕：比较〔b 〕〔c 〕计算结果.2：某公司打算在三个不同的地区设置4个销售点,根据市场预测部门的估计,在不同的地区设置不同数量的销售店,每月可得到的利润如下表所示.试问各个地区应如何设置销售店,3：对下图中的网络,分别用破圈法和生长法求最短树. 五、简答题<每小题10分,共20分>1．试述单纯形法的计算步骤,并说明如何在单纯形表上判断问题是具有唯一最优解、无穷多最优解和无有限最优解.2．简述最小费用最大流问题的提法以与用对偶法求解最小费用最大流的原理和步骤.##政法学院2008—2009学年度第一学期《运筹学》期末考试参考答案与评分标准〔a 卷〕单项选择题<每小题1分,共10分>1.B2.B3.C4.C5.B6.A7.D8.D9.A 10.D 判断题〔每小题1分,共10分〕1.T2.F3.T4.F5.T6.T7.F8.T9.F 10.F 填空题〔每空1分,共15分〕1：基本可行解、可行基；2：右端常数、最小化问题；3：不含闭回路；4：最优目标函数、最优策略、最优路线、最优目标函数值；5：函数、策略；6：点、边；7：无圈、连通. 计算题〔每小题15分,45分〕 1：解 a 〕：其对偶问题为------〔3分〕------〔5分〕d 〕：对偶问题的实质是将单纯形法应用于对偶问题的求解,又对偶问题的对偶即原问题,因此〔b 〕、〔c 〕的计算结果完全相同. --------<2分> 2：解 该问题可以作为三段决策问题,对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 ∞ 3S5{3}∞简答题<每小题10分,共20分> 1：单纯形法的计算步骤第一步：找出初始可行解,建立初始单纯形表.第二步：判断最优,检验各非基变量j x 的检验数1j B j j C B P C σ-=-.（1） 若所有的0j σ≤,则基B 为最优基,相应的基可行解即为基本最优解,计算停止. （2） 若所有的检验数0j σ≤,又存在某个非基变量的检验数所有的0k σ=,则线性规划问题有无穷多最优解.（3） 若有某个非基变量的检验数0j σ>,并且所对应的列向量的全部分量都非正,则该线性规划问题的目标函数值无上界,既无界解,停止计算.第三步：换基迭代（1） 当存在0k σ>,选k x 进基来改善目标函数.若检验数大于0的非基变量不止一个,则可以任选其中之一来作为进基变量.（2） 进基变量k x 确定后,按最小比值原则选择出基变量r x .若比值最小的不止一个,选择其中之一出基.（3） 做主元变换.反复进行上述过程就可以找到最优解或判断出没有有限最优解. 2：最大流问题就是在一定条件下,要求流过网络的物流、能量流或信息流等流量最大的问题.如果已知流过弧(,)i j v v 的单位流量要发生ij c 的费用,要求使总费用为最小的最大流流量分配方法.即在上述最大流问题上还应增加关于费用的目标：minij ijx c∑.这种问题称为最小费用最大流问题.模型可以描述为：采用对偶法求解最大流最小费用问题,其原理为：用福德—富克逊算法求出网络的最大流量,然后用Ford 算法找出从起点s v 到终点t v 的最短增广链.在该增广链上,找出最大调整量ε,并调整流量,得到一个可行流.则此可行流的费用最小.如果此时流量等于最大流量,则目前的流就是最小费用最大流,否则应继续调整.对偶法的步骤归纳如下：第0步：用最大流方法找出网络最大流量max f ,并以0流作为初始可行流.第一步：对于当前可行流,绘制其扩展费用网络图.第二步：用Ford 算法求出扩展费用网络图中从s v 到t v 的最短路.第三步：在最短路线对应的原网络中的增广链上,调整流量,得到新的可行流.第四步：绘制可行流图.若可行流的流量等于最大流量max f ,则已找到最小费用最大流,算法结束；否则从第一步开始重复上述过程。
