运筹学2015学年期末考试题A卷与答案.pdf

《运筹学2015学年期末考试题A卷与答案.pdf》由会员分享，可在线阅读，更多相关《运筹学2015学年期末考试题A卷与答案.pdf（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 运筹学年学年第二学期期末考试题（卷）注意事项：、答题前，考生务必将自己的 XX、班级填写在答题卡上。、答案用钢笔或圆珠笔写在答题卡上，答在试卷上不给分。、考试结束，将试卷和答题卡一并交回。一、单项选择题每小题分，共分 ：在下面的数学模型中，属于线性规划模型的为（）线性规划问题若有最优解，则一定可以在可行域的 （）上达到。内点 顶点 外点 几何点 ：在线性规划模型中，没有非负约束的变量称为（）多余变量 松弛变量 自由变量 人工变量 ：若线性规划问题的最优解同时在可行解域的两个顶点处达到，那么该线性规划问题最优 解为（）两个 零个 无穷多个 有限多个 ：原问题与对偶问题的最优（）相同。解 目标值

2、 解结构 解的分量个数：若原问题中为自由变量，那么对偶问题中的第 个约束一定为 （）等式约束 “”型约束 “”约束 无法确定 ：若运输问题已求得最优解，此时所求出的检验数一定是全部（）小于或等于零 大于零 小于零 大于或等于零：对于个发点、个收点的运输问题，叙述错误的是 该问题的系数矩阵有列 该问题的系数矩阵有行 该问题的系数矩阵的秩必为该问题的最优解必唯一 ：关于动态规划问题的下列命题中错误的是（）、动态规划分阶段顺序不同，则结果不同、状态对决策有影响 、动态规划中，定义状态时应保证在各个阶段中所做决策的相对独立性 、动态规划的求解过程都可以用列表形式实现 ：若 为网络 的一条流量增广链，则

3、 中所有正向弧都为 的（）对边 饱和边 邻边 不饱和边 二、判断题（每小题 分，共 分）：图解法和单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的。：单纯形法的迭代计算过程是从一个可行解转换到目标函数值更大的另一个可行解。（）（）：一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果。（）：若线性规划问题中的 值同时发生改变，反映到最终单纯形表中，不会出现原问题 与对偶问题均为非可行基的情况。（）：若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优解。（）：运输问题的表上作业法实质上就是求解运输问题的单纯形法。（）：对于动态

4、规划问题，应用顺推或逆推解法可能会得出不同的最优解。（）：动态规划的基本方程是将一个多阶段的决策问题转化为一系列具有递推关系的单阶段的 决策问题。（）：图论中的图不仅反映了研究对象之间的关系，而且是真实图形的写照，因而对图中点与 点的相对位置、点与点连线的长短曲直等都要严格注意。（）：网络最短路线问题和最短树问题实质上是一个问题。（）三、填空题（每空分，共分）：线性规划中，满足非负条件的基本解称为 基本可行解，对应的基称为可行基。：线性规划的目标函数的系数是其对偶问题的 右端常数；而若线性规划为最大化 问题，则对偶问题为最小化问题。：在运输问题模型中，个变量构成基变量的充要条件是 不含闭回路。

5、：动态规划方法的步骤可以总结为：逆序求解 最优目标函数，顺序求最优策 略、最优路线和最优目标函数值。：工程路线问题也称为最短路问题，根据问题的不同分为定步数问题和不定步数问题；对 不定步数问题，用迭代法求解，有 函数迭代法和策略迭代法两种方法。：在图论方法中，通常用 点表示人们研究的对象，用 边表示对象之间的 某种联系。：一个无圈且连通的图称为树。四、计算题（每小题分，分）：考虑线性规划问题：（）：写出其对偶问题；（）：用单纯形方法求解原问题；（）：用对偶单纯形方法求解其对偶问题；（）：比较（）（）计算结果。：解）：其对偶问题为 （分）：用单纯形方法求解原问题时每步迭代结果：原问题解 第一步

6、（，）第二步 （，）第三步 （，）（分）：用对偶单纯形方法求解对偶问题时每步迭代结果：对偶问题问题解 第一步 （，）第二步 （，）第三步 （，）（分）：对偶问题的实质是将单纯形法应用于对偶问题的求解，又对偶问题的对偶即原问题，因 此（）、（）的计算结果完全相同。分 ：某公司打算在三个不同的地区设置个销售点，根据市场预测部门的估计，在不同的地区设置不同数量的销售店，每月可得到的利润如下表所示。试问各个地区应如何设置销售店，才能使每月获得的总利润最大？其值是多少？销 利 售 店 润 地 区 ：解 该问题可以作为三段决策问题，对，地区分别设置销售店形成，三个阶段。表示给地区设置销售店时拥有分配的数量

7、，表示给地区 设置销售店的数量。状 态 转 移 方 程 为：；阶 段 效 应 题 中 表 所 示；目 标 函 数：；其中表示在地区设置个销售店时的收益；（分）首先逆序求解条件最有目标函数值集合和条件最有决策集合：时，其中 于是有：（分）时，于是有：（分）时，于是有：（分）因此，最优的分配方案所能得到的最大利润位出得：，分配方案可由计算结果反向查 。即为地区 设置两个销售店，地区 设置 各销售店，地区 设置 个销售店。：对下图中的网络，分别用破圈法和生长法求最短树。：解破圈法 （）：取圈，去掉边。（）：取圈，去掉边。（）：取圈，去掉边。（）：取圈，去掉边。在图中已无圈，此时，而，因此所得的是最短

8、树。结果如下图，其树的总长度为。（分）（分）生长法 根据生长法的基本原理，得以下计算表 据此也得到与破圈法相同的最短树。（分）五、简答题每小题分，共分 试述单纯形法的计算步骤，并说明如何在单纯形表上判断问题是具有唯一最优解、无 穷多最优解和无有限最优解。解：单纯形法的计算步骤 第一步：找出初始可行解，建立初始单纯形表。的检验数 。第二步：判断最优，检验各非基变量 若所有的 ，则基为最优基，相应的基可行解即为基本最优解，计算停止。若所有的检验数 题有无穷多最优解。，又存在某个非基变量的检验数所有的，则线性规划问 若有某个非基变量的检验数，并且所对应的列向量的全部分量都非正，则该线 性规划问题的目

9、标函数值无上界，既无界解，停止计算。第三步：换基迭代 当存在，选进基来改善目标函数。若检验数大于的非基变量不止一个，则 可以任选其中之一来作为进基变量。进基变量 确定后，按最小比值原则选择出基变量。若比值最小的不止一个，选择 其中之一出基。做主元变换。反复进行上述过程就可以找到最优解或判断出没有有限最优解。（分）简述最小费用最大流问题的提法以及用对偶法求解最小费用最大流的原理和步骤。解：最大流问题就是在一定条件下，要求流过网络的物流、能量流或信息流等流量 最大的问题。如果已知流过弧的单位流量要发生的费用，要求使总费用为最小的 最大流流量分配方法。即在上述最大流问题上还应增加关于费用的目标：种问

10、题称为最小费用最大流问题。模型可以描述为：。这 采用对偶法求解最大流最小费用问题，其原理为：用福德富克逊算法求出网络的最大 流量，然后用算法找出从起点到终点的最短增广链。在该增广链上，找出最大调 整量，并调整流量，得到一个可行流。则此可行流的费用最小。如果此时流量等于最大流量，则目前的流就是最小费用最大流，否则应继续调整。对偶法的步骤归纳如下：第步：用最大流方法找出网络最大流量，并以流作为初始可行流。第一步：对于当前可行流，绘制其扩展费用网络图。第二步：用算法求出扩展费用网络图中从 到的最短路。第三步：在最短路线对应的原网络中的增广链上，调整流量，得到新的可行流。第四步：绘制可行流图。若可行流的流量等于最大流量 ，则已找到最小费用最大 流，算法结束；否则从第一步开始重复上述过程