《(完整版)北京交通大学942真题2011.doc》由会员分享，可在线阅读，更多相关《(完整版)北京交通大学942真题2011.doc（10页珍藏版）》请在三一文库上搜索。
1、北京交通大学 942 管理运筹学 2011 年真题一(每题 1分，共 15 分)判断(1) . 线性规划问题的基可行解和其可行域的顶点是一一对 应的；(2) 若x(1), ?梓)分别是某一线性规划问题的 最优解，则 x=?1)+?2)也是该线性规划问题的最优解，其中 ？，? 为正的实数；(3) 若线性规划的对偶问题有最优解，则原线性规划问题也 一定有最优解，反之亦然；( 4)用割平面法求整数规划时，构造的割平面有可能切去一些不属于最优解的整数可行解；(5) 运输问题系数矩阵的某行元素同时加上一个任意常数k， 都不影响最优方案；(6) 如果图T是树，则T中一定存在至少两个顶点，它们的 次为 1；
2、(7) 用 Dijkstra 算法只能求解非负权图中两点 2 之间的最 短路，而 Floyd 算法怎能求解任意赋权图中任意两点之间的 最短路问题；( 8)网络图中任何一个结点都表示前一工序的结束和后一 工序的开始；( 9)结点最早时间同最迟时间相等的点连接的线路就是关 键线路；10）假如到达排队系统的顾客来自两个方面，分别服从普阿松分布，则这两部分顾客合起来的顾客流仍然服从同一普 阿松分布；（11）运输问题也是线性规划模型，因而运输问题有可能存 在最优解，也有可能不存在最优解；（12）只要能将所研究的问题分解成多个不同阶段，就一定 可以用动态规划方法求出其最优解；（13）隐枚举法是一种特殊的分
3、支定界法，它适用于任何 01 规划问题；（14）指派问题效率矩阵 A的元素可分成0与非0元素两部 分，覆盖 0 元素的最少直线数等于位于不同行不同列 0 元素 的最大个数；（15）机器负荷分配问题中，始终固定终端自由的生产效率 要比始端固定终端也固定的生产效率低。二 . 下列每一个问题中至少有一个说法是正确的， 共有 20 个 说法正确，请把 20 个正确说法找出来，超过 20 个时按题顺 序取前 20 个为准，每个 1.5 分，共 30 分）1. 当极大化LP问题单纯性表的基底 B变为？时，则祁变为 岔1 b，岔1 b>0而？?孑？?1 N中存在正数，则（）说法正确。A. 基*?对应的
4、解是最优解，最优解时？?=?b;B. 基 彩寸应的解是基可行解；C. 用单纯形法继续计算一定可在有限步求得最优解；2. 在（m+n个约束条件的运输问题中，下述（ ）回答是正 确的。A. 恰有m+n-1个是独立的；B. 至多有m+n-1个是独立的；C. 恰有m+n个是独立的；D. 至多有m+n个是独立的；3. 用分支定界法解整数规划（LP）时，下列（）说法是正 确的。A 产生分枝问题就是将松弛问题可行域进行分割，舍去那些 不含原问题解的区域；B. 任一分支问题解的目标值都代表该分支问题所含整数解 的目标值上限，所有分支问题中最优者若是整数解，则必为 原问题最优解；C. 若所有分支问题无可行解，则
5、原问题也无可行解；D. 若多个分支问题无整数解，则原问题无最优解。4. 动态规划求解问题时，下列（ ）说法是正确的。A. 无论初始状态和初始决策如何，对于当前状态和决策而言 余下的决策必须构成最优策略；B. 整体最优局部必然最优，因此所有构成策略的子策略最优 时整体也应该最优；C. 动态规划就是把问题分成阶段，根据状态转移方程徐兆最优指标的子策略，从终点逐步到始点优化的过程；D. 策略与决策实际上是一回事。5. 对于图，下列（ ）说法正确。A. 任何图，次为奇数的节点个数必为偶数；B. 任意两个节点直接有且只有一条路相通的是树；C. 一棵具有 p 个节点的树有且仅有 q=p-1 条边，任何具有
6、 p 个节点和 p-1 条边的图就是一棵树D. 从图的任何一个生成树开始，通过有限步连续的树基本变 换可以得到图的每一个生成树，其中边数最少的生成树就是 最小生成树。6. 关于带收发点的容量网络中从出发点到收点的一条增广 链，以下（ ）叙述正确。A. 增广路上的有向边的方向必须是从发点指向收点的；B. 增广路上的有向边必须都是不饱和边；C. 增广路上不能有零流边；D. 增广路上与发点到收点方向的有向边不能是饱和边，相反 方向的有向边不能是零。7. 线性规划问题最优基中某个基变量的目标系数发生变化， 则（ ）正确。A. 该基变量的检验数必然为零；B. 其他基变量的检验数可能变化；C. 所有非基变
7、量检验数均可能变化；D. 所有变量检验数都可能变化。8. 排队论中，下列（）说法正确。A. 系统容量有限制时有效到达率心和 洽义不同，卩（1-?）B. M/M/C系统与C个M/M/1系统比较，一般来说后者服务效率略好且更有灵活性；C. （p-k ）公式适用于 M/G/1模型，正确写法为?= p+?+?T2（1-?）D. k个串联服务站服务时间？?相互独立且服从相同的指数分一一?=T则布?服从k阶爱尔朗分布9. 设线性规划问题 max Z=CX AX=b, X>0，则其对偶问题为min W=Yb YA>C, 丫 （- , +）,下列说法正确的是（）。A. 若X和丫是原问题和对偶问题的
8、可行解，则必有CX>Yb;B. 问题的第k个约束乘以常数 入（入工0），则对偶问题的解 ?=入?丫=入?1 ;C. 将目标函数改变为 max Z=2CX （入工0）,则对偶问题的解 ?=入?丫二入?1 ;D. 模型中全部？?用3?代替，则对偶问题解中必然 ?=3?10. 对线性规划而言，下列说法正确的是（）A. 若R有界凸集，则任意一点 x?R可表示为R的定点的凸组 合；B. 线性规划可行域是凸集，则顶点的个数是有限的，因而总可以在有限步内找到全部基本最优解；?C. 线性规划可行解 x= (?,?,?)为基本可行解的充 要条件是 X 正分量所对应的系数列向量是线性独立的；D. 如果线性规
9、划的最优解不唯一，则最优解集合是凸集。三( 30 分)已知线性规划模型为：Max Z=10x1+5x23? + 4? < 9 5? + 2? < 8?, ? > 0( 1) 用单纯形法求该线性规划模型的最优解；( 2) 写出该线性规划问题的对偶问题， 并求对偶问题的最 优解；(3) 试问 ?1?， ?2?分别在什么范围内变化时，上述最优解不 变；(4) 试问 ?1?在什么范围变化时，上述最优解不变；(5) 如果目标函数变为 Max Z=12x1 +4x2，试讨论最优解 的变化情况；(6) 如果约束条件右端资源由 9变为11，试讨论最819优解的变化情况。四. (20分)铁路部
10、门计划在市内 A B、C三个区设立售票处，每个区至少一家，所得收入如下表所示：-票处数区1234A200280330340B210220225230C180230260280问：售票处如何分配，是总收入最大？（要求写出动态规划模型的基本要素并求解）五. （15分）下图为路网示意图，图中数字为距离（km），假设从天津、丰台、郑州、徐州调运某种物资到石家庄、 德州、邯郸、济南、青岛等地，天津、丰台、郑州、徐州 可调出这种物资的数量分别为 9、10、7、9,（万吨），石家 庄、德州、邯郸、济南、青岛的需求量分别为6、15、3、3、8 （万吨）试求最优调运方案。六. （20分）有三个工厂？?，？，？，
11、它们生产同一种设 备，供应？?，？?，？?地，设工厂？?，?, ?的生产能力分别 是40台、20台和10台。？?，?, ?的需求分别是15台、 25台和10台，运输网络如下图所示，弧旁边数字为容量。 试确定？?，？，？?各生产设备多少台，能通过这个网络运达 ?, ?，?并问有哪几种生产和调运方案？?520101050610102010*62030?七. (10分)某公司要从？,？,？?0十个可供选择的投资项目中确定五个投资对象，使总投资额最少。假设十个 项目的投资额，分别为 ? ?,？命且在项目的选择上要 满足下列限制条件：(1) 选择了 ？,？就不能选择?，反之亦然；(2) 在?,?,?,?中最多只能选择 3个。八. (10分)考虑一个铁路列车编组站，设待编列车到达时 间间隔服从负指数分布，平均 2列/小时，服务台是编组 站，服务时间服从负指数分布，平均每 20分钟可服务一 列。已知编组站到达场共有 2股道，当均被占用时，不能 接车，再来的列车只能停在站外或前方站。（1）求在平稳状态下系统中列车的平均数；（2）每一列车的平均停留时间；（3）等待编组的列车平均数；（4）等待编组的平均时间；（5）如果列车因站中的 2 股道均被占用而只能停在站外或 前方站时，每列列车的费用为a元/小时，求媒体由于列车在站外等候而造成的损失。