运筹学课件第三章运输问题(浙江)

《运筹学课件第三章运输问题(浙江)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章运输问题3.1运输问题的表示3.2初始基础可行解3.3非基变量的检验数3.4基解的调整3.5运输问题的进一步讨论10/7/20211运筹学本章学习要求掌握表上作业法及其在产销平衡运输问题求解中的应用掌握产销不平衡运输问题的求解方法10/7/20212运筹学3.1运输问题的表示网络图表示线性规划模型运输表10/7/20213运筹学某种物资从两个供应地A1，A2运往三个需求地B1，B2，B3。各供应地的供应量、各需求地的需求量、每个供应地到每个需求地每吨物资的运输价格如下表：运价（元/吨）B1B2B3供应量（吨）A123535A2

2、47825需求量（吨）10302060求总运费最低的运输方案。10/7/20214运筹学运价（元/吨）B1B2B3供应量（吨）A123535A247825需求量（吨）10302060minz=2x11+3x12+5x13+4x21+7x22+8x23s.t.x11+x12+x13=35供应地A1x21+x22+x23=25供应地A2x11+x21=10需求地B1x12+x22=30需求地B2x13+x23=20需求地B3x11,x12,x13,x21,x22,x23≥010/7/20215运筹学运输问题的一般提法：假设有m个生产地点

3、，可以供应某种物资（以后称为产地），用Ai来表示，i=1,…,m,有n个销地，用Bj来表示，j=1,…,n，产地的产量和销地的销量分别为ai,bj，从产地Ai到销地Bj运输一个单位物资的运价为Cij，这些数据可汇总于下表，在假设产销平衡的条件下，即∑ai=∑bj，问该如何调运物品使总运费最小？B1B2…Bn产量A1C11C12…C1na1A2C21C22…C2na2………………AmCm1Cm2…Cmnam销量b1b2…bn10/7/20216运筹学建模：设xij表示从Ai到Bj的运量，则所求的数学模型为：minΖ=ΣΣcijxijs

4、.t.Σxij=aii=1,…mΣxij=bjj=1,…,nj=1ni=1mi=1mj=1nxij≥0i=1,…m,j=1,…,n10/7/20217运筹学1.运输问题的网络图表示2312341d1=22d2=13d3=12d4=13s2=27s3=19s1=14产地运价销地6753482759106产量销量总产量60吨总销量60吨产销平衡的运输问题10/7/20218运筹学2.运输问题线性规划模型产地约束销地约束由于前m个产地约束和后n个销地约束是线性相关的，因此运输问题系数矩阵的秩

5、-1。即运输问题有m+n-1个基变量，mn-(m+n-1)个非基变量。例如以上问题m=3，n=4，基变量为3＋4－1＝6个，非基变量为12－6＝6个。10/7/20219运筹学3.运输问题的表格表示10/7/202110运筹学3.2初始基可行解运输问题基的表示西北角法最小元素法沃格尔法10/7/202111运筹学1.运输问题基的表示m个产地、n个销地的运输问题，任何一个基要满足以下三个条件：基变量的个数为m+n-1；基变量不能形成闭回路；10/7/202112运筹学1234123123412312341231234123123412

6、31234123基在运输表中的表示10/7/202113运筹学2.初始基础可行解—西北角法813131466方法：优先满足运输表中左上角空格的供销要求－填一个数字只能划去一行或一列10/7/202114运筹学3.初始基础可行解—最小元素法12015130113021930120200方法：按单位运价的大小，决定供应的先后，优先满足单位运价最小者的供销要求（就近供应）10/7/202115运筹学4.初始基础可行解—沃格尔法3212323311*3113行罚数列罚数414*13*1219方法：计算出每一行及每一列中单位运价最小和次小的两

7、个元素之间的差值，再从差值最大的行或列中找出单位运价最小者，优先满足其供销关系。10/7/202116运筹学3.3非基变量的检验数闭回路法位势法10/7/202117运筹学1.非基变量检验数—闭回路法(1)方法求非基变量检验数σij,以该变量为定点，其他顶点为基变量找一个闭回路，从该非基变量定点为“＋”，“－”，“＋”，“－”依次加减其运价，即为检验数。意义：以该非基变量充当基变量时单位运量运费的损失。当所有的σij≥0，则已得运输问题的最有解。即单位物品由i-j引起总运费的变化。10/7/202118运筹学8131314661.非

8、基变量检验数—闭回路法(1)σ12=c12-c22+c21-c11=7-4+8-6=5510/7/202119运筹学8131314661.非基变量检验数—闭回路法(2)5σ13=c13-c23+c21-c11=5-2+8-6=5510