运筹学那些事，专科学生学习运筹学之运输问题，No.5

文章目录

• 运输问题
• 运输问题及其特殊结构
• 表上作业法概述（注意本小节只是概述，不是解答题目）
• 需求量等于供应量的运输问题
• 闭合回路法
• 修正分配法
• 修正分配法和闭合回路法的关系
• 需要量不等于供应量的运输问题
• 需要量小于供应量
• 需要量大于供应量
• 自考真题

运输问题

运输问题的内容是在几个供应点与几个需求点之间，运输品种、规格、质量等相同的货物时，以达到总的运输费用最低或获得的利润最大等目标

运输问题及其特殊结构

假设某种产品
有m个生产地，用A_i表示，i=1,2,…,m, 其产量分别为 a₁,a₂,…,a_m。
有n个消费地点，用B_j表示，j=1,2,…,m,其需求量分别为 b₁,b₂,…,b_n。
已知由第i个产地到第j个消地的单位物资运输成本为c_ij。

设x_ij代表从第i个产地调运给第j个消地的物资数量，那么在一般产销平衡的条件下，要求解上述运输问题，使得运输成本最小。建立的模型如图所示


这个公式表示 x₁₁+x₁₂+…+x₁₃ = a₁ # a₁表示产地1的产量，说白了就是把产地1的产量运输到所有的消费地点，不能超过产地1的总产量。

在上述模型中，假设所有产地的总产量恰好与所有消地的总需求量相等，这个称为平衡运输问题。

根据以上的特征，在单纯形表方法的基础上，运筹学创造出一种专门用来求解运输问题的简便方法 — 表上作业法。

表上作业法概述（注意本小节只是概述，不是解答题目）

假设某公司经销的主要业务之一是瓷砖，它在三个地区分别设有一个瓷砖厂：A₁，A₂，A₃，其产量分别为50，100，150（单位：万块），该公司把这些瓷砖分别运往五个消费地：B₁、B₂，B₃.B₄.B₅，各消费地的需求量依次分别为25，115，60，30，70（单位：万块）。已知从每个瓷砖厂到各消费地每万块瓷砖的运价表6-3所示，问该公司应如何组织周运，才能在满足各消费地需求的情况下使总的运输成本最少？

设x_ij为由第i厂运往第j销地的瓷砖的数量，并列入产销平衡表中（见表6-4），表格主体部分由3×5个方格组成，是需要填数的方格，表中还给出各产地的产量（a_i，）与各销地的需求量（b_j）。表格的每一行代表相应产地的产量约束，每一列代表相应销地的需求量的约束，每个填数方格代表一条运输路线。
表示作业法是在平衡表上进行的，首先把产销平衡表和运价表压缩在一张表格里，如表6-5，然后求出一个初始调运方案，再加以判别和调整，直至求得最优方案。

需求量等于供应量的运输问题

上小节主要介绍运输问题的数学模型。运输问题存在三种：1. 供需平衡，2.供大于需，3.供小于需

需求量等于供应量的运输问题数学模型为：
假设
x_ij为i供应点供应给j需求点的数量，其中
i=1,2,…,m;i=1,2,…,n
目标函数:总运输成本最小

约束条件：

1. 供应量约束：对n个需求点的供应数量之和不能超过每个供应点的供应能力：
   
2. 需求量约束：m个供应点供应给每一需求点的供应数量之和应保证每个需求点的需求量
   
   总供应量与总需求量保持平衡
   
   按照教材举例说明

例6-1 某公司下属3个工厂（甲厂、乙厂、丙厂）生产同类产品，供应不同地区的3个城市（A城、B城、C城），工厂的供应量、城市的需求量及工厂到不同城市的单件运费如表6-6所示。

注意，方块中的数字表示的是单件运费

首先计算供应量和需求量是否平衡

上述两个式子相等，该例为供需平衡。

建立数学模型
变量：假设X_ij为i长供应给j城的供应数量，如表6-6所示共计9个决策变量。

目标函数：在满足成本需求量的前提下，其运费最小。

式子中8X₁₁表示的就是 运费*供应数量

约束条件：

供应量约束：
X₁₁ + X₁₂ + X₁₃ = 6000
X₂₁ + X₂₂+X₂₃ = 4000
X₃₁ + X₃₂ + X₃₃ =10000

需求量约束：
X₁₁ + X₂₁ + X₃₁ = 5000
X₁₂ + X₂₂ + X₃₂ = 7500
X₁₃ + X₂₃ + X₃₃ = 7500

变量值非负：
X_ij≥0 i =1,2,3 j = 1,2,3

（下面要讲到的表上作业法，可以得到最优方案的解答：X₁₃ = 6000，X₂₁ = 4000，X₃₁ = 1000，X₃₂ = 7500，X₃₃ = 1500。最小运费S_min = 107000元）

闭合回路法

例题：（主要学习表上作业法）

设有一采石公司，它有3个采石厂：W厂、X厂、Y厂，它们每周的采石能力（供应量）如下：W厂为56车/周；X厂为82车/周；Y厂为77车周；
3个采石厂每周的供应量共为215车。该采石公司已与某筑路公司订立了供应石子的合同。
筑路公司现有3个工程段：A段、B段、C段；3个工程段每周的石子需要量如下：A段为72车/周；B段为102车/周；C段为41车/周；
3个工程段每周的石子需要量共为215车。因此这就是一个需要量等于供应量的运输问题。
下表补充3个采石场到3个工程段的单位运输费用，现要求选择一个最佳的运输方案，以达到总运输费用最低的目的。

第一步：建立运输图

第二步：求得一个最初的运输方案
求最初的运输方案是采用一种叫做西北角法的方法，它的具体步骤如下：
（1）从运输图的西北角开始，将第一行（即W厂）的供应量先分配给第一列（即A段），以满足A段的需要；当W厂的供应量大于A段的全部需要量时，剩余的供应量可以往B段分配，这样由西往东分配，直到将W厂的供应量全部分配完为止。
（2）当W厂的全部供应量小于（即不能满足）A段的全部需要量时，即转入第二行（即X厂）的分配：将X厂供应量的一部分或全部先分配给A段，以补足A段的短缺数量；其后，X厂若有剩余的供应量时，再往B段分配，如此等等。

（3）检查最初的运输方案图，也就是上图，看看所有采石场的供应量是否都已分配出去，所有工段的需要量是否都已得到满足，如果计算无误，那么我们就得到了一个最初的运输方案。
（4）有数字的方格，我们叫做数字格或石方格，数字格的数目 = m+n-1,其中m为行数，n为列数。在本例中数字格的数目 = 3+3-1 = 5，也就是说，在运输图6-1的9个变量中，只有5个变量有数字解，其余的变量都为0；变量未0的方格我们叫空格或无石方格

数字格的数目=行数+列数-1的道理，可从线性规划的原理中得到解释。因为按线性规划来讲，就以图6-1为例，我们可以列出6个方程，如：

但这6个方程中，任何一个方程都可以从其它5个方程中推算出来，因为：

（1）式+（2）式+（3）式=215车
（4）式+（5）式+（6）式=215车

所以，例如（6）式就可以推算如下：

（6）式=（1）式+（2）式+（3）式-（4）式-（5式）

因而，根据线性代数的原理，（6）式是与其它5个式子线性相关的，所以在这个例子中，彼此之间线性无关的方程只有5个；若按线性规划的原理来求解本例时，基变量组就只能有5个基变量，从而也就是说只能有5个变量得数字解；这就是数字格的数目=行数m+列数n-1的道理。

这个例子若采用线性规划的方法来求解，只需任意选择上述6个方程中的5个作为约束条件，再列出一个求总运输费用S为最小值的目标函数，即：

变量前的这些数字表示的是单位运输费用

（5）在上图中，我们把数字格中的数字用圆圈圈上，再用虚线从上到下、从左到右把各个圆圈联系起来；从图中我们可以看到：由圆圈和虚线所组成的图形很像一个台阶，所以这种解运输问题的方法也叫阶石法或登石法（stepping-stone method）.

（6）上图最初的运输方案是一个可行方案，它的总运输费用S，为：

S1=56×40+16×160 + 66 × 240 + 36 × 160 +41 × 240=36240（元）

第三步：寻求改进方案

进行这一程序有两个方法，一个是上面已讲到的阶石法；另一个是修正分配法、

阶石法步骤如下
上步骤我们得到的图如下

1. 对上图的每一个空格求改进路线和改进指数。所谓的改进路线就是指从某一个空格开始，所寻求的那一条企图改变原来的运输方案的路线。所谓改进指数就是循着改进路线，当货物的运输量作为一个单位的变化时，会引起总运输费用的改变量。
   在上图中，有4个空格，分别是WB,WC,XC,YA
   现在我们先寻求WB格的改进路线和计算WB格的改进指数。
   当W厂运送一车石子到B段时，即WB格增加一车运量时，WA格就必须减少一车运量，这样才能保证W厂的供应量不超过56车；这是保证W厂的行向平衡

在从B段来看，当WB格增加一车，就需从数字XB格减少一车，以保持B段的需要量仍然为102车；这是保证B段的列向平衡

在从X厂来看，当XB格减少一车，XA格就需增加一车，这样，使X厂的供应量仍然为82车，这是保证X厂的行向平衡

在从A段来看，由于在W行中，WA格已减少一车，而在X行中，XA恰好增加一车，从而保证了A段的列向平衡

这种改进或调整方法，无论从水平或垂直方向进行调整，都必须有增有减，以保持原有平衡

2. 将上述从WB格开始的改进路线画到运输图上，如下图所示
   
   由于要保持行向与列向的平衡，从WB格开始，再同一行或者同一列上，必然一增一减，配对进行，最后仍然回到WB格，所以这是一条闭合路线，这种寻求改进方案的方法就叫闭合回路法。如果用式子表示，
   WB格的改进路线L_WB表示如下
   L_WB = + WB-XB+XA-WA

式子中“+”号表示在该格增加运量，“-”号表示在该格减少运量

3. 计算WB的改进指数：WB格增加一车，就要增加运费80元；XB格减少一车，可减少运费240元；XA格增加一车，要增加运费160元，WA格减少一车，可减少运费40元。依据这些计算结果为
   改进指数 I_WB = +80元-240元+160元-40元 = -40元

4. 按照相同的方法去求其他三个空格的改进路线L和改进指数I
   WC格的改进路线和改进指数如下图所示
   

WC空格：
L_wc= + WC-YC + YB-XB+XA-WA
I_wc= +80元-240元+ 160元-240元+160元-40元=-120元

XC空格：
L_xc= +XC-YC + YB-XB
I_xc=+160元-240元+160元-240元=-160元

YA空格：
L_YA= + YA-XA +XB-YB
l_YA= +80元-160元+240元-160元=0

第四步：建立改进方案

1. 在所有的空格中，挑选绝对值最大的负改进指数所在的空格作为调整格；在本例中，选择XC为调整格
2. 调整格选定以后，调整路线也就选定了，在本例中，调整路线为L_WC = +XC-YC + YB-XB
3. 在调整路线中，挑选是负号格（即减少运量格）的最小运量为调整运量，以保证改进路线上的所有各格都能合理调整。在本例中，挑选出来的负号格的最小运量为41车，我们就以41作为调整量。

依据上述说明，调整之后的方案为

第二个运输方案的总费用S₂为：
S₂ = 56x40+16 × 160 + 25 × 240 +41×160 +77 × 160 = 29680（元）

判断第二个方案是不是最优解，还是按照上面的方法，对第二个方案的各个空格寻求改进路线和计算改进指数；
只有当各个空格的改进指数都大于或等于0时，表明运输方案的再次改进或调整已不能节俭运费，求得最优的运输方案

接下来的步骤，就是算算算了。

修正分配法

修正分配法也叫做位势法

找到最初的运输方案

（1）先把图6-2用西北角得到的最初运输方案进行一些改进：在图的顶上加一行，在图的左侧加一列，经过改进之后的图如下（注意数字是如何算出来的，请继续阅读），在下图中，顶上的一行K₁，K₂，…，K_j的值和左侧一列的R₁，R₂，…，R_i的值是根据每个数字格的单位运输费用分配给每列或每行的位势值。分配方法是：
R₁+ K₁= C_WA=40
R₂+ K₁=C_XA=160
R₂+ K₂ = C_XB = 240
R₃+ K₂ = C_YB = 160
R₃+ K₃= C_YC=240
这些式子中C_WA，C_XA 分别表示的是数字格WA、XA等等的单位运输费用。
令（注意，这个地方是令）R₁ = 0，则K₁ = 40
依次求出
R₂ = 120
K₂ = 120
R₃ = 40
K₃ = 200

（2）计算最初的运输方案中各空格的改进指数
改进指数亦可称为检验数或位势差，用符号 I 表示

位势差的计算，教材中涉及了两种办法，记住其中一种即可
求那个空格的位势差（改进指数）
用
I_空格 = 空格的单位运费 - R值 - 列值

计算出所有的位势差（改进指数）
I_WE = C_WB - R₁ - K₂ = 80 -0-120 = -40
I_WC = C_WC - R₁ - K₃ = 80 -0- 200 = -120
I_XC = C_XC - R₂ - K₃ = 160 -120- 200 = - 160
I_YA = C_YZ - R₃ - K₁ = 80 - 40- 40 = 0

在4个空格中，以XC空格的改进指数 -160 为绝对值最大的负改进指数，选定XC为调整格

L_xc = + XC - YC + YB - XB

在改进路线中，挑选是负号格的最小运量为调整运量，调整方案之后，参加下图，同时按照上文方法调整R值和K值

接下来的步骤就是循环调整，循环调整，一直将所有位势差（改进指数）都调整为大于等于0即可。

修正分配法和闭合回路法的关系

（1）闭合回路法是修正分配法的基础
（2）在判别某个方案是否是最优时，闭合回路法是先对各个空格寻求一条闭合的改进路线，然后再按每条改进路线计算每个空格的改进指数。而修正分配法则是先计算每个空格的改进指数，然后挑选出绝对值最大的负改进指数，以这个改进指数所在的空格为调整格，于是再对这个调整格寻求一条闭合的改进路线。由此可知，修正分配法只需对一个空格，而不必对所有空格寻求闭合的改进路线，从而大大地减少了工作量。

需要量不等于供应量的运输问题

需要量小于供应量

对于需求量小于供应量的运输问题，求最优解的问题方法是：

1. 虚设一个需求点
2. 虚设的需求点的需求量 = 总供应量 - 总需求量
3. 任何一个供应点到虚设的需求点的单位运费都等于0.

需求量小于供应量最初的运输方案是

需要量大于供应量

对于需求量大于供应量的运输问题，求最优解的问题方法是：

1. 虚设一个供应点
2. 虚设的供应点的供应量 = 总需求量 - 总供应量
3. 虚设的供应点到任何一个需求点的单位运费都等于0.

需求量大于供应量最初的运输方案是

自考真题

运输问题，在自考中属于必考内容，题目出现的位置如下图

更多内容，欢迎关注 https://dwz.cn/r4lCXEuL

西北角法/供需平衡运输表，请重点掌握~