运筹学运输问题.ppt

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

1、回顾运输问题的数学模型及其特点；运输问题解法—表上作业法；（两个表格：产销平衡表，单位运价表）表上作业法中初始基可行解的确定方法：最小元素法；Vogel法（最大差额法）闭回路的建立与闭回路法求解检验数11、运输问题的数学模型22、最小元素法确定初始基可行解的步骤步骤一：确定第一个基变量方法：（1）从单位运价表中，找出最小运价；（2）对于最小运价处，用所在行的产量最大限度满足销售量（所在列）的需求。将满足之数填入产销平衡表中相应的位置处；（3）观察产和销的关系：1）如果产量用完，则划去所在行的单位运价信息<表示此产地不能再供应其他地方>；如果销量得到满足，则划去所在

2、列的单位运价信息<表示此销售地不再有需求>。（注意产量和销量的变化）步骤二：确定第二个基变量方法：在剩下的单位运价信息中，寻找最小值。按照上述方法进行操作。33、伏格尔方法（Vogel）确定初始基可行解主旨：最大差额处，优先按最小运价进行调运。第一步：计算单位运价表中同行、同列的最小运费与次小运费之差，分别列在单位运价表的最右列和最下行（行差和列差）。第二步：对行差和列差进行对比，找出最大差额。以与最大差额值同行（或同列）的最小运价为准，倾所在行的产量，最大限度地满足所在列的需求；一旦需求（或库存）被彻底满足（或库存调光），则随即划去该列（或行）的所有运价信息。（

3、注意产量和销量的变化）第三步：重新计算同行同列的最小运费与次小运费之差，并对其它未被确定调拨值的行列，重复第二步的处理，直至构造出某初始调拨方案（初始解）。44、最优性检验的核心思想1、最优检验判断思路：确定初始基可行解后，调查非基变量取值变化对总运费的影响。2、实现方法：在确定的初始基可行解基础上，当非基变量有取值时，考虑总的运费的变化情况？（1）如果所有情况下总费用均增加，证明初始方案为最优；（2）一旦出现了总费用降低，代表给该非基变量安排运量可更优，说明最初方案需要优化。3、需要解决的问题：当非基变量取值时，为保证产销平衡表上的产销平衡，会引起已确定的基变量

4、的连锁变化，导致相应的行或列基变量的波动。→需要靠闭回路法来确定基变量的变动情况。55、闭回路法的构造（1）闭回路：调运方案中由一个空格（非基变量）和若干个有数字格（基变量）的水平和垂直连线所组成的回路。（3）闭回路的构造方法：从选中的空格（非基变量）出发，沿水平或铅垂方向前进，确保只以途中的有数字格（基变量）为拐点实施转向，直到返回出发的空格（非基变量）。6闭回路形式76、利用闭回路法计算非基变量检验数方法1）参考产销平衡表，建立非基变量检验数表，用于填写各非基变量的检验数；2）以确定的初始（或前一可行）调运方案表为准，寻找每个非基变量的闭回路；3）在每个非基变

5、量的闭回路上，计算当非基变量由“0”变为“+1”时，基变量的取值变化规律（+1，还是-1）；4）利用单位运价表中与闭回路相对应的运价信息，计算运费的变化情况（非基变量单位运价-∑处于奇数位置的基变量的单位运价+∑处于偶数位置的基变量的单位运价），即为非基变量检验数；5）将非基变量检验数填入检验数表中相应位置。8销地产地B1B2B3B4产量A1非基变量1（3）非基变量2（11）4（3）3（10）7A23（1）非基变量3（9）1（2）非基变量4（8）4A3非基变量5（7）6（4）非基变量6（10）3（5）9销量3656利用闭回路法计算非基变量检验数方法A1B1非基变量

6、：A1B1+1，A1B3-1，A2B3+1，A2B1-1.运费影响：3-3+2-1=1>0（即为此非基变量的检验数）。A2B2非基变量：A2B2+1，A2B3-1，A1B3+1，A1B4-1，A3B4+1，A3B2-1.运费影响：9-2+3-10+5-4=1>0。非基变量4：A2B4-1，A1B4+1,A1B3-1,A2B3+1。运费影响：8-10+3-2=-1<0。9销地产地B1B2B3B4A112A21-1A31012非基变量检验数表非基变量A2B4的检验数小于0，表明在A2B4处安排运量可以带来更低的运费→如何调整?107、问题对于每一个非基变量，需要重复寻

7、找闭回路，并计算“非基变量+1”时对总运费的影响→繁琐。当出现检验数<0，证明原初始方案或改进方案还不是最优→如何进行基变量的调入调出？采用位势法一次全部计算出所有检验数给检验数<0的非基变量赋值，越大越好。但要考虑产销平衡问题。118、运输问题的校验方法2—位势法利用行位势和列位势两类数据，将检验数与单位运价联系起来12检验数方程λij=cij–ui–vjui，vj行位势列位势单位运价m个产地，n个销地时，则需要确定m个行位势，n个列位势13一般令基变量的λij=0，故确定ui与vj可借助基变量的位势方程组来确定ui+vj=cij（基变量对应的单位运价）它总共含

8、有m+n–