运筹学-第三章-运输问题ppt课件.ppt
《运筹学-第三章-运输问题ppt课件.ppt》由会员分享,可在线阅读,更多相关《运筹学-第三章-运输问题ppt课件.ppt(47页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、2022-8-51运筹学运筹学OPERATIONS RESEARCH2022-8-52第三章第三章 运输问题运输问题n运输问题的数学模型运输问题的数学模型n表上作业法表上作业法n产销不平衡的运输问题及应用产销不平衡的运输问题及应用2022-8-531 1 运输问题的典例及数学模型运输问题的典例及数学模型一、一、 引例引例某公司从三个产地某公司从三个产地 , , 将产品运往四个销地将产品运往四个销地 , , ,各产地的产量,各销地的销量,及各产地往各销,各产地的产量,各销地的销量,及各产地往各销地的运费单价如表所示。应如何调运可使运费最小?地的运费单价如表所示。应如何调运可使运费最小? 1A2A
2、1B2B3B3A4B 销地 运费单价产地B1B2B3B4产量(吨)A13113107A219284A3741059 销量(吨)36562022-8-54解:解:从表中可知:总产量从表中可知:总产量 = = 总销量。这是一个产销平衡的总销量。这是一个产销平衡的 运输问题。假设运输问题。假设 表示从产地表示从产地 运往销地运往销地 的产的产 品数量,品数量, 建立如下表格:建立如下表格:ijxij. 4 , 3 , 2 , 1; 3 , 2 , 1ji于是可建立如下的数学模型于是可建立如下的数学模型: 销地 运费单价产地B1B2B3B4产量(吨)A13113107A219284A3741059 销
3、量(吨)365611x12x13x21x22x23x31x32x33x14x24x34x2022-8-55目标函数目标函数:34333231242322211413121151047829103113xxxxxxxxxxxxMinZ约束条件:约束条件:947343332312423222114131211xxxxxxxxxxxx产量约束产量约束销量约束销量约束20204 , 3 , 2 , 1; 3 , 2 , 1, 06563342414332313322212312111jixxxxxxxxxxxxxij2022-8-56设有设有m个产地,分别为个产地,分别为 ; n 个销地,分别是个销地
4、,分别是 ;从产地从产地 运往销地运往销地 的单位运价是的单位运价是 ,运量,运量 是产地是产地 的产量;的产量; 是销地是销地 的销量。的销量。 mAAA,.,21nBBB,.,21iAjBijcijxisiAjdjB二、二、一般运输问题数学模型一般运输问题数学模型则该运输问题的模型如下:则该运输问题的模型如下:2022-8-57njmixmisxnjdxtsxcfMinijinjijjmiijminjijij,.,1,.1,0,.1,.,1.1111 说明说明:当:当 时,称其为产销平衡的运输问题,时,称其为产销平衡的运输问题,否则产销不平衡。否则产销不平衡。njjmiids112022-
5、8-58说明说明:从上述模型可以看出:从上述模型可以看出:(1)这是一个线性规划的模型;)这是一个线性规划的模型;(2)变量有)变量有mn个;个;(3)约束条件有)约束条件有 m+n 个;个;(4)系数矩阵非常稀疏;系数矩阵的秩一般为(系数矩阵非常稀疏;系数矩阵的秩一般为(m+n-1),m+n-1), 而非而非m+n 。若直接用单纯形法求解,显然单纯形表比较庞大,于是在若直接用单纯形法求解,显然单纯形表比较庞大,于是在单纯形法的基础上创建了表上作业法求解运输问题这一特单纯形法的基础上创建了表上作业法求解运输问题这一特殊的线性规划问题殊的线性规划问题 2022-8-59 从第一节的运输问题的数学
6、模型可知,运输问题实际上从第一节的运输问题的数学模型可知,运输问题实际上也属于线性规划,但由也属于线性规划,但由于于运输问题的特殊性(变量个数较多,运输问题的特殊性(变量个数较多,系数矩阵的特点),如果用单纯形表格方法迭代,计算量很系数矩阵的特点),如果用单纯形表格方法迭代,计算量很大。今天介绍的大。今天介绍的 “表上作业法表上作业法”,是针对运输问题的特殊求解,是针对运输问题的特殊求解方法,实质还是单纯形法,但减少了计算量。方法,实质还是单纯形法,但减少了计算量。 表上作业法表上作业法适用于求解产销平衡的运输问题。(产销不平适用于求解产销平衡的运输问题。(产销不平衡的问题可转化为平衡问题)衡
7、的问题可转化为平衡问题)2 2 运输问题的表上作业法运输问题的表上作业法2022-8-510表上作业法表上作业法 一般步骤一般步骤:1、找出初始基本可行解;、找出初始基本可行解;2、检查各非基变量的检验数,是否达到最优性条件,若达到,则得最优、检查各非基变量的检验数,是否达到最优性条件,若达到,则得最优解;否则解;否则 转第三步;转第三步;3、确定出基变量、进基变量,用闭回路方法进行调整,得到新的基可、确定出基变量、进基变量,用闭回路方法进行调整,得到新的基可 行解;行解;4、重复第二、第三步,直至得到最优解。、重复第二、第三步,直至得到最优解。2022-8-511一、确定初始基本可行解:一、
8、确定初始基本可行解: 对于有对于有m m个产地个产地n n个销地的产销平衡问题,有个销地的产销平衡问题,有m m个关于产量个关于产量的约束方程和的约束方程和n n个关于销量的约束方程。表面上,共有个关于销量的约束方程。表面上,共有m+nm+n个个约束方程。约束方程。 但由于产销平衡,其模型最多只有但由于产销平衡,其模型最多只有m+n-1m+n-1个独立的约束方个独立的约束方程,所以运输问题实际上有程,所以运输问题实际上有m+n-1m+n-1个基变量个基变量。在。在m mn n的产销的产销平衡表上给出平衡表上给出m+n-1m+n-1个数字格,其相对应的调运量的值即为个数字格,其相对应的调运量的值
9、即为基变量的值。基变量的值。2022-8-512 销地 运费单价产地B1B2B3B4产量(吨)A13113107A219284A3741059 销量(吨)3656 那么在该例中,应有那么在该例中,应有 3+4-1=63+4-1=6个基变量。个基变量。2022-8-5131.最小元素法最小元素法 最小元素法的思想是就近供应,即对单位运价最小最小元素法的思想是就近供应,即对单位运价最小的变量分配运输量。的变量分配运输量。 在表上找到单位运价最小的在表上找到单位运价最小的x x2121,并使,并使x x2121取尽可能大取尽可能大的值,即的值,即x x2121=3,=3,把把A A1 1的产量改为的
10、产量改为1 1,B B1 1的销量改为的销量改为0 0,并,并把把B B1 1列划去。在剩下的列划去。在剩下的3 33 3矩阵中再找最小运价,同矩阵中再找最小运价,同理可得其他的基本可行解。理可得其他的基本可行解。 销地 运费单价产地B1B2B3B4产量(吨)A13113107A219284A3741059 销量(吨)3656 销地产地 B1 B2 B3 B4 产量 A1 4 37 3 0 A2 3 1 4 1 0 A3 6 39 3 0 销量 3 0 6 0 5 4 0 6 3 0 20203113108510294712022-8-515表中填表中填有数字的格有数字的格对应于对应于基变量基
11、变量( (取值即为格中数字),而取值即为格中数字),而空格空格对应对应的是的是非基变量非基变量(取值为零)(取值为零). .n在求初始基本可行解时要在求初始基本可行解时要注意注意的一个问题:的一个问题: 当我们取定当我们取定x xijij的值之后,会出现的值之后,会出现A Ai i的产量与的产量与B Bj j的销量都改为零的情的销量都改为零的情况,这时只能划去况,这时只能划去A Ai i行或行或B Bj j列,但不能同时划去列,但不能同时划去A Ai i行与行与B Bj j列。列。(或者在同时划去(或者在同时划去A Ai i行与行与B Bj j列时,在该行或该列的任意空格处填加一列时,在该行或
12、该列的任意空格处填加一个个0 0。)。) 这样可以保证填过数或零的格为这样可以保证填过数或零的格为m+n-1m+n-1个,即保证基变量的个数为个,即保证基变量的个数为m+n-1m+n-1个。个。2022-8-5162.Vogel法法 Vogel法的思想是法的思想是:一地的产品如果不能按照最小运一地的产品如果不能按照最小运费就近供应,就考虑次小运费,这就有差额,差额越大,费就近供应,就考虑次小运费,这就有差额,差额越大,说明不能按最小运费调运时,运费增加得越多。因而差说明不能按最小运费调运时,运费增加得越多。因而差额越大处,就应当采用最小运费调运。额越大处,就应当采用最小运费调运。 销地 运费单
13、价产地B1B2B3B4产量(吨)A13113107A219284A3741059 销量(吨)36562022-8-517 销地产地 B1 B2 B3 B4 A1 5 20 0 0 7 A2 3 11 1 1 6 A36 31 2222 5 1111 3322 20203113102947110852022-8-518二二、最优解的判别、最优解的判别 判别解的最优性需要:判别解的最优性需要:计算检验数。计算检验数。方法有两种方法有两种 闭回路:闭回路:是在已给出的调运方案的运输表上从一个代表是在已给出的调运方案的运输表上从一个代表非基变量的空格出发,沿水平或垂直方向前进,遇到代表非基变量的空格出
14、发,沿水平或垂直方向前进,遇到代表基变量的填入数字的格可转基变量的填入数字的格可转9090度(当然也可以不改变方向)度(当然也可以不改变方向)继续前进,这样继续下去,直至回到出发的那个空格,由继续前进,这样继续下去,直至回到出发的那个空格,由此形成的封闭折线叫做此形成的封闭折线叫做闭回路闭回路。一个空格存在唯一的闭回一个空格存在唯一的闭回路。路。1 1.闭回路法闭回路法因为任意非基向量均可表示为基向量的唯一线性组因为任意非基向量均可表示为基向量的唯一线性组合,因此对于任意空格都合,因此对于任意空格都能够找到、并且只能找到能够找到、并且只能找到唯一的唯一的一条闭回路。一条闭回路。 销地产地 B1
15、 B2 B3 B4 产量 A1 4 3 7 A2 3 1 4 A363 9 销量 3 6 5 6 108531131029471 销地产地 B1 B2 B3 B4 产量 A1(+)1 4 (-) 3 7 A2(-) 3 1 (+) 4 A363 9 销量 3 6 5 6 1085311310294712022-8-520 销地产地 B1 B2 B3 B4 产量 A1(+)1 4 (-) 3 7 A2(-) 3 1 (+) 4 A363 9 销量 3 6 5 6 108531131029471从非基变量从非基变量 出发,找到一个闭回路如上表所示。回路有四出发,找到一个闭回路如上表所示。回路有四个
16、顶点,除个顶点,除 外,其余都为基变量。外,其余都为基变量。调整调运量:调整调运量: ,运费增加了,运费增加了3 3元;元; ,运费减少,运费减少3 3元元 ,运费增加,运费增加2 2元;元; ,运费减少,运费减少1 1元元调整后,调整后,总运费增加总运费增加:3-3+2-1=13-3+2-1=1元。元。说明如果让说明如果让 为基变量,运费就会增加,其增加值为基变量,运费就会增加,其增加值1 1作为作为 的的检验数检验数,111x123x113x11x121x11x11x11x2022-8-521闭回路法计算检验数:闭回路法计算检验数:就是对于代表非基变量的空格就是对于代表非基变量的空格(其调
17、运量为零),把它的调运量调整为(其调运量为零),把它的调运量调整为1 1,由于产销平衡的,由于产销平衡的要求要求, ,必须对这个空格的闭回路中的各顶点的调运量加上或减必须对这个空格的闭回路中的各顶点的调运量加上或减少少1 1。最后计算出由这些变化给整个运输方案的总运输费带来。最后计算出由这些变化给整个运输方案的总运输费带来的变化。以这个变化的数值,作为各空格(非基变量)的检的变化。以这个变化的数值,作为各空格(非基变量)的检验数。验数。判别最优解准则:判别最优解准则:如果所有代表非基变量的空格的检验如果所有代表非基变量的空格的检验数都大于等于零,则已求得最优解;否则继续改进找出最优数都大于等于
18、零,则已求得最优解;否则继续改进找出最优解。解。2022-8-5222.2.位势法位势法 (1 1)对运输表上的每一行赋予一个数值)对运输表上的每一行赋予一个数值 ,对每一列赋予一个数值对每一列赋予一个数值 ,称为行(列,称为行(列) )位势。位势。(2 2)行(列)行(列) )位势的数值是由基变量的检验数所决位势的数值是由基变量的检验数所决定的,即定的,即基变量基变量要满足:要满足: 非基变量非基变量 的检验数就可以用公式的检验数就可以用公式 求出。求出。0jiijijvucjiijijvuciujvijx 销地产地 B1 B2 B3 B4 ui A1 1 2 4 3 0 A2 3 1 1
19、-1 -1 A3 10 6 12 3 -5 vj 2 9 3 10 311310851029471 销地产地 B1 B2 B3 B4 产量 A1 4 3 7 A2 3 1 4 A363 9 销量 3 6 5 6 1085311310294712022-8-524 我们先给我们先给u u1 1赋个任意数值,不妨设赋个任意数值,不妨设u u1 1=0=0,则从基变,则从基变量量x x1111的检验数求得的检验数求得 v v3 3=c=c1313-u-u1 1=3-0=3 =3-0=3 。同理可以求得同理可以求得 v v4 4=10=10,u u2 2= -1= -1,等等见上表。,等等见上表。检验
20、数的求法,即用公式检验数的求法,即用公式 ,如如 。 销地产地 B1 B2 B3 B4 ui A1 1 2 4 3 0 A2 3 1 1 -1 -1 A3 10 6 12 3 -5 vj 2 9 3 10 311310851029471jiijijvuc1203111111vuc2022-8-525位势法计算检验数:位势法计算检验数: 检验数:检验数: ijnmijijijijBijijPvvuucYPcPBCc),.,(1,.,11又因为基变量的检验数为又因为基变量的检验数为0 0,于是由(,于是由(m+n-1)m+n-1)个基变个基变 量的检验数量的检验数可解出可解出 ,进而计算其他非基,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 第三 运输 问题 ppt 课件
限制150内