运输问题(运筹学)选编课件.ppt

《运输问题(运筹学)选编课件.ppt》由会员分享，可在线阅读，更多相关《运输问题(运筹学)选编课件.ppt（61页珍藏版）》请在三一办公上搜索。

1、-1-,第六节 运输问题,Transportation problem,第5章 运输模型,2,问题的提出 运输问题：产地、销地、产量、销量 引例：有A1，A2，A3三座铁矿，每天要把生产的铁矿石运往B1，B2，B3，B4四个炼铁厂。各矿的产量、各厂的销量以及各厂矿间的运价如下表所示。问应如何组织调运才能使运费最少？,一、运输问题的定义,第5章 运输模型,3,(百元/百吨),xij Ai运给Bj的铁矿石数量（百吨）,z 总运费（百元）,调运示意图,A1,A2,A3,B1,B2,B3,B4,5吨,2吨,3吨,2吨,3吨,1吨,4吨,x11,x12,x13,x14,x21,x22,x23,x24,x

2、31,x32,x33,x34,产地,销地,第5章 运输模型,5,(百元/百吨),x11,x12,x13,x14,x21,x22,x23,x24,x31,x32,x33,x34,表式模型,第5章 运输模型,6,数学模型为:min z=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34 x11+x12+x13+x14=5 x21+x22+x23+x24=2 x31+x32+x33+x34=3 x11+x21+x31=2 x12+x22+x32=3 x13+x23+x33=1 x14+x24+x34=4 xij0(i=1,2,3;j

3、=1,2,3,4),s.t.,第5章 运输模型,7,表式模型,产销平衡的运输问题:si=dj 产大于销的运输问题:sidj 产小于销的运输问题:sidj,第5章 运输模型,8,LP式 产销平衡模型,第5章 运输模型,9,LP式 产大于销模型,第5章 运输模型,10,LP式 产小于销模型,第5章 运输模型,11,运输模型有两个特点：(1)它有mn个变量，m+n个约束方程,最大独立方程数：m+n-1(2)其系数阵具有特殊的结构,m=3行,n=4行,A=,1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1,-第3章 运输问题-,-12-,x11 x12 x

4、1n x21 x22 x2n,xm1 xm2 xmn,1 1 1 0 0 0 0 0 00 0 0 1 1 1 0 0 00 0 0 0 0 0 1 1 11 0 0 1 0 0 1 0 00 1 0 0 1 0 0 1 00 0 1 0 0 1 0 0 1,i=1i=2i=mj=1j=2j=n,运输表网络图中的回路,运输表中的闭回路,从运输网络图中一个基应满足的条件，容易得出运输表中一个基必须满足的条件：1、一个基应占表中的m+n-1格；2、构成基的同行同列格子不能构成闭回路；3、一个基在表中所占的m+n-1个格子应包括表的每一行和每一列。运输问题可以用单纯形法求解，但由于其模型的特殊性，也

5、可以用基于单纯形法思想的表上作业法求解。求解的速度要优于单纯形法。,-第3章 运输问题-,-17-,二、表上作业算法求运输问题,表上作业法步骤:初始基本可行解最优性检验改进方案一、确定初始基本可行解1.西北角法2.最小元素法3.Vogel法二、计算非基变量的检验数1.闭回路法2.对偶变量法三、解的改进方法在闭回路内改进。,例2-11 给出运输表及单位运价表如下如下。运用西北角法求初始调运方案。,供应地1的供应量为30，需求地1的需求量为15，在（1，1）上安排运量15。供应地1和需求地1的供应量和需求量分别变为15和0。,需求地4的需求量为75，供应地3的供应量为50，安排（3，4）上的运量为

6、50，供应地3的供应量0，需求地4的需求量25；,供应地4的供应量为25，需求地4的需求量为25，安排（4，4）上的运量25，供应地4的供应量为0，需求地4的需求量为0，供求和需求都得到满足。,用西北角法确定初始可行解方法简单，不会出现回路，而且一般情况下基变量的个数恰为m+n-1个（退化的情况基变量可能少于m+n-1，需通过在相应位置添0的方法处理），而且基变量位于每一行每一列，因而得到的是一个基础可行解。西北角法的缺点是在安排运量时不考虑运价，因而得到的初始解可能离开最优解比较远。以上例子中用西北角法得到的初始解的目标函数值为z=1015+1115+125+1631+99+1050+132

7、5=1777,-第3章 运输问题-,-27-,产地,销地,A1 A2 A3,B1 B2 B3 B4,产地,销地,A1 A2 A3,B1 B2 B3 B4,产地,销地,A1 A2 A3,B1 B2 B3 B4,产量,销量,3 11 3 10 1 9 2 8 7 4 10 5,6,3,4,3,1,3,3 6 5 6,7 4 9,3 6 5 6,7 4 9,产量,销量,3,6,3,5,2,1,(1),(2),(1),(-1),(10),(12),z=c11-c13+c23-c21=1=11,z=-c12+c14-c34+c33=2=12,(0),(2),(2),(9),(1),(12),单位运价表,

8、产销平衡表,（2）最小元素法,-第3章 运输问题-,-28-,产地,销地,A1 A2 A3,B1 B2 B3 B4,7 4 9,产量,销量,3 6 5 6,6,3,5,2,1,3,产地,销地,A1 A2 A3,B1 B2 B3 B4,行两最小元素之差,列两最小元素之差,3 11 3 10 1 9 2 8 7 4 10 5,0 1 1,2 5 1 3,0 1 2,2-1 3,0 1-,2-1 2,7 6-,-1 2,Vogel法:,产销平衡表,2.计算非基变量的检验数zij-cij（1）闭回路法对于非基变量xij，检验数为其中向量Yij可由该非基变量与基变量形成的闭回路来确定，这个闭回路转角处的

9、基变量对应于y=1，其余的基变量对应于y=0。这样就等于转角处基变量对应的cij依次加减的值。,在上例中，用西北角法得到初始基础可行解，计算各非基变量的检验数zij-cij,非基变量（1，3）相应的闭回路为,+6,因此x13的检验数z13-c13=(c12-c22+c23）-c13=(11-12+16)-9=+6。非基变量（1，4）相应的闭回路为,-7,-2,+1,将其他检验数填入运输表，用“”表示。,-7,+5,+6,-2,+10,+8,+1,+1,+3,第5章 运输模型,36,表上作业法,最优性检验 一、位势法(对偶变量法)在初始方案表中,可将基变量所在格的运价cij分解为两部分 ui+v

10、j=cij 其中ui代表产地Ai所在行的行位势量，vj代表销地Bj所在列的列位势量，cij为画圈数字所在格的运价。所有ui，vj的值确定以后，可以证明，ij可按下式计算：ij=cij ui vj 基变量对应的检验数显然全都为0，因此，只需计算非基变量的检验数。这种计算检验数的方法就是位势法。,（2）对偶变量法,设与前m个约束对应的对偶变量为u1，u2，um，与后n个约束对应的对偶变量为v1，v2，vn。则对偶问题为：max y=s1u1+s2u2+smum+d1v1+d2v2+dnvns.t.u1+v1c11 u1+v2c12 um+vncmn(i=1,2,m；j=1,2,n（u1，u2，um

11、，v1，v2，vn无约束）,以上对偶问题，可以简写成：ui+vjcij(i=1,2,m；j=1,2,n)ui，vj：unr 对偶问题中有m+n个变量，mn个约束。,对于运输问题的一个基B，如果能够求出相应的对偶变量 就可以计算非基变量xij的检验数zij-cij：对于一个确定的基，如果xij是基变量，则有由于基变量一共有m+n-1个，因此对偶问题一共有m+n-1个等式约束，只要先确定一个对偶变量的值，就可以由m+n-1个等式约束确定其余m+n-1个对偶变量的值。求出ui、vj的值以后，就可以进一步计算各非基变量的检验数。,-第3章 运输问题-,-40-,产地,销地,A1A2 A3,B1 B1

12、B3 B4,3 10 8 4 5,位势法:,(3),(9),(7),(-2),(1),(-2),2.计算行位势和列位势；令u1=0，则依cij=ui+vj 计算各ui和vj,3.计算空格处位势；ij=ui+vj,行位势,列位势,0,3,-2,-5,3,9,10,1.数字格处上添上对应的运价；,销地,A1 A2 A3,B1 B1 B3 B4,3 11 3 10 1 9 2 8 7 4 10 5,产地,单位运价表,位势表:,产地,销地,A1 A2 A3,7 4 9,销量,3 6 5 6,6,3,5,2,1,3,产销平衡表,B1 B1 B3 B4,-第3章 运输问题-,-41-,产地,销地,A1 A

13、2 A3,B1 B1 B3 B4,74 9,产量,销量,3 6 5 6,6,3,5,2,1,3,(0),(2),(2),(9),(1),(12),检验数表,4.计算空格处检验数：ij=cij-ij,3.解的改进-闭回路法（1）确定进基变量 检验数为正数的非基变量（2）确定离基变量,第5章 运输模型,43,表上作业法,调整非优方案的一般步骤与规则 1进基变量的确定规则 按 min ijij 0=lk 确定xlk进基。若有多个lk同时最小，则选其中最小运价minclk 所对应的那个 xlk进基;又若有多个这样的clk同时最小，则从中任选一个clk对应xlk的 进基。,进而画出进基变量xlk的闭回路

14、及奇偶点。,2离基变量的确定规则 在进基变量xlk的闭回路上，按,确定xpq离基，同时也就确定xpq的值t为调整量。若有多个奇点 xpq 的值同时最小，则选其中最大运价 maxcpq 所对应的那个xpq离基；又若有多个这样的cpq同时最大，则从中任选一个cpq 对应的xpq离基。,第5章 运输模型,44,表上作业法,3非最优方案的调整规则,不在进基变量闭回路上的xij的值不变。,在进基变量的闭回路上：,-第3章 运输问题-,-45-,3.3 产销不平衡运输问题及其应用,Min z=cij xij,n,i=1,j=1,m,一、产销不平衡问题,1产销,Min z=cijxij+0 xi,n+1,n

15、,i=1,j=1,m,i=1,m,-第3章 运输问题-,-46-,产地,销地,A1 A2 Am,B1B2Bn,C11C12C1n C21C22C2n Cm1Cm2Cmn,Bn+1,产销问题单位运价表,销量,产量,b1b2bn,a1 a2 am,aibj,-第3章 运输问题-,-47-,Min z=cij xij,n,i=1,j=1,m,2销产,Min z=cijxij+0 xm+1,j,n,i=1,j=1,m,j=1,n,-第3章 运输问题-,-48-,产地,销地,A1 A2 Am,B1B2Bn,C11C12C1n C21C22C2n Cm1Cm2Cmn,Am+1,销产问题单位运价表,0 0

16、0,销量,产量,b1b2bn,a1 a2 am,bjai,第5章 运输模型,49,表上作业法,产销不平衡问题的解法,第5章 运输模型,50,表上作业法,第5章 运输模型,51,运输模型的应用,短缺资源的分配问题 例4 自来水分配问题,160,110,6 0,210,160,额 外,基 本,2 0,0,5 0,第5章 运输模型,52,5.3 运输模型的应用,D(虚),50,210,甲,甲1,甲2,需 求 量,30,20,乙,70,丙,30,丁,丁1,丁2,10,50,160140190,160140190,M,0,130130200,M,220190230,0,170150M,M,170150M

17、,0,自来水分配问题的规范表式运输模型,第5章 运输模型,53,运输模型的应用,-第3章 运输问题-,-54-,例一：某工厂按合同规定必须于当年的每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂的生产能力及生产每台柴油机的成本如表示。又如果生产出来的柴油机当季不交货，每台每积压一个季度需要存储维护费用0.15万元。要求在完成合同的情况下，做出使全年生产费用最小的决策。,季度,生产能力,(台),单位成本,(万元/台),25353010,10.8 11.1 11.0 11.3,4、应用运输问题模型的其他实例,-第3章 运输问题-,-55-,模型：,设 xij第i季度生产，用于第

18、j季度交货的数量。,obj.min z=cij xij,i=1j=1,4 4,x11+x12+x13+x1425,x22+x23+x2435,x33+x3430,x4410,x11=10,x12+x22=15,x13+x23+x33=25,x14+x24+x34+x44=20,xij 0,(i=1,4;j=1,4),供应：,需求：,-第3章 运输问题-,-56-,单位费用表：,10.8 10.95 11.10 11.25,M 11.10 11.25 11.40,M M 11.00 11.15,M M M 11.30,单位：万元,供应,需求,-第3章 运输问题-,-57-,例二：,某餐馆承办宴会

19、，每晚连续举行，共举行五次。宴会上需用特殊的餐巾，根据参加的人数，预计每晚的需要量为：第一天1000条，第二天700条，第三天800条，第四天1200条，第五天1500条，五天之后，所有的餐巾作废。宴会中用过的餐巾经过洗涤处理后可以重复使用，这样可以降低使用成本。已知每条新餐巾需要1元的费用，送洗时可选择两种方式：快洗仅需要一天时间，每条洗涤费用为0.2元，慢洗需要两天时间，每条洗涤费用0.1元。问：如何安排，可使总费用最低？,-第3章 运输问题-,-58-,建立模型：,设 xj第j天使用新毛巾的数量；yij第i天送第j天使用快洗 餐巾的数量；zij第i天送第j天使用慢洗餐巾的数量；,第一天：

20、x1=1000,第二天：x2+y12=700,第三天：x3+z13+y23=800,第四天：x4+z14+z24+y34=1200,第五天：x5+z15+z25+z35+y45=1500,需求约束,供应约束,新购餐巾：x1+x2+x3+x4+x55200,第一天送洗：y12+z13+z14+z151000,第二天送洗：y23+z24+z25700,第三天送洗：y34+z35800,第四天送洗：y451200,xj0，yij0，zij0，（i=1,4；j=1,5）,Min z=xj+0.2yij+0.1zij,-第3章 运输问题-,-59-,新 购 第一天第二天第三天第四天,111110,M0.20.10.10.10,MM0.20.10.10,MMM0.20.10,供应,需求,产量,销 量,5200 1000 8001200,MMM0.20.10,1000700800120015003700,产销平衡表,人有了知识，就会具备各种分析能力，明辨是非的能力。所以我们要勤恳读书，广泛阅读，古人说“书中自有黄金屋。”通过阅读科技书籍，我们能丰富知识，培养逻辑思维能力；通过阅读文学作品，我们能提高文学鉴赏水平，培养文学情趣；通过阅读报刊，我们能增长见识，扩大自己的知识面。有许多书籍还能培养我们的道德情操，给我们巨大的精神力量，鼓舞我们前进。,