《运筹学》课程授课教案（讲稿）第11讲 运输问题的模型与性质、表上作业法

课程名称：《运筹学》第_11_讲次运输问题的模型与性质；表上作业法授课题目本讲目的要求及重点难点：【目的要求】通过本讲课程的学习，理解并掌握运输问题的模型与性质，会用表上作业法求解。[重点及难点】表上作业法内容[本讲课程的引入]前两章讨论了一般线性规划问题的求解方法，但在实际工作中，往往碰到有些线性规划问题，它们的约束方程组的系数矩阵具有特殊的结构，这就有可能找到比单纯形法更为简便的求解方法。从而可节约计算时间和费用。本章讨论的运输问题就是属于这样一类特殊的线性规划问题。[本讲课程的内容]一、运输问题的数学模型在经济建设中，经常碰到大宗物资调运问题。如煤、钢材、木材、：粮食等等物资，在全国有如若干生产基地，根据已有的交通网，应如何制定调运方案，将这些物资运到各消费地点，而总运费要小。这类问题可用以下数学语言描述。已知有m个生产地点Ai，i=1，2，，m，可供应某种物资，其供应量（产量）分别为ai，i=1，2，，m；有n个销地Bj，j=1，2，，n，其需要量分别为bj，j=1,2，,n；从Ai到Bj运输单位物资的运价（单价）为cij，这些数据可汇总于产销平衡表和单位运价表中。若用xij表示从Ai到Bj的运量，那么在产销平衡的条件下，要求总运费最小的调运方案，可用以下数学模型表示：

课程名称：《运筹学》 第 11 讲次 授课题目 运输问题的模型与性质；表上作业法 本讲目的要求及重点难点： 目的要求] 通过本讲课程的学习，理解并掌握运输问题的模型与性质，会用表上作业法 求解。 [重点及难点] 表上作业法 内 容 [本讲课程的引入] 前两章讨论了一般线性规划问题的求解方法，但在实际工作中，往往碰到有些线性 规划问题，它们的约束方程组的系数矩阵具有特殊的结构，这就有可能找到比单纯形法 更为简便的求解方法。从而可节约计算时间和费用。本章讨论的运输问题就是属于这样 一类特殊的线性规划问题。 [本讲课程的内容] 一、 运输问题的数学模型 在经济建设中，经常碰到大宗物资调运问题。如煤、钢材、木材、；粮食等等物资，在全国有 如若干生产基地，根据已有的交通网，应如何制定调运方案，将这些物资运到各消费地点，而总运费 要小。这类问题可用以下数学语言描述。 已知有 m 个生产地点 Ai ，i ＝ 1，2，.，m ，可供应某种物资，其供应量（产量）分别为 ai ，i ＝ 1，2，.，m ；有 n 个销地 Bj ，j ＝ 1，2，.，n ，其需要量分别为 bj ，j ＝ 1，2，.， n ；从 Ai 到 Bj 运输单位物资的运价（单价）为 cij，这些数据可汇总于产销平衡表和单位运价表中。 若用 xij 表示从 Ai 到 Bj 的运量，那么在产销平衡的条件下，要求总运费最小的调运方案，可 用以下数学模型表示：

内容ZZminz =Cij Xiji=1j=1mZj=b，j=l,2，,ni=1nZ xij = ai,i=1,2,,mj=1xij≥0这就是运输问题的数学模型，它包含mXn个变量，m十n个约束方程。其系数矩阵的结构比较松散，矩阵中对应变量xij的系数列向量Pij=ei+em+j。对产销平衡的运输问题，由于存在以下关系：nmmmnn≥ bj=M(MZ(MXij) =Zxj）=aij=1j=1i=1i=1i=1 j=1所以模型最多只有m十n一1个独立约束方程。即系数矩阵的秩≤m十n一1。例1、某公司从三个产地A1、A2、A3将物品运往四个销地B1、B2、B3、B4，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示销地BiBsB4Bz产量产地37A131110A19284As71059435销量6620（产销平衡)问应如何调运，可使得总运输费最小？解：这是一个产销平衡的运输问题，设xij为从产地Ai运往销地Bj的运输量（i=1，2，3;j=1,2,3,4)所以此运输问题的线性规划模型如下：

内 容 min z ＝ ∑ ∑ cij xij ∑ xij ＝ bj ，j ＝ 1，2，.，n ∑ xij ＝ ai ，i ＝ 1，2，.，m xij ≥ 0 这就是运输问题的数学模型，它包含 m×n 个变量，m＋n 个约束方程。其系数矩阵的结构 比较松散，矩阵中对应变量 xij 的系数列向量 Pij = ei ＋ e m+j 。 对产销平衡的运输问题，由于存在以下关系： ∑ bj = ∑（∑ xij）= ∑（∑ xij）= ∑ ai 所以模型最多只有 m＋n－1 个独立约束方程。即系数矩阵的秩≤m＋n－1。 例 1 某公司从三个产地 A1、A2、A3 将物品运往四个销地 B1、B2、B3、B4，各产地的 产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示 问应如何调运，可使得总运输费最小? 解： 这是一个产销平衡的运输问题，设 xij 为从产地 Ai 运往销地 Bj 的运输量（i = 1，2， 3； j = 1，2，3，4） 所以此运输问题的线性规划模型如下： 销地 产地 B1 B2 B3 B4 产量 A1 3 11 3 10 7 A2 1 9 2 8 4 A3 7 4 10 5 9 销量 3 6 5 6 20（产销平 衡） m m m j=1 j=1 i=1 i=1 j=1 i=1 n n n i=1 j=1 m i=1 n j=1

内容Minf=3x11+11x12+3x13+ 10x14+x21+9x22+2x23+8x24+7x31+4x32+10x33+5x34s.t.x11+x12+x13+x14=7x21 + x22+ x23 + x24 = 4x31 + x32+ x33 + x24 = 9xl1 + x21 +x31 = 3x12+x22+x32= 6x13+x23+x33=5x14 + x24 +x34= 6xj≥0(i=1、2、3;j=1、2、3、4)其系数矩阵为：011000000A=100OU00UUU共有m+n行，分别表示产地和销地；有mn列分别表示各变量；每列只有两个1，其余为0。运输问题求解的有关概念1、基变量的特点（1）基变量共有m+n-1个（2）产销平衡运输问题的m+n-1个变量构成基变量的充分必要条件是不含闭回路定义4.1在表4-5中决策变量格凡是能够排列成下列形式xab, xac,xdc, xde,..,xst, xsb或xab, xcb,xcd, xed,,xst, xat其中，a,d..,s各不相同；b,c..,t各不相同。我们称之为变量集合的一个闭回路，并将上式中的变量称为这个闭回路的顶点

内 容 Min f = 3x11+ 11x12+ 3x13+ 10x14 + x21+ 9x22 + 2x23+ 8x24 + 7x31+ 4x32+ 10x33+ 5x34 s.t. x11+ x12 + x13 + x14 = 7 x21 + x22+ x23 + x24 = 4 x31 + x32+ x33 + x24 = 9 x11 + x21 + x31 = 3 x12 + x22 + x32 = 6 x13 + x23 + x33 = 5 x14 + x24 + x34 = 6 xij ≥ 0 ( i = 1、2、3；j = 1、2、3、4) 其系数矩阵为 ： 共有 m+n 行，分别表示产地和销地；有 mn 列分别表示各变量；每列只有两个 1，其余 为 0 。 运输问题求解的有关概念 1、基变量的特点 （1）基变量共有 m + n -1 个 （2）产销平衡运输问题的 m + n -1 个变量构成基变量的充分必要条件是不含闭回路 定义 4.1 在表 4-5 中决策变量格凡是能够排列成下列形式 xab, xac, xdc，xde,., xst, xsb 或 xab, xcb, xcd, xed,., xst, xat 其中，a,d,.,s 各不相同；b,c,.,t 各不相同。我们称之为变量集合的一个闭回路，并将上 式中的变量称为这个闭回路的顶点。                        0 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 A

内容根据定义可以看出闭回路的一些明显特点：：（1）闭回路均为一封闭折线，它的每一条边，或为水平的，或为垂直的：（2）闭回路的每一条边（水平的或垂直的）均有且仅有两个闭回路的顶点（变量格）。表上作业法是单纯形法在求解运输问题时的一种简化方法。其实质是单纯形法。但具体计算和术语有所不同。可归纳为：（1）找出初始基可行解。即在（mXn）产销平衡表上给出m十n一1个数字格。（2）求各非基变量的检验数，即在表上计算空格的检验数。判别是否达到最优解。如已是最优解，则停止计算，否则转到下一步。（3）确定换入变量和换出变量，在表上用闭回路法调整，找到新的基可行解。重复（2)，（3）直到得到最优解为止。以上运算都可以在表上完成。一、初始基本可行解的确定①在运输问题求解作业数据表中任选一个单元格xij（Ai行Bj列交叉位置上的格），令xij =min (ai, bj)即考虑从Ai向Bj的最大运输量（使行或列在允许的范围内尽量饱和，即使一个约束方程得以满足)，填入xij的相应位置；②从ai或bj中分别减去xij的值，即调整Ai的拥有量及Bj的需求量；③若ai=0，则划去对应的行（把拥有的量全部运走），若bj=0则划去对应的列（把需要的量全部运来)，且每次只划去一行或一列（即每次要去掉且只去掉一个约束)；若运输平衡表中所有的行与列均被划去，则得到了一个初始基本可行解。否则，在剩下的运输平衡表中选下一个变量，转②。按照上述方法所产生的一组变量的取值将满足下面条件：①所得的变量均为非负，且变量总数恰好为m+n-1个②所有的约束条件均得到满足：①所得的变量不构成闭回路。因此，根据定理4.1及其推论，所得的解一定是运输问题的基本可行解。下面通过例子说明表上作业法的计算步骤

内 容 根据定义可以看出闭回路的一些明显特点:： （1）闭回路均为一封闭折线，它的每一条边，或为水平的，或为垂直的； （2） 闭回路的每一条边（水平的或垂直的）均有且仅有两个闭回路的顶点（变量格）。 表上作业法是单纯形法在求解运输问题时的一种简化方法。其实质是单纯形法。但具体计 算和术语有所不同。可归纳为： （1）找出初始基可行解。即在（m×n）产销平衡表上给出 m＋n－1 个数字格。 （2）求各非基变量的检验数，即在表上计算空格的检验数。判别是否达到最优解。如已是 最优解，则停止计算，否则转到下一步。 （3）确定换入变量和换出变量，在表上用闭回路法调整，找到新的基可行解。 重复（2），（3）直到得到最优解为止。 以上运算都可以在表上完成。 一、初始基本可行解的确定 ① 在运输问题求解作业数据表中任选一个单元格 xij ( Ai 行 Bj 列交叉位置上的格)，令 xij = min { ai , bj } 即考虑从 Ai 向 Bj 的最大运输量(使行或列在允许的范围内尽量饱和，即使一个约束方程 得以满足)，填入 xij 的相应位置； ② 从 ai 或 bj 中分别减去 xij 的值，即调整 Ai 的拥有量及 Bj 的需求量； ③ 若 ai = 0，则划去对应的行（把拥有的量全部运走），若 bj = 0 则划去对应的列（把需 要的量全部运来），且每次只划去一行或一列（即每次要去掉且只去掉一个约束）； ④ 若运输平衡表中所有的行与列均被划去，则得到了一个初始基本可行解。否则，在剩 下的运输平衡表中选下一个变量，转②。 按照上述方法所产生的一组变量的取值将满足下面条件： ① 所得的变量均为非负，且变量总数恰好为 m + n – 1 个； ② 所有的约束条件均得到满足； ① 所得的变量不构成闭回路。 因此，根据定理 4.1 及其推论，所得的解一定是运输问题的基本可行解。 下面通过例子说明表上作业法的计算步骤

内容例1某公司经销甲产品。它下设三个加工厂。每日的产量为：A1一7吨，A2一4吨，A3—9吨。该公司把这些产品分别运往四个销售点。各销售点每日销售量为：B1—3吨，B2—6吨，B3一5吨，B4一6吨。已知从各工厂到各销售点的单位产品的运价为表3-1所示。问该公司应如何调运产品，在满足各销售点的需要量的前提下，使总运费为最少解先画出此问题的产销平衡表和单位运价表，见表3-1，表3-2。表3-1产销平衡表B1B2B3B4产量A174A29A35销量366表3-2单位运价表B1B2B3B4A1311310A2192874A3105(1）最小元素法此方法的基本思想是就近供应，即从单位运价表中逐次地挑选最小元素，并比较其对应的产量和销量。当产大于销，划去该元素所在列；当产小于销，划去该元素所在行。然后在未划去的元素中再找最小元素，再确定供应关系。这样在产销平衡表上每填入一个数字，在运价表上就划去一行或一列。表中共有m行n列，总共可划m十n条直线。但当表中只剩下一个元素时，这时当在产销平衡表上填入这个数字时，在运价表上要同时划去一行和一列。此时运价表上的所有元素都划去了，相应地在产销平衡表上填入了m+1个数字。即给出了m+n1个基变量的值，且这m十n一1个基变量对应的系数列向量是线性独立的。因此用最小元素法给出的初始解是运输问题的基可行解

内 容 例 1 某公司经销甲产品。它下设三个加工厂。每日的产量为：A1—7 吨，A2—4 吨， A3—9 吨。该公司把这些产品分别运往四个销售点。各销售点每日销售量为：B1—3 吨，B2—6 吨，B3—5 吨，B4—6 吨。已知从各工厂到各销售点的单位产品的运价为表 3-1 所示。问该公司 应如何调运产品，在满足各销售点的需要量的前提下，使总运费为最少。 解 先画出此问题的产销平衡表和单位运价表，见表 3-1，表 3-2。 表 3-1 产销平衡表 B1 B2 B3 B4 产量 A1 7 A2 4 A3 9 销量 3 6 5 6 表 3-2 单位运价表 B1 B2 B3 B4 A1 3 11 3 10 A2 1 9 2 8 A3 7 4 10 5 (1) 最小元素法 此方法的基本思想是就近供应，即从单位运价表中逐次地挑选最小元素，并比较其对应的 产量和销量。当产大于销，划去该元素所在列；当产小于销，划去该元素所在行。然后在未划 去的元素中再找最小元素，再确定供应关系。这样在产销平衡表上每填入一个数字，在运价表 上就划去一行或一列。表中共有 m 行 n 列，总共可划 m＋n 条直线。但当表中只剩下一个元素 时，这时当在产销平衡表上填入这个数字时，在运价表上要同时划去一行和一列。此时运价表 上的所有元素都划去了，相应地在产销平衡表上填入了 m ＋ n — 1 个数字。即给出了 m ＋ n — 1 个基变量的值，且这 m ＋ n — 1 个基变量对应的系数列向量是线性独立的。因此用最小 元素法给出的初始解是运输问题的基可行解

容内用最小元素法给出的例1的初始解如表3-3：B2B1B3B4产量7A134A2439A3636销量356(2）伏格尔法最小元素法的缺点是：为了节省一处的费用，有时造成在其它处要多花几倍的费用。伏格尔法认为，一产地的产品假如不能按最小运费供应，就应考虑次小运费，这就有一个差额。差额越大，说明不能按最小运费调运时，运费增加越多。因此对差额最大处，就应当采用最小运费调运。基于此，伏格尔法的步骤是：（1）在运价表中分别计算出各行和各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行。（2）从行或列差额中选出最大者，选择它所在行或列中的最小元素，并比较其对应的产量和销量。当产大于销，划去该元素所在列；当产小于销，划去该元素所在行。（3）对运价表中未划去的元素再分别计算出各行和各列的最小运费和次最小运费的差额。重复（1）、（2）步，直到给出初始解为止。用伏格尔法给出的例1的初始解如表3-4：销地B3 产量B1B2B4产地527A114A2339A366销量365由此可见，伏格尔法同最小元素法除在确定供求关系的原则上不同外，其余步骤相同。伏格尔法给出的初始解比用最小元素法给出的初始解更接近最优解。本例用伏格尔法给出的初始

内 容 用最小元素法给出的例 1 的初始解如表 3-3： B1 B2 B3 B4 产量 A1 4 3 7 A2 3 1 4 A3 6 3 9 销量 3 6 5 6 (2) 伏格尔法 最小元素法的缺点是：为了节省一处的费用，有时造成在其它处要多花几倍的费用。伏格 尔法认为，一产地的产品假如不能按最小运费供应，就应考虑次小运费，这就有一个差额。差 额越大，说明不能按最小运费调运时，运费增加越多。因此对差额最大处，就应当采用最小运 费调运。基于此，伏格尔法的步骤是： （1）在运价表中分别计算出各行和各列的最小运费和次最小运费的差额，并填入该表的最 右列和最下行。 （2）从行或列差额中选出最大者，选择它所在行或列中的最小元素，并比较其对应的产 量和销量。当产大于销，划去该元素所在列；当产小于销，划去该元素所在行。 （3）对运价表中未划去的元素再分别计算出各行和各列的最小运费和次最小运费的差额。 重复（1）、（2）步，直到给出初始解为止。 用伏格尔法给出的例 1 的初始解如表 3-4： B1 B2 B3 B4 产量 A1 5 2 7 A2 3 1 4 A3 6 3 9 销量 3 6 5 6 由此可见，伏格尔法同最小元素法除在确定供求关系的原则上不同外，其余步骤相同。伏 格尔法给出的初始解比用最小元素法给出的初始解更接近最优解。本例用伏格尔法给出的初始 销 产 地 地

内容解就是最优解。例2某公司下属有生产一种化工产品的三个产地A1、A2、A3，有四个销售点B1、B2、B3、B4销售这种化工产品。各产地的产量、各销地的销量和各产地运往各销地每吨产品的运费（百元）如下表所示。销产量B1B3B4B1B2B3B4B2产A1753859402948A2A3806315需35405565195求问应如何调运，可使得总运输费最小？最优解的判别二、判别的方法是计算空格（非基变量）的检验数。因运输问题的目标函数是要求实现最小化故当所有检验数非负时，为最优解。下面介绍两种求空格检验数的方法。（一）闭回路法在给出调运方案的计算表上，如表3-3，从每一空格出发找一条闭回路。它是以某空格为起点。用水平或垂直线向前划，每碰到一数字格转90°后，继续前进，直到回到起始空格为止。从每一空格出发一定存在和可以找到唯一的闭回路。因m+n一1个数字格（基变量）对应的系数向量是一个基。任一空格（非基变量）对应的系数向量是这个基的线性组合。闭回路法计算检验数的经济解释为：在已给出初始解的表3-3中，可从任一空格出发，如（A1，B1)，若让AI的产品调运1吨给B1，为了保持产销平衡，就要依次作调整：在（A1，B3）处减少1吨，（A2，B3）处增加1吨，（A2，B1）处减少1吨，即构成了以（A1，B1）空格为起点，其它为数字格的闭回路。如表3-5中的虚线所示。在此表中闭回路各顶点所在格的右上角数字是单位运价

内 容 解就是最优解。 例 2 某公司下属有生产一种化工产品的三个产地 A1、A2、A3 ，有四个销售点 B1、B2、 B3、B4 销售这种化工产品。各产地的产量、各销地的销量和各产地运往各销地每吨产品的运费 （百元）如下表所示。 销 产 B1 B2 B3 B4 产量 B1 B2 B3 B4 A1 75 3 8 5 9 A2 40 2 9 4 8 A3 80 6 3 7 5 需 求 35 40 55 65 195 问应如何调运，可使得总运输费最小? 二、 最优解的判别 判别的方法是计算空格（非基变量）的检验数。因运输问题的目标函数是要求实现最小化， 故当所有检验数非负时，为最优解。下面介绍两种求空格检验数的方法。 （一） 闭回路法 在给出调运方案的计算表上，如表 3-3 ，从每一空格出发找一条闭回路。它是以某空格为 起点。用水平或垂直线向前划，每碰到一数字格转 90°后，继续前进，直到回到起始空格为止。 从每一空格出发一定存在和可以找到唯一的闭回路。因 m ＋ n — 1 个数字格（基变量） 对应的系数向量是一个基。任一空格（非基变量）对应的系数向量是这个基的线性组合。 闭回路法计算检验数的经济解释为：在已给出初始解的表 3-3 中，可从任一空格出发，如 （A1，B1），若让 A1 的产品调运 1 吨给 B1，为了保持产销平衡，就要依次作调整：在（A1， B3）处减少 1 吨，（A2，B3）处增加 1 吨，（A2，B1）处减少 1 吨，即构成了以（A1，B1）空 格为起点，其它为数字格的闭回路。如表 3-5 中的虚线所示。在此表中闭回路各顶点所在格的右 上角数字是单位运价

内容B3产量B1B2B4337A1(+1)34 (-1)12A243 (-1)1 (+1)A39363656销量可见这个调整方案使运费增加(+1)3+（-1)3+（+1)2+(-1)1=1（元）这表明若这样调整运量将增加运费。将‘1’这个数填入（A1，B1）格，这就是检验数。按以上所述，可找出所有空格的检验数。当检验数还存在负数时，说明原方案不是最优解。（二）位势法设ul，u2，，um；vl，v2，，vn是对应运输问题的m+n个约束条件的对偶变量。由线性规划的对偶理论可推得各变量的检验数oij=cij一（ui+vj)。（1）由所有基变量的检验数oj=cij一（ui+vj）=0，cij已知，并可推得ul=0，所以可求得全部ui、vj的值。如表3-6

内 容 可见这个调整方案使运费增加 （+1）3 + （-1）3 + （+1）2 + （-1）1 = 1（元） 这表明若这样调整运量将增加运费。将‘1’这个数填入（A1，B1）格，这就是检验数。 按以上所述，可找出所有空格的检验数。当检验数还存在负数时，说明原方案不是最优解。 （二） 位势法 设 u1 ，u2 ，. ，um ；v1 ，v2 ，. ，vn 是对应运输问题的 m ＋ n 个约束条件的对 偶变量。由线性规划的对偶理论可推得各变量的检验数σij = cij －（ui ＋ vj）。 （1）由所有基变量的检验数σij = cij －（ui ＋ vj）= 0 ，cij 已知，并可推得 u1= 0 ， 所以可求得全部 ui 、vj 的值。如表 3-6。 B1 B2 B3 B4 产量 A1 3 3 7 （+1） 4（-1） 3 A2 1 2 4 3（-1） 1（+1） A3 9 6 3 销量 3 6 5 6

内容B1B2B3B4ui311310A1000282CA2-1005101A3-510012029310vj按oij=cij（ui+vj)，i，jEN计算所有空格的检验数，如表3-7。B1B2B3B4ui0A131012A2-15-5A342910vi3三、改进的方法一闭回路调整法当在表中空格处出现负检验数时，表明未得最优解。若有两个或两个以上的负检验数时，一般选其中最小的负检验数，以它对应的空格为调入格。即以它对应的非基变量为换入变量。由表3-7得（24）为调入格。以此格为出发点，作一闭回路，如表3-8所示。（24）格的调入量是选择闭回路上具有（一1）的数字格中的最小者。即α=min（1，3）=1，（其原理与单纯形法中按θ规划来确定换出变量相同。）然后按闭回路上的正、负号，得到调整方案，加入和减去此值，如表3-9所示。B1B2B3B4产量7A14 (+1)3(-1)4(+1)31 (L1)A29A363销量3656对表3-8给出的解，再用闭回路法或位势法求各空格的检验数，见表3-9，表中所有的检

内 容 B1 B2 B3 B4 ui A1 1 3 2 11 0 3 0 10 0 A2 0 1 1 9 0 2 －1 8 -1 A3 10 7 0 4 12 10 0 5 -5 vj 2 9 3 10 按σij = cij －（ui ＋ vj），i，j ∈ N 计算所有空格的检验数，如表 3-7。 B1 B2 B3 B4 ui A1 3 10 0 A2 1 2 -1 A3 4 5 -5 vj 2 9 3 10 三、 改进的方法 — 闭回路调整法 当在表中空格处出现负检验数时，表明未得最优解。若有两个或两个以上的负检验数时， 一般选其中最小的负检验数，以它对应的空格为调入格。即以它对应的非基变量为换入变量。 由表 3-7 得（24）为调入格。以此格为出发点，作一闭回路，如表 3-8 所示。 （24）格的调入量θ是选择闭回路上具有（—1）的数字格中的最小者。即θ＝ min（1， 3）＝1，（其原理与单纯形法中按θ规划来确定换出变量相同。）然后按闭回路上的正、负号 ， 加入和减去此值，得到调整方案，如表 3-9 所示。 B1 B2 B3 B4 产量 A1 4（+1） 3（-1） 7 A2 3 1（-1） （+1） 4 A3 6 3 9 销量 3 6 5 6 对表 3-8 给出的解，再用闭回路法或位势法求各空格的检验数，见表 3-9，表中所有的检

内 容验数都为非负，故表3-4中的解为最优解。B1B2B3B4产量A102527421A2319639A312 销量3656此时得到的总运费最小，为85元。四、表上作业法计算中的问题（一）无穷多最优解产销平衡的运输问题必存在最优解，那么有唯一最优解还是无穷多最优解？判别依据与第一章讲述的相同，即某个非基变量（空格）的检验数为0时，该问题有无穷多最优解。例如表3-9中，空格（1，1）的检验数是0，表明例1有无穷多最优解，可在表中以（1，1）为调入格，作闭回路，经调整后得到另一最优解。（二）退化（1）当确定初始解的各供需关系时，若在（i，j）格填入某数字后，出现Ai处的余量等于Bj处的需量。这时在产销平衡表上填入一个数，而在单位运价表上相应地要划去一行和一列。为了使在产销平衡表上有m十n一1个数字格，需要添加一个“0'，它的位置可在对应同时划去的那行或那列的任一空格处。（2）在用闭回路法调整时，若在闭回路上出现两个或两个以上的具有（一1）标记的相等的最小值，这是只能选择其中一个作为调入格，经调整后，得到退化解，这时其它数字格必须填入0，表明它是基变量。当出现退化解后，在作改进调整时，可能在某闭回路上有标记为（一1）的取值为0的数字格，这时应取调整量θ=0。[本讲小结】通过学习我们已经全面掌握了产销平衡运输问题的求解方法，希望大家可课下多加练习

内 容 验数都为非负，故表 3-4 中的解为最优解。 B1 B2 B3 B4 产量 A1 0 2 5 2 7 A2 3 2 1 1 4 A3 9 6 12 3 9 销量 3 6 5 6 此时得到的总运费最小，为 85 元。 四、表上作业法计算中的问题 （一） 无穷多最优解 产销平衡的运输问题必存在最优解，那么有唯一最优解还是无穷多最优解？判别依据与第 一章讲述的相同，即某个非基变量（空格）的检验数为 0 时，该问题有无穷多最优解。例如表 3-9 中，空格（1，1）的检验数是 0，表明例 1 有无穷多最优解，可在表中以（1，1）为调入格， 作闭回路，经调整后得到另一最优解。 （二） 退化 （1）当确定初始解的各供需关系时，若在（i，j）格填入某数字后，出现 Ai 处的余量等 于 Bj 处的需量。这时在产销平衡表上填入一个数，而在单位运价表上相应地要划去一行和一列。 为了使在产销平衡表上有 m ＋ n — 1 个数字格，需要添加一个‘0’，它的位置可在对应同时 划去的那行或那列的任一空格处。 （2）在用闭回路法调整时，若在闭回路上出现两个或两个以上的具有（－1）标记的相等 的最小值，这是只能选择其中一个作为调入格，经调整后，得到退化解，这时其它数字格必须 填入 0，表明它是基变量。当出现退化解后，在作改进调整时，可能在某闭回路上有标记为（－ 1）的取值为 0 的数字格，这时应取调整量θ= 0 。 [本讲小结] 通过学习我们已经全面掌握了产销平衡运输问题的求解方法，希望大家可课下多加练习