运输问题及其数学模型精品文稿.ppt

《运输问题及其数学模型精品文稿.ppt》由会员分享，可在线阅读，更多相关《运输问题及其数学模型精品文稿.ppt（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、运输问题及其数学模型第1页，本讲稿共25页第一节第一节运输问题的典例和数学模型运输问题的典例和数学模型第2页，本讲稿共25页例1产地产地A1A2A3三产地四销地三产地四销地,同类可互换产品，单位运价同类可互换产品，单位运价(元元/t),如如何调运，运费最少？何调运，运费最少？794产量产量x 21x 22x 23x 24x 11x 12x 13x 14x 31x 32x 33x 34销量销量6635198231110374510B1销地销地B2B4B3第3页，本讲稿共25页=3 x11+11 x12+3 x13+10 x 14 +x 21+9x22+2 x23+8x24+7 x 31+4 x3

2、2+10 x33+5 x34 x 11+x12+x13 +x14=7x11+x21+x31=3x i j 0,(i=1,2,3;j=1,2,3,4)数学模型数学模型i=13min Z =c i j x i jj=14x 21+x22+x23 +x24=4x12+x22+x32=6x 31+x32+x33 +x34=9x13+x23+x33=5x14+x24+x34=6第4页，本讲稿共25页第一节第一节 运输问题及其数学模型运输问题及其数学模型一、运输问题数学模型产地产地A1A2Am.B1销地销地B2B n销量销量b 2b nb 1a1.ama2产量产量x 11x 12x 1nx 21x 22x

3、 2nx m1x m2x m n.c 11c 12c 1nc 21c 22c 2nc m1c m2c m n第5页，本讲稿共25页产销平衡运输问题数学模型产销平衡运输问题数学模型i=1mmin Z =c i j x i jj=1n平衡平衡 (产产=销销)i=1Q=j=1m a i =b jnx i j 0,(i=1,2,m;j=1,2,n)(i=1,2,m)x i j =a i ,j=1n(j=1,2,n)x i j =b j,i=1mm+n个方程中只有个方程中只有m+n-1个方程是独立的个方程是独立的,运输问题的运输问题的 基本可行解基本可行解 有有 m+n-1 个分量个分量第6页，本讲稿共

4、25页1.运输问题有有限最优解运输问题有有限最优解2.运输问题约束条件的系数矩阵运输问题约束条件的系数矩阵二二、运输问题数学模型的特点运输问题数学模型的特点x11 x12 x1nxm1 xm2 x m n x 21 x22 x2n 1 1 1 .1 1 1 1 1 1 A i j=(0,0,1,0,0,1,0)第第 i 个个 第第(m+j)个个 1 11 1 11 1 11 .m+n个方程中只有个方程中只有m+n-1个方程是独立的个方程是独立的,运输问题的运输问题的 基本可行解基本可行解 有有 m+n-1 个分量个分量.n个个m个个前前m个之和等于后个之和等于后n个之和个之和 第7页，本讲稿共

5、25页2 表上作业法表上作业法 (1)(1)找出找出找出找出初始基可行解初始基可行解(2)求各求各求各求各非基变量的检验数非基变量的检验数(3)确定确定换入变量换入变量和和换出变量换出变量(4)重复重复(2),(3)步，直到求得步，直到求得最优解最优解为止为止为止为止第8页，本讲稿共25页销量销量6635794产量产量例1最小元素法最小元素法产地产地A1A2A33销地销地34361初始调运方案初始调运方案 (初始基可行解初始基可行解)3198231110374510B1B2B 4B3134386 元元第9页，本讲稿共25页销量销量6635794产量产量例1最小元素法最小元素法产地产地A1A2A

6、33销地销地4361初始调运方案初始调运方案 (初始基可行解初始基可行解)198231110374510B1B2B 4B3基变量基变量基变量基变量取值取值取值取值，0 0 也是取值也是取值也是取值也是取值386 元元空格空格为非为非基变量基变量第10页，本讲稿共25页销量销量6635794产量产量例1沃格尔沃格尔(Vogel)法法 产地产地A1A2A31销地销地34225 (初始基可行解初始基可行解)行罚数行罚数311103B1B2B 4B320列列罚罚数数19827451013 42551301121321201201363322532121217600两最小元素之差两最小元素之差两最小元素

7、之差两最小元素之差第11页，本讲稿共25页二二二二 解的最优性检验解的最优性检验解的最优性检验解的最优性检验-闭回路法闭回路法1此空格为入基变量此空格为入基变量。由一个空格和若干个有数字的水平和垂直连线包围成的由一个空格和若干个有数字的水平和垂直连线包围成的封闭回路封闭回路。第12页，本讲稿共25页销量销量6635794产量产量例1闭回路法闭回路法调整调整产地产地A1A2A33销地销地4361非基变量（空格）的检验数非基变量（空格）的检验数198231110374510B1B2B 4B3386 元元，min(3,1)=1从空格出发沿封闭回路前进从空格出发沿封闭回路前进,顺时逆时均可顺时逆时均可

8、.检验数检验数8-2+3-10=-1，需调整，需调整第13页，本讲稿共25页销量销量6635794产量产量例1产地产地A1A2A33销地销地536初始调运方案初始调运方案 (初始基可行解初始基可行解)198231110374510B1B2B 4B3286 元元，min(3,1)=1从空格出发沿封闭回路前进从空格出发沿封闭回路前进,顺时逆时均可顺时逆时均可.185元元第14页，本讲稿共25页vj910230-5-1ui二、解的最优性检验最优性检验-位势法位势法2产地产地A1A2A33销地销地4361198231110374510B1B2B 4B3386 元元121-110127个变量个变量6个方

9、程需补充一个方程个方程需补充一个方程 u1=0基变量的检验数为基变量的检验数为 0第15页，本讲稿共25页vj910230-5-1ui二、解的最优性检验最优性检验-位势法位势法产地产地A1A2A33销地销地4361198231110374510B1B2B 4B3386 元元121-11012调整量：调整量：min(3,1)=1找出找出非基变量的检验数非基变量的检验数为为负空格负空格的的闭回路闭回路第16页，本讲稿共25页vj910330-5-2ui二、解的最优性检验最优性检验-位势法位势法产地产地A1A2A33销地销地4361198231110374510B1B2B 4B3386 元元185元

10、元52调整量：调整量：min(3,1)=1找出找出非基变量的检验数非基变量的检验数为为负空格负空格的的闭回路闭回路第17页，本讲稿共25页vj910330-5-2ui二、解的最优性检验最优性检验-位势法位势法产地产地A1A2A33销地销地2362198231110374510B1B2B 4B3086 元元185元元52非基变量的检验数非基变量的检验数无无负值负值，最优方案！，最优方案！1219最优解不唯一最优解不唯一第18页，本讲稿共25页表上作业法一.给出运输问题的初始基可行解（初始调运方案）三.解的改进1.最小元素法二.解的最优性检验2.位势法(Dual variable method)1

11、.闭回路法2.Vogel 法a.闭回路；b.每个空格都唯一存在一条闭回路 闭回路；第19页，本讲稿共25页表上作业计算框图分析问题列出产销平衡表及单位运价表确定初始调运方案求检验数(闭回路法或位势法)所有检验数0对绝对值最大的负检验数用闭回路法调整，得出新调运方案得到最优方案算出总运价是是否否第20页，本讲稿共25页四四四四.几点说明几点说明几点说明几点说明1 1.多个空格多个空格多个空格多个空格(非基变量非基变量非基变量非基变量)的的的的检验数为负检验数为负检验数为负检验数为负通常取通常取通常取通常取 i ji j 0 销销销销 填一个虚拟的销地填一个虚拟的销地填一个虚拟的销地填一个虚拟的销

12、地第22页，本讲稿共25页供求不平衡运输问题供求不平衡运输问题供求平衡问题供求平衡问题B1B2B3B4B5产量A12113407A21035905A3781207销量23464 填一个虚拟的销地填一个虚拟的销地填一个虚拟的销地填一个虚拟的销地 B5 B5，运价为，运价为，运价为，运价为0 0第23页，本讲稿共25页销量销量3624775产量产量产地产地A1A2A3销地销地21143B1B2B 4B310395B5040028243初始可行解初始可行解 基变量个数基变量个数m+n-1=3+5-1=7332172第24页，本讲稿共25页作 业 阅读阅读 p81 94p101 3.1第25页，本讲稿共25页