高速公路运输问题.ppt

《高速公路运输问题.ppt》由会员分享，可在线阅读，更多相关《高速公路运输问题.ppt（48页珍藏版）》请在优知文库上搜索。

1、1.9 运输问题运输问题1.9.1 数学模型数学模型已知：某种物资有产地已知：某种物资有产地 Ai(i=1 m),产量产量ai 销地销地 Bj(j=1 n),销量销量 bj 从从i 地到地到 j 地的单位产品运价地的单位产品运价Cij 在产销平衡条件下，如何调运使总运费最小在产销平衡条件下，如何调运使总运费最小数学模型：数学模型：minZ=Cij xijj=1i=1nm xij=ai (i=1 m)j=1n xij=bj (j=1 n)i=1mxij 0()设设xij为从为从i 地到地到 j 地的物资运量地的物资运量(1)、设、设 ai=bj=mni=1j=1xi j=ai bj 为为()解解

2、稀疏矩阵稀疏矩阵P11P12 P1n P21P22 P2n Pm1Pm2 Pmm 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1(2)、A=r(A)=m+n-11)r(A)m+nB 0B=P11P12 P1n P21P31 Pn1 1 1 1 1 1 1 1 1 1 2)1.9.2 表上作业法表上作业法产地产地 B1 B2 B3 产量产量 A1 3 5 5 20 A2 1 3 2 40 A3 2 3 4 30 销量销量 60 20 10(1)、初始基本可行解、初始基本可行解 最小元素法最小元素法 西北角法西北角法 vogol法法Z=210 B1 B2 B3 A1 A2

3、A33125335242040306020102040101010 最小元素法步骤：最小元素法步骤：1)CPQ=min(Cij)2)令令XPQ=min(aP,bQ)3)若若 aP bQ，划去第，划去第Q列且列且aP aP-bQ 若若 bQ aP，划去第，划去第P行且行且bQ bQ-aP返回返回 1)注意：注意：1)最小运价有多个时，可任选一个。最小运价有多个时，可任选一个。2)保证数字格为保证数字格为m+n-1个。个。定义：互不相同的定义：互不相同的2k个变量个变量X11 ,X21 ,X22 ,Xkk ,X1k组成一个闭回路。组成一个闭回路。定理定理1：最小元素法方案中，数字格不含闭：最小元素

4、法方案中，数字格不含闭回路。回路。定理定理2：Xij 是可行解，则它是基本可行解是可行解，则它是基本可行解 Xij 的正分量不含闭回路。的正分量不含闭回路。西北角法：西北角法：B1 B2 B3 A1 A2 A3312533524204030602010 040202010 Vogol法：法：1)计算各行各列中最小与次小计算各行各列中最小与次小Cij的差。的差。2)选差最大的行选差最大的行(列列)按按Cij最小填写。最小填写。B1 B2 B3 行行 差差A1 A2A3 60 20 10 1 0 2列列差差1 01 0204030312533524211112122030102010(2)检验是否

5、最优？检验是否最优？闭回路法闭回路法 位势法位势法 闭回路法闭回路法定理定理3：每个空格有唯一一条闭回路：每个空格有唯一一条闭回路(其余拐其余拐点为数字格点为数字格)X11X31X12X32101020X11从从0 1，Z=C11-C12+C32-C31 =3-5+3-2 =-10定理定理4：调整后方案仍为基本可行解：调整后方案仍为基本可行解定义：将定义：将(偶次拐点运价和奇次拐点运价和偶次拐点运价和奇次拐点运价和)记为记为 ij，称，称 ij为检验数。为检验数。11=(3+3)-(5+2)=-10定理定理5：全部：全部 ij 0时，时，Xij 为最优解。为最优解。(3)、方案调整、方案调整1

6、)求出求出 xPQ闭回路，闭回路，xPQ换入。换入。2)调整量调整量 =min 奇拐点处运量奇拐点处运量 ，xst xst换出。换出。3)奇拐点运量奇拐点运量 ，偶拐点运量，偶拐点运量 。得新基本可行解转得新基本可行解转(2)。B1 B2 B3 A1 A2 A33125335242040306020102040101010 B1 B2 B3 A1 A2 A33125335242040306020101040102010 23=-10，13=10，22=10，33=10最优解，最优解，Zmin=190(2)位势法位势法1)()式的对偶规划式的对偶规划 max =ai ui+bj vji=1mj=

7、1n(D)ui+vj Cij (i=1m)(j=1n)其中其中ui ,vj分别称为对应于发点分别称为对应于发点 i,收点收点 j 的位的位势。势。定理定理6：Xij 为为()的可行解，的可行解，(ui ,vj)为为(D)的的可行解，若满足可行解，若满足Xij(Cij-ui-vj)=0,则则Xij 为为()的最优解，的最优解，(ui ,vj)为为(D)的最优解。的最优解。已知已知()的可行解的可行解Xij,如存在一组如存在一组 ui ,vj ,满足满足Xij0时时，ui+vj=Cij Xij=0时时，ui+vj Cij 2)位势法基本思想：位势法基本思想：则则 ui ,vj 为为(D)的可行解的

8、可行解,Xij 为为()的最优解。的最优解。由由 m+n-1个方程，个方程，m+n个个(ui ,vj)，再检查，再检查ui ,vj 是否满足是否满足。3)位势法步骤：已知基本可行解位势法步骤：已知基本可行解Xij 对基变量对基变量Xij，解方程，解方程 ui+vj=Cij，得到，得到 ui ,vj 。对非基变量对非基变量Xij，计算，计算 ij=Cij-ui-vj，若，若 ij 全全 0，停。否则，计算停。否则，计算max ij =PQ ij0转转(3)方案调整。方案调整。B1 B2 B3 A1 A2 A331253352420403060201020401010uivj01011142 B1

9、 B2 B3 A1 A2 A331253352420403060201020401010uivj01011142-1 1 0 1u1+v2=C12=5u1+v3=C13=5u2+v1=C21=1u3+v1=C31=2u3+v2=C32=3注：闭回路法的检验数同于单纯形法的检验数注：闭回路法的检验数同于单纯形法的检验数 11=C11+C32-C12-C31 =C11+(u3+v2)-(u1+v2)-(u3+v1)=C11-u1-v1 所以所以(ui ,vj)可以不同，但不影响可以不同，但不影响 ij 1.9.3 产销不平衡的运输问题产销不平衡的运输问题(1)、产大于销、产大于销minZ=Cij

10、xijj=1i=1nm xij ai (i=1 m)j=1n xij=bj (j=1 n)j=1mxij 0增加松弛变量增加松弛变量xi n+1(i=1 m),Ai 的库存量，销的库存量，销地地 Bn+1。minZ=Cij xijj=1i=1n+1m xij=ai (i=1 m)j=1n+1 xij=bj (j=1 n+1)i=1mxij 0例：例：B1 B2 B3 B4 产量产量 A1 2 11 3 4 7 A2 10 3 5 9 5 A3 7 8 1 2 7销量销量 2 3 4 6 解：解：B1 B2 B3A1 A2A3 210711383512572B4B5233444920002463

11、7产量产量销量销量3 B1 B2 B3A1 A2A3 210711383512572B4B523344492000246337ui220vj0011-2 8 8 7 7 0 2 5 2minZ=35(2)、销大于产、销大于产例：例：A 16 13 22 17 50B 14 13 19 15 60C 19 20 23 M 50 最低需求最低需求最高需求最高需求30 70 0 1050 70 30 不限不限解：解：A B 1614191614191313206050202219231715M50DC”50501030702030M102005020M30010M 01715M050 A B 191

12、913132060501550DC50501030702030500150302020030103020供给供给 :50 :70 :0 :40总运费：总运费：2460例例1：货船调度问题：货船调度问题 里斯本里斯本 雅典雅典 拉戈斯拉戈斯 德班德班 大阪大阪 旧金山旧金山 圣托马斯圣托马斯 净吐量净吐量鹿特丹鹿特丹奥德萨奥德萨孟买孟买新加坡新加坡悉尼悉尼纽约纽约普拉特普拉特净吞量净吞量 1.10.465.27.210.63.05.30.780.70.960.290.150.150.120.030.070.020.150.353.75.79.04.87.18.19.012.74.94.34.14

13、.96.24.65.42.94.68.713.29.87.36.45.28.78.310.28.81.44.61.241.55 0.12 0.100.17 0.020.350.460.960.290.020.241.280.301.9.4 应用举例应用举例例例2 供应问题：某企业按合同，每季度末供应问题：某企业按合同，每季度末提供提供10，15，25，20台同一规格柴油机。台同一规格柴油机。季度季度 生产能力生产能力(台台)单位成本单位成本(千元千元)1 25 10.8 2 35 11.1 3 30 11.0 4 10 11.3每季积压费每季积压费0.15千元千元/台，求：完成合同条台，求：完

14、成合同条件下，全年最小费用方案。件下，全年最小费用方案。解：解：minZ=Cij xijj=1i=144x11=10 x12+x22=15x13+x23+x33=25x14+x24+x34+x44=20 x11+x12+x13+x14 25 x22+x23+x24 35 x33+x34 30 x44 10 xij 0 1 2 3 4 5 1 10.8 10.95 11.10 11.25 252 11.10 11.25 11.40 353 11.00 11.15 304 11.30 10 10 15 25 20 1 2 3 4 5 1 10.8 10.95 11.10 11.25 2 11.10

15、 11.25 11.40 3 11.00 11.15 4 11.30 10 15 25 20 MMMMMM00003025353010例例3：作物布局问题：作物布局问题 B1 B2 B3A1 700 500 480 100A2 850 700 600 400A3 400 300 500 400 300 200 400 土地土地作物作物亩数亩数亩数亩数例例4：转口运输问题：转口运输问题 D1 D2 D3 D4 S1 S2 S3S1S2S3D1D2D3D4 5 (4)3 210 (8)4 7 9 9 8 4 0 2 1 5 (1)0 4 5 3 2 0 50 1 3 23 0 2 32 3 0 1

16、4 1 1 0 5 9 9 0 4 6 7 0 3 4 9 0 4 7 3 0 1 6 2 6 0 0 0解：解：D1 D2 D3 D4 S1 S2 S3S1S2S3D1D2D3D416 21 17 21 15 15 15172536151515912151520202015151515最优解：最优解：5261556172536S3D1D2D3D4S1S2例例5：多维运输问题：多维运输问题M个工厂个工厂 个批发站个批发站 n个商店个商店求最优分配方案，使总运费最小求最优分配方案，使总运费最小Pi :工厂工厂i 生产能力生产能力 (i=1 m)j:批发站批发站 j最大容量最大容量 (j=1 )Dk:商店商店k需求需求量量 (k=1 n)Sij:工厂工厂i 到批发站到批发站 j的单位商品运费的单位商品运费tjk:批发站批发站 j到商店到商店k的单位商品运费的单位商品运费Cijk=Sij+tjk设设xijk为工厂为工厂i 经批发站经批发站 j到商店到商店k的商品数量的商品数量minZ=Cijk xijkjik xijk Pi (i=1 m)jk xijk j (j=1 )ik xijk=Dk