运筹学运输问题VIP免费

1回顾运输问题的数学模型及其特点；运输问题解法—表上作业法；（两个表格：产销平衡表，单位运价表）表上作业法中初始基可行解的确定方法：最小元素法；Vogel法（最大差额法）闭回路的建立与闭回路法求解检验数21、运输问题的数学模型32、最小元素法确定初始基可行解的步骤步骤一：确定第一个基变量方法：（1）从单位运价表中，找出最小运价；（2）对于最小运价处，用所在行的产量最大限度满足销售量（所在列）的需求。将满足之数填入填入产销平衡表产销平衡表中中相应的位置处相应的位置处；（3）观察产和销的关系：1）如果产量用完，则划去所在行的单位运价信息<表示此产地不能再供应其他地方>；如果销量得到满足，则划去所在列的单位运价信息<表示此销售地不再有需求>。（注意产量和销量的变化）步骤二：确定第二个基变量方法：在剩下的单位运价信息中，寻找最小值。按照上述方法进行操作。43、伏格尔方法（Vogel）确定初始基可行解主旨：最大差额处，优先按最小运价进行调运。第一步：计算单位运价表中同行、同列的最小运费与次小运费之差，分别列在单位运价表的最右列和最下行（行差和列差）。第二步：对行差和列差进行对比，找出最大差额。以与最大差额值同行（或同列）的最小运价为准，倾所在行的产量，最大限度地满足所在列的需求；一旦需求（或库存）被彻底满足（或库存调光），则随即划去该列（或行）的所有运价信息。（注意产量和销量的变化）第三步：重新计算同行同列的最小运费与次小运费之差，并对其它未被确定调拨值的行列，重复第二步的处理，直至构造出某初始调拨方案（初始解）。54、最优性检验的核心思想1、最优检验判断思路：确定初始基可行解后，调查非基变量取值变化对总运费的影响。2、实现方法：在确定的初始基可行解基础上，当非基变量有取值时，考虑总的运费的变化情况？（1）如果所有情况下总费用均增加，证明初始方案为最优；（2）一旦出现了总费用降低，代表给该非基变量安排运量可更优，说明最初方案需要优化。3、需要解决的问题：当非基变量取值时，为保证产销平衡表上的产销平衡，会引起已确定的基变量的连锁变化，导致相应的行或列基变量的波动。→需要靠闭回路法来确定基变量的变动情况。65、闭回路法的构造（1）闭回路：调运方案中由一个空格（非基变量）和若干个有数字格（基变量）的水平和垂直连线所组成的回路。（3）闭回路的构造方法：从选中的空格（非基变量）出发，沿水平或铅垂方向前进，确保只以途中的有数字格（基变量）为拐点实施转向，直到返回出发的空格（非基变量）。7闭回路形式86、利用闭回路法计算非基变量检验数方法•1）参考产销平衡表，建立非基变量检验数表，用于填写各非基变量的检验数；•2）以确定的初始（或前一可行）调运方案表为准，寻找每个非基变量的闭回路；•3）在每个非基变量的闭回路上，计算当非基变量由“0”变为“+1”时，基变量的取值变化规律（+1，还是-1）；•4）利用单位运价表中与闭回路相对应的运价信息，计算运费的变化情况（非基变量单位运价-∑处于奇数位置的基变量的单位运价+∑处于偶数位置的基变量的单位运价），即为非基变量检验数；•5）将非基变量检验数填入检验数表中相应位置。9销地产地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非基变量：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。10销地产地B1B2B3B4A112A21-1A31012非基变量检验数表非基变量A2B4的检验数小于0，表明在A2B4处安排运量可以带来更低的运费→如何调整?117、问题对于每一个非基变量，需要重复寻找闭回路，并计算“非基变量+1”时对总运费的影响→繁琐。当出现检验数<0，证明原初始方案或改进方案还不是最优→如何进行基变...