运筹学运输问题-2(1).pdf

回 顾  运输问题的数学模型及其特点；  运输问题解法—表上作业法； （两个表格：产销平衡表，单位运价表）  表上作业法中初始基可行解的确定方 法：最小元素法；Vogel法（最大差额 法）  闭回路的建立与闭回路法求解检验数 1 1、运输问题的数学模型 m n min z  c ij x ij i 1 j 1 . . s t  n , i 1,2 , , m  x ij a i  j 1  m   x ij b j , j 1,2 , , n  i 1  x ij  0 , i 1,2 , , m ; j 1,2 , , n  m n  (  a b ) i j  i 1 j 1 2 2、最小元素法确定初始基可行解的步骤  步骤一：确定第一个基变量 方法：（1）从单位运价表中，找出最小运价；（2 ） 对于最小运价处，用所在行的产量最大限度满足销售量 （所在列）的需求。将满足之数填入产销平衡表中相应 填入产销平衡表中相应 的位置处；（3 ）观察产和销的关系：1）如果产量用 的位置处 完，则划去所在行的单位运价信息表示此产地不能再供 应其他地方 ；如果销量得到满足，则划去所在列的单位 运价信息表示此销售地不再有需求 。（注意产量和销量 的变化）  步骤二：确定第二个基变量 方法：在剩下的单位运价信息中，寻找最小值。按 照上述方法进行操作。 3 3、伏格尔方法（Vogel ）确定初始基可行解 主旨：最大差额处，优先按最小运价进行调运。 第一步：计算单位运价表中同行、同列的最小运费与次小 运费之差，分别列在单位运价表的最右列和最下行 （行 差和列差）。 第二步：对行差和列差进行对比，找出最大差额。以与最 大差额值同行（或同列）的最小运价为准，倾所在行的 产量，最大限度地满足所在列的需求；一旦需求（或库 存）被彻底满足（或库存调光），则随即划去该列（或 行）的所有运价信息。（注意产量和销量的变化） 第三步：重新计算同行同列的最小运费与次小运费之差， 并对其它未被确定调拨值的行列，重复第二步的处理， 直至构造出某初始调拨方案 （初始解）。 4 4、最优性检验的核心思想  1、最优检验判断思路：确定初始基可行解后，调 查非基变量取值变化对总运费的影响。  2、实现方法：在确定的初始基可行解基础上，当 非基变量有取值时，考虑总的运费的变化情况？ （1）如果所有情况下总费用均增加，证明初始方案为最 优； （2 ）一旦出现了总费用降低，代表给该非基变量安 排运量可更优，说明最初方案需要优化。  3、需要解决的问题：当非基变量取值时，为保证 产销平衡表上的产销平衡，会引起已确定的基变 量的连锁变化，导致相应的行或列基变量的波 动。→需要靠闭回路法来确定基变量的变动情