第三章运输问题第一节运输问题典例及数学模型例：三个产地四个销地的运输问题示意图运输问题的线性规划模型需求约束
供应约束上述模型是根据上图的具体问题写出的。一般运输问题的模型形式基本类似。当产销平衡时，约束中的不等号可改为等号。运输问题
的线性规划模型的系数矩阵的列向量都是由两个单位坐标向量叠加构成。从上例中模型的系数矩阵A就很容易看出这个特点。产销平衡运输问题的
表上作业法步骤:（1）在运价表上用Vogel法求出调运方案表；（2）在运价表上用位势法求非基变量的检验数；（3）检验方案是否
最优。是，停止；否，继续（4）；（4）在调运方案表上用闭回路调整法得到新的调运方案；（5）重复（2）。例:某食品公司经销的主
要产品之一是糖果。它下面设有三个加工厂，每天的生产量分别为:A1－7吨，A2－4吨，A3－9吨。拟把这些糖果运往四个门市销售，各
门市的每日销量为B1－3吨，B2－6吨，B3－5吨，B4－6吨。运价表如下，问：如何运送使总运费最小？51047
A38291A2103113A1B4B3B2B1表1：单位运价表门市加工厂9
A34A27A1产量B4B3B2B1表2：产销平衡表销地产地6563销量一
、初始方案的确定：在运价表上用Vogel法求出调运方案表00006100053000435
0033503265031调整次序销地剩余量6563销量862
521421233122Vogel法求初始调运方案a.求出各行、各列最小两元素的差值；b.在运价
表中找出最小差值对应的行或列的最小元的位置，并用“[]”或“○”标记；c.画“[]”元对应的产地的产品尽可能多地调往画“[
]”元对应的销地，并将调运量填入调运方案表中的相应位置，同时，产或销地调运后的剩余量记入本表右上角相应位置。d.若该产地的产
量被全部调运完，则该产地在运价表中的行用一条虚线划去；若该销地的需求量被全部满足，则该销地在运价表中的列用一条虚线划去；凡是被划去
的行或列不再予以考虑。e.若运价表中所有行和列都被划去，停止。否则，回到步骤a.。31521调整次序同列最
小两元素的差000003921[5]10[4]7A301114448861
11[8]29[1]A20027777107000[10][3]113A165
4321654321调整次序调整次序产地剩余量产量同行最小两元素的差B4B3B2B1产地
销地运价Vogel法求调运方案销地6563销量936A3413A2725
A1产量B4B3B2B1方案产地表3：初始调运方案调运方案表中出现的数字被称为有效数字，它们分别对应此时基变
量的值，空格单元的对应变量即是此时的非基变量，其值为0。本表中，基变量x13=5,x14=2,x21=3,x24=1,x3
2=6,x34=3,非基变量x11=x12=x22=x23=x31=x32=0.二、最优性检验与方案的调整：(在
运价表上用位势法求非基变量的检验数。)v4=10v3=3v2=9v1=3v129[5]10[4]7
u3=-5-2-2A312[8]29[1]u2=-217A220[10][3]113u1
=093A1uB4B3B2B1产地销地方案位势法求非基变量的检验数表4首先将运价置于各单元
格的中央，有效数字（基变量）对应的运价要画上“[]”。在u所在列的第一个位置填上u1=0。然后由等式ui+vj
=[cij]求出所有ui，vj的值。其中，[cij]对应表4的画“[]”的运价。如表4中A1B3处基变量x13对应运
价是“[3]”，则由u1+v3=[c13]=3，得v3=3.将ui+vj的计算值分别填入所有未画“[]”运价的单
元格的左上角。将cij-ui+vj的计算值分别填入所有未画“[]”运价的单元格的右下角。每个单元格右下角的数值即为非基变
量的检验数。（3）检验方案是否最优。是，则停止；否则，继续第（4）步。具体法则为：若所有非基变量的检验数都?0，则取得最优解；否
则，进行调运方案调整（4），即换基迭代。显然，表4中非基变量的检验数都?0，故已取得最优解。停止。（4）在调运方案表上用闭回路
调整法得新的调运方案。在一些简单问题中，Vogel法往往能直接求出最优调运方案，上例即是如此。若现在调运方案为6563
销量936A3413A2734A1产量B4B3B2B1方案调运方案1表
5v4=10v3=3v2=9v1=2v129[5]10[4]7u3=-5-2-2A3-1
28[2]9[1]u2=-197A221[10][3]113u1=092A1uB4B
3B2B1运价位势法求非基变量的检验数表6此时，非基变量x24的检验数<0，未取得最优解，须用闭回路调整法在调
运方案表上进行调运方案的调整。6563销量936A34(0)1(3)3A273(1)
4(2)A1产量B4B3B2B1方案闭回路调整法表中闭回路上奇数序号对应的有效数字中的最小值为1.表71.
先从所有负检验数中找到绝对值最大的，对应的单元格出发构造一个闭回路。但这个闭回路必须满足除出发单元格以外的其余每个拐角点处都是有效
数字单元这一条件。表7所示的闭回路即是按此规则做出。2.从出发单元格开始，给这个闭回路上各拐角点依次标上(0),(1),(2
),……,序号。3.找出奇数序号对应的有效数字中的最小值，然后将闭回路上所有奇数序号对应的有效数字减去这个最小值，所有偶数序
号对应的有效数字加上这个最小值。得到调整后的调运方案。这个过程就是单纯形法的换基迭代。调整前，表中x23是基变量，x23=1，且为
奇数序号对应的有效数字中的最小值，x24是非基变量x24=0，调整后，新的调运方案表8中x23=0,x24=1，即此时x23
被换出，x24被换入为新基下的基变量。6563销量936A3413A2725A1
产量B4B3B2B1方案调运方案2表8由前述工作知，已取得最优解。表上作业法与单纯形法的关系运输问题的
模型形式实际上是一种系数矩阵仅含0，1元素的线性规划模型。所以可以利用单纯形法求解。由于模型的特点，使单纯形法求解的过程可用表上作
业法这一简洁形式表现出来，但表上作业法的单纯形法实质没有丝毫改变：表上作业法中的“位势法”实质上是在求单纯表中的检验数；调运方案表中的有效数字实质上就是单纯形法中基变量的值；调运方案表上的“闭回路调整法”实质上是在做单纯表上的换基迭代。注：6564销量936A355＊0A2734A1产量B4B3B2B1方案0添加有效数字0调运方案3表9 |
|
