管理运筹学 04 运输问题.ppt

1.1.运输问题的内涵：运输问题不仅仅是运输问题的内涵：运输问题不仅仅是把某种商品从若干个产地运至若干个销把某种商品从若干个产地运至若干个销地而使总运费最小的问题；从更广义上地而使总运费最小的问题；从更广义上讲，运输问题是具有一定模型特征的线讲，运输问题是具有一定模型特征的线性规划问题。性规划问题。2.2.运输问题的数学模型运输问题的数学模型3.3.运输问题的求解运输问题的求解4.4.运输问题的拓展及应用运输问题的拓展及应用2023/1/222.运输问题的数学模型2023/1/22第46页例4-12023/1/22例4-1的数学模型2023/1/223.运输问题的求解1.求解方法：表上作业法求解方法：表上作业法2.表上作业法的基本步骤表上作业法的基本步骤:(1)找出初始基可行解找出初始基可行解；(2)求检验数并判断最优性；求检验数并判断最优性；(3)确定入基变量和出基变量；确定入基变量和出基变量；(4)调整运输方案；调整运输方案；(5)重复重复24，直至最优。，直至最优。2023/1/22找出初始基可行解1.1.最小元素法最小元素法 (1)(1)基本思想：就近供应基本思想：就近供应 (2)(2)基本步骤基本步骤 (3)3)例例4-14-12.2.伏格尔法伏格尔法 (1)(1)基本思想：机会成本基本思想：机会成本 (2)(2)基本步骤基本步骤 (3)3)例例4-14-12023/1/22最小元素法的基本步骤1.1.找出最小运价，确定供求关系，最大找出最小运价，确定供求关系，最大量的供应量的供应 ；2.2.划掉已满足要求的行或划掉已满足要求的行或(和和)列，如果列，如果需要同时划去行和列，必须要在该行或需要同时划去行和列，必须要在该行或列的任意位置填个列的任意位置填个“0”“0”；3.3.在剩余的运价表中重复在剩余的运价表中重复1 1、2 2两步，直两步，直到得到初始基可行解。到得到初始基可行解。2023/1/22例4-1的最小元素法2023/1/22例4-1的最小元素法2023/1/22例4-1的最小元素法2023/1/22例4-1的最小元素法2023/1/22例4-1的最小元素法2023/1/22例4-1的最小元素法2023/1/22伏格尔法的基本步骤1.1.计算每行、列两个最小运价的差；计算每行、列两个最小运价的差；2.2.找出最大差所在的行或列；找出最大差所在的行或列；3.3.找出该行或列的最小运价，确定供求关找出该行或列的最小运价，确定供求关系，最大量的供应系，最大量的供应 ；4.4.划掉已满足要求的行或划掉已满足要求的行或(和和)列，如果列，如果需要同时划去行和列，必须要在该行或需要同时划去行和列，必须要在该行或列的任意位置填个列的任意位置填个“0”“0”；5.5.在剩余的运价表中重复在剩余的运价表中重复1414步，直到得步，直到得到初始基可行解。到初始基可行解。2023/1/22例4-1的伏格尔法2023/1/22例4-1的伏格尔法2023/1/22例4-1的伏格尔法2023/1/22例4-1的伏格尔法2023/1/22例4-1的伏格尔法2023/1/22例4-1的伏格尔法2023/1/22求检验数并判断最优性1.闭合回路法：从任意一个空格（非基变量）出发，沿着行或列寻找的一条除此空格之外其余顶点均为有数字格（基变量）的回路。空格的闭合回路有且唯一，有数字格不存在闭合回路。2.位势法：行因子i，列因子j，使每一个基变量有cij=i+j。3.判断最优性：若所有的检验数均大于等于零，已得最优方案；否则，进行方案调整。2023/1/22闭合回路法的基本步骤1.1.找出某一空格的闭合回路；找出某一空格的闭合回路；2.2.从该空格开始在闭合回路上给各个顶从该空格开始在闭合回路上给各个顶点进行点进行”+“”+“、”-“”-“间隔标号间隔标号；3.3.计算空格的检验数计算空格的检验数 空格检验数空格检验数=c cij ij(+)-(+)-c cij ij(-)(-)4.4.重重复复1313，直至求得全部的直至求得全部的检验数。检验数。2023/1/22例4-1(最小元素法)2023/1/22闭合回路法求检验数 2023/1/22闭合回路法求检验数 2023/1/22闭合回路法求检验数 2023/1/22例4-1(伏格尔法)2023/1/22闭合回路法求检验数2023/1/22位势法的基本步骤1.1.把基变量对应的运价拿来；把基变量对应的运价拿来；2.2.任意取一个位势因子并赋予一个任意值任意取一个位势因子并赋予一个任意值；3.3.余下的所有因子可根据基变量的运价余下的所有因子可根据基变量的运价c cij ij =i i +j j 来唯一确定；来唯一确定；4.4.计算空格检验数计算空格检验数 ij ij=c cij ij -(i i +j j)。2023/1/22例4-1(最小元素法)2023/1/22位势法求检验数 2023/1/22位势法求检验数 2023/1/22例1(伏格尔法)2023/1/22位势法求检验数 2023/1/22位势法求检验数2023/1/22确定入基变量和出基变量1.确定入基变量确定入基变量：具有最大绝对值的负检：具有最大绝对值的负检验数所对应的变量即为入基变量。验数所对应的变量即为入基变量。2.2.确定出基变量确定出基变量：在入基变量所处的闭合：在入基变量所处的闭合回路上，让入基变量增加，由于供求平衡回路上，让入基变量增加，由于供求平衡关系，带关系，带“+”“+”标号的基变量将随之增加；标号的基变量将随之增加；而带而带“-”“-”标号的基变量将随之减少，最标号的基变量将随之减少，最先减少为零的基变量即为出基变量先减少为零的基变量即为出基变量。2023/1/22确定入基变量2023/1/22确定出基变量2023/1/22调整运输方案1.1.在入基变量所在的闭合回路上，带在入基变量所在的闭合回路上，带 “+”“+”标号的格增加标号的格增加 x x出出 ，带带“-”“-”标号标号的格减少的格减少x x出出 。注意：出基变量减少后的。注意：出基变量减少后的 “0 0”不要保留在表格中，如果同时有多不要保留在表格中，如果同时有多个而带个而带“-”“-”标号的格减少为零，可人为标号的格减少为零，可人为确定之一为出基变量，在表格中保留其它确定之一为出基变量，在表格中保留其它“0 0”。2.2.对调整后的方案求检验数并判断其最对调整后的方案求检验数并判断其最优性。优性。3.3.重复重复1212两步，直至得到最优方案两步，直至得到最优方案。2023/1/22运输方案2023/1/22调整后的运输方案2023/1/22最优运输方案2023/1/224.运输问题的拓展及应用1.1.产销不平衡的运输问题产销不平衡的运输问题 (1)(1)产大于销产大于销 (2)(2)销大于产销大于产2.2.运输问题的应用运输问题的应用 (1)(1)第第5959页例页例4-44-4 (2)(2)第第6060页例页例4-54-5 (3)(3)第第6262页习题页习题6 6 (4)(4)第第6060页例页例4-64-62023/1/22产大于销的运输问题2023/1/22产大于销的运输问题2023/1/22销大于产的运输问题2023/1/22销大于产的运输问题2023/1/22第59页例4-42023/1/22第59页例4-42023/1/22第59页例4-42023/1/22第60页例4-52023/1/22第60页例4-52023/1/22第62页习题6已知某厂每月可生产甲产品已知某厂每月可生产甲产品270270吨，先运至吨，先运至A1A1、A2A2、A3A3三个仓库，然后在分别供应三个仓库，然后在分别供应B1B1、B2B2、B3B3、B4B4、B5B5五个用户。已知五个用户。已知仓库容量分别为仓库容量分别为5050、100100、150150吨，吨，各用户的需要量分别为各用户的需要量分别为2525、105105、6060、3030、7070吨。吨。已知从该厂经各仓库然后供应各用户的运费如下表已知从该厂经各仓库然后供应各用户的运费如下表所示，试确定一个使总运费最少的调运方案。所示，试确定一个使总运费最少的调运方案。2023/1/22第62页习题62023/1/22第62页习题62023/1/22第60页例4-62023/1/22第60页例4-62023/1/22第60页例4-62023/1/22第60页例4-62023/1/22