运筹学 第章运输问题.ppt

《运筹学 第章运输问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、Chapter3运输问题(TransportationProblem)运输问题的数学模型表上作业法运输问题的应用本章主要内容：1从m个发点向n个收点发送某种货物.发点的发量为，收点的收量为。由运往单位货物的运费为，问如何调配，才能使运费最省？问题的提出2表1产销平衡表上述数据可以汇总于表格中,如下:表2单位运价表3运输问题的数学模型设xij代表为从第i个产地调运给第j个销地的物资的数量.在产销平衡的条件下，即使总的运费支出最小，可以表为以下数学形式：4运输问题的约束方程组系数矩阵及特征矩阵A是一个m+n行mn列的矩阵，它的秩为m+n-1。运输

2、问题应该有m+n-1个基变量。3.xij的系数列向量为：m行n行5表上作业法6表上作业法的基本思路：确定初始调运方案最优性检验改进方案71确定初始基可行解运输问题确定初始基可行解，就是求出运输问题的初始调运方案.确定初始基可行解的方法有最小元素法伏格尔法8【例2-1】某公司经销甲产品,下设3个加工厂A1、A2、A3，产品分别运往销售点B1、B2、B3、B4，各工厂的日产量和各销售点的日需求量及各工厂到各销售点的运价如下表所示：（运输问题供需平衡表和运价表如下），求总运费最少的调运方案。销地产地B1B2B3B4发量（T）A13113107A21

3、9284A3741059收量（T）3656表3-39思路：为了减少运费，应优先考虑单位运价最小(或运距最短)的供销业务，最大限度地满足其供销量。在可供物品已用完的产地或需求已全部满足的销地，以后将不再考虑。然后，在余下的供、销点的供销关系中，继续按上述方法安排调运，直至安排完所有供销任务，得到一个完整的调运方案(完整的解)为止。这样就得到了运输问题的一个初始基可行解(初始调运方案)。由于该方法基于优先满足单位运价(或运距)最小的供销业务，故称为最小元素法。1、最小元素法101.最小元素法314633Z=4×3+3×10+3×1+1×2+6×4

4、+3×5=86该方案总运费：（思想：就近供应）不能同时划去行和列保证填有运量的格子为m+n-1表3-411最小元素法，有时按某一最小单位运价优先安排物品调运时，却可能在其他供销点多花几倍的运费，从而使整个运输费用增加。55552.沃格尔法沃格尔法考虑到：一个产地的产品假如不能按照最小运费就近供应，就考虑次小运费，这就有个差额。如果差额不大，当不能按最小单位运价安排运输时造成的运费损失不大；反之，如果差额很大，不按最小运价组织运输就会造成很大损失，故应尽量按最小单位运价安排运输。沃格尔法就是基于这种考虑提出来的。12沃格尔法计算步骤：1)分别算

5、出各行、各列的最小运费与次小运费的差额。2)从行、列中选出差额最大者，选择它所在行、列中的最小元素，进行运量调整。3)对剩余行、列再分别计算各行、列的差额。返回1)、2)。132.伏格尔法①2513①011表3-6[]6②213②0123③212③01[][]3④12④76[]521表3-5Z=85141若有两个以上相同的最大差值，可任取其一。2剩下一行或者一列有空格，填数字，不能划掉。3计算行差，列差时，已经划去的列或者行不再考虑。15销产B1B2B3产量A151812A224114A33674销量91011例用伏格尔法求初始调运方案16销

6、产B1B2B3产量A121012A231114A344销量91011初始调运方案172.2最优解的判别判别办法是计算空格(非基变量)的检验数,因为运输问题的目标函数是实现最小化,所以当所有空格处的检验数大于等于零时,为最优解.下面分别介绍两种计算检验数的方法:闭回路法(2)位势法18①闭回路法闭回路：从空格出发画水平(或垂直)直线，遇到填有运量的方格（数字格）可转90°，然后继续前进，直到到达出发的空格所形成的闭合回路。调运方案的任意空格一定存在唯一闭回路。销产B1B2B3B4供量A1527A2314A3639销量3656表3-7195104

7、7A38291A2103113A1B4B3B2B1销地产地633431计算最小元素法得到的初始基可行解的检验数(+1)(-1)(+1)(-1)(+1)×3+(-1)×3+(+1)×2+(-1)×1=1调整后总运费增加：空格处检验数为1表3-82051047A38291A2103113A1B4B3B2B1销地产地633431(+1)(-1)(+1)(-1)7-5+10-3+2-1=10调整后总运费增加：空格处检验数为10(-1)(+1)表3-921检验数表110121-12因为存在小于零的检验数,所以最小元素法给出的方案不是最优方案.表3-10

8、222.位势法位势：运输问题的对偶变量称为位势。因为m个供应点n个需求点的运输问题有m+n个约束，因此运输问题就有m+n个位势。行位势:关于供应点Ai的约束对应的对