运筹学课件-第三章运输问题.ppt
《运筹学课件-第三章运输问题.ppt》由会员分享,可在线阅读,更多相关《运筹学课件-第三章运输问题.ppt(93页珍藏版)》请在三一办公上搜索。
1、第三章 运输问题,一、运输问题及其数学模型网络图、线性规划模型、运输表二、用表上作业法求解运输问题初始解、解的检验、解的改进三、运输问题的进一步讨论产销不平衡、有运转四、应用举例,一、运输问题及其数学模型,供应地,需求地,例:,运输问题网络图,运输问题数学模型,供应地约束,需求地约束,运输问题线性规划模型,运输问题的描述:设某种物品有m个产地A1,A2,.,Am,各产地的产量分别是a1,a2,.,am;有n个销地B1,B2,.,Bn,各销地的销量分别为b1,b2,.bn。假定从产地Ai(i=1,2,m)向销地出Bj(jl,2,.n)运输单位物品的运价是cij,问怎样调运这些物品才能使总运费最小
2、?,运输问题信息表,运输问题线性规划模型,运价表,如果a=b,则称为产销平衡运输问题,否则,称为产销不平衡运输问题。,运输问题线性规划模型,产销平衡运输问题的数学模型表示:,该模型是一个线性规划模型,可以用单纯形法求解。但是变量数目非常多。如3个产地,4个销地。变量数目会有19个之多。因此应该寻求更简便的解法。为了说明适于求解运输问题的更好的解法,先分析运输问题数学模型的特点。,运输问题线性规划模型,运输问题线性规划模型,运输问题数学模型的特点:1运输问题有有限最优解,是一个可行解。同时,目标函数有下界,且不会趋于负无穷。所以,必存在有限最优解。,运输问题线性规划模型,2运输问题约束条件的系数
3、矩阵,n 行,m 行,系数列向量:,运输问题线性规划模型,由此可知,运输问题具有下述特点:(1)约束条件系数矩阵的元素等于0或1;(2)约束条件系数矩阵的每一列有两个非零元素,这对应于每一个变量在前m个约束方程中出现一次,在后n个约束方程中也出现一次;对产销平衡运输问题,除上述两个特点外,还有以下特点:(3)所有结构约束条件都是等式约束;(4)各产地产量之和等于各销地销量之和。秩(A)=m+n-1 运输问题的基可行解中应包含m+n-1个基变量.,例1 某部门有3个生产同类产品的工厂(产地),生产的产品由4个销售点(销地)出售,各工厂的生产量、各销售点的销售量(假定单位均为t)以及各工厂到各销售
4、点的单位运价(元/t)示于表32中,要求研究产品如何调运才能使总运费最小。,用xij表示由第i个产地运往第j个销地的产品数量,即可写出该问题的数学模型:,运输问题线性规划模型,3.运输问题的解(1)解x必须满足模型中的所有约束条件;(2)基变量对应的约束方程组的系数列向量线性无关;(3)解中非零变量xij的个数不能大于(m+n-1)个,原因是运输问题中虽有(m+n)个结构约束条件,但由于总产量等于总销量,故只有(m+n-1)个结构约束条件是线性独立的;(4)为使迭代顺利进行,基变量的个数在迭代过程中保持为(m+n-1)个。运输问题解的每一个分量,都唯一对应其运输表中的一个格 填有数字的格 空格
5、,下表给出了例1的一个解。,二、表上作业法,表上作业法是一种迭代法,迭代步骤为:1、先按某种规则找出一个初始解(初始调运方案);2、再对现行解作最优性判别;3、若这个解不是最优解,就在运输表上对它进行调整改进,得出个新解;4、再判别,再改进;5、直至得到运输问题的最优解为止。迭代过程中得出的所有解都要求是运输问题的基可行解。,二、表上作业法,例:,1、初始基可行解最小元素法,思路:为了减少运费,应优先考虑单位运价最小(或运距员短)的供销业务,最大限度地满足其供销量。在可供物品已用完的产地或需求已全部满足的销地,以后将不再考虑。然后,在余下的供、销点的供销关系中,继续按上述方法安排调运,直至安排
6、完所有供销任务,得到一个完整的调运方案(完整的解)为止。这样就得到了运输问题的一个初始基可行解(初始调运方案)。由于该方法基于优先满足单位运价(或运距)最小的供销业务,故称为最小元素法。,例:,1、初始基可行解最小元素法,8,2,10,14,8,6,所以,初始基可行解为:目标函数值Z246,练习题,12,13,13,19,1,2,1、初始基可行解西北角法,在满足约束条件下尽可能的给最左上角的变量最大值.,8,8,6,4,8,14,所以,初始基可行解为:目标函数值Z372,练习题,8,13,13,14,6,6,1、初始基可行解沃格尔法,最小元素法,有时按某一最小单位运价优先安排物品调运时,却可能
7、导致不得不采用运费很高的其他供销点,从而使整个运输费用增加。,1、初始基可行解沃格尔法,对每一个供应地或销售地,均可由它到各销售地或到各供应地的单位运价中找出最小单位运价和次小单位运价,并称这两个单位运价之差为该供应地或销售地的罚数。沃格尔法基本思想:在罚数最大处采用最小运费调运。如果罚数的值不大,当不能按最小单位运价安排运输时造成的运费损失不大;反之,如果罚数的值很大,不按最小运价组织运输就会造成很大损失,故应尽量按最小单位运价安排运输。沃格尔法就是基于这种考虑提出来的。,1、初始基可行解沃格尔法,计算步骤:1)分别算出各行、各列的罚数。2)从行、列中选出差额最大者,选择它所在行、列中的最小
8、元素,进行运量调整。3)对剩余行、列再分别计算各行、列的差额。返回1)、2)。,1、初始基可行解沃格尔法,14,所以,初始基可行解为:目标函数值Z244,8,8,12,2,4,练习题,思路:要判定运输问题的某个解是否为最优解,可仿照一般单纯形法,检验这个解的各非基变量(对应于运输表中的空格)的检验数,若有某空格(Ai,Bj)的检验数为负,说明将xij变为基变量将使运输费用减少,故当前这个解不是最优解。若所有空格的检验数全非负,则不管怎样变换解均不能使运输费用降低,即目标函数值已无法改进,这个解就是最优解。以最小元素法的初始解为例。假设产地A1供应1个单位的物品给销地B1。则解的变化和目标函数的
9、变化如何。,2、解的最优性检验闭回路法,2、解的最优性检验闭回路法,例:,8,2,10,14,8,6,1,2,1,10,12,-1,由此可知,为了求某个空格(非基变量)的检验数,先要找出它在运输表上的闭回路,这个闭回路的顶点,除这个空格外,其它均为填有数字的格(基变量格),它是由水平线段和竖直线段依次联接这些顶点构成的一封闭多边形。每个空格都唯一存在这样的一条闭回路。,特征:1.每个顶点都是转角点.2.每一边都是水平或垂直的.3.每一行(或列)若有闭回路的顶点,则必有两个.,某空格的检验数是以该空格为第一个顶点,某回路的奇数顶点运价和减去其偶数顶点运价和。,位于闭回路上的一组变量,它们对应的运
10、输问题约束条件的系数列向量线性相关,因而在运输问题基可行解的迭代过程中,不允许出现全部顶点由填有数字的格构成的闭回路。这就是说,在确定运输问题的基可行解时,除要求非零变量的个数为(mn1)个外,还要求运输表中填有数字的格不构成闭回路。,非基变量xij的检验数闭回路法(1),例:确定下列可行解的检验数,2、解的最优性检验对偶变量法,原问题,设其对偶变量为:,原问题系数矩阵:,对偶问题:,考虑原问题变量xj的检验数为:,假设已得到一个基可行解,其基变量为:,则有:,s=m+n-1,则运输问题变量xij的检验数为:,方程组有m+n-1个方程。因为运输表中每行和每列均有基变量,因此上面方程组含有全部m
11、+n个对偶变量。故解不唯一,其解称为位势。若上述方程的某组解满足对偶问题的所有条件,即:,此时,原问题与对偶问题均可行,故达到最优。其解分别为:,例:,8,2,10,14,8,6,练习题,3、解的改进闭回路调整法,改进的方法是在运输表中找出这个空格对应的闭回路,在满足所有约束条件的前提下,使xij尽量增大并相应调整此闭回路上其它顶点的运输量,以得到另一个更好的基可行解。,解改进的具体步骤为(1)以xij为换入变量,找出它在运输表中的闭回路;(2)以空格(Ai,Bj)为第一个奇数顶点,沿闭回路的顺(或逆)时针方向前进,对闭回路上的顶点依次编号;(3)在闭回路上的所有偶数顶点中,找出运输量最小的顶
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 课件 第三 运输 问题

链接地址:https://www.31ppt.com/p-6434596.html