第3章运输问题

《第3章运输问题》由会员分享，可在线阅读，更多相关《第3章运输问题（13页珍藏版）》请在金锄头文库上搜索。

1、第三章 运输问题一、选择1. 运输问题在用表上作业法计算的时候，用闭回路法进行调整检验时，通过任一空格可以 找到（ ）闭回路A 、惟一 B 、多个 C 、零个 D 不能确定2. 在产销不平衡的运输问题中，如果产大于销，我们（ B ）把他变成一个产销平衡的运 输问题A 假想一个产地 B 假想一个销地 C 去掉一个产地 D 没有办法3. 最小元素法的基本思想就是（ D ）。A依次供应B全面供应C选择供应D就近供应4. 运输问题中在闭回路调整中，使方案中有数字的格 为（ C ）。A m B n C m+n D m+n-15. 在表上作业法中，调运方案中有数字的格为（ C ）A m+n B m-n C

2、 m+n-1D m*n6运输问题的数学模型中，包含有（D）变量。A m+n B m-n C m+n-1D m*n7. 运输问题的数学模型中，包含有（A ）个约束条件。A m+n B m-n C m+n-1D m*n8. 运输问题的数学模型中A m+n B m-n,系数矩阵中线性独立的列向量的最大个数为（C m+n-1D m*n9. 运输问题的解中的基变量数一般为（ C ）A m+n B m-n C m+n-1D m*n10. 运输问题中， 在检验数表上所有检验数都 （C ），此时运输表中给出的方案就是最优方案。 A 大于零 B 等于零 C 大于等于零 D 小于零11. 在产销不平衡的运输问题中

3、，如果销大于产时，可以在产销平衡表上（A），把他变成一个产销平衡的运输问题A 假想一个产地 B 假想一个销地 C 去掉一个产地 D 没有办法12. 运输问题数学模型的特点之一是（ ）A 一定有最优解 B 不一定有最优解 C 一定有基可行解 D 不一定有基可行解13. 运输问题的数学模型的约束条件的系数矩阵的元素由（）组成。A 0B1C0,1D 不确定14.二、填空1. 求解不平衡的运输问题的基本思想是（设立虚供地或虚需求点，化为供求平衡的标准形式） 。2. 运输问题中求初始基本可行解的方法通常有（最小元素法 ） 、 （伏格尔法 ） 两种方法 。3. 伏格尔法有时就用作求运输问题最优方案的（近似

4、解）4. 运输问题最优性检验通常有（闭回路法、位势法）两种方法。5.6. 运 输 问 题 约 束 条 件 系 数 矩 阵 中 ， 变 量 xij 对 应 的 系 数 列 向 量 可 表 为01（ Pijei em j ）107. 运输问题中，在调运方案表中，称填写数字处为由数字的格，它对应运输问题解中的（基 变量取值）。8. 运输问题中，在调运方案表中，称不填数字处为空格，它对应解中的（非基变量） 。9. 最小元素法求解时，当选定最小元素后，发现该元素的行和列的产量等于销量，此时，在 产销平衡表上填一个数， 运价表上就要同时划去一行或一列， 为了保持调运方案中的有数字 格保持 m+n-1 个，

5、就要在同时划去的该行或该列的任一空格位置补填一个（ 0 ）。 10运输问题中的闭回路是指调运方案中由（一个空格） 和若干个有数字格的水平和垂直连线包围成的封闭回路。11. 运输问题中构建闭回路的目的是要计算解中各非基变量（对应空格）的（ 检验数）。12.位势法求任一空格检验数的公式为（ij cij （ui vj） ）13. 用位势法的时候， 如果表中出现有负的检验数时， 对方案进行改进和调整的方法应用 （闭 回路法调整） 。14. 在闭回路调整中，在需要减少运量的地方有两个以上相等的最小数，这样调整时原先空 格处填上了这个最小数， 而有两个以上最小数的地方成了空格， 为了用表上作业法继续计算，

6、 就要把最小数的格之一变为空格，其余补（0） .15位势法计算的时候，首先设 V1等于（1）16. 表上作业法又称为（运输单纯形法）17. 用位势法进行检验的时候，需要找出绝对值最大的（负检验数）用闭回路调整，得出新 的调运方案。18. 实际计算运输问题的检验数的时候，（位势法 ）比较简便。19. 闭回路法进行检验的方法是令某非基本量取值为（1） ，通过变化原基变量的值找到一个 新的可行解，将其同原来的基可行解目标函数值的变化比较。20. 在用闭回路法进行方案调整的时候，要对运量作（最大可能的调整）。21. 构建闭回路的目的是要计算解中（各非基变量）的检验数。22. 构建闭回路的目的是要计算解

7、中对应空格的（检验数） 。23. 任意非基变量均可表示为基向量的（唯一线性组合）。24.三、判断1 表上作业法实质上就是求解运输问题的单纯形法。（正确）2. 当所有产地产量和销地的销量均为整数值时，运输问题的最优解也为整数值。（正确）3. 运输问题是一种特殊的线性规划问题模型，因而求解结果也可能出现下列四种情况之一： 有唯一最优解，有无穷多最优解，无界解，无可行解。 （不正确）n4. 在运输问题中，只要任意给出一组含（m+n-1 ）个非零的 xij ，且满足xij ai ，j1mxij bj ，就可以作为一个初始基可行解。 （不正确）i15. 运输问题就是线性规划问题。 （正确）6. 运输问题

8、一定有可行解。 （正确）。7. 运输问题不可以用单纯形法进行计算。 （不正确）8. 表上作业法在计算运输问题时，比单纯形法可节约计算的时候和费用。（正确）9. 运输问题求初始基可行解的方法为最小元素法，即从单位运价表中最小的运价处开始确 定供销关系，依次类推，一直到给出全部方案为止。 （正确）10. 运输问题求初始基可行解用最小元素法时，如果遇到相同的运价时，应该按照运的多的 优先进行运输。 （不正确）11. 运输问题求初始基可行解用最小元素法时， 如果遇到相同的运价时， 应该任选其一。（正 确）12. 最小元素法求解时，当选定最小元素后，发现该元素的行和列的产量等于销量，此时， 在产销平衡表

9、上填一个数，此时运价表上就要同时划去一行或一列.（不正确）13. 最小元素法为求运输问题的最优方案的近似解。 （不正确）14. 运输问题中，用位势法进行检验的时候，用到的最初的计算表为最小元素作出的初始方 案表。（不正确）15. 运输问题中，用位势法进行检验的时候，用到的最初的计算表为最小元素作出的初始方 案表中有运量的格写入对应的运价形成的表。 （正确）16. 具有中间转运站的问题，可以写出扩大运输问题的产销平衡表与单位运价表，可以应用 表上作业法求解。 （正确）17. 运输问题中，闭回路法和位势法的作用是相同的。（正确）18. 伏格尔法是运输问题求检验数的方法。 （不正确）19. 位势法是

10、求运输问题初始基可行解的方法。 （不正确）20. 在进行运输问题的检验和调整时，都需要用到闭回路法。（正确）21. 用最小元素法给定初始方案只从局部观点考虑就近供应， 可能造成总体的不合理。 （正 确）22. 一般当产销地的数量不多时， Vogel 法给出的初始方案有时就是最优方案。 （正确）四名词解释1. 表上作业法：根据运输问题数学模型结构上具有的特征，在单纯形法的基础上，逐渐创造 出一种专门用来求解运输问题线性规划模型的运输单纯形法。在我国， 这种方法习惯上称为表上作业法2. 运输问题中的闭回路： 是指调运方案中由一个空格和若干个有数字格的水平和垂直连线包 围成的封闭回路。3产销平衡问题

11、：假设Al, A2, .,Am表示某物资的 m个产地，Bl, B2,表示某物资的n个销地；s表示产地Ai的产量；dj表示销地Bj的销量；Cj表示把物资从产地 Ai 运往销地Bj的单位运价。如果 Sl+S2+.+Sm=dl+d2+.+d n,则称该运输问题为产销平衡问题。四、简答1. 写出用伏格尔法求运输问题最优方案近似解的步骤。答： Vogel 法的步骤是从运价表上分别找出每行与每列的最小的两个元素之差,再从差值最 大的行或列中找出最小运价确定供需关系和供应数量。当产地或销地中有一方数量上供应完毕或得到满足时, 划去运价表中对应的行或列, 再重复上述步骤。 一般当产销地的数量不多 时, Vog

12、el 法给出的初始方案有时就是最优方案,所以Vogel 就用作求运输问题最优方案的近似解。2. 写出在运输问题中应用表上作业方法的步骤答：第一步,用最小元素法或 Vogel 给出运输问题的基开行解。第二步,用闭回路法进行最优性检验判别该解的目标函数值是否最优。第三步,如果检验数表中所有数字大于等于零,表明对调运方案作出任何改变将导致运费不会减少,即给定的方案是最优方案。第四步,如果检验数为负值,那就从检验数为负值的格子出发,作一条除该空格外 其余顶点均为有数字格组成的闭回路,在这条闭回路上,按上面讲的方法对运 量作最大可能的调整。第五步,再对调整过的方案,再用闭回路法进行最优性检验,重复以上步

13、骤,直到检验数为正为止,所得的方案为最优解。3. 写出运输问题在产销平衡的条件下,使总的运费支出最小的数学表达式答：如果用 xij 代表从第 i 个产地调运给第 j 个销地的物资的单位数量,那么在产销平 衡的条件下，使总运费支出最小，其数学模型如下：mn min zcij xiji1 j1nxij aii 1, , mj1mxij bjj 1, , ni1 xij 04. 如何把一个产销不平衡的运输问题 （含产大于销和销大于产） 转化为产销平衡的运输问题。 答：当产大于销时，只要增加一个假想的销地 j=n+1（ 实际上是库存 ），该销地总需要量为mn（ aib j ）,而在单位运价表中从各产地

14、到假想销地的单位运价为0，就转化成一个产i 1 j 1销平衡的运输问题。类似地，当销大于产时，可以在产销平衡表中增加一个假想的产地nmi=m+1 ，该地产量为（bjai ），单位运价表上令从该假想产地到各销地的运价为0，j 1 i1同样可以转化为一个产销平衡的运输问题。5. 写出运输问题数学模型的约束条件的系数矩阵和其中变量xij 的系数列向量 p 的表达式。6. 一般线性规划问题应具备什么特征才可以转化并列出运输问题的数学模型，并从而用表上作业法求解。7. 运输问题中，运用闭回路法进行调整的方法。答：从检验数为负值的格出发 （当有两个以上负检验数时， 从绝对值最大的负检验数格出发） ， 作一

15、条除该空格外其余顶点均为有数字格组成的闭回路。 在这条闭回路上， 按上面讲的方法 对运量作最大可能有的调整。8. 运输问题的数学模型的系数矩阵的特点：（ 1）约束条件的系数矩阵的元素只有两个：0、1。（2）元素 xij 对应于每一个变量在前 m 个约束方程中 （第 i 个方程中 ）出现一次， 在后 n 个约束方程中（第 m+j 个方程中）也出现一次。（3）产销平衡问题为等式约束。（ 4）产销平衡问题中各产地产量之和与各销售地点的销量之和相等。9. 运输问题的求解思路是什么？ 答：同单纯形法类似，用表上作业法求解运输问题时，首先给出一个初始方案，一般来讲， 这个方案不会是最好的， 因此需要给出一个判别准则，并对初始方案进行调整、改进， 一直到求得最优方案为止。10. 最小元素法的步骤。答：最小元素法的基本思想是就近供应，步骤是从单位运价表中最小的运价处开始确定供销关系，依次类推，一直到给出全部方案为止。11. 位势法的步骤答：1）用最小元素法确定初始调运方案。2）建立由初始可行解