运筹学复习考点课件.ppt

1、运筹学复习运筹学复习运筹学运筹学第第1 1章章 线性规划及单纯形线性规划及单纯形法法 一、判断题一、判断题（1 1）图解法与单纯形法虽然求解的形式不同，但从几何上理解，两者）图解法与单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的。是一致的。正确。正确。（2 2）线性规划模型中增加一个约束条件，可行域的范围一般将缩小，）线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行域的范围一般将扩大。减少一个约束条件，可行域的范围一般将扩大。正确。这里注意：增加约束，可行域不会变大；减少约束，可行域不会正确。这里注意：增加约束，可行域不会变大；减少约束，可行域不会变小。

2、变小。（3 3）线性规划问题的每一个基解对应可行域的一个顶点。）线性规划问题的每一个基解对应可行域的一个顶点。错误。线性规划的基本定理之一为：线性规划问题的基本可行解对应于错误。线性规划的基本定理之一为：线性规划问题的基本可行解对应于可行域的顶点。可行域的顶点。（7 7）单纯形法计算中，如不按最小比值原则选取换出变量，则）单纯形法计算中，如不按最小比值原则选取换出变量，则在下一个解中至少有一个基变量的值为负。在下一个解中至少有一个基变量的值为负。正确。正确。（8 8）一旦一个人工变量在迭代中变为非基变量后，则该变量及）一旦一个人工变量在迭代中变为非基变量后，则该变量及相应列的数字可以从单纯形表

3、中删除，而不影响计算结果。相应列的数字可以从单纯形表中删除，而不影响计算结果。正确。正确。人工变量一般是为取得对应的初始基基向量而引入的，它一旦成人工变量一般是为取得对应的初始基基向量而引入的，它一旦成为出基变量，其地位已被对应的入基变量取代，删除单纯形表中为出基变量，其地位已被对应的入基变量取代，删除单纯形表中该变量及相应列的数字，不影响计算结果。该变量及相应列的数字，不影响计算结果。（1111）线性规划问题的可行解如为最优解，则该可行解一定是基本可）线性规划问题的可行解如为最优解，则该可行解一定是基本可行解。行解。错误。错误。唯一最优解时，最优解是可行域顶点，对应基本可行解；无穷多最优唯一

4、最优解时，最优解是可行域顶点，对应基本可行解；无穷多最优解时，除了其中的可行域顶点对应基本可行解外，其余最优解不是可解时，除了其中的可行域顶点对应基本可行解外，其余最优解不是可行域的顶点。行域的顶点。（1212）若线性规划问题具有可行解，且其可行域有界，则该线性规划）若线性规划问题具有可行解，且其可行域有界，则该线性规划问题最多具有有限个数的最优解。问题最多具有有限个数的最优解。错误。错误。如果在不止一个可行解上达到最优，它们的凸组合仍然是最优解，如果在不止一个可行解上达到最优，它们的凸组合仍然是最优解，这样就有了无穷多的最优解。这样就有了无穷多的最优解。(13)(13)若线性规划问题的可行域

5、可以伸展到无限，则该问题一定具若线性规划问题的可行域可以伸展到无限，则该问题一定具有无界解。有无界解。错误。错误。（1414）如果某线性规划模型的一个最优解不是基可行解，则可以）如果某线性规划模型的一个最优解不是基可行解，则可以断定该问题有无穷多最优解。断定该问题有无穷多最优解。正确正确二、选择题二、选择题 1.1.用单纯形法求解线性规划问题采用两阶段法计算时，第一阶段用单纯形法求解线性规划问题采用两阶段法计算时，第一阶段计算的单纯形表中人工变量系数取值（）计算的单纯形表中人工变量系数取值（）A.A.必须为必须为“-1-1”，其余变量系数为，其余变量系数为“0 0”；B.B.可取某一负的常数，

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

7、何线性规划问题存在并具有唯一的对偶问题。正确。正确。（2 2）对偶问题的对偶一定是原问题。）对偶问题的对偶一定是原问题。正确。正确。（3 3）根据对偶问题的性质，当原问题为无界解时，其对偶问）根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解；反之，当对偶问题无可行解时，其原问题具有无界题无可行解；反之，当对偶问题无可行解时，其原问题具有无界解。解。错误。错误。二、已知线性规划问题：二、已知线性规划问题：（a a）写出其对偶问题写出其对偶问题；（b b）已知原问题用两阶段法求解时得到的最终单纯形表如下已知原问题用两阶段法求解时得到的最终单纯形表如下,试写出其试写出其对偶问题的最优解。对

8、偶问题的最优解。536-60080100151412000-6401-1100-1000 三、四、某厂生产四、某厂生产、三种产品，分别经过三种产品，分别经过A A、B B、C C三种设备加工，三种设备加工，已知生产单位各种产品已知生产单位各种产品所需要的设备台时，设所需要的设备台时，设备的现有加工能力以及备的现有加工能力以及每件产品的预期的利润每件产品的预期的利润如下表：如下表：设备能力/台hA111100B1045600C226300单位产品利润/元106410640006010101000100004010001060006010101000100004010006010101002500

9、10000第第3 3章章 运输问题运输问题（4 4）如果运输问题单位运价表的某一行（或某一列）元素分别）如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数加上一个常数k k，最优调运方案将不会发生变化。，最优调运方案将不会发生变化。正确。正确。（5 5）如果运输问题单位运价表的某一行（或某一列）元素分别）如果运输问题单位运价表的某一行（或某一列）元素分别乘上一个常数乘上一个常数k k，最优调运方案将不会发生变化。，最优调运方案将不会发生变化。错误。错误。（6 6）如果运输问题单位运价表的全部元素乘上一个常数）如果运输问题单位运价表的全部元素乘上一个常数k k（k0k0），最优调运方

10、案将不会发生变化。），最优调运方案将不会发生变化。正确。正确。（7 7）用位势法求运输问题某一调运方案的检验数时，其结果可）用位势法求运输问题某一调运方案的检验数时，其结果可能同闭回路法求得的结果有异。能同闭回路法求得的结果有异。错误。错误。（8 8）运输问题初始方案的基本要求）运输问题初始方案的基本要求:（m+n-1m+n-1）个数字格，不存）个数字格，不存在全部以数字格为顶点的闭回路。在全部以数字格为顶点的闭回路。正确。正确。二、已知运输问题的产销平衡表，单位运价表及某一调运方案如下：二、已知运输问题的产销平衡表，单位运价表及某一调运方案如下：产销平衡表及调运方案产销平衡表及调运方案 单位

11、运价表单位运价表第4章 整数规划与分配问题 一、判断题一、判断题（1 1）整数规划解的目标函数值一般优于其相应的线性规划问题的解的目标）整数规划解的目标函数值一般优于其相应的线性规划问题的解的目标函数值函数值；错误。错误。（2 2）用分枝定界法求解一个极大化的整数规划问题时，任何一个可行解的）用分枝定界法求解一个极大化的整数规划问题时，任何一个可行解的目标函数值是该问题目标函数值的下界；目标函数值是该问题目标函数值的下界；正确。正确。（3 3）用分枝定界法求解一个极大化的整数规划问题时，当得到多于一个可）用分枝定界法求解一个极大化的整数规划问题时，当得到多于一个可行解时，通常可任取其中一个作为

12、下界值，再进行比较剪枝。行解时，通常可任取其中一个作为下界值，再进行比较剪枝。错误。错误。（4 4）指派问题效率矩阵的每个元素都乘上同一个常数）指派问题效率矩阵的每个元素都乘上同一个常数k k，将不影，将不影响最优指派方案；响最优指派方案；错误。错误。（5 5）指派问题数学模型的形式同运输问题十分相似，故也可以）指派问题数学模型的形式同运输问题十分相似，故也可以用表上作业法求解；用表上作业法求解；正确。正确。（6 6）用割平面法求解整数规划时，构造的割平面有可能切去一）用割平面法求解整数规划时，构造的割平面有可能切去一些不属于最优解的整数。些不属于最优解的整数。错误。错误。（7 7）分枝定界法

13、在需要分枝时必须满足：一是分枝后的各子问）分枝定界法在需要分枝时必须满足：一是分枝后的各子问题必须容易求解；二是各个子问题解的集合必须覆盖原问题的解。题必须容易求解；二是各个子问题解的集合必须覆盖原问题的解。正确。正确。（8 8）一个整数规划问题如果存在两个以上的最优解，则该问题）一个整数规划问题如果存在两个以上的最优解，则该问题一定有无穷多最优解。一定有无穷多最优解。错误。错误。二、某科学实验卫星拟从下列仪器装置中选若干件装上，有关数据资料如下表：三、四、五、第5章 目标规划 一、判断题（1）线性规划问题是目标规划问题的一种特殊形式。正确。（2）正偏差变量取正值，负偏差变量应取负值。错误。（

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

15、6个偶点，则下述（）可能成为其含有奇点的个数。A.3 B.5 C.7 D.8 答案：D。第7章 计划评审方法和关键路线法 一、判断题。（1）网络图中只能有一个始点和一个终点；正确。（2）网络图中因虚作业的时间为零，因此在各项时间参数的计算中可将其忽略。错误。（3）网络图中关键路线的延续时间相当于求图中从起点到终点的最短路。错误。（4）网络图中求关键路线的问题可表达为求解一个线性规划模型；正确。（5）网络图中从一个事件出发如果存在多项作业，则其中用时最长的一项作业必包含在该网络图的关键路线内。错误。（6）一项非关键路线上的作业在其最早开始于最迟结束的时间段内均可任意安排。错误。（7）若一项作业的

16、总时差为10d，说明任何情况下该项作业从开始到结束之间总有10d的机动时间。错误。（8）一个网络只存在唯一的关键路线。错误。（9）为了在最短时间内完成项目，其关键路线上作业的开始或结束时间不允许有任何延迟。正确。（10）网络关键路线上的所有作业，其总时差和自由时差均为零。正确。（11）任何非关键路线上的作业，其总时差和自由时差均不为零。错误。（12）若一项作业的总时差为零，则其自由时差一定为零。正确。（13）若一项作业的自由时差为零，则其总时差比为零。错误。（14）当作业时间用a,m,b三点估计时，m等于完成该项作业的期望时间。错误。第8章 动态规划 一、判断题。（1）动态规划的最优性原理保证了从某一状态开始的未来决策独立于先前已作出的决策。正确。（2）对一个动态规划问题，应用顺推或逆推解法可能会得出不同的最优解。错误。（3）一个动态规划问题若能用网络表达时，节点代表各阶段的状态值，各条弧代表了可行的方案选择。正确。（4）动态规划的基本方程是将一个多阶段的决策问题转化为一系列具有递推关系的单阶段决策问题。正确。（5）建立动态规划模型时，阶段的划分是最关键和最重要的一步。错误。（6）动态规划是用于求解多阶段优化决策的模型和方法，这里多阶段既可以是时间顺序的自然分段，也可以是根据问题性质人为地将决策过程划分成先后顺序的阶段。正确。