运筹学复习考点

1、运筹学复习运筹学复习 运筹学 第1 1章 线性规划及单纯形 法 ?一、判断题一、判断题 ?（1）图解法与单纯形法虽然求解的形式不同，但从几何上理解，两者 是一致的。 ? 正确。 ? （2）线性规划模型中增加一个约束条件，可行域的范围一般将缩小， 减少一个约束条件，可行域的范围一般将扩大。 ?正确。这里注意：增加约束，可行域不会变大；减少约束，可行域不会 变小。 ?（3）线性规划问题的每一个基解对应可行域的一个顶点。 ?错误。线性规划的基本定理之一为：线性规划问题的基本可行解对应于错误。线性规划的基本定理之一为：线性规划问题的基本可行解对应于 可行域的顶点。 ?（7）单纯形法计算中，如不按最小比

2、值原则选取换出变量，则 在下一个解中至少有一个基变量的值为负。 ?正确。 ?（8）一旦一个人工变量在迭代中变为非基变量后，则该变量及 相应列的数字可以从单纯形表中删除，而不影响计算结果。 ?正确。 ?人工变量一般是为取得对应的初始基基向量而引入的，它一旦成 为出基变量，其地位已被对应的入基变量取代，删除单纯形表中 该变量及相应列的数字，不影响计算结果。 ?（11）线性规划问题的可行解如为最优解，则该可行解一定是基本可 行解。行解。 ?错误。 ?唯一最优解时，最优解是可行域顶点，对应基本可行解；无穷多最优 解时，除了其中的可行域顶点对应基本可行解外，其余最优解不是可 行域的顶点。 ?（12）若线

3、性规划问题具有可行解，且其可行域有界，则该线性规划 问题最多具有有限个数的最优解。问题最多具有有限个数的最优解。 ?错误。 ? 如果在不止一个可行解上达到最优，它们的凸组合仍然是最优解， 这样就有了无穷多的最优解。 ?(13)若线性规划问题的可行域可以伸展到无限，则该问题一定具若线性规划问题的可行域可以伸展到无限，则该问题一定具 有无界解。 ?错误。 ?（14）如果某线性规划模型的一个最优解不是基可行解，则可以 断定该问题有无穷多最优解。断定该问题有无穷多最优解。 ?正确 二、选择题二、选择题 ?1.用单纯形法求解线性规划问题采用两阶段法计算时，第一阶段 计算的单纯形表中人工变量系数取值（）

4、?A.必须为“-1”，其余变量系数为“ 0”； ?B.可取某一负的常数，其余变量系数为“ 0”； ?C.取值为零，其余变量系数为原目标函数中系数 Cj值； ?D.为某一正的常数值，其余变量取值为“ 0”。 ?答案：D ?六、已知某线性规划问题单纯形法迭代时得到中间某两步的单纯 形表如下表所示，试将表中空白处的数字填上。 5 1 0 0 0 0 0 5 1 0 0 0 4 0 1 0 4 0 1 检验数：(0,0,0,-45/41,-24/41,-11/41) 第2章 线性规划的对偶理论 ?一、判断题 ?（1）任何线性规划问题存在并具有唯一的对偶问题。 ?正确。 ? （2）对偶问题的对偶一定是原

5、问题。 ?正确。 ? （3）根据对偶问题的性质，当原问题为无界解时，其对偶问 题无可行解；反之，当对偶问题无可行解时，其原问题具有无界 解。 ?错误。 ?二、已知线性规划问题：二、已知线性规划问题： ?（a）写出其对偶问题； ?（b）已知原问题用两阶段法求解时得到的最终单纯形表如下,试写出其 对偶问题的最优解。 5 3 6 -6 0 0 8 0 1 0 0 1 5 14 1 2 0 0 0 -6 4 0 1 -1 1 0 0 -1 0 0 0 ?三、 ?四、某厂生产四、某厂生产、 三种产品，分别经过三种产品，分别经过 A、B、C三种设备加工， 已知生产单位各种产品 所需要的设备台时，设 备的现

6、有加工能力以及 每件产品的预期的利润 如下表：如下表： 设备能力/台?h A 1 1 1 100 B 10 4 5 600 C 2 2 6 300 单位产品利润/元 10 6 4 10 6 4 0 0 0 6 0 1 0 10 1 0 0 0 100 0 0 4 0 1 0 0 0 10 6 0 0 0 6 0 1 0 10 1 0 0 0 100 0 0 4 0 1 0 0 0 6 0 1 0 10 1 0 0 25 0 0 1 0 0 0 0 第3章 运输问题 ?（4）如果运输问题单位运价表的某一行（或某一列）元素分别 加上一个常数加上一个常数k，最优调运方案将不会发生变化。，最优调运方案

7、将不会发生变化。 ?正确。 ?（5）如果运输问题单位运价表的某一行（或某一列）元素分别 乘上一个常数k，最优调运方案将不会发生变化。 ?错误。 ?（6）如果运输问题单位运价表的全部元素乘上一个常数 k （k0），最优调运方案将不会发生变化。），最优调运方案将不会发生变化。 ?正确。 ?（7）用位势法求运输问题某一调运方案的检验数时，其结果可）用位势法求运输问题某一调运方案的检验数时，其结果可 能同闭回路法求得的结果有异。能同闭回路法求得的结果有异。 ?错误。 ?（8）运输问题初始方案的基本要求）运输问题初始方案的基本要求 :（m+n-1）个数字格，不存）个数字格，不存 在全部以数字格为顶点的闭

8、回路。在全部以数字格为顶点的闭回路。 ?正确。 二、已知运输问题的产销平衡表，单位运价表及某一调运方案如下：二、已知运输问题的产销平衡表，单位运价表及某一调运方案如下： ? 产销平衡表及调运方案 单位运价表 第4章 整数规划与分配问题 ?一、判断题一、判断题 ?（1）整数规划解的目标函数值一般优于其相应的线性规划问题的解的目标 函数值； ?错误。错误。 ?（2）用分枝定界法求解一个极大化的整数规划问题时，任何一个可行解的 目标函数值是该问题目标函数值的下界； ?正确。 ?（3）用分枝定界法求解一个极大化的整数规划问题时，当得到多于一个可 行解时，通常可任取其中一个作为下界值，再进行比较剪枝。

9、?错误。 ?（4）指派问题效率矩阵的每个元素都乘上同一个常数）指派问题效率矩阵的每个元素都乘上同一个常数 k，将不影，将不影 响最优指派方案； ?错误。 ?（5）指派问题数学模型的形式同运输问题十分相似，故也可以 用表上作业法求解；用表上作业法求解； ?正确。 ?（6）用割平面法求解整数规划时，构造的割平面有可能切去一）用割平面法求解整数规划时，构造的割平面有可能切去一 些不属于最优解的整数。些不属于最优解的整数。 ?错误。 ?（7）分枝定界法在需要分枝时必须满足：一是分枝后的各子问 题必须容易求解；二是各个子问题解的集合必须覆盖原问题的解。题必须容易求解；二是各个子问题解的集合必须覆盖原问题

10、的解。 ?正确。 ?（8）一个整数规划问题如果存在两个以上的最优解，则该问题 一定有无穷多最优解。一定有无穷多最优解。 ?错误。 ?二、某科学实验卫星拟从下列仪器装置中选若干件装上，有关数 据资料如下表： ?三、 ?四、 ?五、 第5章 目标规划 ?一、判断题 ?（1）线性规划问题是目标规划问题的一种特殊形式。 ?正确。 ?（2）正偏差变量取正值，负偏差变量应取负值。 ?错误。 ? （3）目标规划模型中，可以不包含系统约束（绝对约束）， 但必须包含目标约束。 ?正确。 选择题 ?1.对于目标规划模型，下述（ ）的表述是不正确的。 ?A.可以不含有系统约束； ?B.目标约束方程必须同时含有正负偏

11、差变量； ?C.单纯形法求解时，若存在小于 0的检验数，则需继续迭代需找 最优解； ?D.目标函数不应出现关于偏差变量最大化的结构。 ?答案：C。 ?二、 ?五、 C点点 第6章 图与网络分析 ?（4）求图的最小支撑树以及求图中一点至另一点的最短路问题， 都可以归结为求解整数规划问题。 ?正确。 ?（5）任一图中奇点的个数可能为奇数个，也可能为偶数个。 ?错误。 ?（6）任何n个节点，（n-1）条边的图一定是树图。 ?错误。 选择题 ?1.已知某个连通图共有 6个偶点，则下述（ ）可能成为其含有 奇点的个数。 ?A.3 ?B.5 ?C.7 ?D.8 ?答案：D。 第7章 计划评审方法和关键路线

12、法 ?一、判断题。 ?（1）网络图中只能有一个始点和一个终点； ?正确。 ?（2）网络图中因虚作业的时间为零，因此在各项时间参数的计 算中可将其忽略。 ?错误。 ?（3）网络图中关键路线的延续时间相当于求图中从起点到终点 的最短路。 ?错误。 ?（4）网络图中求关键路线的问题可表达为求解一个线性规划模 型； ?正确。 ?（5）网络图中从一个事件出发如果存在多项作业，则其中用时 最长的一项作业必包含在该网络图的关键路线内。 ?错误。 ?（6）一项非关键路线上的作业在其最早开始于最迟结束的时间 段内均可任意安排。 ?错误。 ?（7）若一项作业的总时差为 10d，说明任何情况下该项作业从开 始到结束

13、之间总有10d的机动时间。 ?错误。 ?（8）一个网络只存在唯一的关键路线。 ?错误。 ?（9）为了在最短时间内完成项目，其关键路线上作业的开始或 结束时间不允许有任何延迟。 ?正确。 ?（10）网络关键路线上的所有作业，其总时差和自由时差均为零。 ?正确。 ?（11）任何非关键路线上的作业，其总时差和自由时差均不为零。 ?错误。 ?（12）若一项作业的总时差为零，则其自由时差一定为零。 ?正确。 ?（13）若一项作业的自由时差为零，则其总时差比为零。 ?错误。 ?（14）当作业时间用a,m,b三点估计时，m等于完成该项作业的期 望时间。 ?错误。 第8章 动态规划 ?一、判断题。 ?（1）动态规划的最优性原理保证了从某一状态开始的未来决策 独立于先前已作出的决策。 ?正确。 ?（2）对一个动态规划问题，应用顺推或逆推解法可能会得出不 同的最优解。 ?错误。 ?（3）一个动态规划问题若能用网