第3章运输问题习题3.3表348

第3章 运输问题3.1 判断表3-l 和表3-2中给出的调运方案能否作为用表上作业法求解时的初始解?为什么?表3-1 表3-2解：表3-l 中有5个基格，而要作为初始解，应有m+n-l=3+4-1=6个基格，所以表3-l 给出的调运方案不能作为表上作业法的初始解；表3-2中，有10个数基格，而理论上只应有m+n-l=9个，多出了一个，所以表3-2给出的调运方案不能作为表上作业法的初始解。

3.2 表3-3和表3-4中，分别给出两个运输问题的产销平衡表和单位运价表，试用伏格尔(Vogel)法直接给出近似最优解。

表3-3 表3-4解：（1）第一步：在表3-3中分别求各行和各列的最小运价和次小运价的差额，并分别填入该表的最右列和最下行，如表3-5所示。

表3-5第二步：从行差额或列差额中选出最大者，选择它所在行或列中的最小元素。

在表3-5中,第3列是最大差额所在列。

第3列中最小元素为1，可确定产地2的产品优先供应销地3的需要，得表3-6。

同时将运价表中的第3列数字划去，如表3-7所示。

表3-6 表3-7第三步：对表3-7中未划去的元素再分别计算出各行、各列的最小运价和次小运价的差额，并填入该表的最右列和最下行。

重复第一、二步，直到给出初始解为止，初始解如表3-8所示。

表3-8（2）第一步：在表3-4中分别计算各行和各列的最小运价和次小运价的差额，并分别填入该表的最右列和最下行，如表3-9所示。

表3-9第二步：从行或列差额中选出最大者，选择它所在行或列中的最小元素。

在表3-9中第3列是最大差额所在列。

第3列中最小元素为3，可确定产地1的产品优先供应销地3的需要。

同时将运价表中的第1行数字划去，如表3-10所示。

表3-10第三步：对表3-10中未划去的元素再分别计算出各行、各列的最小运价和次小运价的差额，填入该表的最右列和最下行。

重复第一、二步，直到给出初始解为止，初始解见表3-10的单位运价中格子的右上方方格中的数据。

第3章运输问题一、选择题（在以下各题中，从备选答案当选出1个或多个正确答案）1. 以下变量组是一个闭回路的有( )A.{ x21, x11, x 12, x32, x33, x23,}B.{x11, x 12, x 23, x 34, x 41, x 13}C.{ x21, x 13, x 34, x 41, x 12}D.{ x 12, x 32, x 33, x 23, x 21, x 11}E.{ x12, x22, x32, x33, x23, x21}2. 有m具产地n个销地的平稳运输问题模型具有特点( )A.有mn个变量m+n个约束B.有m+n个变量mn个约束C.有mn个变量m+n-1个约束D.有m+n-1个基变量mn－m－n+1个非基变量E.系数矩阵的秩等于m+n-1.3. 以下说法正确的有( )A.运输问题的运价表第r行的每个c ij同时加上一个非零常数k，其最优调运方案不变B.运输问题的运价表的所有c ij同时乘以一个大于零的常数k，其最优调运方案不变C.运输问题的运价表第p列的每一个c ij同时乘以一个非零常数k，其最优调运方案不变D.运输问题的运价表的所有c ij同时乘以一个非零常数k, 其最优调运方案转变E.不平稳运输问题不必然存在最优解4. 以下结论正确的有( )A.任意一个运输问题不必然存在最优解B.任何运输问题都存在可行解C.产量和销量均为整数的运输问题必存在整数最优解+n －1个变量组组成基变量的充要条件是它不包括任何闭回路E.运输单纯形法（表上作业法）的条件是产量等于销量的平稳问题二、填空题1. 运输问题中⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=847534763C关于基变量x 11,x 21,x 22,x 32,x 33令位势u 1=0那么位势(u 2,u 3,,v 1,v 2,v 3)=( ),查验数（λ12，λ13，λ23，λ31）=( )。

2. 关于以下运输问题2015101510203064351415161710987⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=C（1）用最小元素法取得的初始基可行解X 1=( )。

运输问题习题1．甲、乙、丙三个城市每年分别需要煤炭320、250、350吨，由A 、B 两处煤矿负责供应。

已知煤炭年供应量为A ——400万吨，B ——450万吨。

由煤矿至各城市的单位运价(万元/万吨)。

见表1：由于需大于供，经研究平衡决定，甲城市供应量可减少0~30万吨，乙城市需要量应全部满足，丙城市供应量不少于270万吨。

试求将供应量分配完又使总运费为最低的调运方案。

2．已知运输问题的产销平衡表、单位运价表及最优调运方案分别见表2和表3。

（1） 从A 2→B2的单位运价C 22在什么范围内变化时，上述最优调运方案不变？提示: 只需检验数220σ≥（2） A 2→B4的单位运价C 24变为何值时，有无穷多最优调运方案。

提示: 检验数242424()c u v σ=-+=03．试分析分别发生下列情况时,运输问题的最优调运方案及总运价有何变化.(a) 单位运价表第i 行的每个ij c 都加上一个常数λ;对于任意基变量的检验数，在没加常数λ以前，有 ij ij i j c u v σ=--加常数后令**,i i j j u u v v λ==+，那么基变量的检验数等于***()()ij ij i j ij i j ij c u v c u v σλσ=+-+=--=也就是检验数没有变化，因而最优调运方案没有变化 (b) 单位运价表第j 列的每个ij c 都加上一个常数λ; 对于第j 列基变量的检验数，在没加常数λ以前，有 ij ij i j c u v σ=--加常数后令**,i i j j u u v v λ==+，那么基变量的检验数等于***()()ij ij i j ij i j ij c u v c u v σλσ=+-+=--=又由于其它列的位势不改变，因而检验数也不改变 也就是检验数没有变化，因而最优调运方案没有变化 (c) 单位运价表所有ij c 都乘上一个常数λ。

对于第j 列基变量的检验数，在没加常数λ以前，有 ij ij i j c u v σ=--加常数后令**,i i j j u u v v λλ==，那么基变量的检验数等于***()()()ij ij i j ij i j ij c u v c u v σλλλσ=-+=--= 因此，当0λ≥时检验数的符号没有改变，因而最优调运方案没有变化；而0λ<时检验数的符号改变，因而最优调运方案变化。

第三章运输问题一、选择1、运输问题在用表上作业法计算得时候,用闭回路法进行调整检验时，通过任一空格可以找到( )闭回路A、惟一Ｂ、多个 C、零个Ｄ不能确定2、在产销不平衡得运输问题中,如果产大于销，我们(Ｂ )把她变成一个产销平衡得运输问题A 假想一个产地B 假想一个销地C 去掉一个产地D 没有办法3、最小元素法得基本思想就就是( Ｄ)。

Ａ依次供应B全面供应 C 选择供应D就近供应4、运输问题中在闭回路调整中,使方案中有数字得格为( C ）。

A m Ｂ n C m+ｎ D m+n-１5、在表上作业法中,调运方案中有数字得格为( C )Ａm＋n B ｍ-n Ｃｍ+n-1 D m*n6、运输问题得数学模型中,包含有(D）变量。

A ｍ+n Ｂｍ-n C m+n－1 Ｄm*n７、运输问题得数学模型中,包含有（A)个约束条件。

A ｍ+nB m-n Ｃｍ+n-１ D m*n8、运输问题得数学模型中,系数矩阵中线性独立得列向量得最大个数为(C)Ａｍ+n B m－n C ｍ＋ｎ-1 Dｍ＊n9、运输问题得解中得基变量数一般为(C )A ｍ+ｎB ｍ-nC m+n-1D m*ｎ1０、运输问题中，在检验数表上所有检验数都(C ),此时运输表中给出得方案就就是最优方案。

A大于零B等于零C大于等于零D小于零11.在产销不平衡得运输问题中,如果销大于产时,可以在产销平衡表上( A),把她变成一个产销平衡得运输问题A 假想一个产地B 假想一个销地C 去掉一个产地D 没有办法１2、运输问题数学模型得特点之一就是( ）Ａ一定有最优解Ｂ不一定有最优解C 一定有基可行解Ｄ不一定有基可行解1３、运输问题得数学模型得约束条件得系数矩阵得元素由()组成。

A 0B1Ｃ0,1Ｄ不确定1４、二、填空1、求解不平衡得运输问题得基本思想就是(设立虚供地或虚需求点,化为供求平衡得标准形式) 。

2、运输问题中求初始基本可行解得方法通常有(最小元素法）、(伏格尔法）两种方法。

第3章运输层练习题一、选择题1.当一个TCP报文段到达目的主机时，通过什么来定向套接字？A.封装报文段的数据报中的源IP地址B.目的端口号C.源端口号D.以上所有答案：D提示：TCP套接字是通过一个四元组：（IP地址，源端口号，目的IP地址，目的端口号）来标识的。

当一个TCP报文段从网络到达一台主机时，主机使用全部四个值来将报文段定向（多路分解）到相应的套接字。

2. UDP具有以下哪些特征？A.在服务器上维护连接状态信息B.通过三次握手建立连接C.调节发送速率D.以上都不是答案：D3.当一个UDP报文段到达某个主机时，为了将报文段提交给合适的套接字，操作系统使用：A.源IP地址B.源端口号C.目的端口号D.以上全部答案：C提示：UDP套接字是由一个包含目的IP地址和目的端口号组成的二元组来全面标识的。

在多路分解时，目标主机通过检查报文段中的目的端口号，将报文段定向到相应套接字。

4.在什么样的情况下，停止等待协议的效率会变得很低：疑难：▇重点：★一般：▲了解：◆自学：※3章运输层A.当源主机和目的主机之间的距离很近而且传输速率很高时B.当源主机和目的主机之间的距离很远而且传输速率很高时C.当源主机和目的主机之间的距离很近而且传输速率很低时D.当源主机和目的主机之间的距离很远而且传输速率很低时答案：B提示：使用停止等待协议，发送方在确认接收方已经正确地接收了当前传送的分组之前不会发送新的数据。

所以在传输效率很高的前提下，主机之间距离越远，不必要的等待时间就越长。

流水线操作具有以下哪些特点：A.发送方必须能缓存它已发送了但还没有收到确认的分组B.每一个正在传输的分组具有独一无二的顺序号C.发送方在收到确认信号之前可传输多个分组D.以上都是答案：D6.TCP什么时候对报文段采用快速重传？A.报文段的定时器过期B.估计往返时延过长C.收到之前发出的一个报文段的三个重复ACK以上都不是答案：C提示：当接收方检测到数据流中出现了缺失，它会简单的对收到的最后一个有序字节给出重复确认，即产生一个该数据的重复的ACK。

运输问题习题1．甲、乙、丙三个城市每年分别需要煤炭320、250、350吨，由A 、B 两处煤矿负责供应。

已知煤炭年供应量为A ——400万吨，B ——450万吨。

由煤矿至各城市的单位运价(万元/万吨)。

见表1：表1：甲 乙 丙 A 15 18 22 B212516由于需大于供，经研究平衡决定，甲城市供应量可减少0~30万吨，乙城市需要量应全部满足，丙城市供应量不少于270万吨。

试求将供应量分配完又使总运费为最低的调运方案。

万吨。

试求将供应量分配完又使总运费为最低的调运方案。

甲（1） 甲（2） 乙丙（1） 丙（2）A 15 15 18 22 22 400B 21 21 25 16 16 450C M 0 M M 0 7029030250 270802．已知运输问题的产销平衡表、单位运价表及最优调运方案分别见表2和表3。

表2：产销平衡表及最优调运方案：产销平衡表及最优调运方案销地1 销地2 销地3 销地4 产量产量 产地1 5 10 15 产地2 10 15 25 产地3 5 5 销 量5151510表3：单位运价表：单位运价表B1 B2 B3 B4 A1 10 1 20 11 A2 12 7 9 20 A32141618（1） 从A 2→B2的单位运价C 22在什么范围内变化时，上述最优调运方案不变？在什么范围内变化时，上述最优调运方案不变？提示提示: :只需检验数220s ³ （2） A 2→B4的单位运价C 24变为何值时，有无穷多最优调运方案。

变为何值时，有无穷多最优调运方案。

提示提示: :检验数242424()c u v s =-+=0 3．试分析分别发生下列情况时,运输问题的最优调运方案及总运价有何变化.(a) 单位运价表第i 行的每个ij c 都加上一个常数l ; 对于任意基变量的检验数，在没加常数l 以前，有以前，有 ij ij i j c u v s =--加常数后令**,i i j j u u v v l ==+，那么基变量的检验数等于，那么基变量的检验数等于 ***()()ijijijij i j ij c u v c u v s l s =+-+=--= 也就是检验数没有变化，因而最优调运方案没有变化也就是检验数没有变化，因而最优调运方案没有变化(b) 单位运价表第j 列的每个ij c 都加上一个常数l ; 对于第j 列基变量的检验数，在没加常数l 以前，有以前，有ij ij i j c u v s =-- 加常数后令**,i i j j u u v v l ==+，那么基变量的检验数等于，那么基变量的检验数等于***()()ij ij i j ij i j ij c u v c u v s l s =+-+=--= 又由于其它列的位势不改变，因而检验数也不改变又由于其它列的位势不改变，因而检验数也不改变 也就是检验数没有变化，因而最优调运方案没有变化也就是检验数没有变化，因而最优调运方案没有变化 (c) 单位运价表所有ij c 都乘上一个常数l 。

第三章运输问题一、建立下列问题的数学模型1、P119, 3.6某厂按照合同规定须于当年每季度末分别提供10，15，25，20台同一规格的柴油机。

已知该厂各季度的生产能力及生产每台柴油机的成本如表所示。

又如果生产出来的柴油机当季不交货，每台每积压一个季度，存储维护费用0.15万元。

要求在完成合同的情况下，使得全年生产（存储）费用最小的决策。

将此问题归结为运输问题，试建立该问题的产销平衡及单位运价表。

解：以四个季度为产地和销地，建立产销平衡运输表如下：2、P119, 3.7上题中若允许某些季度末交货时发生短缺，但全部合同必须于Ⅳ季度末完成。

又缺货时，每台每晚交一个季度，罚款0.1万元。

为使总的生产、存储和缺货罚款损失费用最小，重新列出用运输问题求解时的产销平衡和单位运价表。

解：以四个季度为产地和销地，建立产销平衡运输表如下：3、P119, 3.8某造船厂在某年算起的连续三年的年末各提供三条规格相同的货轮，已知该厂今后三年的的生产能力及生产成本如下表所示。

已知加班生产时每条货轮成本比正常生产时高70万元，又知造出的货轮如当年不交货，每条每积压一年增加维护费用40万元。

在签订合同时，已有以前积压的两条，该厂希望在第三年末交货后多留一条备用。

问该厂应如何安排生产计划，满足上述要求，并使得总费用最小。

请列出产销平衡表和单位运价表。

解4、P120, 3.9为确保飞行的安全，飞机上的发动机每半年必须强迫更换进行大修。

某维修厂估计某种型号的战斗机从下一个半年起的今后三年内每半年需更换的发动机数量分别为：100,70,80,120,150,140（台）。

更换发动机时，可以换上新的，也可以用经过大修的旧的发动机。

已知每台新发动机的购置费是10万元，而旧发动机的维修方式有两种：快修，每台2万元，半年交货（本期拆下，下期即可用上，半年为一期）；慢修，每台1万元，一年才能交货（本期拆下，下下期可用上）。

该厂新接手该项发动机的更换维修任务，又知三年后这种战斗机将退役，退役后这种发动机将报废。

习题三3.1 求解下表所示的运输问题，分别用最小元素法、西北角法和伏格尔法给出初始基可行解：3.2由产地A1，A2发向销地B1，B2的单位费用如下表，产地允许存贮，销地允许缺货，存贮和缺货的单位运费也列入表中。

求最优调运方案，使总费用3.3对如下表的运输问题：(2)若产地Z的供应量改为100，求最优方案。

3.4 某利润最大的运输问题，其单位利润如下表所示：(2)当A1的供应量和B3的需求量各增加2时，结果又怎样?８８3.5 某玩具公司分别生产三种新型玩具，每月可供量分别为1000、2000、2000件，它们分别被送到甲、乙、丙三个百货商店销售。

已知每月百货商店各类玩具预期销售量均为1500件，由于经营方面原因，各商店销售不同玩具的盈利额不同,见下表。

又知丙百货商店要求至少供应C玩具1000件，而拒绝进A玩具。

求满足上述条件下使总盈利额最大的供销分配方案。

甲乙丙可供量A 5 4 －1000B 16 8 9 2000C 12 10 11 20003.6 目前，城市大学能存贮200个文件在硬盘上，100个文件在计算机存贮器上，300个文件在磁带上。

用户想存贮300个字处理文件，100个源程序文件，100个数据文件。

每月，一个典型的字处理文件被访问8次，一个典型的源程序文件被访问4次，一个典型的数据文件被访问2次。

当某文件被访问时，重新找到该文件所需的时间取决于文件类型和存贮介质，如下表。

时间（分钟）处理文件源程序文件数据文件硬盘 5 4 4存贮器 2 1 1磁带10 8 6 如果目标是极小化每月用户访问所需文件所花的时间，请构造一个运输问题的模型来决定文件应该怎么存放并求解。

3.7已知下列五名运动员各种姿势的游泳成绩（各为50米）如表5-2：试用运输问题的方法来决定如何从中选拔一个参加200混合泳的接力队，使预期比赛成绩为最好。

3.8 求总运费最小的运输问题，其中某一步的运输图如下表。

８９９０（1）写出a,b,c,d,e 的值，并求出最优运输方案；（2）A 3到B 1的单位运费满足什么条件时，表中运输方案为最优方案。

i a j b iA jB 1A 2A 3A 1B 2B 3B 4B 311310719284741059365620运输问题作业题目1：对下表所给运输问题： （1） 用西北角法求初始解；（2）用最小元素法求初始解，并求出最优解解：（1） 用西北角法求初始解：131421243234(,,,,,)(3,4,2,2,3,6)B x x x x x x x *T T ==（2） 用最小元素法求初始解：2 / 4用位势法求最优解：由于241a =-，所以表３－４９所示的解不是最优解，选择24a 为进基变量，闭回路如上图，调整为下图所示基可行解。

由此看出检验数均为非负，即位最优解，此时131421243234(,,,,,)(5,2,3,1,6,3)B x x x x x x x *T T ==111222233133(,,,,,)(0,0,0,0,0,0)D x x x x x x x *T T ==3 / 4351021381465385f *=⨯+⨯+⨯+⨯+⨯+⨯=5.题目123123123X X X Y Y Y a a a 设有和三个化肥厂供应和三个化肥厂，有关参数如表，假设三个化肥厂供应量和必须全部运完。

建模使总运量最优。

ix 1x 2x 3x jy 1y 2y 3y ijw i a 单位运价'jb "i b 供应量50604016132214--19--2023700307030不限解答：最低需求总量：7030100.+=供应总量：506040150++=3301501008070308018018015030y ∴+∴++=∴-=最高需求量为（-）=最高需求量为供应量缺少12345123451613222250141919602023234003070303050B B B B B A A M A M A MMA4 / 4题目3某厂月底安排某一产品在下月四周生产计划。

估计每件产品在第一周与第二周的生产成本为150元，后两周的生产成本为170元，各周产品需求量分别为700件，800件，1000件和1200件，工厂每周至多生产产品900件，在第二周，第三周可加班生产。