运筹学课件第三节运输问题的进一步讨论

第三节运输问题的进一步讨论一、产销不平衡的运输问题供大于求供不应求增加虚拟销地

增加虚拟产地

产销平衡的运输问题对应的运价

？转化第三节运输问题的进一步讨论一、产销不平衡的运输问题供大于1各地之间的运价在原问题运价表基础上进行扩展：增加虚拟销地，就地贮存的物品的不经过运输，运价等于零；增加虚拟产地，各个销地所欠缺的物品，其运价等于零；考虑转运，从一地运往自身的单位运价记为零或为负；不存在运输线路的则记为M（一个足够大的正数）；各地之间的运价在原问题运价表基础上进行扩展：增加虚拟销地，就2供应大于需求：数学模型增加一个假想的目的地供应大于需求：数学模型增加一个假想的目的地3B1B2…BnBn+1(贮存)产量A1x11x12…x1nX1,n+1a1A2x21x22…x2nX2,n+1a2:::…:::Amxm1xm2…XmnXm,n+1am销量b1b2…bn产地销地c11c1nc2n000cmncm2cm1c22c21c12B1B2…BnBn+1(贮存)产量A1x11x12…x1nX4二、有转运的运输问题特点是所调运的物资不是由产地直接运送到销地，而是经过若干中转站送达。求解思路：转化成一个等价的产销平衡运输问题，再用表上作业法求出最优调运方案。

二、有转运的运输问题5第一步，将产地、转运点、销地重新编排，转运点既作为产地又作为销地；第二步，各地之间的运价在原问题运价表基础上进行扩展：从一地运往自身的单位运价记为零或为负，不存在运输线路的则记为M（一个足够大的正数）；第一步，将产地、转运点、销地重新编排，转运点既作为产地又作为6第三步，由于经过转运点的物资量既是该点作为销地的需求量，又是该点作为产地时的供应量，但事先又无法获取该数量的确切值，因此通常将调运总量作为该数值的上界。对于产地和销地也作类似的处理。第三步，由于经过转运点的物资量既是该点作为销地的需求量，又是7

例1:某公司有A1、A2两个分厂生产某种产品，分别供应B1、B2、B3三个地区的销售公司销售。假设两个分厂的产品质量相同，假设有两个中转站T1、T2，并且物资的运输允许在各产地、各销地及各转运站之间，即可以在A1、A2、B1、B2、B3、T1、T2之间相互转运。有关数据如下表所示，试求总费用为最少的调运方案。例1:某公司有A1、A2两个分厂生产某种产品，分别8产地中转站销地产量A1A2T1T2B1B2B3产地A1

12131137A21

351929中转T123

1284T2151

452销地B13124

14B2119851

2B3324242

需求量475

产地、销地及中转站的有关数据、运价（元/kg）

发送接受产地中转站销地产量A1A2T1T2B1B2B3产地A9解：从表可以看出，从A1到B2直接运费单价为11元/kg；但从A1经A2到B2，运价为1+9=10元/kg；而从A1经T2到B2只需l+5=6元/kg；若从A1到A2再经B1到B2仅仅需l+1+1=3元/kg。可见转运问题比一般运输问题复杂。现在我们把此转运问题化成一般运输问题，要做如下处理：解：从表可以看出，从A1到B2直接运费单价为1110①由于问题中的所有产地、中转站、销地都可以看成产地，也可以看成销地，因此整个问题可以看成一个有7个产地有7个销地的扩大的运输问题；②对扩大了的运输问题建立运价表，将表中不可能的运输方案用任意大的正数M代替；③所有中转站的产量等于销量，也即流入量等于流出量。①由于问题中的所有产地、中转站、销地都可以看成产地，也可11每个中转站的转运量不会超过16kg，可以规定T1，T2的产量和销量均为16kg。由于实际的转运量：这里si表示i点的流出量，dj表示j点的流入量，对中转点来说，因此si=dj=16。每个中转站的转运量不会超过16kg，可以规定T1，T212这样可以在每个约束条件中增加一个松弛变量xii

，xii相当于一个虚构的中转站，其意义就是自己运给自己。(16-xii)就是每个中转站的实际转运量，xii的对应运价cii=0；④扩大了的运输问题中原来的产地与销地由于也具有转运作用，所以同样在原来的产量与销量的数字上加上16kg，即两个分厂的产量改为23、25kg，销量均为16kg；三个销地这样可以在每个约束条件中增加一个松弛变量xii，xii13的每天销量改为20、23、21kg，产量均为16kg，同时引进xii为松弛变量。于是得到带有中转运输的产销平衡运输表的每天销量改为20、23、21kg，产量均为16kg14产地中转站销地产量A1A2T1T2B1B2B3产地A10121311323A2103519225中转T1230128416T2151045216销地B1312401416B21198510216B3324242016需求量16161616202321128带有中转站的产销平衡运输表发送接受产地中转站销地产量A1A2T1T2B1B2B3产地A1

12131137A21

351929中转T123

1284T2151

452销地B13124

14B2119851

2B3324242

需求量475产地中转站销地产量A1A2T1T2B1B2B3产地A15使用生产B1B2B3生产量A12436≤a1≤11A2156a2=7A3324a3≥4使用量1046例2：产地A1至少发出6个单位物品，最多能生产11单位物品；A2必须发出7个单位物品；A3至少发出4个单位物品；确定最优方案。使用B1B2B3生产量A12436≤a1≤1116使用生产B1B2B3B4（虚拟）生产量A1243M6（必须发出的）A1`24305A2156M7（必须发出的）A3324M4（必须发出的）A3`32403使用量10465解：当A1的产量a1=6（min)，A1,A2的产量之和=13，总需求量为20，所以在产销平衡的情况下A3的产量最大为7；如果A1,A3的产量均取最大11，7，则总产量大于总需求20，此时应增加一个虚销地B4,需求量为5。使用B1B2B3B4生产量A1243M6（必须发17例3：某公司承担4条航线运输任务，已知（1）各条航线的起点和终点以及每天的航班数；各个城市之间的航行时间；每次装船、卸船时间均为1天；问题：公司至少需要配备多少条船才能满足需要？航线起点城市终点城市每天航班数量1234EBADDCFB3211例3：某公司承担4条航线运输任务，已知（1）各条航线的起点和18从至ABCDEFABCDEF0121477103138823015551413150172078517037852030从至ABCDEFA012147719航线装船（天）卸船（天）航行（天）小记（天）航班数量所需船数12341111111117371319591532115710915所需要船只共91条船。城市ABCDEF每天到达每天需要余缺数01-112-120231203-3101各个港口之间调度。每天到达某一个港口的船只数量与它所需要发出船只数量不相等而产生的。将多余船只调往需要的港口，应采用合理的运输方案，单位运价为一对港口城市之间的航行时间。航线装船（天）卸船（天）航行（天）小记（天）航班数量所需船数20至由ABE多余船只C2352D1413172F7831缺少船只1135用表上作业方法求解运输问题，得到最优解按照这两个方案调运船只，其目标函数等于40。，说明各个港口之间调度所需要船只至少40艘。所以，总的需求：91+40=131至ABE多余船只C2352D1413172F783121

有m个产地A1,A2,…,Am和n个目的地B1,B2,B3,…,Bn都可以作为中间转运站使用，因此，发送和接受物品的地点有m+n个。ai:第i个产地的产量bj:第j个目的地的需求量xij:第i个产地运到第j个目的地数量Cij：第i个产地运到第j个目的地的单位运价Ci：第i个地点转运单位物品的费用ti:第i个地点转运物品的数量产地与目的地统一编号，产地在前，目的地在后有m个产地A1,A2,…,Am和n个目的地B1,224个约束条件两边均加上Q;令xii=Q-ti,xjj=Q-tj4个约束条件两边均加上Q;令xii=Q-ti,xjj=Q-23运筹学课件第三节运输问题的进一步讨论24xij≥0(i,j=1,2,…,m+n)说明:当i=j时,所有的cij=-cixij≥0(i,j=1,2,…,m+n)说明:当i=j时,所25产地销地发送量1……….mm+1…..m+n产地1.mx11…………….….x1m.Xm1………..…xmmX1,m+1…….x1,m+n.Xm,m+1…xm,m+nQ+a1Q+am目的地m+1.m+nxm+1,1……xm+1,m.Xm+n,1…xm+n,mXm+1,m+1….xm+1,m+n.Xm+n,m+1….xm+n,m+nQQ接受量Q…QQ+bm+1….Q+bm+n发送接受产地销地发送量1……….mm+1…..m+n产地126接受发送产地销地发送量1……….mm+1…..m+n产地1.m-c1…………….….c1m.cm1………..…-cmc1,m+1…….c1,m+n.cm,m+1…cm,m+nQ+a1Q+am目的地m+1.m+ncm+1,1……cm+1,m.cm+n,1…cm+n,m-cm+1……..….cm+1,m+n.cm+n,m+1……….-cm+nQQ接受量Q…QQ+bm+1….Q+bm+n接受产地销地发送量1……….mm+1….2712345104020305225643543153运输系统，2个产地1，2；一个中间转运站3；2个目的地4，5；产地的产量a1=10,a2=40,a3=a4=a5=0;目的地接受量b1=b2=b3=0,b4=30,b5=20例4：

12345104020305225643543153运输系统28接受发送产地转运销地发送量12345产地1-4532M6025-12M490转运332-35550销地42M5-36505M456-550接受量5050508070接受产地转运销地发送量12345产地1-453229接受发送产地转运销地发送量12345产地1501060250202090转运350050销地4505055050接受量5050508070用最小元素法求解初始运输方案接受产地转运销地发送量12345产地15010630接受发送产地转运销地发送量12345产地1501060250202090转运3302050销地4505055050接受量5050508070经过2次迭代得到最优解，其运输方案：由1地运输10单位物品到4地；由2地运输20单位物品到5地；由2地运输20单位物品到3地，再由3地转到4地；Z=C14x14+c25x25+c23x23+c3x34+c34x34=2X10+4X20+2X20+3X20+5X20=300接受产地转运销地发送量12345产地15010631小结:产销不平衡的运输问题和有转运的运输问题。小结:32第三节运输问题的进一步讨论一、产销不平衡的运输问题供大于求供不应求增加虚拟销地

增加虚拟产地

产销平衡的运输问题对应的运价

？转化第三节运输问题的进一步讨论一、产销不平衡的运输问题供大于33各地之间的运价在原问题运价表基础上进行扩展：增加虚拟销地，就地贮存的物品的不经过运输，运价等于零；增加虚拟产地，各个销地所欠缺的物品，其运价等于零；考虑转运，从一地运往自身的单位运价记为零或为负；不存在运输线路的则记为M（一个足够大的正数）；各地之间的运价在原问题运价表基础上进行扩展：增加虚拟销地，就34供应大于需求：数学模型增加一个假想的目的地供应大于需求：数学模型增加一个假想的目的地35B1B2…BnBn+1(贮存)产量A1x11x12…x1nX1,n+1a1A2x21x22…x2nX2,n+1a2:::…:::Amxm1xm2…XmnXm,n+1am销量b1b2…bn产地销地c11c1nc2n000cmncm2cm1c22c21c12B1B2…BnBn+1(贮存)产量A1x11x12…x1nX36二、有转运的运输问题特点是所调运的物资不是由产地直接运送到销地，而是经过若干中转站送达。求解思路：转化成一个等价的产销平衡运输问题，再用表上作业法求出最优调运方案。

二、有转运的运输问题37第一步，将产地、转运点、销地重新编排，转运点既作为产地又作为销地；第二步，各地之间的运价在原问题运价表基础上进行扩展：从一地运往自身的单位运价记为零或为负，不存在运输线路的则记为M（一个足够大的正数）；第一步，将产地、转运点、销地重新编排，转运点既作为产地又作为38第三步，由于经过转运点的物资量既是该点作为销地的需求量，又是该点作为产地时的供应量，但事先又无法获取该数量的确切值，因此通常将调运总量作为该数值的上界。对于产地和销地也作类似的处理。第三步，由于经过转运点的物资量既是该点作为销地的需求量，又是39

例1:某公司有A1、A2两个分厂生产某种产品，分别供应B1、B2、B3三个地区的销售公司销售。假设两个分厂的产品质量相同，假设有两个中转站T1、T2，并且物资的运输允许在各产地、各销地及各转运站之间，即可以在A1、A2、B1、B2、B3、T1、T2之间相互转运。有关数据如下表所示，试求总费用为最少的调运方案。例1:某公司有A1、A2两个分厂生产某种产品，分别40产地中转站销地产量A1A2T1T2B1B2B3产地A1

12131137A21

351929中转T123

1284T2151

452销地B13124

14B2119851

2B3324242

需求量475

产地、销地及中转站的有关数据、运价（元/kg）

发送接受产地中转站销地产量A1A2T1T2B1B2B3产地A41解：从表可以看出，从A1到B2直接运费单价为11元/kg；但从A1经A2到B2，运价为1+9=10元/kg；而从A1经T2到B2只需l+5=6元/kg；若从A1到A2再经B1到B2仅仅需l+1+1=3元/kg。可见转运问题比一般运输问题复杂。现在我们把此转运问题化成一般运输问题，要做如下处理：解：从表可以看出，从A1到B2直接运费单价为1142①由于问题中的所有产地、中转站、销地都可以看成产地，也可以看成销地，因此整个问题可以看成一个有7个产地有7个销地的扩大的运输问题；②对扩大了的运输问题建立运价表，将表中不可能的运输方案用任意大的正数M代替；③所有中转站的产量等于销量，也即流入量等于流出量。①由于问题中的所有产地、中转站、销地都可以看成产地，也可43每个中转站的转运量不会超过16kg，可以规定T1，T2的产量和销量均为16kg。由于实际的转运量：这里si表示i点的流出量，dj表示j点的流入量，对中转点来说，因此si=dj=16。每个中转站的转运量不会超过16kg，可以规定T1，T244这样可以在每个约束条件中增加一个松弛变量xii

，xii相当于一个虚构的中转站，其意义就是自己运给自己。(16-xii)就是每个中转站的实际转运量，xii的对应运价cii=0；④扩大了的运输问题中原来的产地与销地由于也具有转运作用，所以同样在原来的产量与销量的数字上加上16kg，即两个分厂的产量改为23、25kg，销量均为16kg；三个销地这样可以在每个约束条件中增加一个松弛变量xii，xii45的每天销量改为20、23、21kg，产量均为16kg，同时引进xii为松弛变量。于是得到带有中转运输的产销平衡运输表的每天销量改为20、23、21kg，产量均为16kg46产地中转站销地产量A1A2T1T2B1B2B3产地A10121311323A2103519225中转T1230128416T2151045216销地B1312401416B21198510216B3324242016需求量16161616202321128带有中转站的产销平衡运输表发送接受产地中转站销地产量A1A2T1T2B1B2B3产地A1

12131137A21

351929中转T123

1284T2151

452销地B13124

14B2119851

2B3324242

需求量475产地中转站销地产量A1A2T1T2B1B2B3产地A47使用生产B1B2B3生产量A12436≤a1≤11A2156a2=7A3324a3≥4使用量1046例2：产地A1至少发出6个单位物品，最多能生产11单位物品；A2必须发出7个单位物品；A3至少发出4个单位物品；确定最优方案。使用B1B2B3生产量A12436≤a1≤1148使用生产B1B2B3B4（虚拟）生产量A1243M6（必须发出的）A1`24305A2156M7（必须发出的）A3324M4（必须发出的）A3`32403使用量10465解：当A1的产量a1=6（min)，A1,A2的产量之和=13，总需求量为20，所以在产销平衡的情况下A3的产量最大为7；如果A1,A3的产量均取最大11，7，则总产量大于总需求20，此时应增加一个虚销地B4,需求量为5。使用B1B2B3B4生产量A1243M6（必须发49例3：某公司承担4条航线运输任务，已知（1）各条航线的起点和终点以及每天的航班数；各个城市之间的航行时间；每次装船、卸船时间均为1天；问题：公司至少需要配备多少条船才能满足需要？航线起点城市终点城市每天航班数量1234EBADDCFB3211例3：某公司承担4条航线运输任务，已知（1）各条航线的起点和50从至ABCDEFABCDEF0121477103138823015551413150172078517037852030从至ABCDEFA012147751航线装船（天）卸船（天）航行（天）小记（天）航班数量所需船数12341111111117371319591532115710915所需要船只共91条船。城市ABCDEF每天到达每天需要余缺数01-112-120231203-3101各个港口之间调度。每天到达某一个港口的船只数量与它所需要发出船只数量不相等而产生的。将多余船只调往需要的港口，应采用合理的运输方案，单位运价为一对港口城市之间的航行时间。航线装船（天）卸船（天）航行（天）小记（天）航班数量所需船数52至由ABE多余船只C2352D1413172F7831缺少船只1135用表上作业方法求解运输问题，得到最优解按照这两个方案调运船只，其目标函数等于40。，说明各个港口之间调度所需要船只至少40艘。所以，总的需求：91+40=131至ABE多余船只C2352D1413172F783153

有m个产地A1,A2,…,Am和n个目的地B1,B2,B3,…,Bn都可以作为中间转运站使用，因此，发送和接受物品的地点有m+n个。ai:第i个产地的产量bj:第j个目的地的需求量xij:第i个产地运到第j个目的地数量Cij：第i个产地运到第j个目的地的单位运价Ci：第i个地点转运单位物品的费用ti:第i个地点转运物品的数量产地与目的地统一编号，产地在前，目的地在后有m个产地A1,A2,…,Am和n个目的地B1,544个约束条件两边均加上Q;令xii=Q-ti,xjj=Q-tj4个约束条件两边均加上Q;令xii=Q-ti,xjj=Q-55运筹学课件第三节运输问题的进一步讨论56xij≥0(i,j=1,2,…,m+n)说明:当i=j时,所有的cij=-cixij≥0(i,j=1,2,…,m+n)说明:当i=j时,所57产地销地发送量1……….mm+1…..m+n产地1.mx11…………….….x1m.Xm1………..…xmmX1,m+1…….x1,m+n.Xm,m+1…xm,m+nQ+a1Q+am目的地m+1.m+nxm+1,1……xm+1,m.Xm+n,1…xm+n,mXm+1,m+1….xm+1,m+n.Xm+n,m+1….xm+n,m+nQQ接受量Q…QQ+bm+1….Q+bm+n发送接受