《运筹学》期末考试复习资料小抄版（呕心沥血整理）.doc

运筹学判断题 一、第1章 线性规划的基本理论及其应用 1、线性规划问题的可行解集不一定是凸集。（×） 2、若线性规划无最优解则其可行域无界。（×） 3、线性规划具有惟一的最优解是指最优表中非基变量检验数全部非零。（√） 4、线性规划问题的每一个基本可行解对应可行域的一个顶点。（√） 5、若线性规划模型的可行域非空有界，则其顶点中必存在最优解。（√） 6、线性规划问题的大M法中，M是负无穷大。（×） 7、单纯形法计算中，若不按最小比值原则选取换出变量，则在下一个解中至少有一个基变量为负。（√） 8、对于线性规划问题的基本可行解，若大于零的基变量数小于约束条件数，则解是退化的。（√）。 9、一旦一个人工变量在迭代过程中变为非基变量后，则该变量及相应列的数字可以从单纯性表中删除，且这样做不影响计算结果。（√） 10、线性规划的目标函数中系数最大的变量在最优解中总是取正值。（×） 11、对一个有个变量，个约束的标准型的线性规划问题，其可行域的顶点恰好为个。（×） 12、线性规划解的退化问题就是表明有多个最优解。（×） 13、如果一个线性规划问题有两个不同的最优解，则它有无穷多个最优解。（√） 14、单纯型法解线性规划问题时值为0的变量未必是非基变量。（√） 15、任何线性规划问题度存在并具有唯一的对偶问题。（√） 16、对偶问题的对偶问题一定是原问题。（√） 17、根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解；反之，当对偶问题无可行解时，其原问题为无界解。（×） 18、若原问题有可行解，则其对偶问题也一定有可行解。（×） 19、若原问题无可行解，其对偶问题也一定无可行解。（×） 20、若原问题有最优解，其对偶问题也一定有最优解。（√） 21、已知为线性规划的对偶问题的最优解，若，说明在最优生产计划中，第种资源一定有剩余。（×） 22、原问题具有无界解，则对偶问题不可行。（√） 23、互为对偶问题，或者同时都有最优解，或者同时都无最优解。（√） 24、某公司根据产品最优生产计划，若原材料的影子价格大于它的市场价格，则可购进原材料扩大生产。（√） 25、对于线性规划问题，已知原问题基本解不可行，对偶问题基本解可行，可采用对偶单纯形法求解。（√） 26、原问题（极小值）第个约束是“”约束，则对偶变量。（√） 27、线性规划问题的原单纯形解法，可以看作是保持原问题基本解可行，通过迭代计算，逐步将对偶问题的基本解从不可行转化为可行的过程。（√） *28、运输问题不能化为最小费用流问题来解决。（×） 29、运输问题一定有最优解。（√） 30、若运输问题的可行解退化，则存在等于零的数字格。（√） 31、运输问题是特殊的线性规划问题，表上作业法也是特殊形式的单纯形法。（√） 32、按最小元素法（或伏格尔法）给出的初始基可行解，从每一空格出发可以找出，而且仅能找出唯一闭合回路。（√） 33、如果运输问题单位运价表的某一行（或某一列）元素分别乘上一个常数，调运方案将不会发生变化。（×） 34、如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数，调运方案将不会发生变化。（√） 35、如果运输问题单位运价表的全部元素分别乘上一个常数，调运方案将不会发生变化。（√） 36、运输问题独立约束条件数个，变量数是个，于是基变量数为个。（×） 37、整数规划解的目标函数值一般优于其相应的线性规划问题的解的目标函数值。（×） 38、一个整数规划问题如果存在两个以上的最优解，则该问题一定有无穷多最优解。（×） 39、分支定界法在需要分支时必须满足：一是分支后的各子问题必须容易求解；二是各子问题解的集合必须覆盖原问题的解 。（√） 40、整数规划的最优解是先求相应的线性规划的最优解然后取整得到。（×） 41、用分支定界法求解一个极大化的整数规划问题时，任何一个可行解的目标函数值是该问题的下界。（√） 42、用分支定界法求解一个极大化的整数规划问题，当得到多于一个可行解时。通常可任取其中一个作为下界值，再进行比较剪枝。（×） 43、求最大值的整数规划问题中，其松弛问题的最优解是整数规划问题最优解的上界。（√）44、匈牙利算法是对指派问题求最小值的一种求解方法。（√） 45、指派问题效率矩阵的每个元素分别乘上一个常数，将不影响最优指派方案。（×） 46、指派问题数学模型的形式同运输问题十分相似，故也可以用表上作业法求解。（√） 47、匈牙利算法是对指派问题求最小值的一种求解方法。（√） 48、应用匈牙利算法求解工作指派问题时，对不打勾的行和打钩的列画横线。（√） 49、求解效率最大的指派问题，可以用指派矩阵的最小元素减去该矩阵的各元素，得到新的指派矩阵，再用匈牙利算法求解。（×） 二、第4章 1、图论中的图不仅反映了研究对象之间的关系，而且是真实图形的