运筹学复习考点

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