表上作业法
PVS-黄旭华作文素材
2023年2月21日发(作者：轴端挡圈)项目四运输问题
学习目标
知识目标
1.了解运输问题模型的特点
2.学会产销不平衡运输问题的转化
3.掌握产销平衡的运输问题的表上作业法
4.掌握Excel求解运输问题
能力目标
1.会建立运输问题数学模型
2.会表上作业法求解产销平衡的运输问题
3.熟练掌握Excel求解运输问题
任务一运输问题的数学模型
情景导入入：
例题4-1设有某种物质要从A1,A2,A3三个仓库运往四个销售点B1,B2,B3,B4。各发点
（仓库）的发货量、各收点（销售点）的收货量以及Ai到Bj的单位运费Cij如表4-1（
=1,2,3；=1,2,3,4）。请问如何组织运输才能使总运费最少？
表4-1
销售点
运价
仓库
B1B2B3B4产量
A1
9181109
A2
11681810
A3
14122166
销量
497525
任务：学会建立运输问题的数学模型，学会产销不平衡问题变为产销平衡问题
产销不平衡运输问题
对于产销不平衡的运输问题，可将其分为总供给量(总产量)大于总需求量(总销量)和总
需求量(总销量)大于总供给量(总产量)两种情形。对于这两种情形通过按具体情况虚设收点
或虚设设发点，其收量或发量是其总量的差数，并按实际意义确定各新增格子上的单位运
价，均可将它们转化为产销平衡的运输问题。
（一）需求量小于供应量的运输问题
对于需求量小于供应量的运输问题,采取的求最优解的方法是:
i
j
1.虚设一个需求点。
2.虚设的需求点的需求量=总供应量-总需求量。
3.任何一个供应点到虚设的需求点的单位运费设置为无穷大，用M表示。这里所包含的意
思是:任何一个供应点如果向虚设的需求点有供应量的话，由于它们之间的单位运费用是无
穷大,那就是说，在一般情况下，不会考虑向虚设点运输货物,因为那是多余的供应量。
（二）需求量大于供应量的运输问题
对于需求量大于供应量的运输问题，采取的求最优解的方法是:
1.虚设一个供应点。
2.虚设的供应点的供应量=总需求量-总供应量。
3.虚设的供应点到任何一个需求点的单位运输费用设置为无穷大，用M表示。这里所包含
的意思是:虚设的供应点向任何一个需求点一般不供应货物，由于它们之间的单位运输费用
是无穷大,那就是说，该项运量根本不能运出，因为供应点是虚设的，从而对应的需求点就
短缺该项运量。
任务二运输问题的表上作业法
情境导入：
针对任务一中的例题4-1，我们已经写出其数学模型，该如何求解该模型得到一个最
优调运方案呢？
任务：理解表上作业法思路，学习最小元素法，掌握闭回路发检验
表上作业法可分为3个基本步骤:确定初始方案;进行最优性检；调整、改进非最优方
案。重复第二和第三步，直至得到最优方案。
（一）初始方案的确定
确定初始方案的方法较多，有西北角法、最小元素法和最大差额法(又称Vogel法)等，
下面我们简单介绍西北角法和最小元素法。
1.西北角法
西北角法的思想是:先给作业表中左上角那格安排最大运量，然后划去该格所在的
行行或列，重复进行，直到求出初始方案为止。具体步骤为:
（1）从运输表中左上角点(1,1)开始，先选x11为基变量，并令x11=min（a1,bl）将x11
的值填写在产销平衡表中,并将a1,bl均减去x11;
（2）若a1-x11=0,则划去a1所在行，否则，划去bl,所在列;
（3）然后在运输表余下表格中选取左上角上的点,重复上述步骤，直到最后必选取xmn
为基变量，这时同时划去最后一行和最后列。
这些被选取的基变量在运输表中的每一行每一列至少有一个,其个数恰好有m+n-1个，
并且不出现闭回路，它们正好构成了一个基本可行解。
2.最小元素法
所谓“最小元素”，是指运价表中最小运价Cij。该法的基本思想是“运价小者优先供
应”，即先给运价表中最小运价那格安排最大运量，然后划去该运价所在行或列;接下去继
续这样做，每次总在表中剩余运价的最小元素那格确定运量,直到求出初始方案为止。
上述过程可总结为以下步骤:
（1）在单位运价表中找出最小元素Cij,令xij=min（ai,bj)。
（2）将xij的值填写在产销平衡表中，并将ai,bj均减去xij
（3）若ai-xij=0,则划去ai所在行，否则，划去bj,所在列;
（4）在单位运价表中未划去的部分,重复上述步骤。
可以证明,最小元索法确定的方案肯定不会构成闭回路，因此，它必可作为表上作业法
的初始方案。
请用最小元素法给出初始可行解（初始调运方案），并求出初始运费。
表4-3产销平衡及运价表
销售点
运价
仓库
B1B2B3B4产量
A1918110
9
A2116818
10
A3
1412216
6
销量
497525
（二）求出检验数，判别方案是否最优
确定初始方案后,就要对它进行最优性检验，即检验初始基本可行解对应的目标值是否
达到最优。表上作业法求检验数一般有两种方法：位势法和闭回路法。
下面介绍闭回路方法。
首先介绍闭回路的概念：如果已确定了某一调运方案，从某一空格出发（无调运量的
格子），沿水平方向或垂直方向前进，遇到某一个适当有调运量的格子就转向90°(当然也
可以不改变方向)继续前进。如此继续下去，经过若干次，就一定回到原来出发的空格。这
样形成的一条由水平和垂直线段组成的封闭折线称为闭回路。
由闭回路的构成可见，除起点是空格外，其余所有的拐角点都是填有调运量的。我们
可以证明一个重要的事实：从每一个空格出发都存在唯一的闭回路。
所谓闭回路法，就是在代表非基变量的空格(其调运量为零)对应的闭回路上作运量的
调整，首先在此空格处运量加上1,其次在闭回路的顶点上依次减1,加1，减....最后我们
计算出由于这些变化给整个运输方案的总运费带来的变化。我们把奇数顶点运价之和减去
偶数顶点运价之和即可得到非基变量的检验数。
在讨论闭回路法求检验数时，我们看到如果某人空格的检验数为正，那么若使该空格
的调运量增加（即由非基变量变为基变量），总运费就会增加之，如果某个空格的检验数为
负，若使该空格的调运量增加，总运费就会减少。我们自然会想到：如果没有负的检验，
总运费就不能再减少了。一般我们有如下结论，即判别最优方案准则：
对于运输问题的一个基本可行方案，如果所有的检验数非负，即,那么该方案
就是一组最优方案。这里的结论和前面线性规划的结论是一致的。因为运输问题是极小化
线性规划问题。所以，最优判别准则是所有检验数非负。
请结合下表，计算检验数，填入下表：
检验格闭回路检验数
X12X12—X11—X21—X22—X12σ12=
X14X14—X34—X13—X11—X14σ14=
X23X23—X13—X11—X21—X23σ23=
X24X24—X34—X31—X21—X24σ24=
X32X32—X31—X21—X22—X32σ32=
X33X33—X31—X11—X13—X33σ33=
0
ij
（三）调运方案的改进
如果所得的基本可行方案不是最优的，就要对其进行改进，这一步工作想当于普通单
纯形法的换基迭代，其运算法则和步骤是：
第一步确定进基格。选取绝对值最大的负检验数格为进基格，标以“*”，进基格所
对应的变量就是单纯形法所对应的变量；
第二步作从进基格出发作闭回路，并沿任一方向对该闭回路的顶点进行编号，但进
基格必须为第一个顶点；
第三步确定调整量，求出闭回路上所有偶数顶点调运量的极小值,叫做调整量；
第四步调整方案，令此闭回路上所有奇数顶点的调运量加，所有偶数顶点的调运
量减，其余调运量不变。调整后进基格由空格变为数字格，在闭回路的偶数顶点中选取
一个调运量为零的顶点改为空格，如果有几个偶数顶点的调运量同时变为零，只能选取其
中一个顶点改为空格，这个变为空格的偶数顶点所对应的变量，就是单纯形法是所说的出
基变量。
（四）重复（二）（三）步，直到所有检验数均为负数，得到最优方案。
表上作业法的几点说明
首先，使用表上作业法求解运输问题，要先考察该问题是否为产销平衡的运输问题，
如是产销不平衡问题，需要先转化为产销平衡问题再进行求解。
第二，在给出初始方案或者进行方案调整的过程中，可能出现退化解的现象，即填上
一个运输量可以同时划去两个约束条件，遇到这种情况要在其所在行和列剩余的任一非基
变量中随机给定一个“0”运量。
第三，在闭回路法进行非基变量检验的时候，要计算所有检验数，选取检验数为负数
的，且绝对值最大的那个格子进行调整。
下面请结合以上步骤，完成改题目
第一次调整后的调运方案如下表：
销售点
运价
仓库
B1B2B3B4产量
A1918110
9
A2
116818
10
A31412216
6
销量
497525
调整后运输费用为：
计算检验数，填入下表：
检验格闭回路检验数
判定是不是最优解，如不是，继续进行调整。
填空题
1．物资调运问题中，有m个供应地，A
l
，A
2
…，A
m
，A
j
的供应量为a
i
(i=1，2…，m)，n
个需求地B
1
，B
2
，…B
n
，B的需求量为b
j
(j=1，2，…，n)，则供需平衡条件为（）
2．物资调运方案的最优性判别准则是：当全部检验数（）时，当前的方案一定是最优
方案。
3．若调运方案中的某一空格的检验数为1，则在该空格的闭回路上调整单位运量而使运费
（），若某一空格的检验数为—5，则在该空格的闭回路上调整单位运量将（）。
4．调运方案的调整是要在检验数出现（）的点为顶点所对应的闭回路内进行运
量的调整。
5．按照表上作业法给出的初始调运方案，从每一空格出发可以找到且仅能找到（）
条闭回路
6．在表上作业法所得到的调运方案中，从某空格出发的闭回路的转角点所对应的变量必
为（）。
选择题
1．用闭回路法调整调运方案时，下列做法正确的是:
A．奇点处加调整量，偶点处减调整量B．奇点处减调整量，偶点处加调整量
C．奇点偶点同时加或减一个调整量D．都不对
2．对m个产地，n个销地的平衡运输问题，其基变量的个数为：D
A．m-nB．m+nC．MnD．m+n-1
3．标准指派问题(m人，m件事)的规划模型中，有（）个决策变量
A．MB．m*mC．2mD．都不对
4．关于指派问题的决策变量的取值，下列说法正确的是：
A．不一定为整数B．不是0就是1C．只要非负就行D．都不对
5．求解运输问题中，当供大于求时，可增加一个：
A．虚拟产地B．虚拟销地C．都可D．都不可
6．产销不平衡的运输问题中，当供大于求时，增加的虚拟销地相当于：
A．亏空B．原地库存C．异地库存D．都不对
7．确定运输问题的初始调运方案的方法是：
A．最小元素法B．单纯形法C．匈牙利法D．闭回路法
8．一般来说，用沃格尔法与最小元素法求解初始调运方案时，目标函数的值：
A．一样优B．前者的优C．后者的优D．不好说
9．运输问题的数学模型中包含（）个约束条件
A．m*nB．m+nC．m+n-1D．m*n-1
10．用EXCEL求解线性规划问题时，可变单元格是：
A．目标函数B．决策变量C．约束方程D．都不是
11．关于运输问题的说法不正确的是：
A．它可用线性规划的单纯形表求解B．它可用表上作业法求解
C．它的约束方程数等于基变量的数目D．它一定有最优解
12．平衡运输问题一定存在：
A．整数解B．最优解C．无穷多解D．以上都不对
13．典型的运输问题的平衡是指：
A.每个需求方物资的需要量一样B.每个供应方物资的供应量一样
C.总的需求量与总的供应量一样D.需求方和供应方个数一样
14．有6个产地4个销地的平衡运输问题模型具有特征:
A．有10个变量24个约束B．有24个变量10个约束
C．有24个变量24约束D．有9个基变量10个非基变量
15．有m个产地n个销地的平衡运输问题模型具有特征:
A．有mn个变量m+n个约束B．有m+n个变量mn个约束
C．有mn个变量m+n－1约束D．有m+n－1个基变量，mn－m－n－1个非基变量
16．用增加虚设产地或虚设销地的方法可将产销不平衡的运输问题化为产销平衡的运输问
题处理，该方法：
A．正确B．错误C．不一定D．无法判断
17．建立运输问题的改进方案，在调整路线中调整量应为：
A．奇数格的最小运量B．奇数格的最大运量
C．偶数格的最小运量D．偶数格的最大运量
18．考虑某运输问题,设其总需求量为Q,总供应量为G,且Q 问题,则应：D A．使诸供应点的供应总量减少G-Q B．使诸需求点的需求总量增加G-Q C．虚设一个需求量为G-Q的需求点,且任一供应点到该虚设需求点的单位运费为充分大 D．虚设一个需求量为G-Q的需求点,且任一供应点到该虚设需求点的单位运费为0 19．在解运输问题时,若已求得各个空格的改进路线和检验数，则选择调整格的原则是： A．在所有空格中,挑选值最小的正检验数所在的空格作为调整格 B．在所有空格中,挑选绝对值最小的正检验数所在的空格作为调整格 C．在所有空格中,挑选为正值且最大的检验数所在的空格作为调整格 D．在所有空格中,挑选绝对值最小的负检验数所在的空格作为调整格 20．当某供给地与某需求地之间不允许运输时，它对应的运价为： A．零B．无穷大C．随便取D．以上都不对 21．当运输问题是求利润最大化时，采取的措施是:B A．仍用最小元素法求初始调运方案B．应用最大元素法求初始调运方案 C．不可西北角法求初始调运方案D．检验数都大于零时得到最优解 22．如果下表为一产销平衡运输问题的一组基可行解（左上角为运价），则x14的检验数为： A．8B．7C．4D．5 用最小元素法，求解产销平衡的运输问题，并用闭回路法检验是否是最优解，不要求调整 基解找更优的解。 某公司经销甲产品。该公司下设三个加工厂。每日的产量分别是：A1为7吨，A2为4吨， A3为9吨。该公司把这些产品分别运往4个销售点。各销售点的每日销量为：B1为3吨， B2为6吨，B3为4吨，B4为6吨。已知从各工厂到各销售点的单位产品的运价如下表所 示。请利用最小元素法求解并用闭回路法检验和调整，确定公司在满足各销售点的需要量 的前提下，使总运费为最少。 B1B2B3B4 产量 A13113107 A219284 A3741059 销量 3656