运筹学-第2章运输问题.ppt

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

1、2021/7/161第二章运输问题(TransportationProblem,TP)运输问题的数学模型(单一物品的调度运输问题。)运输问题的求解产销平衡的运输问题求解产销不平衡的运输问题求解应用举例软件应用2021/7/1622.1运输问题的数学模型例1现需将三个供应地KansasCity、Omaha、DesMoines的物品运往三个货物需求地Chicago、St.Louis、Cincinnati，各供应地的供应量、各需求地的需求量和各供应地运往各需求地的每单位物品的运费如表。问如何安排运输，可是总费用最小？ToFromKansasCi

2、tyOmahaDesMoinesDemandChicagoSt.LouisCincinnatiSupply67481151011122001003006002751751502021/7/163设，从供应地调往需求地的运输量销地产地B1B2…Bn产量A1x11x12…x1na1A2x21x22…x2na2………………Amxm1xm2…xmnam销量b1b2…bnc11c12cm1c21c22c2nc1ncmncm2设xij为从产地Ai运往销地Bj的运输量2021/7/165模型一般形式：显然，运输问题是一类特殊的线性规划问题等式约束供应地

3、约束需求地约束总产量=总销量供需平衡关于运输问题的基本结论：定理1:设有m个产地n个销地且产销平衡的运输问题，则基变量数为m+n-1。证明(略)原因是:虽有m+n个约束条件，但由于总产量=总销量，导致只有m+n-1个是独立的。因此有一个是多余的。注：上述定理说明：解中非零变量的个数不超过m+n-1.因此：非基变量的个数为：mn-(m+n-1)定理2运输问题一定有最优解。原因：有可行解xij=aibj/Q.且有下界.2021/7/1672.2运输问题的求解--表上作业法产销平衡的运输问题求解针对运输问题的特点，设计了一个方法--表上作业法。

4、它是一种求解运输问题的特殊方法，其实质是单纯形法。步骤描述方法第一步求初始基行可行解（初始调运方案）表上给出m+n-1个数字格最小元素法、西北角法、元素差额法、第二步求检验数并判断是否得到最优解当非基变量的检验数σij全都非负时得到最优解，若存在检验数σij<0，说明还没有达到最优，转第三步。计算表中空格检验数闭回路法和位势法第三步调整运量，即换基，选一个变量出基，对原运量进行调整得到新的基可行解，转入第二步表上调整（闭回路调整）2021/7/168产销平衡的运输问题2021/7/169求初始基本可行解---西北角法优先满足运输表中西北角

5、(即左上角)上空格的供销需求.5025ToFromKansasCityOmahaDesMoinesDemandChicagoSt.LouisCincinnatiSupply6748115101112200100300600275175150150100275特点：数字格（行数+列数-1），空格（其余）2021/7/1610求初始基本可行解---最小元素法就近供应，即从单位运价最小的地方开始供应（调运），然后次小，直到最后供完为止。175125ToFromKansasCityOmahaDesMoinesDemandChicagoSt.Lou

6、isCincinnatiSupply67481151011122001003006002751751502575200特点：数字格（行数+列数-1），空格（其余）2021/7/1611求初始基本可行解----伏格尔法对最小元素法进行了改进，考虑到产地到销地的最小运价和次小运价之间的差额，如果差额很大，就选最小运价先调运，否则会增加总运费。避免最小元素法有可能出现“顾此失彼”的坏事情。ToFromKansasCityOmahaDesMoinesDemandChicagoSt.LouisCincinnatiSupply674811510111

7、220010030027517515017510025150150特点：数字格（行数+列数-1），空格（其余）第1步求初始方案-方法3:沃格尔(Vogel)法单位销地运价产地产量行差额311310719284741059销量3656列差额71135215××第1步求初始方案-方法3:沃格尔(Vogel)法单位销地运价产地产量行差额311310719284741059销量3656列差额7135275×××3×第1步求初始方案-方法3:沃格尔(Vogel)法单位销地运价产地产量行差额311310719284741059销量3656列差额113

8、515×××3×631××2该方案的总运费:(1×3)＋(4×6)＋(3×5)＋(2×10)＋(1×8)＋(3×5)＝85元2021/7/1615求最优解闭合回路法—阅读教科书位势法2021/