运输问题的特殊解法.ppt

《运输问题的特殊解法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、表上作业法图上作业法第三章运输问题的特殊解法(TransportationProblem)第一节运输问题的表上作业法一、运输问题的数学模型及其特点设某种物品有m个产地A1,A2,…,Am，各产地的产量分别是a1,a2,…,am；有n个销地Bl,B2,…,Bn,各销地的销量分别为bl,b2,…,bn。假定从产地Ai(i＝1,2,…,m)向销地Bj(j＝1,2,…,n)运输单位物品的运价是cij，问怎样调运这些物品能使总运费最小?这是由多个产地供应多个销地的单品种物资运输问题。为直观清楚起见，可将数据汇总于产销平衡表和单位运价表中：销地产地12…n产量销地产地12…n平1a11c11c12…c1

2、n运衡2a22c21c22…c2n价表..................表mammcm1cm2…cmn销量b1b2…bn（1）产销平衡时矩阵形式（2）产大于销时（3）产小于销时特征运输问题的基本可行解中应包括m+n-1个基变量平衡运输问题必有可行解，也必有最优解二、表上作业法的思路和步骤步骤：1）确定初始调运方案2）解的最优性判断3）调整方案4）重复2）3）步，直到找到最优方案找到初始基可行解最优性判断调整找到新的基可行解重复2、3步直到找到最优解例1某部门有3个生产同类产品的工厂（产地），生产的产品由4个销售点出售，各工厂的有关资料如下表，问应怎样调运才使总运费最少?收点发点B1B2B3

3、B4产量B1B2B3B4A17311312A241928A3974105销量365620（一）确定初始调运方案1、最小元素法思路：就近供应，优先安排运价最小的收发点之间的物资调运量，然后次小，直到给出初始基可行解解题步骤：（1）在运价表中找到最小运价c1k（2）将的Al产品给Bk①若al>bk，则将al改写为al-bk，划掉bk，同时将运价表中k列的运价划掉②若al

4、标函数值为：z＝3×4＋12×3十1×3十2×1＋4×6十5×3＝92(元)314633①②③④⑤⑥313432、西北角法思路：该法优先满足运输表中西北角上空格的供销需求收点发点B1B2B3B4产量B1B2B3B4A17311312A241928A3974105销量365620342236对应的目标函数值为：z＝3×3＋11×4十9×2十2×2＋10×3十5×6＝135(元)3、伏格尔法思想：最小元素法为了节省一处的费用，有时可能造成在其他处要多花几倍的运费。伏格尔法考虑到，一地的产品假如不能按最小运费就近供应，就考虑次小运费，因此就会有一个差额。差额越大，说明不能按最小运费调运时，运费增加

5、越多。因而，对差额最大处，就应当采用最小运费调运解题步骤：（1）计算运输表中每一行和每一列的次小单位运价和最小运价之间的差值（2）从行或列差中选择最大者，选择它所在行或列中的最小元素clk，将Al的产品优先供应Bk，同时将运价表中已满足的行或列划掉。（3）如此重复(1)、(2)，直到分配完毕收点发点B1B2B3B4产量B1B2B3B4行差A17311312A241928A3974105销量3656205130116125243333125对应的目标函数值为：z＝3×2＋3×5十1×1十8×3＋4×6十5×3＝85(元)注：伏格尔法除确定供求关系的原则与最小元素法不同外，其余步骤与最小元素法相

6、同。与最优解的接近程度：伏格尔法、最小元素法、西北角法2（二）解的最优性检验求出各非基变量的检验数，判别是否均不小于0：如果是，则得到最优解，停止计算；否则转入下一步注：因为目标函数要求最小化，所以σij<0表示运费减少，σij>0表示运费增加。表格中有调运量的地方为基变量，空格处为非基变量。基变量的检验数σij＝0，需计算非基变量的检验数是否不小于0。1、闭回路法闭回路——以某一空格为起点，用水平线或垂直线向前画，碰到某一个数字格转90度后，继续前进，直到回到起始空格为止B1B2B3B4产量A1437A2314A3639销量365620空格处检验数的计算公式：[偶拐角点对应运价之和]-[奇

7、拐角点对应运价之和]利用最小元素法形成的初始调运方案进行说明：B1B2B3B4产量B1B2B3B4A1437311312A23141928A363974105销量3656202、位势法提出：闭回路法需要多次作闭回路，多次对照运价表，多次计算，繁琐复杂，特别是收发点多时尤为不便，故提出位势法——在运价表上直接操作解题步骤：（1）编制位势表在运输问题的单价表中的基变量处画圈，同时在表中增加一行（列位势）和一列（行