《运筹学》期末复习题.doc

-最新资料推荐- 运筹学期末复习题 运筹学期末复习题 一、单项选择题 1、下列叙述正确的是（ ）。 A线性规划问题，若有最优解，则必是一个基变量组的可行基解 B线性规划问题一定有可行基解 C线性规划问题的最优解只能在最低点上达到 D单纯形法求解线性规划问题时，每换基迭代一次必使目标函数值下降一次 答案： A 2、线性规划的变量个数与其对偶问题的（ ）相等。 A变量目标函数 B变量约束条件 C约束条件个数 D不确定 答案： C 3、在利用表上作业法求各非基变量的检验数时，有闭回路法和（ ）两种方法。 A西北角法 B位势法 C最低费用法 D元素差额法 答案： B 4、下列各项（ ）不是目标规划的特点。 A多目标 B单一目标 C具有优先次序 D不求最优 答案： B 5、下列关于图的说法中，错误的为（ ）。 A点表示所研究的事物对象 B边表示事物之间的联系 C无向图是由点及边所构成的图 D无环的图称为简单图 答案： D 6、利用单纯形法求解线性规划问题时，首先需要（ ）。 A找初始基础可行基 B检验当前基础可行解是否为最优解 C确定改善方向 D确定入变量的最大值和出变量 答案： A 7、对偶问题最优解的剩余变量解值（ ）原问题对应变量的检验数的绝对值。 A大于 B小于 C等于 D不能确定 答案： C 第 1 页 共 17 页运筹学期末复习题 8、当某个非基变量检验数为零，则该问题有（ ）。 A无解 B无穷多最优解 C退化解 D惟一最优解 答案： B 9、PERT 网络图中，（ ）表示一个工序。 A节点 B弧 C权 D关键路线 答案： B 10、假设对于一个动态规划问题，应用顺推法以及逆推解法得出的最优解分别为 P 和 D，则有（ ）。 APD BPD CP=D D不确定 答案： C 11、下列有关线性规划问题的标准形式的叙述中错误的是（ ）。 A目标函数求极大 B约束条件全为等式 C约束条件右端常数项全为正 D变量取值全为非负 答案： C 12、线性规划问题的数学模型由目标函数、约束条件和（ ）三个部分组成。 A非负条件 B顶点集合 C最优解 D决策变量 答案： D 13、如果原问题有最优解，则对偶问题一定具有（ ）。 A无穷多解 B无界解 C最优解 D不能确定 答案： C 14、运输问题的基变量有（ ）个。 Am n Bm+n-1 Cm+n D不确定 答案： B 15、目标规划的目标权系数是定量的概念，数值（ ），表示该目标越重要。 A越小 B越大 C为 0 D为正 第 2 页 共 17 页运筹学期末复习题 答案： B 16、下列叙述正确的是（ ）。 A线性规划问题，若有最优解，则必是一个基变量组的可行基解 B线性规划问题一定有可行基解 C线性规划问题的最优解一定唯一 D单纯形法求解线性规划问题时，每换基迭代一次必使目标函数值下降一次 答案： A 17、设 M 是线性规划问题， N 是其对偶问题，则（ ）不正确。 AM 有最优解， N 不一定有最优解 B若 M 和 N 都有最优解，则二者最优值肯定相等 C若 M 无可行解，则 N 无有界最优解 DN 的对偶问题为 M 答案： A 18、PERT 网络图中，（ ）表示为完成某个工序所需的时间或资源等数据。 A节点 B弧 C权 D圆圈 答案： C 19、网络的最大流量应（ ）它的最小割集的容量。 A大于 B等于 C小于 D不大于 答案： B 20、利用单纯形法求解线性规划问题时，判断当前解是否为最优解的标准为所有非基变量的检验数应为 （ ）。 A正 B负 C非正 D非负 答案： C 21、若原问题为无界解，则对偶问题的解是（ ）。 A无解 B无穷多解 C无界解 D不能确定 答案： A 22、PERT 网络图中，（ ）表示一个事件，用圆圈和里面的数字表示。 第 3 页 共 17 页运筹学期末复习 题 A节点 B弧 C权 D关键路 线 答案： A 23、具有 7 个节点的树 T 的边恰好为 （ ）条。 A5 B6 C7 D 8 答案： B 24、下列数学模型中， （ ）是线性规划模型。 A. MinZ =3 x 1 + x 2 2 x 3 B. MaxZ=10x 1 +x 2 -3x 3 2x 1 +3x 2 -4x 3 12 2 x 1 +5x 2 15 4x 1 +x 2 +2x 3 8 x 1 -8x 2 +3x 3 22 3x 1 -x 2 +3x 3 =6 x j 0, j=1,2,3 x 1 0,x 2 无约束 ,x 3 0 C. Z=5x 1 +6x 2 +8x 3 -9x 4 D. 2 MaxZ=x 1 +4x 2 -8x 3 +x 4 x 1 +4x 3 -x 4 =19 x 1 +4x 3 -x 4 =29 x 2 -5x 3 +4x 4 30 x 2 -5x 3 +4x 4 40 x 1 +x 2 -6x 4 9 x 1 +x 2 -6x 4 19 x j 0,j=1,2,3,4 x j 0,j=1,2,3,4 答案： A 25、若线性规划问题的最优解不唯一，则在最优单 纯形 表上 （ ）。 A非基变量的检验数都为 零 B非基变量检验数不必有为 零 者 C非基变量检验数必有为 零 D非基变量的检验数都小于零 答案： C 26、对于总运输费用最小的运输问题，若已得最优运输方案，则其 中所有空 格的检验数均 （ ）。 A非正 B非负 C大于 0 D小于 0 答案： B 27、下列步骤中，不属于目标规划模型图解法的为 （ ）。 A作平面直角坐标系 B作出目标约束所在直线，标出偏 差方向 C作出目标函数的一族平行 线 D按优先级次序，确定满 意 解 答案： C 28、下列关于图的说法中，错 误 的 为 （ ）。 第 4 页 共 17 页运筹学期末复习题 A点表示所研究的事物对象 B边表示事物之间的联系 C无向图是由点及边所构成的图 D无环的图称为简单图 答案： D 二、判断题 1、若 LP 问题有最优解，则要么最优解唯一，要么有无穷多最优解。 （ ） 答案： 对 2、在运输问题的解的检验数的计算时，常采用匈牙利法。 （ ） 答案： 错 + 3、偏差变量是指实际值与目标值的差距，其中 d 可以用来表示实际值未达到目标值的差距。 （ ） 答案： 错 4、作业的最早结束时间是它的最早开始时间加上该项作业的计划时间。 （ ） 答案： 对 5、关键路线上的作业称为关键作业。 （ ） 答案： 对 6、破圈法可以用来求解部分树。 （ ） 答案： 对 7、增加约束条件时，线性规划模型的可行域不扩大。 （ ） 答案： 对 8、线性规划问题存在至少一个对偶问题。 （ ） 答案： 错 9、产地数与销地数相等的运输问题是产销平衡运输问题。 （ ） 答案： 错 10、在互为对偶的一对原问题与对偶问题中，不管原问题是求极大或是极小，原问题可行解的目标函数值 都一定超过其对偶问题可行解的目标函数值。 （ ） 答案： 错 11、图的最小生成树一定唯一。 （ ） 答案： 错 12、动态规划的逆推与顺推解法得到不同的最优解。 （ ） 答案： 错 13、对于线性规划标准型，利用单纯形求解时，每做一次换基迭代，都能保证它相应的目标函数值必为不 第 5 页 共 17 页运筹学期末复习题 减少。 （ ） 答案： 对 14、当目标规划问题模型中存在 1 x d 5 x 的约束条件，则该约束为系统约束。 （ ） 2 答案： 错 15、PERT 网络图中，事件通常用箭线表示，作业用圆圈表示。 （ ） 答案： 错 16、无多重边的图称为简单图。 （ ） 答案： 错 17、运输问题、最短路问题和求网络最大流问题，都可看作是最小费用流的特例。 （ ） 答案： 对 18、目标规划问题中，权系数是定量的概念，数值越大，表示该目标越重要。 （ ） 答案： 对 19、若线性规划问题存在可行域，则问题的可行域是凸集。 （ ） 答案： 对 20、目标规划模型中，应同时包含系统约束与目标约束。 （ ） 答案： 错 21、PERT 网络图中，任何消耗时间或资源的行动都可称作作业。 （ ） 答案： 对 22、任务分配问题共有 m m 个约束条件。 （ ） 答案： 错 23、树枝总长为最短的部分树称为图的最小部分树。 （ ） 答案： 对 24、目标的优先级是一个定性的概念，不同优先级的目标无法从数量上来衡量。 （ ） 答案： 对 25、单纯形法计算中，应选取最小正检验数对应的变量作为换入变量。 （ ） 答案： 错 26、当目标规划问题模型中存在 2 1 x 4 x 的约束条件，则该约束为目标约束。 （ ） 2 答案： 错 27、PERT 网络图中，事件消耗一定的时间和资源。 （ ） 答案： 错 第 6 页 共 17 页运筹学期末复习题 28、在动态规划模型中，问题的阶段数等于问题中的子问题的数目。 （ ） 答案： 对 29、运输问题和求网络最大流问题，都可看作是最小费用流的特例。 （ ） 答案： 对 30、当网络中不存在任何增广链时，则网络达到最大流状态。 （ ） 答案： 对 31、在可行解的状态下，原问题与对偶问题的目标函数值是相等的。 （ ） 答案： 错 32、在解决运输问题时，采用闭回路法，可以得到运输问题的基本可行解。 （ ） 答案： 错 33、在整数规划问题中，若变量取值为 0 或者 1，则为 01 规划问题。 （ ） 答案： 对 34、PERT 网络图是由结点、弧及权所构成的有向图。 （ ） 答案： 对 35、完成各个作业需要的时间最长的路线称为关键路线。 （ ） 答案： 对 三、名词解释题 1、规划问题 答案： 生产和经营中经常提出如何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益。 这就是所谓的规划问题。 2、对偶问题 答案： 内容一致但从相反角度提出的一对问题称为对偶问题。 3、无向图 答案： 无向图是指由点及边所构成的图。 4、割集 答案： 割集是指容量网络中一组弧的集合，割断这些弧，能使流中断，简称割。 5、路线 答案： 从 PERT 网络图中从最初事件到最终事件的一条路。 6、偏差变量 答案： 偏差变量指实际值与目标值的差距。 第 7 页 共 17 页运筹学期末复习题 7、PERT 网络图 答案： PERT 网络图是由结点、弧及权所构成的有向图。 8、增广链 答案： 由发点到收点之间的一条链，如果在前向弧上满足流量小于容量，即 f ij c ij ，后向弧上满足流量大 于 0，即 f ij 0，则称这样的链为增广链。 9、系统约束 答案： 系统约束指某种资源在使用上要受到严格的限制，决不允许超用或超负荷运行。 10、简单图 答案： 既没有自环也没有平行边的图称为简单图。 11、状态转移律 答案： 状态参数变化的规律。 从第 k 阶段的某一状态值 s k 出发，当决策变量 x k 的取值确定之后，下一阶段 的状态值 s k+1 按某种规律 T(s k , x k ) 确定。 12、闭回路 答案： 闭回路指调运方案中由一个空格和若干个有数字格的水平和垂直连线包围成的封闭回路。 13、正偏差变量 答案： 正偏差变量指实际值超出目标值的差距。 14、作业的最早开始时间 答案： 作业的最早开始时间是它的各项紧前作业最早结束时间中的最大一个值。 15、连通图 答案： 若一个图中，任意两点之间至少存在一条链，称这样的图为连通图。 16、0-1 规划问题 答案： 在整数规划问题中，若变量取值为 0 或者 1，则为 0-1 规划问题。 17、负偏差变量 答案： 负偏差变量指实际值未达到目标值的差距。 18、作业的最迟结束时间 答案： 作业的最迟结束时间是它的各项紧后作业最迟开始时间中的最小一个。 19、最小割 答案： 网络中所有割集中容量之和为最小的一个割集。 20、偏差变量 + - 答案： 偏差变量指实际值与目标值的差距。 d 表示实际值超出目标值的差距； d 表示实际值未达到目标值 的差距。 第 8 页 共 17 页运筹学期末复习 题 21、图 答案： 图是指点 V 和边 E 的集合，用以表示对某种现实事物的抽象。 其中点表示所研究的事物对象；边表 示事物之间的联系。 22、容量网络 答案： 容量网络指对网络上的每条弧 (v i ， v j ) 都给出一个最大的通过能力，称为该弧的容量，记 为 c(v i ， v j )，简称容量。 以 c ij 表示。 23、状态 答案： 状态指某阶段初始状况。 既反映前面各阶段决策的结局，又是本阶段作出决策的出发点和依 据。 是 动态规划中各阶段信息的传递 点和结合点。 四、简答题 1、简述避圈法的步骤？ 答案： 答： 将图中所有的点分为 V 和 v两部分，其中 V 最小部分树内点的集合； v 非最小部分树 内点的集合。 （1）任取一点 vi 加粗，令 vi V；（2）取 V 中与 v相连的边中一条最短 的边 (vi,vj) ，加粗 (vi,vj) ，令 vj V；（3）重复（ 2），至所有的点均在 V 之内。 2、简述利用分枝定界法求解整数规划问题时，首先需要寻找替代问题，简述替代问题应具 备的条件。 答案： （1）容易求解； （2）松弛问题的解集应全部包含原问题的解集。 3、简述图解法的适用条件和基本步骤。 答案： 答： 对于只含两个变量的线性规划问题，可通过在平面上作图的方法求解。 图解法的步骤如下 ： （1）建立平面直角坐标系； （2）图示约束条件，找出可行域； （3）图示代表目标函数的直线及目标函数值增加（或减小）的方向； （4）将目标函数直线沿其法线方向在可行域内向可行域边界平移至目标函数达到最优值为止 ，目标 函数达到最优值的点就为最优点。 4、简述利用元素差额法确定运输问题初始方案的基本思想和步骤。 答： 基本思想： 从总体考虑，得到初始可行方案。 步骤： 从运价表上分别找出每行与每列的最小的两个元 素之差，再从差值最大的行或列中找出最小运价确定供需关系和供应数量。 5、简述求网络最大流的标号算法的基本步骤。 答： 第一步： 标号过程，找一条增广 链 第 9 页 共 17 页运筹学期末复习题 （1）给源点 s 标号s + , (s)= ，表示从 s 点有无限流出潜力 （2）找出与已标号节点 i 相邻的所有未标号节点 j ，若 1) (i, j ) 是前向弧且饱和，则节点 j 不标号； 2) (i, j) 是前向弧且未饱和，则节点 j 标号为 i + , ( j) ，表示从节点 i 正向流出，可增广 ( j) =min (i) , c ij f ij ； 3) ( j,i ) 是后向弧，若 f =0，则节点 j 不标号； ji 4) ( j,i) 是后向弧，若 f 0，则节点 j 标号为 i , ( j ) ，表示从节点 j 流向 i ，可增广 ji ( j) =min (i) , f ji ； （3）重复步骤 （2），可能出现两种情况： 1) 节点 t 尚未标号，但无法继续标记，说明网路中已不存在增广链，当前流 V ( f ) 就是最大 流；所有获标号的节点在 V 中，未获标号节点在 V 中， V 与 V 间的弧即为最小割集；算法结束； 2) 节点 t 获得标号，找到一条增广链，由节点 t 标号回溯可找出该增广链；到第二步。 第二步： 增广过程。 （1）对增广链中的前向弧，令 f = f + (t) , (t) 为节点 t 的标记值； （2）对增广链中的后向弧，令 f = f - (t) ； （3）非增广链上的所有支路流量保持不变。 第三步： 抹除图上所有标号，回到第一步。 6、简述目标规划问题图解分析法的基本思路？ 答案： 除了刚性约束必须严格满足外，对所有的目标约束允许出现偏差，求解的过程是按照问题要求从高 层到低层逐层优化，在不加大高层偏差值的情况下，使该层次的加权偏差值达到最小，进而找出满意解。 7、简述产销平衡运输问题的数学模型？ 答： 具有 m 个产地 a i （ i 1,2, ,m ）和 n 个销地 b j （ j 1, 2, ,n ）的运输问题的数学模型为 m n min z w ij x ij i 1 j 1 第 10 页 共 17 页运筹学期末复习题 m x ij b , ( j 1, 2, , n) j i 1 n s.t. x ij a i , (i 1,2, m) j 1 x ij 0 对于产销平衡问题有 n m b j a i j 1 i 1 运输问题有 m n 个决策变量， m n 个约束条件。 由于产销平衡条件，只有 m n 1 个相互独立， 因此，运输问题的基变量只有 m n 1 个。 8、简述树的性质？ 答： （1）任何树必存在次数为 1 的点；（2 ）具有 n个节点的树 T 的边恰好为 n 1 条；（3 ）任何有 n 个 节点， n 1 条边的连通图必是一棵树。 9、简述整数规划的求解方法有哪些？ 答： 整数规划的求解方法包括： （1）图解法；（2）分枝定（限）界法； （3）割平面法；（4）匈牙利法；（5） 隐枚举法。 10、简述网络图的绘制原则和注意事项？ 答： （1）节点标号原则： 箭头节点的标号要大于箭尾节点的标号。 （ 2）两个节点之间只能表示一道工序， 只能划一条箭线。 作业和箭线是一对一的关系。 （3）全图只有一个起点、一个终点。 （ 4）不能出现缺口与 回路。 （5）各项作业之间的关系： 1）作业 a 结束后可以开始 b 和 c 2）作业 c 在 a 和 b 均结束后才能开始 第 11 页 共 17 页运筹学期末复习题 3）ab 两项作业结束后才可以开始 c 和 d 4）作业 c 在 a 结束后即可进行，但作业 d 必须同时在 a 和 b 结束后才能开始 （6）从左到有，从上到下，尽量避免交叉。 五、计算题 1、某一最大化线性规划问题在利用单纯形法计算时得到表 1。 其中 a,b,c, d, e, f 为未知数， 原问题中要求 各变量均非负。 问 a,b,c, d, e, f 应满足什么条件下，有下面各解成立？ 表 1 C X B b x 1 B x x 3 x 4 x 5 2 x 6 x f 7 c 1 0 e 0 3 x 2 -1 -5 0 1 -1 0 4 第 12 页 共 17 页运筹学期末复习题 x 6 a -3 0 0 -4 1 6 c j z b d 0 0 -3 0 j （1）是非可行解； （2）是唯一最优解； （3）有无穷多最优解； （4）是退化基可行解； （5）是可行解但非最优解，只有 x 可以为换入变量且换出变量必为 x 6 。 1 解： （1）当所有基变量取值均非负时的基解才是可行基解，故当 f 0 时，表中是非可行解。 （2）当现行解为可行解，且对应的非基变量的检验数均小于 0 时，线性规划问题才有唯一最优解， 即 f 0,b 0,d 0 。 （3）当所有非基变量检验数都小于等于 0 且其中存在一个非基变量 x 检验数等于 0，而在 x j 的系数 j 列向量中有大于 0 的分量时有无穷多最优解。 所以 f 0,b 0, d 0 或 f 0,d 0,b 0,c 0 。 （ 4 ） 现 行 解 为 退 化 基 可 行 解 的 条 件 是 基 变 量 中 含 有 零 分 量 且 所 有 的 检 验 数 均 非 正 。 所 以 b 0, d 0, f 0 。 （5）因是可行解，所以有 f 0 ；非最优解且只有 x 可以为换入变量，所以有 b 0,d 0 ；只有 x 6 1 可以为换出变量，所以有 f 6 7 a ，故参数应满足： f 0,b 0, d 0 ， f 6 7 a 。 2、已知： （1）运输问题的供需关系与单位运价表（见表 1）； （2）用最小元素法求得表 1 的初始调运方案（见表 2）； 试用闭回路法求其检验数，并判断此初始调运方案是否最优。 表 1 供需关系与单位运价表 销地 甲 乙 丙 丁 产量 产地 1 3 2 7 6 50 2 7 5 2 3 60 3 2 5 4 5 25 销量 60 40 20 15 表 2 初始调运方案 销地 甲 乙 丙 丁 产量 产地 第 13 页 共 17 页运筹学期末复习题 1 10 40 50 2 25 20 15 60 3 25 25 销量 60 40 20 15 解： 先找出各非基变量的闭回路，即从表 2 的某一空格（非基变量）为起点，用水平或垂直线，只有碰到 数字格（基变量）后才旋转 90 ，继续向前划，直到回到起始空格为止。 检验数的计算，就是从空格对应 的单位运价开始，对闭回路所对应的单位运价交替地赋予 +和 -号，并计算它们的代数和，如表 3 所示。 表 3 空格 闭回路 检验数 （1 丙） （1 丙）（ 2 丙）（ 2 甲）（ 1 甲）（ 1 丙） 7-2+7-3=9 （1 丁） （1 丁）（ 2 丁）（ 2 甲）（ 1 甲）（ 1 丁） 6-3+7-3=7 （2 乙） （2 乙）（ 2 甲）（ 1 甲）（ 1 乙）（ 2 乙） 5-7+3-2=-1 （3 乙） （3 乙）（ 3 甲）（ 1 甲）（ 1 乙）（ 3 乙） 5-2+3-2=4 （3 丙） （3 丙）（ 3 甲）（ 2 甲）（ 2 丙）（ 3 丙） 4-2+7-2=7 （3 丁） （3 丁）（ 3 甲）（ 2 甲）（ 2 丁）（ 3 丁） 5-2+7-3=7 选出检验数最小的为（ -1 ），小于 0，所以该初始调运方案不是最优调运方案。 3、试用单纯形法解下列线性规划问题。 max z x 1 2x 2 2x 1 2x 2 8 s.t . 0x 1 2x 2 4 x ， 1 x 2 0 解： 化标准形，找一个单位矩阵作为基，列出初始单纯形表 max z x 1 2x 0x 0x 2 3 4 2x 1 2x 2 x 3 8 s.t . 0x 1 2x 2 x 4 4 x ， 1 x ， 2 x ， 3 x 4 0 建立初始单纯形表 表 1 第 14 页 共 17 页运筹学期末复习题 c 1 2 0 0 j b i C X B b x 1 B x x 3 x 4 2 a ik i 0 x 3 8 2 2 1 0 0 x 4 0 2 0 1 4 c j z j 如表 1 所示， 其中 c 为目标函数中决策变量 x j 的系数 （ j 1，2，3，4 ），由系数矩阵 j A 2 0 2 2 1 0 0 1 选择单位矩阵 B = 1 1 0 0 1 作为初始可行基，则对应的基变量为 T X B (x 3 ，x 4 ) ，基变量的系数 C B =（0， 0），常数向量 （资源向量） T b (8,4) ，列出约束方程组的增光矩阵 bA. （注： X B 所对应的列的变量 （ x 3 ， x ）为基变量，其余的变量都为非基变量） 4 计算初始单纯形表中的检验数 1 c j z = c j C B B P j j = (1) c j C P ，如非基变量 x 1 x 2 ， 的检验数： B j c 1 z = 1 (1) c 1 C B P =1- （0 0 ） 1 2 0 =1- （0*2+0*2 ）=1 c 2 z = 2 (1) c 2 C B P =2- （0 0 ） 2 2 2 =2- （0*2+0*2 ）=2 基变量 x 3 ，x 4 的检验数为 0（所有基变量的检验数都必定为 0，不用再另行计算） ，由于非基变量的检 验数为 1 和 2，都大于零，所以当前的基础可行解不是最优解，需要进行线性变换。 确定换入变量和换