《运筹学》课程教学资源（PPT课件讲稿）第三章 特殊的线性规划——运输问题（3.2）运输问题的表上作业法

32运输问题的表上作业法 、表上作业法的基本思想是:先设法给出 一个初始方案,然后根据确定的判别准则对初 始方案进行检查、调整、改进,直至求出最 优方案,如图3-1所示。 表上作业法和单纯形法的求解思想完全一致, 但是具体作法更加简捷

3.2 运输问题的表上作业法 一、表上作业法的基本思想是:先设法给出 一个初始方案,然后根据确定的判别准则对初 始方案进行检查、调整、改进，直至求出最 优方案，如图3-1所示。 表上作业法和单纯形法的求解思想完全一致， 但是具体作法更加简捷

确定初始方案 判定是否是 (初始 最优? 结束 基本可行解) 最优方案 改进调整 (换基迭代) 图3-1运输问题求解思路图

确定初始方案 ( 初 始 基本可行解) 改进调整 （换基迭代） 否 判定是否 最 优？ 是 结 束 最优方案 图3-1 运输问题求解思路图

二、初始方案的确定 1、作业表(产销平衡表) 初始方案就是初始基本可行解。 将运输问题的有关信息表和决策变量—调 运量结合在一起构成“作业表”(产销平衡 表)。 表33是两个产地、三个销地的运输问题作业表

二、 初始方案的确定 1、作业表（产销平衡表） 初始方案就是初始基本可行解。 将运输问题的有关信息表和决策变量——调 运量结合在一起构成“作业表”（产销平衡 表）。 表3-3是两个产地、三个销地的运输问题作业表

表3-3运输问题作业表(产销平衡表) 调销地 多 1 B2 产量 产地 11 12 13 11 12 13 a C 21 C 22 C 23 2 21 22 23 a2 销量 ∑a=∑b 2

调 销地 运 量 产地 B1 B2 B3 产 量 A1 c11 X11 c12 X12 c13 X13 a1 A2 c21 X21 c22 X22 c23 X23 a2 销 量 b1 b2 b3   = = = 3 1 2 1 j j i i a b 表3-3 运输问题作业表（产销平衡表）

其中x是决策变量,表示待确定的从第个产 地到第个销地的调运量,c1为从第i个产地到 第j个销地的单位运价或运距。 2、确定初始方案的步骤: (1)选择一个x1;令x1:=min{a;b}= 第讠个产地的产量全部运到第个销地 b满足第个销地需求 将具体数值填入x:在表中的位置;

其中xij是决策变量，表示待确定的从第i个产 地到第j个销地的调运量，cij为从第i个产地到 第j个销地的单位运价或运距。 2、确定初始方案的步骤： （1）选择一个xij，令xij= min{ai，bj }=     满足第 个销地需求 第 个产地的产量全部运到第 个销地 j j b i j i a 将具体数值填入xij在表中的位置；

(2)调整产销剩余数量:从a和b中分别减去 x的值,若ax=0,则划去产地A所在的行,即 该产地产量已全部运出无剩余,而销地B尚有 需求缺口ba;若bx1=0,则划去销地B所在 的列,说明该销地需求已得到满足,而产地A1 尚有存余量a1-b (3)当作业表中所有的行或列均被划去,说明 所有的产量均已运到各个销地,需求全部满足, x;的取值构成初始方案。否则,在作业表剩余 的格子中选择下一个决策变量,返回步骤(2

（2）调整产销剩余数量：从ai和bj中分别减去 xij的值，若ai -xij =0，则划去产地Ai所在的行，即 该产地产量已全部运出无剩余，而销地Bj尚有 需求缺口bj -ai；若bj -xij =0，则划去销地Bj所在 的列，说明该销地需求已得到满足，而产地Ai 尚有存余量ai -bj； （3）当作业表中所有的行或列均被划去，说明 所有的产量均已运到各个销地，需求全部满足， xij的取值构成初始方案。否则，在作业表剩余 的格子中选择下一个决策变量，返回步骤（2）

按照上述步骤产生的一组变量必定不构成 闭回路,其取值非负,且总数是m+n-1个, 因此构成运输问题的基本可行解 对x;的选择采用不同的规则就形成各种不 同的方法,比如每次总是在作业表剩余的格 子中选择运价(或运距)最小者对应的x 则构成最小元素法,若每次都选择左上角格 子对应的x就形成西北角法(也称左上角 法)

按照上述步骤产生的一组变量必定不构成 闭回路，其取值非负，且总数是m+n-1个， 因此构成运输问题的基本可行解。 对xij的选择采用不同的规则就形成各种不 同的方法，比如每次总是在作业表剩余的格 子中选择运价（或运距）最小者对应的xij， 则构成最小元素法，若每次都选择左上角格 子对应的xij就形成西北角法（也称左上角 法）

3、举例 例3-2甲、乙两个煤矿供应A、B、C 三个城市用煤,各煤矿产量及各城 市需煤量、各煤矿到各城市的运输 距离见表3-4,求使总运输量最少的 调运方案

3、举例 例3-2 甲、乙两个煤矿供应A、B、C 三个城市用煤，各煤矿产量及各城 市需煤量、各煤矿到各城市的运输 距离见表3-4，求使总运输量最少的 调运方案

表3-4 例3-2有关信息表 运距城市 日产量 (供应量) 煤矿 甲 90 70 100 200 80 65 75 250 日销量 (需求量)100150200 450

表3-4 例3-2有关信息表 100 150 200 450 日销量 （需求量） 乙 80 65 75 250 甲 90 70 100 200 日产量 A B C （供应量） 运距 城市 煤矿

例3-2的数学模型 minZ=90x1+70x2+100x3180x21+65x2+75x23总运输量 x1+x12+x13=200 x2,+x2+x23=250日产量约束 +xn1=100 s t X+. 22 150需求约束 x,+xn,=200 x≥0,i=1,2,j=1,2,3

例3-2 的数学模型             = = + = + = + = + + = + + = = + + + + + 0, 1,2; 1,2,3; 200 150 100 250 200 . . min 90 70 100 80 65 75 1 3 2 3 1 2 2 2 1 1 2 1 2 1 2 2 2 3 1 1 1 2 1 3 1 1 1 2 1 3 2 1 2 2 2 3 x i j x x x x x x x x x x x x st Z x x x x x x i j 需求约束 日产量约束 总运输量