管理运筹学基础 答案

1、管理运筹学基础判断正误线性规划问题的一般模型中不能出现等式约束。正确答案：说法错误在线性规划模型的标准型中,%身=1，2，m）一定是非负的。正确答案：说法正确解答参考：3.判断正误线性规划问题的基本解一定是基本可行解正确答案：说法错误解答参考：5.判断正误同一问题的线性规划模型是唯一的。正确答案：说法错误解答参考：12.第一个顶点和最后一个顶点相同的闭链叫回路。正确答案：说法错误解答参考：14.判断正误Djisktra算法可求出非负赋权图中一顶点到任一顶点的最短距离。正确答案：说法正确 解答参考：15.简述编制统筹图的基本原则。参考答案：统筹图是有向图，箭头一律向右；统筹图只有一个起始点。一个

2、终点， 没有缺口；两个节点之间只能有一个作业相连；统筹图中不能出现闭合回路。17.简述西北角法、最小元素法、差值法确定运输问题初始基本可行解的过程并指出那种方法得出的解较优。参考答案：西北角法：按照地图中的上北下南，左西右东的判断，对调运表中的 最西北角上的空格优先满足最大供应，之后划去一行或一列，重复这种做法，直 至得到初始可行解。最小元素法：对调运表中的最小运价对应的空格优先没醉最 大供应，之后划去一行或一列，重复这种做法，直至得到初始可行解。差值法： 在运价表中，计算各行和各列的最小运价和次最小运价之差，选出最大者，它所 在某行或某列中的最小运价对应的空格优先满足最大供应，重复这种做法，

3、直至 得到初始可行解。一般来讲，用差值法求出的初始可行解最接近最优解，也就是 最优的。2.用图解法求最优解时，只需求出可行域顶点对应的目标值，通过比较大小，就能 找出最优解。正确答案：说法正确单纯形法计算中，选取最大正检验数对应的变量作为换入变量，将使目标函数的 值增加更快。正确答案：说法错误解答参考：6.若原问题有无穷多最优解，则其对偶问题也一定有无穷多最优解。正确答案：说法正确解答参考：表上作业法中，任何一种确定初始基本可行解的方法都必须保证有血+ n -1）个变量。 正确答案：说法正确 解答参考：用分枝定界法求解一个极大化整数规划问题时，任何一个可行解的目标函数值是该问题目标函数值的下界

4、正确答案：说法正确解答参考：用割平面法解整数规划问题时，要求包括松弛变量在内的全部变量必须取整数。正确答案：说法正确解答参考：有向图G中任意两点是可达的，称此图为强连通图正确答案：说法正确13. G的任一流f的流值valf可能超过任一割的容量。正确答案：说法错误判断正误统筹网络中任一节点都表示前一道工序的结束和后一道工序的开始正确答案：说法错误解答参考：20.用标号法求图所示的网络中从vs到vt的最大流。参考答案：（1）Valf =5（2） Valf =72.用单纯形法求解标准型线性规划问题时，与检验数大于0相对应的变量都可被选作换入变量。正确答案：说法正确解答参考：当所有产量和销量均为整数值

5、时，运输问题的最优解也为整数解。正确答案：说法错误判断正误任一图G中，当点集确定之后，树图是G中边数最少的连通图。正确答案：说法正确解答参考：既要满足流值最大又要满足费用最小的流是不存在的。正确答案：说法错误解答参考：简述如何在单纯型表上判别问题是否具有唯一解、无穷多解、无界解或无可行解 参考答案：将检验数q-z/作为判断基本可行解是否为最优解的标准，判断的方法如下：(1)若所有非基变量的检验数q-z0，已经达到最优解；若存在沽0，但所有沽0所在列对应的所有aW0，无界解;从几何意义的角度就是说，约束条件方程组没有可行域，则线 性规划问题五可行解；在最优单纯形表中，如果出现检验数等于0的个数多

6、于基变量 的个数，线性规划模型就有多重解。判断正误线性规划问题的一般模型中不能出现等式约束。正确答案：说法错误5.判断正误同一问题的线性规划模型是唯一的。正确答案：说法错误正确答案：说法错误在运输问题中，只要给出一组含有（m + n -1）个非零的x.且满足全部约束，就可以作为基本可行解。正确答案：说法错误1.线性规划一般模型中的变量不一定是非负的。正确答案：说法正确解答参考：图解法与单纯形法求解的形式不同，但从几何上理解，两者是一致的。正确答案：说法正确解答参考：5.若原问题可行，而对偶问题不可行，则原问题无界。正确答案：说法正确解答参考：表上作业法中，任何一种确定初始基本可行解的方法都必须

7、保证有血+ n -1）个变量。 正确答案：说法正确解答参考：用割平面法解整数规划问题时，要求包括松弛变量在内的全部变量必须取整数。正确答案：说法正确有向图G中任意两点是可达的，称此图为强连通图正确答案：说法正确解答参考:14.f为G上一个流，若e为f不饱和边，那么e也一定为f正边。正确答案：说法错误16. .在统筹网络图中只能有一个始点和一个终点。正确答案：说法正确21.简述分枝定界法的主要步骤参考答案：第一步：先不考虑整数约束条件，对一般情况的线性规划问题用单纯形法或 对偶单纯形法求解。如果求出的最优解满足整数规划问题的所有整 数约束条件，那么这个最优解也就是整数规划问题的最优解，如果 有一

8、个或多个整数约束条件没有被满足，转到第二步。第二步：任意选择一个应该是整数而不是整数解的变量九，设它的非整数解 是外，同时设bk对应的整数位是bk，现在将原问题分成两枝，一 枝是在原问题的基础上，增加约束条件xkWbk；另一枝是在原问题 的基础上，增加约束条件xkNbk+1，这样就构成了两个新的线性规 划问题的子问题。第三步：按照第3.3节对偶单纯形法扩展应用的思路，分别对分枝后的两个 新线性规划子问题继续求解。若新的解不满足原问题整数约束，再 按第二步进行新的分枝，直到满足下面的情况停止分枝：24.简述运输方案的调整过程。参考答案：第一步：确定换入变量同单纯形法一样，在所有的负检验数中，一般

9、选取检验数最小的非基变 量作为换入变量。第二步：确定换出变量和调整量由定理5.4可知，由此时还是非基变量的换入变量和一组基变量可以组 成一个唯一的闭回路，找到这个闭回路以后，以此非基变量为起点，取 此闭回路中偶数顶点取值最小的基变量做为换出变量，调整量的量值即 为此基变量的值。第三步：调整方法(1)闭回路以外的变量取值均保持不变。(2)针对闭回路，奇数顶点变量的值全部加上调整量，偶数顶点变量的 值全部减去调整量。第四步：标识方法为了保证基变量的个数为m+n-1个，在标识上作如下处理：(1)调整后，原来作为非基变量的换入变量就变成了基变量，所以 要把这个变量的值标识成“。”。(2)调整后，原来作为基变量的换出变量就变成了非基变量，所以 要在这个变量的位置打上“X”。第五步：继续求检验数，如果存在负的检验数，就返回第一步，否则计算停 止，说明找到了最优解。1. 一般情况下，松弛变量和多余变量的目标函数系数为零。正确答案：说法正确3.由应用问题建立的线性规划模型中，其约束方程有多种形式正确答案：说法正确解答参考：整数规划问题的可行解与其线性规划问题的可行域内的整数点相对应。正确答案：说法正确解答参考：若Q为f饱和链，则链中至少有一前向边条边为f饱和边，同时至少有一条边后向为f零 边。正确答案