运输问题的基本求解 方法:表上作业法 基本可行解 最优否 结束 换基 步骤: 1.确定初始基可行解(西北角法、最小元素法) 2最优性检验(闭回路法、位势法) 3解的改进(闭回路调整法)
16 运输问题的基本求解 方法：表上作业法 基本可行解 结束 换基 最优否 步骤： 1.确定初始基可行解（西北角法、最小元素法） 2.最优性检验（闭回路法、位势法） 3.解的改进（闭回路调整法）
初始基可行解的确定 求解运输问题的初始基可行解的基本步骤: (1)在产销平衡表中选一个单元x,令x=min(a,b}, 即A尽量满足B的需求,使一个约束方程得到满足, 将xn的值填入表中相应位置 (2)从a1和b中分别减去x;的值,即A在尽可能满足B 的需求后,调整A供给量和B需求量 (3)若a1=0,则划去对应行(A产品全部供给完), 若b;=0,则划去对应列(B需求全部满足),注意每 次只能划去一行或一列(即只去掉一个约束)。 (4)若产销平衡表中所有的行或列均被划去,则结束。 否则,在剩下的产销平衡表中选下一个变量,转步骤 (2)继续进行
17 初始基可行解的确定 求解运输问题的初始基可行解的基本步骤： （1）在产销平衡表中选一个单元xij，令xij =min{ai，bj}， 即Ai尽量满足Bj的需求，使一个约束方程得到满足， 将xij的值填入表中相应位置。 （2）从ai和bj中分别减去xij的值，即Ai在尽可能满足Bj 的需求后，调整Ai供给量和Bj需求量。 （3）若ai =0，则划去对应行（ Ai产品全部供给完）， 若bj =0，则划去对应列（ Bj需求全部满足），注意每 次只能划去一行或一列（即只去掉一个约束）。 （4）若产销平衡表中所有的行或列均被划去，则结束。 否则，在剩下的产销平衡表中选下一个变量，转步骤 （2）继续进行
最终产生的一组变量将满足下面的条件: (1)所有的变量x非负,且变量总数为 m+n-1 (2)所有的约束均得到满足 (3)所有的变量x不构成闭回路
18 最终产生的一组变量将满足下面的条件： （1）所有的变量xij非负，且变量总数为 m+n-1。 （2）所有的约束均得到满足。 （3）所有的变量xij不构成闭回路
西北角法 也称为左上角法,每次选取的x,都是左 上角第一个元素,也就是说,优先安排 运价表上编号最小的产地和销地之间的 运输业务。该方法的特点是x选取方便, 因而算法简单易实现。 19
19 西北角法 也称为左上角法，每次选取的xij ，都是左 上角第一个元素，也就是说，优先安排 运价表上编号最小的产地和销地之间的 运输业务。该方法的特点是xij选取方便， 因而算法简单易实现
例 用西北角法求解上例的初始调运方案 解第一步,从表中选取西北角的元素x1,取x1=min{a1, b1}=100,意即A煤矿尽可能满足城市B1的需求量100, 此时B1达到全部需求后,需求量修改为b1=100-100=0, A1的供给量第一次修改为a1’=200-100=100。划去第1 列 第二步,重复第一步,选取剩下的表中西北角的元素 ⅹ12,取ⅹ2=min{a13,b2}=100,意即A煤矿尽可能满 足B2城市的需求量,此时A1已供给完所有的煤,供给 量第二次修改为a1=100-100=0,B2未满足全部需求, 需求量修改为b2=150-100=50。划去第1行;
20 例 用西北角法求解上例的初始调运方案。 解 第一步，从表中选取西北角的元素x11，取x11 =min{a1， b1}=100，意即A1煤矿尽可能满足城市B1的需求量100， 此时B1达到全部需求后，需求量修改为b1 ’=100-100=0， A1的供给量第一次修改为a1 ’=200-100=100 。划去第1 列； 第二步，重复第一步，选取剩下的表中西北角的元素 x12，取x12 =min{a1 ’ ，b2}=100 ，意即A1煤矿尽可能满 足B2城市的需求量，此时A1已供给完所有的煤，供给 量第二次修改为a1 ’=100-100=0 ， B2未满足全部需求， 需求量修改为b2 ’=150-100=50 。划去第1行；