5运输问题+指派问题判断题ppt课件

1、1、运输问题的基可行解中基变量的个数一定是mn1个。 2、运输问题是一种特殊形式的 LP 问题，因而其求解结果也可能会有唯一的最优解或多个最优解。 3、应用表上作业法的最小元素法确定运输问题的初始调运方案时，遇有退化基本可行解时，一定注意补 0, 否则，初始调运方案的数字格数目不满足：数字格数目=m+n-1。 4、运输问题是一种特殊的 LP 问题，总有可行解存在。 5、分支定界法的分支约束为和。 6、整数线性规划的目标函数值一定优于其松弛问题的目标函数值。 7、运输问题不是线性规划问题。 8、运输问题通常用表上作业法求解。 9、运输问题不可能有无界解。 10、运输问题的m+n个约束条件都是线性

2、独立的。,1-5 BAAAA 6-10 BBAAB,1,;,11、运输问题的基可行解中基变量的个数一定是mn1个。 12、运输问题有m+n-1个基变量。 13、运输问题的解中非零变量的个数不能大于m+n-1个。 14、最小元素法的基本思想是优先考虑单位运价最小的运输业务。 15、沃格尔法的基本思想是，如果罚数的值很大时，不按最小运价组织运输就会造成很大损失，故优先考虑罚数最大的行或列中单位运价最小的元素。 16、运输问题的解的最优性检验可用闭回路法。 17、运输表中，每一个空格总可以和一些填有数字的格用水平线或垂直线连在一闭合回路上。 18、闭回路都是一个简单的矩形，不可以是由水平和垂直线组成

3、的其它更复杂的封闭多边形。 19、产量大于销量时，可虚拟一产地。,11-15 BAAAA 16-19 AABB,2,;,20、当迭代到运输问题的最优解时，如果有某个非基变量的检验数等于零，则说明该运输问题有无穷最优解。 21、产销平衡问题是说产地与销地的个数相等。 22、求解运输问题时，表上作业法一般比单纯形法简单方便。 23、表上作业法求解运输问题的基本步骤是确定初始调运方案，最优性检验，方案调整。 24、指派问题的效率矩阵的每一行（或每一列）的各元素分别减去一个该行（或该列）的最小元素，得到一个新的效率矩阵，则以该新矩阵为效率矩阵的指派问题与原问题有相同的最优解。 25、按最小元素法给出的

4、初始基可行解，从每一空格出发可找到而且仅能找到惟一的闭回路。 26、运输问题用最小元素法可以直接求得最优解。 27、运输问题模型是一种特殊的线性规划模型，所以运输问题也可以用单纯形法求解。,20 A 21-25 BAAAA 26-27 BA,3,;,28、表上作业法实质上就是求解运输问题的单纯形法。 29、运输问题一般来讲，用沃格尔法求解的初始解优于用最小元素法求解的最优解。 30、运输问题一定存在最优解。 31、用分支定界法求解整数规划问题时，求对应松弛问题极大值的目标值是各分枝的上界。 32、整数规划中，割平面的构造应满足能割掉松弛问题的最优解，但不割掉原问题的可行解。 33、割平面方法是

5、通过不断改进松弛问题，来求得线性规划问题的最优解。 34、匈牙利算法是求解指派问题的一种常见算法。 35、匈牙利法是对指派问题求最小值的一种求解方法。 36、指派问题矩阵中，覆盖所有零元素的最小直线数等于独立零元素的最大个数。,28-30 AAA 31-36 AAAAAA,4,;,37、指派问题的每个元素都加上同一个常数k，并不会影响最优分配方案。 38、指派问题是一种特殊的运输问题。 39、指派问题目标是使得完成n件事情的总费用最小。 40、将指派问题效率表中的每一行元素同时减去一个数后最优解不变。 41、用位势法计算检验数时，每一行（或列）的位势的值是唯一的，所以每一个空格的检验数是唯一的。 42、当所有产地的产量和销地的销量都是整数时，运输问题的最优解也是整数。