运筹学第三章运输问题培训课程课件.ppt

1、运筹学第三章运输问题运筹学第三章运输问题ppt课件3.1 运输问题的典例和数学模型 3.2 运输问题的求解方法：表上作业法3.3 几类特殊的运输问题3.4 运输问题的应用 运输问题 根据已有的交通网，如何制定运输方案，使得这些物资被运送到各个销售地，并保证某个指标最优(例如总运费最小)。3.1 运输问题的典例和数学模型一、典例 某食品公司经营糖果业务，公司下设三个工厂A1、A2、A3，四个销售门市部B1、B2、B3、B4。已知每天各自的生产量、销售量及调运时的单位运输费用情况。问：如何调运可使总费用最小？生产量：A17吨，A2 4吨，A3 9吨销售量：B1 3吨，B2 6吨，B3 5吨，B4

2、6吨产地单位运价销地B1 B2 B3 B4 A1A2A3 3 11 3 10 1 9 2 8 7 4 105调运示意图A1A2A3B1B2B3B47吨4吨9吨3吨6吨5吨6吨x11x12x13x14x21x22x23x24x31x32x33x34产地销地二、建立模型设 xij第i产地到第j销地之间的调运量，则有Min z=cij xij34i=1 j=1x11+x12+x13+x14=7x11+x21+x31=3xij0,(i=1,2,3；j=1,2,4)产量限制销量限制x21+x22+x23+x24=4x31+x32+x33+x34=9x12+x22+x32=6x13+x23+x33=5x1

3、4+x24+x34=6单单位位运运价价表表产产销销平平衡衡表表一般模型表示(ai=bj)三、模型的特点1.变量数：mn个2.约束方程数：m+n个 最大独立方程数：m+n-13.系数列向量结构：Pij=第i个分量第m+j个分量01 11 10 注:表上作业法适用于下列情形已知每天各自的生产量、销售量及调运时的单位运输费用情况。x33+x34302 -1 3为使数字格的个数恰好等于m+n-1，在同时划去的行列中，任选（或选其价A1 A2 A32 1 4 3 3 5 -2 1 -2 35 15 15 10已知每天各自的生产量、销售量及调运时的单位运输费用情况。2 运输问题的求解方法：表上作业法x33

4、+x34302 1 4 3 3 5 -2 1 -2 3注：位势法求检验数的依据是对偶理论。00 11.(4)若在中途同时有行列要求得到满足，将同时划掉一行一列，最后数字格个数将少于m+n-1个。0 0 0 1 1 1 0 0 0 x11 x12 x1n x21 x22 x2n ,xm1 xm2 xmn1 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 1i=1i=2i=mj=1j=2j=n关于运输模型的几个结论(1)设有m个产地，n个销地且产销平

5、衡的运输问题，则基变量数是m+n1；(2)若变量组B包含有闭回路，则B中变量对应的列向量线性相关；(3)m+n1个变量组构成基变量的充要条件是它不包含任何闭回路。初始基可行解新的基可行解最优否？STOPYN 3.2 运输问题的求解方法：表上作业法单纯形法求解思路表上作业法步骤表上作业法步骤:初始运输方案最优性检验改进运输方案一、初始方案的确定1.最小元素法最小元素法2.VogelVogel法法二、最优性检验1.闭回路法闭回路法2.位势法位势法三、方案改进方法在闭回路闭回路内改进。3产地销地A1 A2 A3B1 B2 B3 B4产地销地A1 A2 A3B1 B2 B3 B4产量销量3 11 3

6、10 1 9 2 8 7 4 10 5 634133 6 5 67 4 9单位运价表产销平衡表最小元素法最小元素法例 产地销地A1 A2 B1 B215 1510 20产量销量2851最小元素法：z=810+25+115=105Vogel法：z=105+152+51=85VogelVogel法法B1 B2 B3 B42 -1 3(3)在进行调运方案改进时，若沿闭合回路出现多个可作为调出变量的数字格（即闭回路上的数字格最小值有多个），此时，任选一个为调出变量，其余的填0，保证调整后的调运方案中仍有m+n1个数字格。x14+x24+x34+x44=202 5 1 35 15 15 10第二天送洗：

7、y23+z24+z25700为使数字格的个数恰好等于m+n-1，在同时划去的行列中，任选（或选其价T1 T2 T3 T4B1 B2 B3 B4第二天：x2+y12=700(1)任何运输问题都有基可行解，且有最优解；0 1 3 2 1 0 1 1 3 1 0 2 2 1 2 0(4)若在中途同时有行列要求得到满足，将同时划掉一行一列，最后数字格个数将少于m+n-1个。运筹学第三章运输问题ppt课件2 1 4 3 3 5 -2 1 -2 3第一天送洗：y12+z13+z14+z15100023 26 25 2623 26 25 26产地销地A1 A2 A3B1 B2 B3 B47 4 9产量销量3

8、 6 5 6635213产地销地A1 A2 A3B1 B2 B3 B4行两最小元素之差列两最小元素之差3 11 3 10 1 9 2 8 7 4 10 5 0 1 12 5 1 3 0 1 22 -1 30 1-2 -1 27 6-1 2VogelVogel法法产销平衡表针对最小元素法和vogel法，需要说明的几点(1)任何运输问题都有基可行解，且有最优解；(2)如果供应量和需求量都是整数，那么一定可以得到整数形式的最优解;(4)若在中途同时有行列要求得到满足，将同时划掉一行一列，最后数字格个数将少于m+n-1个。为使数字格的个数恰好等于m+n-1，在同时划去的行列中，任选（或选其价格系数最小

9、元素对应的）空格，填上数字0作为特殊的数字格（即基变量）。(3)用最小元素法和vogel法得到的是运输问题的一个基可行解，数字格对应基变量；例产地销地A1 A2 A3B1 B2 B3 B4产地销地A1 A2 A3B1 B2 B3 B4产量销量2 7 3 11 8 4 6 9 4 3 10 5 2030 25 10 1520 10 50单位运价表产销平衡表102515100产地销地A1 A2 A3B1 B2 B3 B4产地销地A1 A2 A3B1 B2 B3 B4产地销地A1 A2 A3B1 B2 B3 B4产量销量3 11 3 10 1 9 2 8 7 4 10 5 6343133 6 5 6

10、7 4 93 6 5 67 4 9产量销量363521(1)(2)(1)(-1)(10)(12)z=c11-c13+c23-c21=1=11z=c12-c14+c34-c32=2=12(0)(2)(2)(9)(1)(12)单位运价表产销平衡表闭闭回回路路法法注:只要求的基变量是正确的，并且数目为m+n1个，那么每个非基变量的闭回路存在且唯一，因此，检验数唯一。产地销地A1 A2 A3B1 B1 B3 B4位势法位势法4132.计算行位势和列位势；令v1=1，则依cij=ui+vj 计算各ui和vj 3.计算空格处位势；ij=ui+vj行位势ui列位势vj 110-42894.计算空格处检验数：

11、ij=cij-ij1.数字格处上添上对应的运价；销地A1 A2 A3B1 B1 B3 B43 11 3 10 1 9 2 8 7 4 10 5 产地单位运价表位势表:2105(2)(9)(8)(9)(-3)(-2)产地销地A1 A2 A3B1 B1 B3 B47 4 9产量销量3 6 5 66343(-1)3(1)(2)(1)(10)1(12)检验数表注：位势法求检验数的依据是对偶理论。注:对于同一组基变量，所求的检验数是唯一的；(2)在最优解表中，有非基变量（即空格)的检验数为0，根据线性规划单纯形法原理知，应有无穷多最优解，即有多解。运输问题表上作业法求多解的方法任选一检验系数为0的空格入

12、基，进行方案改进，可得新的最优解；(3)在进行调运方案改进时，若沿闭合回路出现多个可作为调出变量的数字格（即闭回路上的数字格最小值有多个），此时，任选一个为调出变量，其余的填0，保证调整后的调运方案中仍有m+n1个数字格。16 13 22 17 14 13 19 15 19 20 23 x11+x21+x31=35 15 15 103 6 6 53 11 3 10 1 9 2 8 7 4 10 5T1 T2 T3 T43 几类特殊的运输问题x14+x24+x34=63 11 3 10 1 9 2 8 7 4 10 500 11.0 1 0 0 1 0 0 1 03 几类特殊的运输问题不能出现循

13、环倒运现象，允许自身往自身最多调运一次，运价为cii=0；2 1 4 3 3 5 -2 1 -2 350 70 30 不限x11+x12+x13+x14=78 6 7 7(4)若在中途同时有行列要求得到满足，将同时划掉一行一列，最后数字格个数将少于m+n-1个。A1 A2 A3注:表上作业法适用于下列情形 5例产地销地A1 A2 A3B1 B1 B3 B47 4 9产量销量3 6 5 6635213(0)(2)(2)(9)(1)(12)产地销地A1 A2 A3B1 B1 B3 B47 4 9产量销量3 6 5 6633124(1)产地销地A1 A2 A3B1 B2 B3 B4产量销量63223

14、3 6 6 56 5 9(2)(1)(-1)(10)(12)例6产地销地A1 A2 A3B1 B2 B3 B4产量销量63033 6 6 56 5 9 2练习产地销地A1 A2 A3B1 B2 B3 B4产地销地A1 A2 A3B1 B2 B3 B4产量销量10 1 20 11 12 7 9 20 2 14 16 18 5 15 15 1015 25 5单位运价表产销平衡表最小元素法产地销地A1 A2 A3B1 B2 B3 B4产地销地A1 A2 A3B1 B2 B3 B4产量销量10 1 20 11 12 7 9 20 2 14 16 18 5 15 15 1015 25 5单位运价表产销平

15、衡表155151000Vogel法产地销地A1 A2 A3B1 B2 B3 B4产地销地A1 A2 A3B1 B2 B3 B4产量销量10 1 20 11 12 7 9 20 2 14 16 18 5 15 15 1015 25 5单位运价表产销平衡表8 6 7 79 2 125-6 11 910 2 -15-6 -910 13 -105100注:表上作业法适用于下列情形cij0；min z；产销平衡。表表上上作作业业法法步步骤骤3.3 几类特殊的运输问题一、产销不平衡问题1产销2销产二、需求量不确定三、中转问题Min z=cij xijni=1j=1mm)1,2,.,(i 1ainjijxn

16、)1,.,j ;m.,1,(i 0n),.,1,2(j 1xijjmiijbx一、产销不平衡问题1产销(aibj)Min z=cijxij+0 xi,n+1ni=1 j=1mm)1,2,.,(i 11ainjijx1)nn,1,.,j ;m.,1,(i 01)nn,.,1,2(j 1xijjmiijbxi=1m产地销地A1 A2 AmB1B2BnC11C12C1n C21C22C2n Cm1Cm2CmnBn+1 产销问题单位运价表销量产量b1b2bna1 a2 amaibjMin z=cij xijni=1j=1mm)1,2,.,(i 1ainjijxn)1,.,j ;m.,1,(i 0n),

17、.,1,2(j 1xijjmiijbx2销产(bjai)Min z=cijxij+0 xm+1,jni=1 j=1m1)mm,1,2,.,(i 1ainjijxn)1,.,j ;1mm,.,1,(i 0n),.,1,2(j 11xijjmiijbxj=1n产地销地A1 A2 AmB1B2BnC11C12C1n C21C22C2n Cm1Cm2CmnAm+1销产问题单位运价表0 0 0销量产量b1b2bna1 a2 ambjai例：例：有A、B、C三个化肥厂供应四个地区、的农用化肥，三个工厂每年各自的产量为A-50万吨，B-60万吨，C-50万吨。四个地区的需求量分别是地区最高50万吨，最低30

18、万吨，地区为70万吨，地区为30万吨以下，地区不低于10万吨。问：如何调运，可使总的调运费用最小？单位调运费用如下表所示。产地销地A 产量最低需求16 13 22 17 14 13 19 15 19 20 23 单位运价表50 60 5030 70 0 10单位：万元/万吨设 xij-第i工厂调至第j需求地区的化肥数量二、需求量不确定BC最高需求 50 70 30 不限A B C 161613221717 14141319151519192023 M MM0M0M0供应需求产量销 量50 60 50 302070301050产销平衡表D50注：M表示无穷大正数，最低需求不能由D生产地提供。最优

19、方案 需求产地I产量A5050B20103060C3020050D302050销量302070301050练习产地销地A 最高发量4 6 7 -7 8 单位运价表60 40 400BC销量70 80 50D最低发量80 40 不限505 4 6 4 5 -三、中转问题在前面的例题中，若既可以从Ai运到Bj，也可以经过中间站T1、T2、T3、T4或者Ai、Bj转运，称为扩大的运输问题。几点说明：1.所有的产地、销地、中间站均视作产地、销地；2.不能出现循环倒运现象，允许自身往自身最多调运一次，运价为cii=0；3.转运量可定位总的产量之和；4.实际产地产量为转运量与该产地实际产量之和，实际销地销

20、量为转运量与实际销量之和。A1 A2 A3T1 T2 T3 T4 B1 B2 B3 B4A1 A2 A3T1 T2 T3 T4B1 B2 B3 B40 1 3 1 0 -3 -02 1 4 3 3 5 -2 1 -2 33 11 3 10 1 9 2 8 7 4 10 52 3 1 1 5 -4 -2 3 2 33 1 7 11 9 4 3 2 10 10 8 50 1 3 2 1 0 1 1 3 1 0 2 2 1 2 0 2 8 4 6 4 5 2 7 1 8 2 4 1 -2 6 2 4 1 1 8 5 8 -4 2 2 2 6 7 4 60 1 4 2 1 0 2 1 4 2 0 3

21、2 1 3 0产销产量销量27 24 2920 20 20 2020 20 20 2020 20 2020 20 20 20 23 26 25 26产销平衡表3.4 运输问题的应用 例：例：某工厂按合同规定必须于当年的每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂的生产能力及生产每台柴油机的成本如表示。又如果生产出来的柴油机当季不交货，每台每积压一个季度需要存储维护费用0.15万元。要求在完成合同的情况下，做出使全年生产费用最小的决策。季度生产能力(台)单位成本(万元/台)25353010模型：设xij第i季度生产，用于第j季度交货的数量。obj.min z=cij xi

22、ji=1j=1 4 4x11+x12+x13+x1425 x22+x23+x2435 x33+x3430 x4410 x11 =10 x12+x22 =15x13+x23+x33 =25x14+x24+x34+x44=20 xij 0,(i=1,4;j=1,4)供应：需求：Min z=cij xijM0M0M0C11C12C1n C21C22C2n Cm1Cm2Cmn3 几类特殊的运输问题x14+x24+x34=623 26 25 260 1 3 1 0 -3 -0B1 B2 B3 B4T1 T2 T3 T4注:表上作业法适用于下列情形1 1 1 0 0 0 0 0 0B1B2Bnx14+x2

23、4+x34=6B1 B2 B3 B4x13+x23+x33=5 2 运输问题的求解方法：表上作业法B1 B2 B3 B4T1 T2 T3 T4x11+x21+x31=3单位费用表 10.8 10.9511.10 11.25 M 11.10 11.25 11.40 M M 11.00 11.15 M MM 11.30单位：万元供应需求例例:某餐馆承办宴会，每晚连续举行，共举行五次。宴会上需用特殊的餐巾，根据参加的人数，预计每晚的需要量为：第一天1000条，第二天700条，第三天800条，第四天1200条，第五天1500条，五天之后，所有的餐巾作废。宴会中用过的餐巾经过洗涤处理后可以重复使用，这样

24、可以降低使用成本。已知每条新餐巾需要1元的费用，送洗时可选择两种方式：快洗仅需要一天时间，每条洗涤费用为0.2元，慢洗需要两天时间，每条洗涤费用0.1元。问：如何安排，可使总费用最低？第四天送洗：y45120020 20 20 20宴会中用过的餐巾经过洗涤处理后可以重复使用，这样可以降低使用成本。B1 B2 B3 B4M MM 11.00 11.zij第i天送第j天使用慢洗餐巾的数量；2 7 3 11 8 4 6 9 4 3 10 5最小元素法：z=810+25+115=105M MM 11.B1 B1 B3 B4B1 B1 B3 B430 25 10 152 运输问题的求解方法：表上作业法销

25、售量：B1 3吨，B2 6吨，B3 5吨，B4 6吨x4410 x14+x24+x34=623 26 25 262 8 4 6 4 5 2 7 1 8 2 4 1 -2 6Min z=cijxij+0 xm+1,j新购餐巾：x1+x2+x3+x4+x55200Min z=cij xij3 6 6 52 3 1 1 5 -4 -2 3 2 3x44103 11 3 10 1 9 2 8 7 4 10 51 运输问题的典例和数学模型B1 B2 B3 B4第一天送洗：y12+z13+z14+z151000第四天送洗：y4512002 运输问题的求解方法：表上作业法3 11 3 10 1 9 2 8

26、7 4 10 5zij第i天送第j天使用慢洗餐巾的数量；(2)在最优解表中，有非基变量（即空格)的检验数为0，根据线性规划单纯形法原理知，应有无穷多最优解，即有多解。B1B2Bnb1b2bn2元，慢洗需要两天时间，每条洗涤费用0.最小元素法：z=810+25+115=105关于运输模型的几个结论建立模型设 xj第j天使用新毛巾的数量；yij第i天送第j天使用快洗 餐巾的数量；zij第i天送第j天使用慢洗餐巾的数量；第一天：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