运筹学2015学年期末考试题A卷及答案.docVIP

运筹学2015年学年第二学期 期末考试题（a卷） 注意事项： 1、答题前，考生务必将自己的姓名、班级填写在答题卡上。 2、答案用钢笔或圆珠笔写在答题卡上，答在试卷上不给分。 3、考试结束，将试卷和答题卡一并交回。 单项选择题(每小题1分，共10分) 1：在下面的数学模型中，属于线性规划模型的为（ ） 2．线性规划问题若有最优解，则一定可以在可行域的 （）上达到。 A．内点 B．顶点 C．外点 D．几何点?在线性规划模型中，没有非负约束的变量称为 （）? ? ? ?? A．多余变量 B．松弛变量自由变量D．人工变量?原问题与对偶问题的最优（）相同。 ．解．目标值 ． 解结构 ．解的分量个数若原问题中为自由变量，那么对偶问题中的第个约束一定为 （） A．等式约束B．“≤”型约束C．“≥”约束 D．无法确定? ? ??若运输问题已求得最优解，此时所求出的检验数一定是全部（）? ? ? ? ? ? ? ? ? ? ?A．于或等于零 B．大于零 C．小于零 D．于或等于零?若为的增广链，则中所有都为的（） A．对边 B．饱和边 C．邻边 D．不饱和边? ?值同时发生改变，反映到最终单纯形表中，不会出现原问题与对偶问题均为非可行基的情况。（×） 5：若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优解。（√ ） 6：运输问题的表上作业法实质上就是求解运输问题的单纯形法。（√ ） 7：对于动态规划问题，应用顺推或逆推解法可能会得出不同的最优解。（× ） 8：动态规划的基本方程是将一个多阶段的决策问题转化为一系列具有递推关系的单阶段的决策问题。（√ ） 9：图论中的图不仅反映了研究对象之间的关系，而且是真实图形的写照，因而对图中点与点的相对位置、点与点连线的长短曲直等都要严格注意。（× ） 10：网络最短路线问题和最短树问题实质上是一个问题。（× ） 填空题（每空1分，共15分） 1：线性规划中，满足非负条件的基本解称为___基本可行解_____，对应的基称为___可行基_____。 2：线性规划的目标函数的系数是其对偶问题的__右端常数______；而若线性规划为最大化问题，则对偶问题为___最小化问题_____。 3：在运输问题模型中，个变量构成基变量的充要条件是__不含闭回路______。 4：动态规划方法的步骤可以总结为：逆序求解____最优目标函数____，顺序求____最优策略、____、___最优路线_____和___最优目标函数值_____。 5：工程路线问题也称为最短路问题，根据问题的不同分为定步数问题和不定步数问题；对不定步数问题，用迭代法求解，有____函数____迭代法和____策略____迭代法两种方法。 6：在图论方法中，通常用____点____表示人们研究的对象，用___边_____表示对象之间的某种联系。 7：一个_____无圈___且____连通____的图称为树。 四、计算题（每小题15分，45分） 1：考虑线性规划问题： （a）：写出其对偶问题； （b）：用单纯形方法求解原问题； （c）：用对偶单纯形方法求解其对偶问题； （d）：比较（b）（c）计算结果。 1：解 a）：其对偶问题为 ------（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）：对偶问题的实质是将单纯形法应用于对偶问题的求解，又对偶问题的对偶即原