运筹学复习考点

运筹学复习运筹学复习运筹学运筹学第第1 1章章 线性性规划及划及单纯形法形法一、判断一、判断题（1）图解法与解法与单纯形法形法虽然求解的形式不同，但从几何上理解，两者是然求解的形式不同，但从几何上理解，两者是一致的。一致的。正确。正确。（2）线性性规划模型中增加一个划模型中增加一个约束条件，可行域的范束条件，可行域的范围一般将一般将缩小，小，减少一个减少一个约束条件，可行域的范束条件，可行域的范围一般将一般将扩大。大。正确。正确。这里注意：增加里注意：增加约束，可行域不会束，可行域不会变大；减少大；减少约束，可行域不会束，可行域不会变小。小。（3）线性性规划划问题的每一个基解的每一个基解对应可行域的一个可行域的一个顶点。点。错误。线性性规划的基本定理之一划的基本定理之一为：线性性规划划问题的基本可行解的基本可行解对应于于可行域的可行域的顶点。点。（7）单纯形法形法计算中，如不按最小比算中，如不按最小比值原原则选取取换出出变量，量，则在下一个解中至少有一个基在下一个解中至少有一个基变量的量的值为负。正确。正确。（8）一旦一个人工）一旦一个人工变量在迭代中量在迭代中变为非基非基变量后，量后，则该变量及量及相相应列的数字可以从列的数字可以从单纯形表中形表中删除，而不影响除，而不影响计算算结果。果。正确。正确。人工人工变量一般是量一般是为取得取得对应的初始基基向量而引入的，它一旦成的初始基基向量而引入的，它一旦成为出基出基变量，其地位已被量，其地位已被对应的入基的入基变量取代，量取代，删除除单纯形表中形表中该变量及相量及相应列的数字，不影响列的数字，不影响计算算结果。果。（11）线性性规划划问题的可行解如的可行解如为最最优解，解，则该可行解一定是基本可可行解一定是基本可行解。行解。错误。唯一最唯一最优解解时，最，最优解是可行域解是可行域顶点，点，对应基本可行解；无基本可行解；无穷多最多最优解解时，除了其中的可行域，除了其中的可行域顶点点对应基本可行解外，其余最基本可行解外，其余最优解不是可解不是可行域的行域的顶点。点。（12）若）若线性性规划划问题具有可行解，且其可行域有界，具有可行解，且其可行域有界，则该线性性规划划问题最多具有有限个数的最最多具有有限个数的最优解。解。错误。如果在不止一个可行解上达到最如果在不止一个可行解上达到最优，它，它们的凸的凸组合仍然是最合仍然是最优解，解，这样就有了无就有了无穷多的最多的最优解。解。(13)若若线性性规划划问题的可行域可以伸展到无限，的可行域可以伸展到无限，则该问题一定具一定具有无界解。有无界解。错误。（14）如果某）如果某线性性规划模型的一个最划模型的一个最优解不是基可行解，解不是基可行解，则可以可以断定断定该问题有无有无穷多最多最优解。解。正确正确二、二、选择题1.用用单纯形法求解形法求解线性性规划划问题采用两采用两阶段法段法计算算时，第一，第一阶段段计算的算的单纯形表中人工形表中人工变量系数取量系数取值（）（）A.必必须为“-1”，其余，其余变量系数量系数为“0”；B.可取某一可取某一负的常数，其余的常数，其余变量系数量系数为“0”；C.取取值为零，其余零，其余变量系数量系数为原目原目标函数中系数函数中系数Cj值；D.为某一正的常数某一正的常数值，其余，其余变量取量取值为“0”。答案：答案：D六、已知某线性规划问题单纯形法迭代时得到中间某两步的单纯形表如下表所示，试将表中空白处的数字填上。5100000510004010401检验数：(0,0,0,-45/41,-24/41,-11/41)第第2 2章章 线性性规划的划的对偶理偶理论一、判断一、判断题（1）任何）任何线性性规划划问题存在并具有唯一的存在并具有唯一的对偶偶问题。正确。正确。（2）对偶偶问题的的对偶一定是原偶一定是原问题。正确。正确。（3）根据）根据对偶偶问题的性的性质，当原，当原问题为无界解无界解时，其，其对偶偶问题无可行解；反之，当无可行解；反之，当对偶偶问题无可行解无可行解时，其原，其原问题具有无界解。具有无界解。错误。二、已知二、已知线性性规划划问题：（a）写出其写出其对偶偶问题；（b）已知原已知原问题用两用两阶段法求解段法求解时得到的最得到的最终单纯形表如下形表如下,试写出其写出其对偶偶问题的最的最优解。解。536-60080100151412000-6401-1100-1000三、四、某厂生四、某厂生产、三种三种产品，分品，分别经过A、B、C三种三种设备加工，加工，已知生已知生产单位各种位各种产品品所需要的所需要的设备台台时，设备的的现有加工能力以及有加工能力以及每件每件产品的品的预期的利期的利润如下表：如下表：设备能力/台hA111100B1045600C226300单位产品利润/元10641064000601010100010000401000106000601010100010000401000601010100250010000第第3 3章章 运运输问题（4）如果运）如果运输问题单位运价表的某一行（或某一列）元素分位运价表的某一行（或某一列）元素分别加上一个常数加上一个常数k，最，最优调运方案将不会运方案将不会发生生变化。化。正确。正确。（5）如果运）如果运输问题单位运价表的某一行（或某一列）元素分位运价表的某一行（或某一列）元素分别乘上一个常数乘上一个常数k，最，最优调运方案将不会运方案将不会发生生变化。化。错误。（6）如果运）如果运输问题单位运价表的全部元素乘上一个常数位运价表的全部元素乘上一个常数k（k0），最），最优调运方案将不会运方案将不会发生生变化。化。正确。正确。（7）用位）用位势法求运法求运输问题某一某一调运方案的运方案的检验数数时，其，其结果可果可能同能同闭回路法求得的回路法求得的结果有异。果有异。错误。（8）运）运输问题初始方案的基本要求初始方案的基本要求:（m+n-1）个数字格，不存）个数字格，不存在全部以数字格在全部以数字格为顶点的点的闭回路。回路。正确。正确。二、已知运二、已知运输问题的的产销平衡表，平衡表，单位运价表及某一位运价表及某一调运方案如下：运方案如下：产销平衡表及平衡表及调运方案运方案单位运价表位运价表第4章 整数规划与分配问题一、判断一、判断题（1）整数）整数规划解的目划解的目标函数函数值一般一般优于其相于其相应的的线性性规划划问题的解的目的解的目标函数函数值；错误。（2）用分枝定界法求解一个极大化的整数）用分枝定界法求解一个极大化的整数规划划问题时，任何一个可行解的，任何一个可行解的目目标函数函数值是是该问题目目标函数函数值的下界；的下界；正确。正确。（3）用分枝定界法求解一个极大化的整数）用分枝定界法求解一个极大化的整数规划划问题时，当得到多于一个可，当得到多于一个可行解行解时，通常可任取其中一个作，通常可任取其中一个作为下界下界值，再，再进行比行比较剪枝。剪枝。错误。（4）指派）指派问题效率矩效率矩阵的每个元素都乘上同一个常数的每个元素都乘上同一个常数k，将不影，将不影响最响最优指派方案；指派方案；错误。（5）指派）指派问题数学模型的形式同运数学模型的形式同运输问题十分相似，故也可以十分相似，故也可以用表上作用表上作业法求解；法求解；正确。正确。（6）用割平面法求解整数）用割平面法求解整数规划划时，构造的割平面有可能切去一，构造的割平面有可能切去一些不属于最些不属于最优解的整数。解的整数。错误。（7）分枝定界法在需要分枝）分枝定界法在需要分枝时必必须满足：一是分枝后的各子足：一是分枝后的各子问题必必须容易求解；二是各个子容易求解；二是各个子问题解的集合必解的集合必须覆盖原覆盖原问题的解。的解。正确。正确。（8）一个整数）一个整数规划划问题如果存在两个以上的最如果存在两个以上的最优解，解，则该问题一定有无一定有无穷多最多最优解。解。错误。二、某科学实验卫星拟从下列仪器装置中选若干件装上，有关数据资料如下表：三、四、五、第5章 目标规划一、判断题（1）线性规划问题是目标规划问题的一种特殊形式。正确。（2）正偏差变量取正值，负偏差变量应取负值。错误。（3）目标规划模型中，可以不包含系统约束（绝对约束），但必须包含目标约束。正确。选择题1.对于目标规划模型，下述（）的表述是不正确的。A.可以不含有系统约束；B.目标约束方程必须同时含有正负偏差变量；C.单纯形法求解时，若存在小于0的检验数，则需继续迭代需找最优解；D.目标函数不应出现关于偏差变量最大化的结构。答案：C。二、五、C点点第6章 图与网络分析（4）求图的最小支撑树以及求图中一点至另一点的最短路问题，都可以归结为求解整数规划问题。正确。（5）任一图中奇点的个数可能为奇数个，也可能为偶数个。错误。（6）任何n个节点，（n-1）条边的图一定是树图。错误。选择题1.已知某个连通图共有6个偶点，则下述（）可能成为其含有奇点的个数。C.7答案：D。第7章 计划评审方法和关键路线法一、判断题。（1）网络图中只能有一个始点和一个终点；正确。（2）网络图中因虚作业的时间为零，因此在各项时间参数的计算中可将其忽略。错误。（3）网络图中关键路线的延续时间相当于求图中从起点到终点的最短路。错误。（4）网络图中求关键路线的问题可表达为求解一个线性规划模型；正确。（5）网络图中从一个事件出发如果存在多项作业，则其中用时最长的一项作业必包含在该网络图的关键路线内。错误。（6）一项非关键路线上的作业在其最早开始于最迟结束的时间段内均可任意安排。错误。（7）若一项作业的总时差为10d，说明任何情况下该项作业从开始到结束之间总有10d的机动时间。错误。（8）一个网络只存在唯一的关键路线。错误。（9）为了在最短时间内完成项目，其关键路线上作业的开始或结束时间不允许有任何延迟。正确。（10）网络关键路线上的所有作业，其总时差和自由时差均为零。正确。（11）任何非关键路线上的作业，其总时差和自由时差均不为零。错误。（12）若一项作业的总时差为零，则其自由时差一定为零。正确。（13）若一项作业的自由时差为零，则其总时差比为零。错误。（14）当作业时间用a,m,b三点估计时，m等于完成该项作业的期望时间。错误。第8章 动态规划一、判断题。（1）动态规划的最优性原理保证了从某一状态开始的未来决策独立于先前已作出的决策。正确。（2）对一个动态规划问题，应用顺推或逆推解法可能会得出不同的最优解。错误。（3）一个动态规划问题若能用网络表达时，节点代表各阶段的状态值，各条弧代表了可行的方案选择。正确。（4）动态规划的基本方程是将一个多阶段的决策问题转化为一系列具有递推关系的单阶段决策问题。正确。（5）建立动态规划模型时，阶段的划分是最关键和最重要的一步。错误。（6）动态规划是用于求解多阶段优化决策的模型和方法，这里多阶段既可以是时间顺序的自然分段，也可以是根据问题性质人为地将决策过程划分成先后顺序的阶段。正确。