《运筹学》第三章运输问题.ppt

《《运筹学》第三章运输问题.ppt》由会员分享，可在线阅读，更多相关《《运筹学》第三章运输问题.ppt（48页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、B1 B2 B3 B4 A1A2A3 3 11 3 10 1 9 2 8 7 4 1054调运示意图A1A2A3B1B2B3B47吨4吨9吨3吨6吨5吨6吨x11x12x13x14x21x22x23x24x31x32x33x34产地销地5二、建立模型设 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=5x14+x24+x3

3、4=66单单位位运运价价表表产产销销平平衡衡表表7一般模型表示(ai=bj)8三、模型的特点1.变量数：mn个2.约束方程数：m+n个 最大独立方程数：m+n-13.系数列向量结构：Pij=第i个分量第m+j个分量01 11 10 9x11 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=n10关于运输模型的几个结论：(1)设有m个产地，n个销

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

5、 B4产量销量3 11 3 10 1 9 2 8 7 4 10 5 634133 6 5 67 4 9单位运价表产销平衡表最小元素法最小元素法14例 产地销地A1 A2 B1 B215 1510 20产量销量2851最小元素法：z=810+25+115=105Vogel法：z=105+152+51=85VogelVogel法法15产地销地A1 A2 A3B1 B2 B3 B47 4 9产量销量3 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

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

7、销地A1 A2 A3B1 B2 B3 B4产量销量2 7 3 11 8 4 6 9 4 3 10 5 2030 25 10 1520 10 50单位运价表产销平衡表10251510018产地销地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 67 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

8、)(2)(2)(9)(1)(12)单位运价表产销平衡表闭闭回回路路法法19注:只要求的基变量是正确的，并且数目为m+n-1个，那么每个非基变量的闭回路存在且唯一，因此，检验数唯一。20产地销地A1 A2 A3B1 B1 B3 B4位势法位势法4132.计算行位势和列位势；令v1=1，则依cij=ui+vj 计算各ui和vj 3.计算空格处位势；ij=ui+vj行位势ui列位势vj 110-42894.计算空格处检验数：ij=cij-ij1.数字格处上添上对应的运价；销地A1 A2 A3B1 B1 B3 B43 11 3 10 1 9 2 8 7 4 10 5 产地单位运价表位势表:2105(2

9、)(9)(8)(9)(-3)(-2)21产地销地A1 A2 A3B1 B1 B3 B47 4 9产量销量3 6 5 66343(-1)3(1)(2)(1)(10)1(12)检验数表注：位势法求检验数的依据是对偶理论。22注:(1)对于同一组基变量，所求的检验数是唯一的；(2)在最优解表中，有非基变量（即空格)的检验数为0，根据线性规划单纯形法原理知，应有无穷多最优解，即有多解。运输问题表上作业法求多解的方法：任选一检验系数为0的空格入基，进行方案改进，可得新的最优解；(3)在进行调运方案改进时，若沿闭合回路出现多个可作为调出变量的数字格（即闭回路上的数字格最小值有多个），此时，任选一个为调出变

10、量，其余的填0，保证调整后的调运方案中仍有m+n-1个数字格。235例：产地销地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 663312244(1)产地销地A1 A2 A3B1 B2 B3 B4产量销量632233 6 6 56 5 9(2)(1)(-1)(10)(12)例：6产地销地A1 A2 A3B1 B2 B3 B4产量销量63033 6 6 56 5 9 225练习产地销地A1 A2 A3B1 B2 B3 B4产地销地A1 A2 A3B

11、1 B2 B3 B4产量销量10 1 20 11 12 7 9 20 2 14 16 18 5 15 15 1015 25 5单位运价表产销平衡表26最小元素法产地销地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单位运价表产销平衡表15515100027Vogel法产地销地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

12、 25 5单位运价表产销平衡表8 6 7 79 2 125-6 11 910 2 -15-6 -910 13 -10510028注:表上作业法适用于下列情形：(1)cij0；(2)min z；(3)产销平衡。表表上上作作业业法法步步骤骤293.3 几类特殊的运输问题一、产销不平衡问题1产销2销产二、需求量不确定三、中转问题30Min z=cij xijni=1j=1m一、产销不平衡问题1产销(aibj)Min z=cijxij+0 xi,n+1ni=1 j=1mi=1m31产地销地A1 A2 AmB1B2BnC11C12C1n C21C22C2n Cm1Cm2CmnBn+1 产销问题单位运价表

13、销量产量b1b2bna1 a2 amaibj32Min z=cij xijni=1j=1m2销产(bjai)Min z=cijxij+0 xm+1,jni=1 j=1mj=1n33产地销地A1 A2 AmB1B2BnC11C12C1n C21C22C2n Cm1Cm2CmnAm+1销产问题单位运价表0 0 0销量产量b1b2bna1 a2 ambjai34例：例：有A、B、C三个化肥厂供应四个地区、的农用化肥，三个工厂每年各自的产量为A-50万吨，B-60万吨，C-50万吨。四个地区的需求量分别是地区最高50万吨，最低30万吨，地区为70万吨，地区为30万吨以下，地区不低于10万吨。问：如何调

14、运，可使总的调运费用最小？单位调运费用如下表所示。产地销地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 不限35A B C 161613221717 14141319151519192023 M MM0M0M0供应需求产量销 量50 60 50 302070301050产销平衡表D50注：M表示无穷大正数，最低需求不能由D生产地提供。36最优方案：需求产地I产量A5050B20103060C3020050

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

16、 T3 T4B1 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 2 1 3 0产销产量销量27 24 2920 20

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

18、+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)供应：需求：43单位费用表：10.8 10.9511.10 11.25 M 11.10 11.25 11.40 M M 11.00 11.15 M MM 11.30单位：万元供应需求44例例:某餐馆承办宴会，每晚连续举行，共举行五次。宴会上需用特殊的餐巾，根据参加的人数，预计每晚的需要量为：第一天1000条，第二天700条，第三天800条，第四天1200条，第五天1500条，五天

19、之后，所有的餐巾作废。宴会中用过的餐巾经过洗涤处理后可以重复使用，这样可以降低使用成本。已知每条新餐巾需要1元的费用，送洗时可选择两种方式：快洗仅需要一天时间，每条洗涤费用为0.2元，慢洗需要两天时间，每条洗涤费用0.1元。问：如何安排，可使总费用最低？45建立模型：设 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+

20、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.1zij46新 购 第一天第二天第三天第四天111110 M0.20.10.10.10MM0.20.10.10MMM0.20.10供应需求产量销 量5200 1000 700 800 1200MMM0.20.101000700800120015003700产销平衡表47第3章学习要求掌握产销不平衡运输问题转化为产销平衡问题的处理办法；掌握掌握产销不平衡运输问题转化为产销平衡问题的处理办法；掌握运输问题在实践中的典型应用运输问题在实践中的典型应用；(1)(1)了解产销平衡运输问题的数学模型及其特点；了解产销平衡运输问题的数学模型及其特点；(2)(2)掌握运输问题的表上作业法，包括初始调运方案的确定、检掌握运输问题的表上作业法，包括初始调运方案的确定、检验数的计算、运输方案的调整方法；验数的计算、运输方案的调整方法；(3)(3)掌握产销不平衡运输问题转化为产销平衡问题的处理办法；掌握产销不平衡运输问题转化为产销平衡问题的处理办法；了解运输问题在实践中的典型应用。了解运输问题在实践中的典型应用。48