《五讲运输问题与指派问题》由会员分享，可在线阅读，更多相关《五讲运输问题与指派问题（65页珍藏版）》请在金锄头文库上搜索。
1、Excel在经济管理中的应用 第五讲 运输问题与指派问题 5.1 5.1 运输问题运输问题(transportation problem)(transportation problem) 一、什么是运输问题一、什么是运输问题 二、运输问题的分类二、运输问题的分类 三、供需均衡运输问题的建模与求解三、供需均衡运输问题的建模与求解 四、供需非均衡运输问题的建模与求解四、供需非均衡运输问题的建模与求解 五、运输问题的应用 一、什么是运输问题一、什么是运输问题 在经济建设中，经常碰到大宗物资调运问题，在经济建设中，经常碰到大宗物资调运问题， 如煤、钢铁、木材、粮食等等物资。在全国有如煤、钢铁、木材、粮
2、食等等物资。在全国有 若干若干生产基地生产基地，根据已有的交通网，应如何制，根据已有的交通网，应如何制 定调运方案，将这些物资运到定调运方案，将这些物资运到各消费地点各消费地点，而，而 总费用最小总费用最小。 例例 ：设有三个化肥厂供应四个地区的农用化肥，：设有三个化肥厂供应四个地区的农用化肥， 假定等量的化肥在这些地区使用效果相同。各化假定等量的化肥在这些地区使用效果相同。各化 肥厂年产量，各地区年需要量及从各化肥厂到各肥厂年产量，各地区年需要量及从各化肥厂到各 地区运送单位化肥的运价如表所示，试求出总的地区运送单位化肥的运价如表所示，试求出总的 运费最节省的化肥调拨方案。运费最节省的化肥调
3、拨方案。 需求地区 化肥厂 地区1 地区2 地区3地区4 产量 （万吨 ） 厂11613221750 厂21413191560 厂31920231050 需求量 （万吨） 50703010 运价：万元运价：万元/ /万吨万吨 1. 1.供应节点供应节点：运输的起点，像生产厂商，提供的：运输的起点，像生产厂商，提供的 产品数量是有限的。产品数量是有限的。 2. 2.需求节点：需求节点：运输的终点或目的地，像销售地点运输的终点或目的地，像销售地点 或用户所在地，需求量是一个特定的值。或用户所在地，需求量是一个特定的值。 3. 3.假设：假设：产品不能从一个供应节点运输到另一个产品不能从一个供应节点
4、运输到另一个 供应节点，也不能从一个需求节点运输到另一供应节点，也不能从一个需求节点运输到另一 个需求节点，只能从供应节点运至需求节点。个需求节点，只能从供应节点运至需求节点。 4. 4. 运输问题：运输问题：在满足供应节点的供应量约束和在满足供应节点的供应量约束和 需求节点的需求量约束的条件下，为了使运输需求节点的需求量约束的条件下，为了使运输 成本最低，如何安排运输。成本最低，如何安排运输。 二、运输问题的分类二、运输问题的分类 1 1、供需均衡的运输问题、供需均衡的运输问题 所有供应点的供应量之和等于所有需求点所有供应点的供应量之和等于所有需求点 的的 需求量之和的运输问题。需求量之和的
5、运输问题。 2 2、供需非均衡的运输问题、供需非均衡的运输问题 所有供应点的供应量之和不等于所有需求点所有供应点的供应量之和不等于所有需求点 的需求量之和的运输问题。的需求量之和的运输问题。 需求地区 化肥厂 地区1 地区2 地区3地区4 产量 （万吨 ） 厂11613221750 厂21413191560 厂31920231050 需求量 （万吨） 50703010 运价：万元运价：万元/ /万吨万吨 需求地区 化肥厂 地区1 地区2 地区3地区4 产量 （万吨 ） 厂11613221750 厂21413191580 厂31920231050 需求量 （万吨） 50703010 运价：万元运
6、价：万元/ /万吨万吨 需求地区 化肥厂 地区1 地区2 地区3地区4 产量 （万吨 ） 厂11613221750 厂21413191560 厂31920231050 需求量 （万吨） 60703010 运价：万元运价：万元/ /万吨万吨 三、供需均衡运输问题的建模与求解三、供需均衡运输问题的建模与求解 已知有已知有mm个生产地点个生产地点A A i i , i=1, 2 , , i=1, 2 , , m , m，可供应某可供应某 种物资，其供应量分别是种物资，其供应量分别是a a i i , i=1, 2 , , i=1, 2 , , m , m， 有有n n个销地个销地B B j j ,
7、j=1, 2 , , j=1, 2 , , n , n，其需要量分别为其需要量分别为b bj j， ， j=1, 2 , j=1, 2 , , n , n， 从从A A i i 到到 B B j j 运输单位物资的运费为运输单位物资的运费为c c ij ij （单价）单价） ， 可用一个表格来表示出来。可用一个表格来表示出来。 销地 产地 B1 B2 Bn产量 A1 A2 Am c11 c12 c1n c21 c22 c2n cm1 cm2 cmn a1 a2 am 销量 b1 b2 bn 成本表成本表 对于产销平衡的运输问题，有下面的关系式：对于产销平衡的运输问题，有下面的关系式： n n
8、mm b b j j = = a a i i j=1 i=1j=1 i=1 销地 产地 B1 B2 Bn产量 A1 A2 Am x11 x12 x1n x21 x22 x2n xm1 xm2 xmn a1 a2 am 销量 b1 b2 bn 运量分配表运量分配表 用用x x ij ij 表示从表示从A A i i 到到B B j j 的的运量，在产销平衡的条件下，要运量，在产销平衡的条件下，要 求得总运费最小的调运方案，可求解以下数学模型：求得总运费最小的调运方案，可求解以下数学模型： m nm n Min Min z z = = c c ij ij x xij ij i=1 j=1 i=1
9、j=1 s.t. s.t. mm x x ij ij = = b bj j ， ， j = 1j = 1，2 2，n n i=1 i=1 n n x x ij ij = = a a i i ， i =1i =1，2 2，mm j=1 j=1 x xij ij 0 在这个数学模型中，包含有在这个数学模型中，包含有m m n n个变量，有（个变量，有（ m+nm+n）个约束方程，约束条件中变量的系数比个约束方程，约束条件中变量的系数比 较特殊，不是较特殊，不是1 1就是就是0 0。 例例 5.2.1 5.2.1 海华设备厂均衡运输问题海华设备厂均衡运输问题 海华设备厂下设三个位于不同地点的分厂海华
10、设备厂下设三个位于不同地点的分厂 A A、B B、C C，该三个分厂生产同一种设备，设每该三个分厂生产同一种设备，设每 月的生产能力分别为月的生产能力分别为2020台、台、3030台和台和4040台。海华台。海华 设备厂有四个固定用户，该四个用户下月的设设备厂有四个固定用户，该四个用户下月的设 备需求量分别为备需求量分别为2020台、台、1515台、台、2323台和台和3232台。设台。设 各分厂的生产成本相同，从各分厂至各用户的各分厂的生产成本相同，从各分厂至各用户的 单位设备运输成本如表单位设备运输成本如表4.2.14.2.1所示，所示， 表表5.2.1 5.2.1 海华设备厂运输成本表海
11、华设备厂运输成本表 分厂 名称 运输成本（元/台）月生 产能 力（ 台） 用户1用户2用户3用户4 分厂A7040806020 分厂B701001105030 分厂C80701304040 下月设 备需求 量（台 ） 2015233290 而且各分厂本月末的设备库存量为零。问该厂应而且各分厂本月末的设备库存量为零。问该厂应 如何安排下月的生产与运输，才能在满足四个用如何安排下月的生产与运输，才能在满足四个用 户需求的前提下，使总运输成本最低。户需求的前提下，使总运输成本最低。 解：可用一个网络图来描述解：可用一个网络图来描述 A A B B C C 4 4 3 3 2 2 1 1 7070 4
12、040 8080 6060 7070 100100 110110 5050 8080 7070 130130 4040 2020 3030 4040 2020 1515 2323 3232 总供应量总供应量=20+30+40=90=20+30+40=90（台），（台）， 总需求量总需求量=20+15+23+32=90=20+15+23+32=90（台），（台）， 供应量之和等于需求量之和，供需均衡。供应量之和等于需求量之和，供需均衡。 决策变量是下月各分厂为各用户生产与运输决策变量是下月各分厂为各用户生产与运输 的设备数量。可设：的设备数量。可设： 分厂分厂A A下月为四个用户生产和运输的设备
13、数量下月为四个用户生产和运输的设备数量 分别为分别为A A 1 1 ， A A 2 2 ， A A 3 3 ， A A 4 4 （台）；台）； 分厂分厂B B下月为四个用户生产和运输的设备数量分下月为四个用户生产和运输的设备数量分 别为别为B B 1 1 ， B B 2 2 ， B B 3 3 ， B B 4 4 （台）；台）； 分厂分厂C C下月为四个用户生产和运输的设备数量分下月为四个用户生产和运输的设备数量分 别为别为C C 1 1 ， C C 2 2 ， C C 3 3 ， C C 4 4 （台）。台）。 目标函数是总运输成本最小化，目标函数是总运输成本最小化， 总运输成本总运输成本=
14、 70A= 70A 1 1 +40 A+40 A 2 2 +80 A +80 A 3 3 60 A 60 A 4 4 + + 70B 70B 1 1 +100 B +100 B 2 2 +110 B +110 B 3 3 +50 B +50 B 4 4 + 80C + 80C 1 1 +70 C +70 C 2 2 +130 C +130 C 3 3 +40 C +40 C 4 4 约束条件有两部分，第一部分是需求约束，各约束条件有两部分，第一部分是需求约束，各 用户从各分厂收到的设备总数不得少于它们的用户从各分厂收到的设备总数不得少于它们的 需求量：需求量： A A1 1 + B+ B 1
15、1 + C + C 1 1 =20 =20 A A2 2 + B+ B 2 2 + C + C 2 2 =15=15 A A3 3 + B+ B 3 3 + C + C 3 3 =23 =23 A A4 4 + B+ B 4 4 + C + C 4 4 =32 =32 第二部分是生产能力约束，各分厂生产和运输的第二部分是生产能力约束，各分厂生产和运输的 设备总数不得超过其生产能力：设备总数不得超过其生产能力： A A1 1 + A+ A 2 2 + A + A 3 3 + A + A 4 4 =20 =20 B B 1 1 + B + B 2 2 + B + B 3 3 + B + B 4 4 =30 =30 C C 1 1 + C + C 2 2 + C + C 3 3 + C + C 4 4 =40 =40 最后，还有非负约束：最后，还有非负约束： A A1 1 ，A A 2 2 ， A A 3 3 ， A A 4 4 ，B B 1 1 ， B B 2 2 ， B B 3 3 ， B B 4 4 ， C C 1 1 ， C C 2 2 ， C C 3 3 ， C C 4 4 0 线性规划模型为：线性规
