运输问题及其数学模型实用教案

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

2、31 + 4 x32 + 10 x33 + 5 x34 x 11 +x12 + x13 + x14 = 7 . .tsx11 + 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第2页/共24页第三页，共24页。一 、运输(ynsh)问题数学模型产地产地A1A2A

3、m.B1销地销地B2B n销量销量b 2b nb 1a1.ama2产量产量x 11x 12x 1nx 21x 22x 2nx m1x m2x m n.c 11c 12c 1nc 21c 22c 2nc m1c m2c m n第3页/共24页第四页，共24页。i = 1mmin Z = c i j x i jj = 1n平衡平衡(pnghng) (产产=销销)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

4、i j = b j ,i = 1mm+n个方程中只有个方程中只有(zhyu)m+n-1个方程是独立的个方程是独立的, 运输问题的运输问题的 基本可行解基本可行解 有有 m+n-1 个分量个分量第4页/共24页第五页，共24页。1. 运输问题运输问题(wnt)有有限最优解有有限最优解2. 运输问题运输问题(wnt)约束条件的系数约束条件的系数矩阵矩阵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

5、 11 .m+n个方程中只有个方程中只有m+n-1个方程是独立的个方程是独立的, 运输问题的运输问题的 基本可行解基本可行解 有有 m+n-1 个分量个分量. .n个个m个个前前m个之和等于后个之和等于后n个之和个之和 第5页/共24页第六页，共24页。第6页/共24页第七页，共24页。销量销量6635794产量产量产地产地(chnd)A1A2A33销地销地34361初始初始(ch sh)调运方案调运方案 ( 初始初始(ch sh)基可行解基可行解 )3198231110374510B1B2B 4B3134386 元元第7页/共24页第八页，共24页。销量销量6635794产量产量产地产地(c

6、hnd)A1A2A33销地销地4361初始调运方案初始调运方案(fng n) ( 初始基可行初始基可行解解 )198231110374510B1B2B 4B3386 元元空格空格为非为非基变量基变量第8页/共24页第九页，共24页。销量销量6635794产量产量产地产地(chnd)A1A2A31销地销地34225 ( 初始初始(ch sh)基可行解基可行解 )行罚数行罚数311103B1B2B 4B320列列罚罚数数1982745101342551301121321201201363322532121217600两最小元素两最小元素(yun s)之差之差两最小元素之差两最小元素之差第9页/共2

7、4页第十页，共24页。此空格此空格(kn )为入基变为入基变量。量。由一个空格和若干个有数字由一个空格和若干个有数字(shz)的水平和垂直连线包围的水平和垂直连线包围成的成的封闭回路封闭回路。第10页/共24页第十一页，共24页。销量销量6635794产量产量产地产地(chnd)A1A2A33销地销地4361非基变量（空格非基变量（空格(kn )）的检验数）的检验数198231110374510B1B2B 4B3386 元元 ， min(3,1)=1从空格出发沿封闭回路前进从空格出发沿封闭回路前进, 顺时逆时均可顺时逆时均可.检验数检验数8-2+3-10= -1，需调整，需调整第11页/共24

8、页第十二页，共24页。销量销量6635794产量产量产地产地(chnd)A1A2A33销地销地536初始初始(ch sh)调运方案调运方案 ( 初始初始(ch sh)基基可行解可行解 )198231110374510B1B2B 4B3286 元元 ， min(3,1)=1从空格出发沿封闭回路前进从空格出发沿封闭回路前进(qinjn), 顺时逆时均可顺时逆时均可.185元元第12页/共24页第十三页，共24页。vj910230-5-1ui产地产地(chnd)A1A2A33销地销地4361198231110374510B1B2B 4B3386 元元121-110127个变量个变量(binling)

9、6个方程需补充一个方程个方程需补充一个方程 u1=0基变量的检验数为基变量的检验数为 0第13页/共24页第十四页，共24页。vj910230-5-1ui产地产地(chnd)A1A2A33销地销地4361198231110374510B1B2B 4B3386 元元121-11012调整调整(tiozhng)量：量：min(3, 1)=1找出找出非基变量的检验数非基变量的检验数为为负空格负空格的的闭回路闭回路第14页/共24页第十五页，共24页。vj910330-5-2ui产地产地(chnd)A1A2A33销地销地4361198231110374510B1B2B 4B3386 元元185元元52

10、调整调整(tiozhng)量：量：min(3, 1)=1找出找出非基变量的检验数非基变量的检验数为为负空格负空格的的闭回路闭回路第15页/共24页第十六页，共24页。vj910330-5-2ui产地产地(chnd)A1A2A33销地销地2362198231110374510B1B2B 4B3086 元元185元元52非基变量的检验非基变量的检验(jinyn)数无负值，最优方案！数无负值，最优方案！1219最优解不唯一最优解不唯一第16页/共24页第十七页，共24页。一. 给出运输(ynsh)问题的初始基可行解（初始调运方案）三. 解的改进(gijn)1. 最小元素法二. 解的最优性检验2. 位

11、势法(Dual variable method)1. 闭回路法2. Vogel 法a. 闭回路；b. 每个空格都唯一存在一条闭回路 闭回路；第17页/共24页第十八页，共24页。分析问题(wnt)列出产销平衡表及单位运价表确定初始(ch sh)调运方案求检验数(闭回路法或位势法)所有检验数0对绝对值最大的负检验数用闭回路法调整，得出新调运方案得到最优方案算出总运价是是否否第18页/共24页第十九页，共24页。第19页/共24页第二十页，共24页。B1B2B3B4产量A1211347A2103595A378127销量2346第20页/共24页第二十一页，共24页。B1B2B3B4B5产量A12113407A21035905A3781207销量23464第21页/共24页第二十二页，共24页。销量销量(xio lin