《《运输问题》PPT课件》由会员分享，可在线阅读，更多相关《《运输问题》PPT课件（57页珍藏版）》请在金锄头文库上搜索。
1、运筹学运筹学OPERATIONAL RESEARCH第三章第三章 运输问题运输问题1课件第一节第一节 运输问题及其数学模型运输问题及其数学模型一、运输问题的典型形式及其数学模型一、运输问题的典型形式及其数学模型1.引例引例2课件求最小运费的运输方案求最小运费的运输方案 销地销地产地产地B1B2B3产量产量A1645300A2655200销量销量1501502003课件minZ = 6x11 + 4x12+5x13+6x21 +5x22 +5x23x11 +x12+x13 = = 300x21+x22+x23 = = 200x11 +x21 = 150x12 +x22 = 150x13 +x23
2、 = 200 xij 04课件A1AmB1B2Bna1cijA2a2ambnb2b1求最小运费的运输方案求最小运费的运输方案2. 典型的运输问题：典型的运输问题：5课件 销地销地产地产地B1B2Bn产量产量A1a1A2a2Amam销量销量b1b2bnc11c12cm1c21c22c2nc1ncmncm26课件 销地销地产地产地B1B2Bn产量产量A1x11x12x1na1A2x21x22x2na2Amxm1xm2xmnam销量销量b1b2bnc11c12cm1c21c22c2nc1ncmncm27课件minZ = 6x11 + 4x12+5x13+6x21 +5x22 +5x23x11 +x1
3、2+x13 = = 300x21+x22+x23 = = 200x11 +x21 = 150x12 +x22 = 150x13 +x23 = 200 xij 03. 运输问题的数学模型运输问题的数学模型8课件i=1,2j =1, 2, 3xij 09课件i=1,2,mj =1, 2, ,nxij 0典型运输问题的数学模型典型运输问题的数学模型10课件二、运输问题数学模型的特点：二、运输问题数学模型的特点：1.运输问题一定有最优解；运输问题一定有最优解；2.运输问题约束条件的系数矩阵：运输问题约束条件的系数矩阵：x11 +x12+x13 = = 300 x21+x22+x23 = = 200x1
4、1 + x21 = 150 x12 +x22 = 150 x13 +x23 = 200 xij 011课件x11 x12 x13 x21 x22 x23 1 1 1 1 1 11 1 1 1 1 12个个3个个12课件x11 +x12+ +x1n = =a1 x21+x22+ +x2n = =a2 xm1+xm2+ +xmn = =amx11 + x21 + xm1 =b1 x12 +x22 + xm2 =b2 x1n +x2n + xmn=bn xij 013课件x11 x12 x1n x21 x22 x2n xm1 xm2 xmn 1 1 1 1 1 1 1 1 11 1 1 1 1 1
5、1 1 1mn14课件系数矩阵的特点：系数矩阵的特点： （1）约束条件的系数矩阵的元素只有两个：）约束条件的系数矩阵的元素只有两个：0、1。 （2）元素）元素 xij 对应于每一个变量在前对应于每一个变量在前m个约个约束方程中束方程中(第第i个方程中个方程中)出现一次，在后出现一次，在后n个个约束方程中（约束方程中（第第m+j 个方程中个方程中）也出现一次。）也出现一次。 （3）产销平衡问题为）产销平衡问题为等式等式约束。约束。 （4）产销平衡问题中各产地产量之和与各销）产销平衡问题中各产地产量之和与各销售地点的销量之和相等。售地点的销量之和相等。15课件3. 运输问题基变量的个数：运输问题基
6、变量的个数： m+n-1个个16课件第二节第二节 表上作业法表上作业法一、表上作业法的基本思想和步骤：一、表上作业法的基本思想和步骤：1.基本思想：同基本思想：同单纯形法单纯形法的基本思想的基本思想基本可行解基本可行解是否为最优解是否为最优解换基换基结束结束YN17课件2. 表上作业法的步骤表上作业法的步骤（1）寻找初始基可行解；）寻找初始基可行解； 最小元素法、西北角法、沃格尔法最小元素法、西北角法、沃格尔法（2）求出非基变量检验数（空格检验数）求出非基变量检验数（空格检验数），判断是否为最优解；，判断是否为最优解；闭回路法、位势法闭回路法、位势法（3）换基改进，找到新的基可行解）换基改进，
7、找到新的基可行解闭回路调整法闭回路调整法（4 ）重复（）重复（2）（）（3）18课件二、确定初始基可行解二、确定初始基可行解（一）最小元素法：（一）最小元素法：19课件 销地销地产地产地B1B2B3B4产量产量A116A210A322销量销量8141214484125210391146811求运费最小的运输方案。求运费最小的运输方案。例题例题 （P82例例1）20课件412521039114681102 销地销地产地产地B1B2B3B4产量产量A110616A28210A314822销量销量81412144800600621课件4125210391146811 销地销地产地产地B1B2B3B4
8、产量产量A116A210A322销量销量814121448（二）西北角法（二）西北角法22课件4125210391146811 销地销地产地产地B1B2B3B4产量产量A18816A26410A381422销量销量814121448（二）西北角法（二）西北角法23课件（三）沃格尔法（三）沃格尔法伏格尔法思路：伏格尔法思路：一产地的产品假如不能按最小运费就近供应，一产地的产品假如不能按最小运费就近供应，就考虑次小运费，这就有一个差额。差额越就考虑次小运费，这就有一个差额。差额越大，说明不能按最小运费调运时，运费增加大，说明不能按最小运费调运时，运费增加越多。因而，对差额最大处，就应当采用最越多。
9、因而，对差额最大处，就应当采用最小运费调运小运费调运24课件罚数罚数=次小费用次小费用-最小费用最小费用1、在运价表中分别计算出各行、列的行罚、在运价表中分别计算出各行、列的行罚数和列罚数，并填入该表的最右列和最下数和列罚数，并填入该表的最右列和最下行。行。2、从行或列差额中选出最大者，选择它所、从行或列差额中选出最大者，选择它所在行或列的最小元素。按类似于最小元素在行或列的最小元素。按类似于最小元素法优先供应，划去相应的行或列。法优先供应，划去相应的行或列。3、对表中未划去的元素重复、对表中未划去的元素重复1，2步，直至步，直至所有的行和列被划掉为止。所有的行和列被划掉为止。沃格尔法基本步骤
10、沃格尔法基本步骤：25课件4125210391146811 销地销地产地产地B1B2B3B4产量产量行罚行罚数数A1124160A282101A3148221销量销量814121448列罚数列罚数251326课件三、最优解的判别三、最优解的判别(一一)闭回路法闭回路法 闭回路：从空格出发，遇到数字格闭回路：从空格出发，遇到数字格可以旋转可以旋转90度，最后回到空格所构成的度，最后回到空格所构成的回路。回路。思路：计算空格（非基变量）思路：计算空格（非基变量） 检验数检验数求空格检验数有两种方法求空格检验数有两种方法27课件4125210391146811 销地销地产地产地B1B2B3B4产量产
11、量A110616A28210A314822销量销量81412144811=4-4+3-2=1 12=12-11+6-5=222=10-3+4-11+6-5=1 24=9-11+4-3=-131=8-2+3-4+11-6=10 33=11-6+11-4=1228课件（1） 每一空格有且仅有一条闭回路；每一空格有且仅有一条闭回路；（2） 不允许由全部顶点是数字格构不允许由全部顶点是数字格构成的闭回路。成的闭回路。注：注：29课件x11 +x12+ +x1n = =a1 x21+x22+ +x2n = =a2 xm1+xm2+ +xmn = =amx11 + x21 + xm1 =b1 x12 +x
12、22 + xm2 =b2 x1n +x2n + xmn=bn xij 0minZ = c11x11 + c12x12+ +c1nx1n + +cm1xm1 +cm2xm2 + +cmnxmn(二二)对偶变量法（位势法）对偶变量法（位势法）1.基本原理基本原理30课件设对偶变量向量为设对偶变量向量为 Y=(u1,u2, ,um, v1, v2, ,vn)对偶规划为对偶规划为 ui+vjciji=1,2,3 mj=1,2,3 n31课件 j = = C j- CBB-1 Pj = Cj - Y Pj ij = = C ij- CBB-1 Pij = Cij - Y Pij = Cij - (u1,
13、u2, ,um, v1, v2, ,vn) Pij = Cij - ( ui+ vj ) 当当xij 为基变量时为基变量时 ij = Cij - ( ui+ vj )=0 上式共上式共m+n-1个，而对偶变量有个，而对偶变量有m+n个个，因因此，任选一个对偶变量为此，任选一个对偶变量为0，可求出其余所，可求出其余所有的有的ui， vj 。 再根据再根据ij = Cij - ( ui+ vj )求出所有非基求出所有非基变量的检验数。变量的检验数。32课件 销地销地产地产地B1B2B3B4产产量量uiA110616 u1= A28210 u2=A314822 u3=销量销量814121448vjv
14、1=v2=v3=v4=412521039114681133课件 销地销地产地产地B1B2B3B4产产量量uiA110616 u1=0A28210 u2=-1A314822 u3=-5销量销量814121448vjv1=3v2=10 v3=4v4=11412521039114681111=4-(3+0) =1 12=12-(10+0)=222=10-(10-1)=1 24=9-(11-1)=-131=8-(-5+3)=10 33=11-(-5+4)=1234课件四、解的改进四、解的改进闭回路调整法闭回路调整法 销地销地产地产地B1B2B3B4产量产量A110616A28210A314822销量销
15、量8141214481 13 32 24 4以以x24为换入变量，以为换入变量，以(A2,B4)为第一个奇数顶为第一个奇数顶点，对闭回路上顶点依此编号点，对闭回路上顶点依此编号找偶数点中最小运输量，闭回路上奇数顶点加找偶数点中最小运输量，闭回路上奇数顶点加上此数，偶数顶点减去此数上此数，偶数顶点减去此数35课件 销地销地产地产地B1B2B3B4产量产量A110+2 6-216A28 2-2+210A314822销量销量81412144836课件 销地销地产地产地B1B2B3B4产量产量A112416A28210A314822销量销量81412144811=4-11+9-2 =0 12=12-1
16、1+6-5=222=10-9+6-5=2 23=3-9+11-4=131=8-6+9-2=9 33=11-6+11-4=12412521039114681137课件五、需要注意的问题五、需要注意的问题 （1 1）多个空格（非基变量）的检验数为负，）多个空格（非基变量）的检验数为负，任一个都可作为换入变量。一般任一个都可作为换入变量。一般ij00中最小的中最小的对应变量作为换入变量。对应变量作为换入变量。 （2 2）最优解时，如果有某非基变量的检验数）最优解时，如果有某非基变量的检验数为为0 0，则说明该运输问题有无穷多最有解。，则说明该运输问题有无穷多最有解。 （3 3）迭代过程中，若某一格填
17、数时需同时划）迭代过程中，若某一格填数时需同时划去一行和一列，此时出现退化。为保证去一行和一列，此时出现退化。为保证m+n-1个非空格，需在上述的行或列中填入数字个非空格，需在上述的行或列中填入数字0 0( (它它的位置是在对应的同时划去的那行或那列的所的位置是在对应的同时划去的那行或那列的所有空格中对应单位运价最小的任一空格有空格中对应单位运价最小的任一空格) )38课件练习：练习： 销地销地产地产地B1B2B3B4产量产量A116A210A322销量销量814121448311419281035710求最小运费的运输方案求最小运费的运输方案39课件第三节第三节 运输问题的进一步讨论运输问题
18、的进一步讨论一、产销不平衡的运输问题一、产销不平衡的运输问题例例1：31271125943561 销地销地产地产地B1B2B3B4产量产量A18A25A39销量销量4356产大于销时，增加一个假想的销地产大于销时，增加一个假想的销地40课件 销地销地产地产地B1B2B3B4B5产量产量A18A25A39销量销量435643127112594356100041课件 销地销地产地产地B1B2B3B4B5产量产量A14048A2325A3549销量销量435643127112594356100042课件当产大于销时，即当产大于销时，即加入假想销地加入假想销地Bn+1（假想仓库），销量为（假想仓库），
19、销量为 运费为运费为043课件i=1,2,mj =1, 2, ,nxij 044课件i=1,2,mj =1, 2, ,n，n+1xij 045课件当销大于产时，即当销大于产时，即加入假想产地加入假想产地Am+1，产量为，产量为 运费为运费为046课件i=1,2,mj =1, 2, ,nxij 047课件i=1,2,m，m+1j =1, 2, ,nxij 048课件A1B1B2B3A2二、有转运的运输问题二、有转运的运输问题产产地地销销地地49课件m个产地个产地n个销地都可以作为中间转运站，个销地都可以作为中间转运站，从而发送地接收地都有从而发送地接收地都有m+n个个将将m个产地与个产地与n个销
20、地统一编号，产地排个销地统一编号，产地排在前，销地排在后，则有在前，销地排在后，则有假设为产销平衡问题，即假设为产销平衡问题，即数学模型数学模型50课件xi1 + +xi,i-1 + xi,i+1+ . +xi,m+n = =ai+ti i=1,2,mxi1+ +xi,i-1 + xi,i+1+ +x i,i+m= = ti i=m+1,m+n x1j+ +xj-1,j+ xj+1,j + +xm+n,j= tj j=1,2,mx1j+ +xj-1,j+ xj+1,j + +xm +n,j = bj+tj j=m+1,m+n xij 0, i,j=1,2,m+n (ij)其中其中t i为为第第
21、i个地个地点转点转运物运物品的品的数量数量ti或或tj移到等式左侧，等式两端加移到等式左侧，等式两端加Q Q 得：得：51课件xi1 + +xi,i-1 + (Q Q-ti)+xi,i+1+ . +xi,m+n = =Q Q+ +ai i=1,2,mxi1+ +xi,i-1 + (Q Q-ti ) + xi,i+1+ +x i,i+m= =Q Q i=m+1,m+n x1j+ +xj-1,j+ (Q Q- tj ) + xj+1,j + +xm+n,j= Q Q j=1,2,mx1j+ +xj-1,j+ (Q Q- tj)+ xj+1,j + +xm +n,j = Q Q+bj j=m+1,m
22、+n xij 0, i,j=1,2,m+n (ij)其中其中t i为为第第i个地个地点转点转运物运物品的品的数量数量令令xii=Q-ti ,xjj = Q-tj ,cii=-c i52课件其中其中c i为为地地i个地个地点转点转运单运单位物位物品的品的费用费用53课件 接收接收 发送发送产地产地销地销地发送发送量量1 mm+1 m+n产产地地1mx11 x1m xm1 xmmx1,m+1 x1,m+n xm,m+1 xm,m+nQ+a1 Q+am销销地地m+1m+nxm+1,1 xm+1,m xm+n,1 xm+1,mxm+1,m+1 xm+1,m+n xm+n,m+1xm+n,m+n Q Q
23、接收量接收量Q QQ+bm+1 Q+bm+n运输表运输表54课件 接收接收 发送发送产地产地销地销地发送发送量量1 mm+1 m+n产产地地1m-c1 c1m cm1 -cmc1,m+1 c1,m+n cm,m+1 cm,m+nQ+a1 Q+am销销地地m+1m+ncm+1,1 cm+1,m cm+n,1 cm+1,m-cm+1 cm+1,m+n cm+n,m+1 -cm+n Q Q接收量接收量Q QQ+bm+1 Q+bm+n运价表运价表55课件13524105432652205304135340例：例： 两个产地两个产地1，2，两个销地，两个销地4，5及中间转运站及中间转运站356课件 接收接收 发送发送产地产地转运转运销地销地发送发送量量12345产地产地160290转运转运350销地销地450550接收量接收量5050508070-453MM4255-36542M2253-35M-16-5用最小元素法得初始运输方案，再经两次用最小元素法得初始运输方案，再经两次迭代得最优解。迭代得最优解。57课件
