第三章——1 第三章 运输问题
在生产实际中，经常需要将某种物资从一些产地运往一些销地，因而存在如何调运使总的运费最小的问题。这类问题一般可用线性规划模型来描述，当然可以用单纯形法求解。但由于其模型结构特殊，学者们提供了更为简便和直观的解法—-表上作业法。此外,有些线性规划问题从实际意义上看，并非运输问题，但其模型结构类似运输问题，也可以化作运输问题进行求解。
第一节 运输问题及其数学模型
首先来分析下面的问题。
例3。1 农产品经销公司有三个棉花收购站，向三个纺织厂供应棉花。三个收购站A 1、A2、A3的供应量分别为50kt、45kt和65kt，三个纺织厂B1、B2、B3的需求量分别为20kt、70kt和70kt。已知各收购站到各纺织厂的单位运价如表3-1所示（单位：千元/kt)，问如何安排运输方案，使得经销公司的总运费最少?
表3-1
纺织厂
收购站 B1 B2 B3
A1
A2
A3 4
6
2 8
3
5 5
6
7
设xij表示从Ai运往Bj的棉花数量，则其运输量表如下表所示。
表3—2
纺织厂
收购站 B1 B2 B3 供应量(kt）
A1
A2
A3 x11
x21
x31 x12
x22
x32 x13
x23
x33 50
45
65
需求量（kt） 20 70 70 160
由于总供应量等于总需求量，因此，一方面从某收购站运往各纺织厂的总棉花数量等该收购站的供应量，即
x11+x12+x13 = 50
x21+x22+x23 = 45
x31+x32+x33 = 65 第三章——2 另一方面从各收购站运往某纺织厂的总棉花数量等该纺织厂的需要量,即
x11+x21+x31 = 20
x12+x22+x32 = 70
x13+x23+x33 = 70
因此有该问题的数学模型为
min f= 4x11+8x12+5x13+6x21+3x22+6x23+2x31+5x32+7x33
一、某工厂生产甲乙两种产品，需A、B二种原料，其有关数据如表所示：
页脚内容1 第三章 运输问题
在生产实际中，经常需要将某种物资从一些产地运往一些销地，因而存在如何调运使总的运费最小的问题。这类问题一般可用线性规划模型来描述，当然可以用单纯形法求解。但由于其模型结构特殊，学者们提供了更为简便和直观的解法——表上作业法。此外，有些线性规划问题从实际意义上看，并非运输问题，但其模型结构类似运输问题，也可以化作运输问题进行求解。
第一节 运输问题及其数学模型
首先来分析下面的问题。
例3.1 农产品经销公司有三个棉花收购站，向三个纺织厂供应棉花。三个收购站A 1、A2、A3的供应量分别为50kt、45kt和65kt，三个纺织厂B1、B2、B3的需求量分别为20kt、70kt和70kt。已知各收购站到各纺织厂的单位运价如表3—1所示（单位：千元/kt），问如何安排运输方案，使得经销公司的总运费最少？
表3—1
纺织厂
收购站 B1 B2 B3
A1
A2
A3 4
6
2 8
3
5 5
6
7
设xij表示从Ai运往Bj的棉花数量，则其运输量表如下表所示。
表3—2
纺织厂
收购站 B1 B2 B3 供应量（kt）
A1
A2
A3 x11
x21
x31 x12
x22
x32 x13
x23
x33 50
45
65
需求量（kt） 20 70 70 160
由于总供应量等于总需求量，因此，一方面从某收购站运往各纺织厂的总棉花数量等该收购站的供应量，即
x11+x12+x13 = 50
x21+x22+x23 = 45
x31+x32+x33 = 65 一、某工厂生产甲乙两种产品，需A、B二种原料，其有关数据如表所示：
页脚内容2 另一方面从各收购站运往某纺织厂的总棉花数量等该纺织厂的需要量，即
x11+x21+x31 = 20
x12+x22+x32 = 70
x13+x23+x33 = 70
运筹学运输问题的方法
运筹学中的运输问题可以通过以下方法进行解决：
1. 确定初始方案：最小元素法、付格尔法和西北角法等，其中最小元素法是先找出运费最小的，然后优先满足。付格尔法是算出行差额和列差额，依次对差额最大的行或列中运费较小的先分配。西北角法也是一种求初始可行解的方法。
2. 判定最优解：可以采用闭回路法或者位势法求检验数。闭回路法是对所选回路上进行“奇+偶-”的操作，而位势法则是直接用公式：检验数=cij-ui-vj。
3. 调整优化解：以检验数＜0且最小的数开始入基，对偶数点选择最小的xij出基。接着为满足表格平衡，使奇数点加上xij，偶数点减xij，记住出基的点为空格点了，这样才能保证有数点一直是m+n-1个。对于产销不平衡的问题，则考虑增设一个仓库存放多出来的部分，或者增设一个产地弥补不足的部分，这些运费均为0，后做法同上。
4. 重复上述步骤：如果还未得到最优解，则重复步骤2和3，直到求得最优解。
总的来说，运筹学的运输问题需要综合运用多种方法进行求解，通过不断调整和优化解，最终得到最优解。
00运输问题
运输问题（transportation problem）一般是研究把某种商品从若干个产地运至若干个销地而使总运费最小的一 类问题。然而从更广义上讲，运输问题是具有一定模型特征的线性规划问题。它不仅可以用来求解商品的调运问题，还可以解决诸多非商品调运问题。运输问题是一种特殊的线性规划问题，由于其技术系数矩阵具有特殊的结构，这就有可能找到比一般单纯形法更简便高效的求解方法，这正是单独研究运输问题的目的所在。 §1运输问题的数学模型 [例4-1] 某公司经营某种产品，该公司下设A、B、C三个生产厂，甲、乙、丙、丁四个销售点。公司每天把三个工厂生产的产品分别运往四个销售点，由于各工厂到各销售点的路程不同，所以单位产品的运费也就不同案。各工厂每日的产量、各销售点每日的销量，以及从各工厂到各销售点单位产品的运价如表4-1所示。问该公司应如何调运产品，在满足各销售点需要的前提下，使总运费最小。 表4-1 甲 乙 丙 丁 产量（ai） A 3 11 3 10 7 B 1 9 2 8 4 C 7 4 10 5 9 销量（bj） 3 6 5 6 设代表从第个产地到第个销地的运输量（；），用代表从第个产地到第个销地的运价，于是可构造如下数学模型：
（；运出的商品总量等于其产量） 00 （；运来的商品总量等于其销量） 通过该引例的数学模型，我们可以得出运输问题是一种特殊的线性规划问题的结论，其特殊性就在于技术系数矩阵是由“1”和“0”两个元素构成的。 将该引例的数学模型做一般性推广，即可得到有个产地、个销地的运输问题的一般模型。注意：在此仅限于探讨总产量等于总销量的产销平衡运输问题，而产销不平衡运输问题将在本章的后续内容中探讨。
（；运出的商品总量等于其产量） （；运来的商品总量等于其销量） 供应约束确保从任何一个产地运出的商品等于其产量，需求约束保证运至任何一个销地的商品等于其需求。除非负约束外，运输问题约束条件的个数是产地与销地的数量和，即；而决策变量个数是二者的积，即。由于在这个约束条件中，隐含着一个总产量等于总销量的关系式，所以相互独立的约束条件的个数是个。 §2运输问题的求解 运输问题的求解采用表上作业法，该方法是单纯形法求解运输问题的一种特定形式，其实质是单纯形法。既然表上作业法是一种特定形式的单纯形法，它自然与单纯形法有着完全相同的解题步骤，所不同的只是完成各步采用的具体形式。表上作业法的基本步骤可参照单纯形法归纳如下： 1． 找出初始基可行解：即要在阶产销平衡表上给出“”个数字格（基变量）； 2． 求各非基变量（空格）的检验数，判断当前的基可行解是否是最优解，如已得到最优解，则停止计算，否则转到下一步；
