运输问题及其数学模型.pptx

第一第一节运运输问题的典例和数学模型的典例和数学模型例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=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第一节第一节 运输问题及其数学模型运输问题及其数学模型一、运输问题数学模型产地产地A1A2Am.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产销平衡运平衡运输问题数学模型数学模型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 个分量个分量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个之和个之和 2 表上作表上作业法法 (1)找出找出初始基可行解初始基可行解(2)求各求各非基变量的检验数非基变量的检验数(3)确定确定换入变量换入变量和和换出变量换出变量(4)重复重复(2),(3)步，直到求得步，直到求得最优解最优解为止为止销量销量6635794产量产量例1最小元素法最小元素法产地产地A1A2A33销地销地34361初始调运方案初始调运方案 (初始基可行解初始基可行解)3198231110374510B1B2B 4B3134386 元元销量销量6635794产量产量例1最小元素法最小元素法产地产地A1A2A33销地销地4361初始调运方案初始调运方案 (初始基可行解初始基可行解)198231110374510B1B2B 4B3基变量基变量基变量基变量取值取值取值取值，0 0 也是取值也是取值也是取值也是取值386 元元空格空格为非为非基变量基变量销量销量6635794产量产量例1沃格沃格尔(Vogel)法法 产地产地A1A2A31销地销地34225 (初始基可行解初始基可行解)行罚数行罚数311103B1B2B 4B320列列罚罚数数19827451013 42551301121321201201363322532121217600两最小元素之差两最小元素之差两最小元素之差两最小元素之差二二二二 解的最解的最解的最解的最优优性性性性检验检验-闭回路法回路法1此空格为入基变量此空格为入基变量。由一个空格和若干个有数字的水平和垂直连线包围成的由一个空格和若干个有数字的水平和垂直连线包围成的封闭回路封闭回路。销量销量6635794产量产量例1闭回路法回路法调整整产地产地A1A2A33销地销地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-1ui二、解的最最优性性检验-位位势法法2产地产地A1A2A33销地销地4361198231110374510B1B2B 4B3386 元元121-110127个变量个变量6个方程需补充一个方程个方程需补充一个方程 u1=0基变量的检验数为基变量的检验数为 0vj910230-5-1ui二、解的最最优性性检验-位位势法法产地产地A1A2A33销地销地4361198231110374510B1B2B 4B3386 元元121-11012调整量：调整量：min(3,1)=1找出找出非基变量的检验数非基变量的检验数为为负空格负空格的的闭回路闭回路vj910330-5-2ui二、解的最最优性性检验-位位势法法产地产地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对绝对值最大的负检验数用闭回路法调整，得出新调运方案得到最优方案算出总运价是是否否四四.几点几点说明明1 1.多个空格多个空格多个空格多个空格(非基变量非基变量非基变量非基变量)的的的的检验数为负检验数为负检验数为负检验数为负通常取通常取通常取通常取 i ji j 0 销销销销 填一个虚拟的销地填一个虚拟的销地填一个虚拟的销地填一个虚拟的销地供求不平衡运供求不平衡运输问题供求平衡供求平衡问题B1B2B3B4B5产量A12113407A21035905A3781207销量23464 填一个虚拟的销地填一个虚拟的销地填一个虚拟的销地填一个虚拟的销地 B5B5，运价为，运价为，运价为，运价为0 0销量销量3624775产量产量产地产地A1A2A3销地销地21143B1B2B 4B310395B5040028243初始可行解初始可行解 基变量个数基变量个数m+n-1=3+5-1=7332172作 业 阅读阅读 p81 94p101 3.1