一、某工厂生产甲乙两种产品，需A、B二种原料，其有关数据如表所示：
第三章 运输问题
在生产实际中，经常需要将某种物资从一些产地运往一些销地，因而存在如何调运使总的运费最小的问题。这类问题一般可用线性规划模型来描述，当然可以用单纯形法求解。但由于其模型结构特殊，学者们提供了更为简便和直观的解法——表上作业法。此外，有些线性规划问题从实际意义上看，并非运输问题，但其模型结构类似运输问题，也可以化作运输问题进行求解。
第一节 运输问题及其数学模型
首先来分析下面的问题。
例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
一、某工厂生产甲乙两种产品，需A、B二种原料，其有关数据如表所示：
另一方面从各收购站运往某纺织厂的总棉花数量等该纺织厂的需要量，即 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
一、某工厂生产甲乙两种产品，需A、B二种原料，其有关数据如表所示：
该模型中，包含了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 B1 x11 x21 x31 B2 x12 x22 x32 B3 x13 x23 x33 B4 x14 x24 x34 B5 x15 x25 x35 B6 x16 x26 x36 B7 x17 x27 x37 闭回路1：x11，x12，x22，x23，x33，x31，x11； 页脚内容
3
运筹学 第3章 运输问题
