第三章运输规划-PowerPointPresentat

1、本章重点本章重点第三章第三章 货物货物运输方案的优化方法运输方案的优化方法 产销平衡运输问题的数学模型产销平衡运输问题的数学模型 产销平衡运输问题的产销平衡运输问题的表上作业法表上作业法 本章内容本章内容运输问题的数学模型运输问题的数学模型表上作业法表上作业法运输问题的扩展运输问题的扩展1 1 货物运输问题货物运输问题bnb2b1需求量需求量BnB2B1 需方需方供方供方AmA2A1ama2a1供应量供应量nijjm1iiba供需平衡供需平衡运价运价bnb2b1需求量需求量BnB2B1 需方需方供方供方AmA2A1ama2a1供应量供应量nijjm1iibacmncm2cm1c2nc22c21

2、c1nc12c11如何建立供需搭配，使总的运输费用最小？如何建立供需搭配，使总的运输费用最小？供供需需 平平衡衡表表数学模型数学模型设从设从Ai到到Bj的物资运量为的物资运量为xij ， n1jm1iijijxczmin产销平衡产销平衡运输问题的数学模型。运输问题的数学模型。n1jjm1iibaAi的产品全部的产品全部供应出去供应出去m, 2 , 1iaxin1jijn, 2 , 1jbxjm1iijBj的需求全的需求全部得到满足部得到满足n, 2 , 1j ;m, 2 , 1i0 xijm mn n 个变量，个变量，m+nm+n 个约束，独立的约束方程个约束，独立的约束方程m+nm+n- -

3、1 1 个，每个变量的系数是有个，每个变量的系数是有 2 2 个个 1 1、其它元、其它元素均为素均为 0 0 的向量。的向量。 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 mnm2m12n222111xxxxx xx xxn11211mn销销 产产 B1 B2 Bn 产产量量 c11 c12 c1n A1 x11 x12 x1n a1 c21 c22 c2n A2 x21 x22 x2n a2 cm1 cm2 cmn Am xm1 xm2 xmn am 销销量量 b1 b1 bn 平衡表、运价表和二为一：平衡表、运价表和二为一：销产B1B2Bn产量A1x11x12x1na

4、1A2x21x22x2na2Amxm1xm2xmnam销量b1b1bn约束条件或解可用产销平衡表表示约束条件或解可用产销平衡表表示: minjijijxczmin11 )n,j(bx)m,i (axmijijnjiij1 1 11 )n,j;m,i (xij11 0 uivj无约束无约束 （i=1,2, ,m;j=1,2, ,n)uivj设设u ui i, ,v vj j为对偶变量，对偶问题模型为为对偶变量，对偶问题模型为nijjjm1iiivbuawmaxijjicvum个个 n个个2 2 初始调运方案的编制初始调运方案的编制计算步骤：计算步骤：(1) 找出初始调运方案。即在找出初始调运方案

5、。即在(mn)产销平衡表产销平衡表上给出上给出m+n- -1个数字格。个数字格。(最小元素法或差值法）最小元素法或差值法）(2) 求检验数。（闭回路法或位势法）求检验数。（闭回路法或位势法） 判别是否判别是否达到最优解。如已是最优解，则停止计算，否则达到最优解。如已是最优解，则停止计算，否则转到下一步。转到下一步。(3) 对方案进行改善，找出新的调运方案。（表上对方案进行改善，找出新的调运方案。（表上闭回路法调整）闭回路法调整）确定确定m+n-1个基变量个基变量 (4) (4) 重复（重复（2 2）、（）、（3 3），直到求得最优调运方案。），直到求得最优调运方案。空格空格 例例 运输问题供需

6、平衡表和运价表如下，求最优调运输问题供需平衡表和运价表如下，求最优调运方案。运方案。 供 需B1B2B3B4供应量（T）A13113107A219284A3741059需求量（T）3656最小元素法最小元素法销销 产产 B1 B2 B3 B4 产产量量 3 11 3 10 A1 7 1 9 2 8 A2 4 7 4 10 5 A3 9 销销量量 3 6 5 6 314 633Z=4Z=43+33+310+310+31+11+12+62+64+34+35=865=86该方案总运费：该方案总运费：. 差额法差额法 分别计算各行、各列次小、最小运价的差额，分别计算各行、各列次小、最小运价的差额，优先

7、在最大差额处进行供需搭配。优先在最大差额处进行供需搭配。销 地产 地B1B2B3B4行 差 额A1A2A3317119432101085011列 差 额2513步骤：步骤：10 计算未划去行、列的差额；计算未划去行、列的差额； 20 找出最大差额对应的最小元素找出最大差额对应的最小元素cij进行供需分配；进行供需分配；30 在未被划去的行、列重新计算差额。在未被划去的行、列重新计算差额。 销销产产B1B2B3B4供量供量A17A24A39销量销量 3656 6B1B2B3B4行差额行差额A13113100A219281A3741051列差额列差额2513 销销产产B1B2B3B4供量供量A17

8、A24A3 9销量销量 3656 6B1B2B3B4行差额行差额A13113100A219281A3741052列差额列差额213 3 销销产产B1B2B3B4供量供量A17A24A3 9销量销量 3656 6B1B2B3B4行差额行差额A13113100A219281A374105列差额列差额212 3 3 销销产产B1B2B3B4供量供量A17A24A3 39销量销量 3656 6B1B2B3B4差额差额A13113107A219286A374105差额差额12 3 5 1 23 调运方案的改进调运方案的改进 闭回路法闭回路法 闭回路：从空格出发顺时针闭回路：从空格出发顺时针(或逆时针或逆

9、时针)画水画水(或垂直或垂直)直线直线，遇到填有运量的方格，遇到填有运量的方格可转可转90，然后继续前进，直到到达出，然后继续前进，直到到达出发的空格所形成的闭合回路。发的空格所形成的闭合回路。调运方案的任意空格存在唯一闭回路。调运方案的任意空格存在唯一闭回路。 销销产产B1B2B3B4供量供量A1 5 27A23 14A3 6 39销量销量 3656差额法方案差额法方案一、最优调运方案的判定一、最优调运方案的判定 闭回路法闭回路法 闭回路：从空格出发顺时针闭回路：从空格出发顺时针(或逆时针或逆时针)画水平画水平(或或垂直垂直)直线，遇到填有运量的方格直线，遇到填有运量的方格可转可转90，然后

10、继续，然后继续前进，直到到达出发的空格所形成的闭合回路。前进，直到到达出发的空格所形成的闭合回路。调运方案的任意空格存在唯一闭回路。调运方案的任意空格存在唯一闭回路。 销销产产B1B2B3B4供量供量A1 5 27A23 14A3 6 39销量销量 3656销销 产产 B1 B2 B3 B4 产产量量 3 11 3 10 A1 7 1 9 2 8 A2 4 7 4 10 5 A3 9 销销量量 3 6 5 6 314 633最小元素法最小元素法+-+- x11为换入变量，为换入变量，x11增加增加1，运费的变化为，运费的变化为3- -1+2- -3=1。这个变化就是。这个变化就是x11的检验数

11、，故的检验数，故 11=1 基变量的检验数为零基变量的检验数为零( 基变量基变量xij)， ij=cij-(ui+vj), ui,vj自由变量自由变量. 位势法位势法标准型运输问题的对偶问题是：标准型运输问题的对偶问题是： njjjmiiivbuamax11 )n,j;m,i (cvuijji11 XBXNXS0CN-CBB-1N-CBB-1-YS1-YS2-Y检验数检验数 得得m+n- -1个方程，令某个个方程，令某个ui ( 或或vj)=0，可解出可解出m+n个个ui 和和vj；由此得非基变量的检验数。由此得非基变量的检验数。对偶变量值等于原问题对偶变量值等于原问题的检验数的检验数松弛变量

12、松弛变量销销 产产 B1 B2 B3 B4 产产量量 3 11 3 10 A1 7 1 9 2 8 A2 4 7 4 10 5 A3 9 销销量量 3 6 5 6 314 633位势法位势法 令令v1=0, 由由c21=3= u2 +v1，得得 u2=3B1B2B3B4ui311310A11928A274105A3vj 0 1 1 2B1B2B3B4ui311310A11928A274105A3vj 0 1 1 28-3 7位势表位势表2989-3-2)vu(cjiijij检验数检验数B1B2B3B4ui311310A11928A274105A3vj 0 1 1 28-3 7检验数表检验数表1

13、21-11012 24=-10，当前方案，当前方案 不是最优方案。不是最优方案。二、二、 调运方案的调整调运方案的调整pqijj , i)(min 0 xpq为换入变量为换入变量 =min1，3=1 从从( (p,q)p,q)空格开始画闭回路，其它转角点都是空格开始画闭回路，其它转角点都是填有运量的方格，并从填有运量的方格，并从( (p,q)p,q)空格开始给闭回路上空格开始给闭回路上的点按的点按+1+1，-1-1，+1+1，-1-1编号，编号，-1-1格的最小运量格的最小运量为为调整量。调整量。换出变量换出变量销销地地 产产地地 B1 B2 B3 B4 产产量量 A1 A2 A3 3 6 4(+1) 1(- -1) 3(- -1) (+1) 3 7 4