第三章 运输问题
在生产实际中，经常需要将某种物资从一些产地运往一些销地，因而存在如何调运使总的运费最小的问题。这类问题一般可用线性规划模型来描述，当然可以用单纯形法求解。但由于其模型结构特殊，学者们提供了更为简便和直观的解法——表上作业法。此外，有些线性规划问题从实际意义上看，并非运输问题，但其模型结构类似运输问题，也可以化作运输问题进行求解。
第一节 运输问题及其数学模型
首先来分析下面的问题。
例3.1 农产品经销公司有三个棉花收购站，向三个纺织厂供应棉花。三个收购站A 1、A2、A3的供应量分别为50kt、45kt和65kt，三个纺织厂B1、B2、B3的需求量分别为20kt、70kt和70kt。已知各收购站到各纺织厂的单位运价如表3—1所示（单位：千元/kt），问如何安排运输方案，使得经销公司的总运费最少？
表3—1 纺织厂 收购站 A1 A2 A3 B1 4 6 2 B2 8 3 5 B3 5 6 7 设xij表示从Ai运往Bj的棉花数量，则其运输量表如下表所示。
表3—2
纺织厂 收购站 A1 A2 A3 需求量（kt） B1 x11 x21 x31 20 B2 x12 x22 x32 70 B3 x13 x23 x33 70 供应量（kt） 50 45 65 160
由于总供应量等于总需求量，因此，一方面从某收购站运往各纺织厂的总棉花数量等该收购站的供应量，即
x11+x12+x13 = 50 x21+x22+x23 = 45 x31+x32+x33 = 65
第三章——1
另一方面从各收购站运往某纺织厂的总棉花数量等该纺织厂的需要量，即
x11+x21+x31 = 20 x12+x22+x32 = 70 x13+x23+x33 = 70
因此有该问题的数学模型为
min f= 4x11+8x12+5x13+6x21+3x22+6x23+2x31+5x32+7x33
x11+x12+x13 = 50 x21+x22+x23 = 45 x31+x32+x33 = 65 x11+x21+x31 = 20 x12+x22+x32 = 70 x13+x23+x33 = 70
xij≥0，i=1，2，3；j=1，2，3 生产实际中的一般的运输问题可用以下数学语言描述。
已知有m个生产地点Ai，i=1，?，m，可供应某种物资，其供应量（产量）为ai，i=1，?，m；有n个销售地点Bj，j=1，?，n， 需要该种物资，其需要量（销量）为bj，j=1，?，n； 从Ai到Bj运输单位物资的运价（单价）为cij； 设Σai=Σbj，这些数据可汇总于如下产销平衡表，现要制定一个使总运费最小的调运方案。
表3—3 运输问题产销平衡表 销 地 产地 A1 A2 ? Am 销量 B1 c11 c21 ? cm1 b1 B2 c12 c22 ? cm2 b2 ? ? ? ? ? ? Bn c1n c2n ? cmn bn 产量 a1 a2 ? am Σai Σbj 若用xij表示从Ai到Bj的运量，在产销平衡的条件下，要求得总运费最小的调运方案，其数学模型如下（模型Y）
minf???cijxiji?1j?1mn?ni?1,?,m??xij?ai
j?1???mj?1,?n??xij?bj?i?1?xij?0,i?1,?,m;j?1,?,n???
第三章——2
该模型中，包含了m×n个变量，（m+n）个约束条件，且有特殊结构的系数矩阵，即
x11x12?x1nx21x22?x2n?xm1xm2?xmn
?11?1???11?1???????11?1???1?11????111????????111???????m行? ??????n行???上述矩阵的列向量可用pij来描述，显然pij中除第i个元素和第m+j个元素为1
以外，其余元素均为0。
第二节 表上作业法
一、运输问题数学模型的基本概念
对于运输问题的数学模型（模型Y）有如下定理。 定理3.1 运输问题的数学模型必有最优解。
首先，运输问题一定有可行解；而任何单位运价cij≥0，因此对于任一可行解必有目标函数值大等于零，即目标函数有下界。因此，对于极小化的运输问题必有最优解。
定理3.2 运输问题约束方程系数矩阵A的秩为m+n－1，即R（A）=m+n－1。 由定理3.1可知，我们在求解运输问题时就不需要进行无最优解的判别；另外从定理3.2可知，运输问题任一基可行解的非零分量的个数不能多于m+n－1，或者说基变量的个数为m+n－1。
定义3.1（闭回路的定义） 在运输问题的调运表中，凡能排成xi1j1，xi1j2，xi2j3，?，xisjs，xisj1形式的变量集合，称为一个闭回路，其中诸变量称为该闭回路的顶点。
下表中即为两个闭回路。 表3—4 A1 A2 A3 x11 x21 x31 B1 x12 x22 x32 B2 x13 x23 x33 B3 x14 x24 x34 B4 x15 x25 x35 B5 x16 x26 x36 B6 x17 x27 x37 B7 闭回路1：x11，x12，x22，x23，x33，x31，x11；
第三章——3
闭回路2：x15，x16，x36，x37，x27，x25，x15；
闭回路有如下特点：①每个顶点都是转角；②每行或每列只有且仅有两个顶点；③每个顶点的连线都是水平的或垂直的。
定理3.3 运输问题m+n－1个变量xi1j1，xi2j2，?，xisjs（s=m+n－1）构成某一基可行解的基变量的充要条件是：不包含以这些变量为顶点的闭回路。
该定理能帮助我们简便地求出基可行解或判别某一可行解是否为基可行解。
二、表上作业法
和一般线性规划一样，运输问题的最优解也一定可以在其基可行解中找到。类似于单纯形法，表上作业法仍然需要解决如下问题：
（1）确定初始基可行解 （2）最优解的判定； （3）基可行解的转换。
（一）初始基可行解的确定
确定初始基可行解的方法很多，如最小元素法、伏格尔法、西北角法等。这里仅介绍既常用又简便的方法——最小元素法。
这种方法的基本思想就是就近供应，即从单位运价表中最小的运价开始确定供销关系，然后次小。一直到求出初始基可行解为止。结合例3.2，给出最小元素法的具体步骤。
例3.2 设有某物资从A1，A2，A3处运往B1，B2，B3，B4四个地方，各处供应量、需求量及单位运价见下表。问应如何安排运输方案，才能使总运费最少？
表3—5 销 地 产地 A1 A2 A3 销量 B1 3 2 8 40 B2 7 4 3 20 B3 6 3 8 15 B4 4 3 9 25 产量 50 20 30 100 100 （1）列出如表3—6所示的调运表（包括单价、产量与销量）；
（2）在调运表中找出一个单位运价最小的格子，在相应的运量位置上填上尽可能大的数（必须满足约束条件）。
如表3—6中，单位运价c21=2为最小，这样在c12所在格子相应运量位置上填上尽可能大的数20（满足A2产量为20的约束条件）；
（3）在填有数字的格子所在行或者列运量应该为0的位置上打“×”，（即表示该运量为0，相应的变量为非基变量）且只能在行或列的方向上打“×”，不能同时在两个方向上打“×”；
第三章——4
如第2行第1个填有运量为20的格子，由于A2的供应量已全部用完，因此，该行的其它格子的运量应全部为零，这样在相应的运量位置上打“×”。
（4）在没有填数，也未打“×”的格子重复上述（2）、（3）步； （5）最后剩下的一行或列只能填数，不能打“×”。 表3—6 销 地 产地 A1 A2 A3 销量 B1 20 20 7 4 3 B2 B3 6 3 8 5 4 3 9 B4 25 产量 50 20 30 3 2 8 × × 20 20 × 10 15 × × 25 × 40 表中给出的x11=20，x13=5，x14=25，x21=20，x32=20，x33=10，其它xij=0，显然是该运输问题的一个可行解，同时，调运表中不包含以这些非零变量为顶点的闭回路。因此，该可行解就是该运输问题的一个基可行解。更一般地，可以证明，由最小元素法给出的可行解就是运输问题的一个基可行解。
（二）最优解的判定
最优解的判定，通常有两种方法，即闭回路法和位势法。 1．闭回路法
在表3—6所描述的调运表中，任一非基可变量都可以作出这样的闭回路：该闭回路以选定的非基变量为第一个顶点，其余的顶点都是基变量。可以证明，对于任一非基变量，这样的闭回路只有唯一一条。
在这样的闭回路上，可以对调运方案进行调整，而能使调运方案仍然满足所有约束条件，即满足产销平衡的要求。例如，对表3—6中非基变量x12作闭回路，如表3—7。
表3—7 销 地 产地 A1 A2 A3 销量
B1 20 20 40 7 4 3 B2 6 3 8 B3 5 4 3 9 B4 25 产量 50 20 30 3 2 8 20 20 10 15 25 第三章——5