第3章 运输问题.docx

《第3章 运输问题.docx》由会员分享，可在线阅读，更多相关《第3章 运输问题.docx（19页珍藏版）》请在三一办公上搜索。

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

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

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

4、 5. 6.运输问题约束条件系数矩阵中，变量xij对应的系数列向量可表为0M11M07.运输问题中，在调运方案表中，称填写数字处为由数字的格，它对应运输问题解中的。 8. 运输问题中，在调运方案表中，称不填数字处为空格，它对应解中的。 9.最小元素法求解时，当选定最小元素后，发现该元素的行和列的产量等于销量，此时，在产销平衡表上填一个数，运价表上就要同时划去一行或一列，为了保持调运方案中的有数字格保持m+n-1个，就要在同时划去的该行或该列的任一空格位置补填一个。 10运输问题中的闭回路是指调运方案中由和若干个有数字格的水平和垂直连线包围成的封闭回路。 11. 运输问题中构建闭回路的目的是要计

5、算解中各非基变量的。 12.位势法求任一空格检验数的公式为 13.用位势法的时候，如果表中出现有负的检验数时，对方案进行改进和调整的方法应用。 14.在闭回路调整中，在需要减少运量的地方有两个以上相等的最小数，这样调整时原先空格处填上了这个最小数，而有两个以上最小数的地方成了空格，为了用表上作业法继续计算，就要把最小数的格之一变为空格，其余补. 15.位势法计算的时候，首先设v等于 116.表上作业法又称为 17.用位势法进行检验的时候，需要找出绝对值最大的用闭回路调整，得出新的调运方案。 18.实际计算运输问题的检验数的时候，比较简便。 19.闭回路法进行检验的方法是令某非基本量取值为，通过

6、变化原基变量的值找到一个新的可行解，将其同原来的基可行解目标函数值的变化比较。 20.在用闭回路法进行方案调整的时候，要对运量作。 21.构建闭回路的目的是要计算解中的检验数。 22. 构建闭回路的目的是要计算解中对应空格的。 23.任意非基变量均可表示为基向量的。 24. 三、判断 1表上作业法实质上就是求解运输问题的单纯形法。 2.当所有产地产量和销地的销量均为整数值时，运输问题的最优解也为整数值。 3.运输问题是一种特殊的线性规划问题模型，因而求解结果也可能出现下列四种情况之一：有唯一最优解，有无穷多最优解，无界解，无可行解。 4.在运输问题中，只要任意给出一组含个非零的xij，且满足x

7、=a，j=1ijinx=bi=1ijmj，就可以作为一个初始基可行解。 5.运输问题就是线性规划问题。 6.运输问题一定有可行解。 7.运输问题不可以用单纯形法进行计算。 8.表上作业法在计算运输问题时，比单纯形法可节约计算的时候和费用。 9. 运输问题求初始基可行解的方法为最小元素法，即从单位运价表中最小的运价处开始确定供销关系，依次类推，一直到给出全部方案为止。 10. 运输问题求初始基可行解用最小元素法时，如果遇到相同的运价时，应该按照运的多的优先进行运输。 11. 运输问题求初始基可行解用最小元素法时，如果遇到相同的运价时，应该任选其一。 12. 最小元素法求解时，当选定最小元素后，发

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

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

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

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

12、，使总的运费支出最小的数学表达式 答：如果用 xij 代表从第 i 个产地调运给第 j 个销地的物资的单位数量，那么在产销平衡的条件下，使总运费支出最小，其数学模型如下： mn minz=cijxiji=1j=1n (i=1,L,m)xij=ai j=1 m (j=1,L,n)xij=bj i=1xij0 4.如何把一个产销不平衡的运输问题转化为产销平衡的运输问题。 答：当产大于销时，只要增加一个假想的销地j=n+1(实际上是库存)，该销地总需要量为j=1ji=1inm同样可以转化为一个产销平衡的运输问题。 5.写出运输问题数学模型的约束条件的系数矩阵和其中变量xij的系数列向量pij的表达式

13、。 6.一般线性规划问题应具备什么特征才可以转化并列出运输问题的数学模型，并从而用表上作业法求解。 7.运输问题中，运用闭回路法进行调整的方法。 答：从检验数为负值的格出发，作一条除该空格外其余顶点均为有数字格组成的闭回路。在这条闭回路上，按上面讲的方法对运量作最大可能有的调整。 8.运输问题的数学模型的系数矩阵的特点： 约束条件的系数矩阵的元素只有两个：0、1。 元素 xij 对应于每一个变量在前m个约束方程中(第i个方程中)出现一次，在后n个约束方程中也出现一次。 产销平衡问题为等式约束。 产销平衡问题中各产地产量之和与各销售地点的销量之和相等。 9.运输问题的求解思路是什么？ 答：同单纯

14、形法类似，用表上作业法求解运输问题时，首先给出一个初始方案，一般来讲，这个方案不会是最好的，因此需要给出一个判别准则，并对初始方案进行调整、改进，一直到求得最优方案为止。 10最小元素法的步骤。 答：最小元素法的基本思想是就近供应，步骤是从单位运价表中最小的运价处开始确定供销关系，依次类推，一直到给出全部方案为止。 11.位势法的步骤 答：1）用最小元素法确定初始调运方案。2）建立由初始可行解得出的调运方案表中有数字的格换成对应格的运价。3）在此表中右面和下面增加一行或一列，并填上这一一些数字，是表中的各个数刚好等于它所占行和所占列的这些新填写的数字之和。用新填的数字。4）利用公式数，u，vi

15、j代表这些l=cijij-(ui+vj)，求出各空格出的检验数，其中lij为检验cij为对应格的单位运价表中的运价。 12表上作业法计算步骤框图。 分析实际问题列出产销平衡表及单位运价表确定初始调运方案求检验数是否满足工期要求是得到最优方案算出总的运价否计算并累计增加的费用13.运输问题建模注意的两个问题。 答：1）产销平衡。如产大于销，则虚设一个销地，其销量为原总产量与总销量之差；若销大于产，则虚设一个产地，其产量为原总产量与总产量之差，在没有特殊限制时，运输费用均取零。 2）大M技术。当某个格中的运输量须限制为零时，可令该格的单位运输费用为M 14.闭回路法：首先，对每个非基量找出以其为起

16、始顶点，其他顶点均为基变量的闭回路。然后利用这些闭回路求检验数；把闭回路的每一顶点按一个方向的顺序标号，并把奇标号的单位运输费用取正值，偶标号的单位运输费用取负值，其代数和即为该非基变量的检验数。 五、计算 1.现有某种货物从A1，A2，A3三个产地运往B1，B2，B3，B4，4个销地。产销需求及运价如表所示，问应如何安排调运方案，才能使总运费最少？ 产销需求及运价表 运价 销B B B B 产量234地1元/t产地 1.5 2 0.3 3100A1 7 0.8 1.4 280A2 1.2 0.3 2 2.550A3销量50 70 80 302302.某地区有三个化肥厂，除供应地区需要外，估计

17、每年可供应本地区的数字为：化肥厂A-7万t，B-8万t，C-3万t，有四个产粮区需要该种化肥，需要量为：甲-6万t，乙-6万t，丙-3万t，丁-3万t。已知从各化肥厂到各产粮区的每t化肥的运价如表所示 产销需求及运价表 运价 销甲 乙 丙 丁 地元/t产地 5 8 7 3A 4 9 10 7BC销量产量7 8 3 8 4 2 96 6 3 33. 下表给出运输问题的产销平衡表和单位运价表，试用伏格尔法直接给出近似最优解 产销需求及运价表 运价 销B B B 产量23地1元/t产地 5 1 8 12A1 2 4 1 14A2 3 6 7 4A3销量309 10 11 答：伏格尔法求解 销地产地5

18、110233491011 B1 B2 B3 产量 A1 A2 A3 销量212111144MinZ=5*2+2*3+3*4+1*10+1*11=49 产销需求及运价表 运价 销地元/t产地1 234销量1 2 3 4 5 产量 10 2 3 15 9 5 10 15 2 4 15 5 14 7 15 20 15 13 M 82530203020 20 30 10 251054.已知某运输问题的产销平衡表盒单位运价表如表所示。 产销需求及运价表 运价 销A1 A2 A3 A4 A5 A6地元/t产地B1 B2B3B4销量 2 1 3 3 3 5 4 2 2 4 4 4 3 5 4 2 4 1 4

19、 2 2 1 2 2 3030 50 20 40 30 11产量50406031 求最优的运输挑拨方案 单位运价表中的案不变。 .伏格尔法 下表给出运输问题的产销平衡表和单位运价表，试用伏格尔法求出近似解。 销地 运价 1 2 3 4 5 产量 C,C,C133541分别在什么范围内变化时，上面求出的最优调拨方产地 1 2 3 4 销量 3. 销地 运价 产地 10 5 15 20 20 2 10 5 15 20 3 15 14 13 30 15 2 7 M 10 9 4 15 8 25 25 30 20 30 105 1 2 3 4 5 差 10 15 20 5 10 差 销地 1 产地 1

20、 2 3 4 2 10 15 3 5 5 2 15 14 13 10 1 1 2 3 15 7 M 5 5 5 M-2 4 9 4 15 8 4 4 4 1 2 2 2 2 5 5 5 5 5 5 5 5 产量 25 30 20 30 105 1 25 2 20 10 3 20 4 5 25 销量 20 20 30 10 25 minZ=5*20+5*20+3*25+2*10+13*5+8*25=560 六、综合 某地区有三个化肥厂，除供应外地区需要外，估计每年可供应本地区的数字为：化肥厂A-7万t，B-8万t，C-3万t，有四个产粮区需要该种化肥，需要量为：甲地区-6万t，乙地区-6万t，丙

21、地区-3万t，丁地区-3万t，已知从各化肥厂到各产粮区的每t化肥的运价如表，根据资料制定一个使总的运费最少的方案。 产粮区 化肥厂 A B C 销量 产粮区 化肥厂 A B C 销量 甲 5 4 8 6 甲 6 6 乙 8 9 4 6 乙 4 2 0 6 丙 7 10 2 3 丙 3 3 丁 3 7 9 3 丁 3 3 产量 7 8 3 产量 7 8 3 答：用最小元素法求初始可行解 4*6+9*2+8*4+2*3+3*3=89 闭回路法检验 产粮区 化肥厂 A B C 销量 甲 5 无 4 6 8 无 6 乙 8 4 9 2 4 0 6 丙 7 无 10 无 2 3 3 丁 3 3 7 无 9 无 3 产量 7 8 3