运筹学试题讲解.pdfVIP

习题讲解 一、判断题（共计 10分，每小题 1分，对的打√，错的打X） 1. 无孤立点的图一定是连通图。 2. 对于线性规划的原题和其对偶问题，若其中一个有最优解，另一个也一定有最优解。 3. 如果一个线性规划问题有可行解，那么它必有最优解。 4．对偶问题的对偶问题一定是原问题。  0 5．用单纯形求解标准形式（求最小值）的线性规划问题时，与 j 对应的变量都可以 被选作换入变量。 6．若线性规划的原问题有无穷多个最优解时，其对偶问题也有无穷多个最优解。 7. 度为 0 的点称为悬挂点。 8. 表上作业法实质上就是求解运输问题的单纯形法。 9. 一个图 G 是树的充分必要条件是边数最少的无孤立点的图。 10. 任何线性规划问题都存在且有唯一的对偶问题。 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨ 10 X √ X √ √ √ X √ X √ 一、判断题（对的打√，错的打X. 共计 10分，答在下面的表格中）  x 1、单纯形法计算中，选取最大正检验数 k对应的变量 k作为换入变量，可使目标函数值 得到最快的减少。 2、单纯形法计算中，如不按最小非负比值原则选出换出变量，则在下一个解中至少有一个 基变量的值是负的。 3、对于一个动态规划问题，应用顺推法和逆推法可能会得到不同的最优解。 x 0 x 4、应用对偶单纯形法计算时，若单纯形表中某一基变量 i ，且 i所在行的所有元素 都大于或等于零，则其对偶问题具有无界解。 5、用位势法计算检验数时，每一行（或列）的位势的值是唯一的，所以每一个空格的检验 数是唯一的。 6、动态规划的最短路问题也可以用图论中求最短路问题的方法求解。 7、图论中的图是为了研究问题中有哪些对象及对象之间的关系，它与图的几何形状无关。 8、 动态规划只是用来解决和时间有关的问题。 9、在画网络计划图时，允许有多个起点和多个终点。 10、因为运输问题是一种特殊的线性规划模型，因而求其解也可能出现下列四种情况：有 唯一最优解；有无穷多个最优解；无界解；无可行解。 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨ 10 X X X √ √ X X X X √ 一、 判断题（每题 1 分，共 15 分） （ ）1、 若线性规划问题存在两个不同的最优解，则必然有无穷多个最优解。 （ ）2、 图解法同单纯形法虽然求解形式不同，但从几何上理解，两者是一致的。 （ ）3、 连通图 G 的生成树是取 G 的部分点和部分边所组成的树。 （ ）4、 如线性规划问题存在最优解，则最优解一定对应可行域边界上的一个点。 （ ）5、 按最小元素法（或 Vogel法）给出的初始基可行解，从每一空格出发可以找到而且 仅能找到惟一的闭回路。 （ ）6、 已知 yi*为线性规划的对偶问题的最优解，若 yi*=0，说明在最优生产计划中第 i种 资源一定有剩余。 （ ）7、 对偶问题的对偶问题未必是原问题。 - （ ）8、 当目标规划模型中存在 x + x + d = 4 的约束条件，则该约束为系统约束。 1 2 （ ）9、目标规划中的正偏差变量大于等于