运输问题及其数学模型

1、例1产地产地A1A2A3三产地四销地三产地四销地, 同类可互换产品，单位运价同类可互换产品，单位运价(元元/ t ), 如何调运，运费最少？如何调运，运费最少？794产量产量x 21x 22x 23x 24x 11x 12x 13x 14x 31x 32x 33x 34销量销量6635198231110374510B1销地销地B2B4B3= 3 x11 + 11 x12 + 3 x13 + 10 x 14 + x 21 + 9x22 + 2 x23 + 8x24 + 7 x 31 + 4 x32 + 10 x33 + 5 x34 x 11 +x12 + x13 + x14 = 7 . .tsx

2、11 + 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第一节第一节 运输问题及其数学模型运输问题及其数学模型一 、运输问题数学模型产地产地A1A2Am.B1销地销地B2B n销量销量b 2b nb 1a1.ama2产量产量x 11x 12x 1

3、nx 21x 22x 2nx m1x m2x m n.c 11c 12c 1nc 21c 22c 2nc m1c m2c m n产销平衡运输问题数学模型产销平衡运输问题数学模型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个方程是独立的个方程是独

4、立的, 运输问题的运输问题的 基本可行解基本可行解 有有 m+n-1 个分量个分量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个方程是独立的个方程是独立的, 运输问题的运输问题的 基本可行解

5、基本可行解 有有 m+n-1 个分量个分量. .n个个m个个前前m个之和等于后个之和等于后n个之和个之和 2 表上作业法表上作业法 销量销量6635794产量产量例1最小元素法最小元素法产地产地A1A2A33销地销地34361初始调运方案初始调运方案 ( 初始基可行解初始基可行解 )3198231110374510B1B2B 4B3134386 元元销量销量6635794产量产量例1最小元素法最小元素法产地产地A1A2A33销地销地4361初始调运方案初始调运方案 ( 初始基可行解初始基可行解 )198231110374510B1B2B 4B3386 元元空格空格为非为非基变量基变量销量销量6

6、635794产量产量例1沃格尔沃格尔(Vogel)法法 产地产地A1A2A31销地销地34225 ( 初始基可行解初始基可行解 )行罚数行罚数311103B1B2B 4B320列列罚罚数数19827451013 42551301121321201201363322532121217600两最小元素之差两最小元素之差两最小元素之差两最小元素之差-闭回路法闭回路法1此空格为入基变量此空格为入基变量。由一个空格和若干个有数字的水平和垂直连线包围成的由一个空格和若干个有数字的水平和垂直连线包围成的封闭回路封闭回路。销量销量6635794产量产量例1闭回路法闭回路法调整调整产地产地A1A2A33销地销地

7、4361非基变量（空格）的检验数非基变量（空格）的检验数198231110374510B1B2B 4B3386 元元 ， min(3,1)=1从空格出发沿封闭回路前进从空格出发沿封闭回路前进, 顺时逆时均可顺时逆时均可.检验数检验数8-2+3-10= -1，需调整，需调整销量销量6635794产量产量例1产地产地A1A2A33销地销地536初始调运方案初始调运方案 ( 初始基可行解初始基可行解 )198231110374510B1B2B 4B3286 元元 ， min(3,1)=1从空格出发沿封闭回路前进从空格出发沿封闭回路前进, 顺时逆时均可顺时逆时均可.185元元vj910230-5-1u

8、i二、解的最优性检验最优性检验 - 位势法位势法2产地产地A1A2A33销地销地4361198231110374510B1B2B 4B3386 元元121-110127个变量个变量6个方程需补充一个方程个方程需补充一个方程 u1=0基变量的检验数为基变量的检验数为 0vj910230-5-1ui二、解的最优性检验最优性检验 - 位势法位势法产地产地A1A2A33销地销地4361198231110374510B1B2B 4B3386 元元121-11012调整量：调整量：min(3, 1)=1找出找出非基变量的检验数非基变量的检验数为为负空格负空格的的闭回路闭回路vj910330-5-2ui二、

9、解的最优性检验最优性检验 - 位势法位势法产地产地A1A2A33销地销地4361198231110374510B1B2B 4B3386 元元185元元52调整量：调整量：min(3, 1)=1找出找出非基变量的检验数非基变量的检验数为为负空格负空格的的闭回路闭回路vj910330-5-2ui二、解的最优性检验最优性检验 - 位势法位势法产地产地A1A2A33销地销地2362198231110374510B1B2B 4B3086 元元185元元52非基变量的检验数非基变量的检验数无无负值负值，最优方案！，最优方案！1219最优解不唯一最优解不唯一表上作业法一. 给出运输问题的初始基可行解（初始调运方案）三. 解的改进1. 最小元素法二. 解的最优性检验2. 位势法(Dual variable method)1. 闭回路法2. Vogel 法a. 闭回路；b. 每个空格都唯一存在一条闭回路 闭回路；表上作业计算框图分析问题列出产销平衡表及单位运价表确定初始调运方案求检验数(闭回路法或位势法)所有检验数0对绝对值最大的负检验数用闭回路法调整，得出新调运方案得到最优方案算出总运价是是否否五. 供求不平衡运输问题例2B1B2B3B4产量A1211347A2103595A378127销量2346B1B2B3B4B5产量A