第3章 运输问题.doc

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

2、 C m+n-1 D m*n 6.运输问题的数学模型中，包含有（ D）变量。A m+n B m-n C m+n-1 D m*n 7. 运输问题的数学模型中，包含有（ A）个约束条件。A m+n B m-n C m+n-1 D m*n 8. 运输问题的数学模型中,系数矩阵中线性独立的列向量的最大个数为（C ）A m+n B m-n C m+n-1 D m*n 9. 运输问题的解中的基变量数一般为（C ）A m+n B m-n C m+n-1 D m*n 10.运输问题中，在检验数表上所有检验数都（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）ePjmiij 0107.运输问题中，在调运方案表中，称填写数字处为由数字的格，它对应运输问题解中的（基变量取值） 。8. 运输问题中，在调运方案表中，称不填数字处为空格，它对应解中的（非基变量） 。9.最小元素法求解时，当选定最小元素后，发现该元素的行和列的产量等于销量，此时，在产销平衡表上填一个数，运价表上就要同时划去一行或一列，为了保持调运方案中的有数字格保持 m+n-1 个，就要在同时划去的该行或该列的任一空格位置补填一

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

6、设 等于（1）v16.表上作业法又称为（运输单纯形法）17.用位势法进行检验的时候，需要找出绝对值最大的（负检验数）用闭回路调整，得出新的调运方案。18.实际计算运输问题的检验数的时候， （位势法 ）比较简便。19.闭回路法进行检验的方法是令某非基本量取值为（ 1） ，通过变化原基变量的值找到一个新的可行解，将其同原来的基可行解目标函数值的变化比较。20.在用闭回路法进行方案调整的时候，要对运量作（最大可能的调整） 。21.构建闭回路的目的是要计算解中（各非基变量）的检验数。22. 构建闭回路的目的是要计算解中对应空格的（检验数） 。23.任意非基变量均可表示为基向量的（唯一线性组合） 。24

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

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

9、）14.运输问题中，用位势法进行检验的时候，用到的最初的计算表为最小元素作出的初始方案表。 （不正确）15. 运输问题中，用位势法进行检验的时候，用到的最初的计算表为最小元素作出的初始方案表中有运量的格写入对应的运价形成的表。 （正确）16.具有中间转运站的问题，可以写出扩大运输问题的产销平衡表与单位运价表，可以应用表上作业法求解。 （正确）17.运输问题中，闭回路法和位势法的作用是相同的。 （正确）18.伏格尔法是运输问题求检验数的方法。 （不正确）19.位势法是求运输问题初始基可行解的方法。 （不正确）20.在进行运输问题的检验和调整时，都需要用到闭回路法。 （正确）21. 用最小元素法给

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

11、j 表示销地 Bj 的销量；C ij 表示把物资从产地 Ai运往销地 Bj 的单位运价。如果 s1+s2+.+sm=d1+d2+.+dn, 则称该运输问题为产销平衡问题。四、简答1. 写出用伏格尔法求运输问题最优方案近似解的步骤。 答：Vogel 法的步骤是从运价表上分别找出每行与每列的最小的两个元素之差，再从差值最大的行或列中找出最小运价确定供需关系和供应数量。当产地或销地中有一方数量上供应完毕或得到满足时，划去运价表中对应的行或列，再重复上述步骤。一般当产销地的数量不多时，Vogel 法给出的初始方案有时就是最优方案，所以 Vogel 就用作求运输问题最优方案的近似解。2.写出在运输问题中

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

13、答：如果用 代表从第 i 个产地调运给第 j 个销地的物资的单位数量，那么在产销xij平衡的条件下，使总运费支出最小，其数学模型如下：4.如何把一个产销不平衡的运输问题（含产大于销和销大于产）转化为产销平衡的运输问题。答：当产大于销时，只要增加一个假想的销地 j=n+1(实际上是库存 )，该销地总需要量为（),而在单位运价表中从各产地到假想销地的单位运价为 0，就转化成一个产njjmiiba1销平衡的运输问题。类似地，当销大于产时，可以在产销平衡表中增加一个假想的产地i=m+1，该地产量为（ ） ，单位运价表上令从该假想产地到各销地的运价为miinjja10，同样可以转化为一个产销平衡的运输问

14、题。5.写出运输问题数学模型的约束条件的系数矩阵和其中变量 的系数列向量 的表达式。xij pij6.一般线性规划问题应具备什么特征才可以转化并列出运输问题的数学模型，并从而用表上作业法求解。7.运输问题中，运用闭回路法进行调整的方法。答：从检验数为负值的格出发（当有两个以上负检验数时，从绝对值最大的负检验数格出发） ，作一条除该空格外其余顶点均为有数字格组成的闭回路。在这条闭回路上，按上面讲的方法对运量作最大可能有的调整。8.运输问题的数学模型的系数矩阵的特点：（1）约束条件的系数矩阵的元素只有两个：0、1。（2）元素 xij 对应于每一个变量在前 m 个约束方程中(第 i 个方程中)出现一

15、次，在后 n 个约束方程中（第 m+j 个方程中）也出现一次。（3）产销平衡问题为等式约束。0,1 , min11ijmjijijiinjijxnjbmaxcz（4）产销平衡问题中各产地产量之和与各销售地点的销量之和相等。9.运输问题的求解思路是什么？答：同单纯形法类似，用表上作业法求解运输问题时，首先给出一个初始方案，一般来讲，这个方案不会是最好的，因此需要给出一个判别准则，并对初始方案进行调整、改进，一直到求得最优方案为止。10最小元素法的步骤。答：最小元素法的基本思想是就近供应，步骤是从单位运价表中最小的运价处开始确定供销关系，依次类推，一直到给出全部方案为止。11.位势法的步骤答：1）

16、用最小元素法确定初始调运方案。2）建立由初始可行解得出的调运方案表中有数字的格换成对应格的运价。3）在此表中右面和下面增加一行或一列，并填上这一一些数字，是表中的各个数刚好等于它所占行和所占列的这些新填写的数字之和。用 ， 代表这uivj些新填的数字。4）利用公式 ，求出各空格出的检验数，其中 为)(vucjiijijij检验数， 为对应格的单位运价表中的运价。cij12表上作业法计算步骤框图。确定初始调运方案 （ 最小元素法或 V o g e l 法 ）求检验数 （ 闭回路法或位势法 ）是否满足工期要求计算并累计增加的费用是否分析实际问题列出产销平衡表及单位运价表得到最优方案算出总的运价13

17、.运输问题建模注意的两个问题。答：1）产销平衡。如产大于销，则虚设一个销地，其销量为原总产量与总销量之差；若销大于产，则虚设一个产地，其产量为原总产量与总产量之差，在没有特殊限制时，运输费用均取零。2）大 M 技术。当某个格中的运输量须限制为零时，可令该格的单位运输费用为 M（充分大的数）14.闭回路法：首先，对每个非基量找出以其为起始顶点，其他顶点均为基变量的闭回路。然后利用这些闭回路求检验数；把闭回路的每一顶点按一个方向的顺序标号，并把奇标号的单位运输费用取正值，偶标号的单位运输费用取负值，其代数和即为该非基变量的检验数。五、计算1.现有某种货物从 A1，A 2，A 3三个产地运往 B1，

18、B 2，B 3，B 4，4 个销地。产销需求及运价如表所示，问应如何安排调运方案，才能使总运费最少？（应用表上作业法，t 为吨） 产销需求及运价表B1B2B3B4销地运价 元 / t产地产量（ t ）销量（ t ）A1A2A31 . 5 2 0 . 3 37 0 . 8 1 . 4 21 . 2 0 . 3 2 2 . 55 0 7 0 8 0 3 01 0 08 05 02 3 02.某地区有三个化肥厂，除供应地区需要外，估计每年可供应本地区的数字为：化肥厂 A-7 万 t，B-8 万 t，C-3 万 t，有四个产粮区需要该种化肥，需要量为：甲-6 万 t，乙-6 万 t，丙-3 万 t，丁

19、-3 万 t。已知从各化肥厂到各产粮区的每 t 化肥的运价如表所示（表中单位：元/t）产销需求及运价表甲 乙 丙 丁 销地运价 元 / t产地产量（ t ）销量（ t ）A BC5 8 7 34 9 1 0 78 4 2 96 6 3 37833. 下表给出运输问题的产销平衡表和单位运价表，试用伏格尔法直接给出近似最优解 产销需求及运价表B1B2B3销地运价 元 / t产地产量（ t ）销量（ t ）A1A2A35 1 8 2 4 1 3 6 7 9 1 0 1 1 1 21 443 0答：伏格尔法求解 销地产地B1 B2 B3 产量A1A2 A3 21 0341 21 4491 01 1销量

20、5 12131 1MinZ=5*2+2*3+3*4+1*10+1*11=49（元）产销需求及运价表1 2 3 4 5 销地运价 元 / t产地产量（ t ）销量（ t ）1 2341 0 2 3 1 5 95 1 0 1 5 2 41 5 5 1 4 7 1 52 0 1 5 1 3 M 82 0 2 0 3 0 1 0 2 52 53 02 03 01 0 54.已知某运输问题的产销平衡表盒单位运价表如表所示。产销需求及运价表A 1 A 2 A 3 A 4 A 5 A 6销地运价 元 / t产地产量（ t ）销量（ t ）B 1 B 2B 3B 42 1 3 3 3 54 2 2 4 4 4

21、3 5 4 2 4 14 2 2 1 2 23 0 5 0 2 0 4 0 3 0 1 15 04 06 03 13 0（1） 求最优的运输挑拨方案（2） 单位运价表中的 分别在什么范围内变化时，上面求出的最优调拨方C41351,案不变。.伏格尔法（10）下表给出运输问题的产销平衡表和单位运价表，试用伏格尔（Vogel）法求出近似解。 （M为无穷大）销地运价（元）产地1 2 3 4 5 产量1 10 2 3 15 9 252 5 10 15 2 4 303 15 5 14 7 15 204 20 15 13 M 8 30销量 20 20 30 10 25 1053. （共 10 分）差销地运价产地1 2 3 4 5 1 10 2 【3】 15 9 12 【5】 10 15 【2】 4 2 2 2 23 15 【5】 14 7 15 5 5 54 20 15 13 M 8 5 5 5 5 5 3 10 5 4 10 5 1 5 4 5 1 5 4差 2 M-2销地产地1 2 3 4 5 产量1 25（3） 252 20（5） 10（2） 303 20（5） 204 5（13） 25（8） 30销量 20 20 30 10 25 105（3 分）560*8130*230*min Z