运筹学 第3章 运输问题

第三章 运输问题

在生产实际中，经常需要将某种物资从一些产地运往一些销地，因而存在如何调运使总的运费最小的问题。这类问题一般可用线性规划模型来描述，当然可以用单纯形法求解。但由于其模型结构特殊，学者们提供了更为简便和直观的解法——表上作业法。此外，有些线性规划问题从实际意义上看，并非运输问题，但其模型结构类似运输问题，也可以化作运输问题进行求解。

第一节 运输问题及其数学模型

首先来分析下面的问题。

例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

二、销大于产

销大于产的运输问题的特征是Σai < Σbj，其数学模型为：

mnminf???cijxiji?1j?1?ni?1,?,m??xij?ai ?j?1??mj?1,?n??xij?bj?i?1?xij?0,i?1,?,m;j?1,?,n???解此问题可假想一个产地Am+1，其产量为：am+1 = Σbj－Σai； 若用xm+1，j表

示从Am+1到Bj的运量，可令cm+1，j=0或等于第Bj产地每缺单位物资的损失。因为xm+1，j实际上表示Bj销地所缺的物资数量。经处理后，问题变成了产销平衡的运输问题，其数学模型为：

minf???cijxiji?1j?1m?1n?ni?1,?,m?1??xij?ai ?j?1??m?1j?1,?n??xij?bji?1??xij?0,i?1,?,m?1;j?1,?,n???此时，可用表上作业法求解。在用最小元素法求解该问题初始基可行解时，若

某行的运价全为零时，则该行最后考虑。

第四节 运输问题的应用

一、一般的产销不平衡运输问题

例3.3 表3—12给出了三个产地及四个销地的某物资供应量与需求量及从各产到各销地的单位物资运价（元/单位物资），试求出运费最小的运输方案。

第三章——11

表3—12 销 地 产地 A1 A2 A3 需求量(t) B1 3 7 9 50 B2 2 5 6 100 B3 4 2 3 150 B4 5 1 5 50 供应量(t) 200 100 150 450 350 解 由表可知，总供应量为450(t)，总需求量为350(t)，即问题为产大于销的运输问题。因此，需要假想一个销地B5，其需求量为450－350=100(t)。问题并未给出物资的存储费用，因此，从各产地到B5的单位运价视为零，即ci5=0（i=1，2，3）。这样得到新的产销平衡表如表3—13。 表3—13 销 地 产地 A1 A2 A3 需求量(t) B1 3 7 9 50 B2 2 5 6 100 B3 4 2 3 150 B4 5 1 5 50 B5 0 0 0 100 供应量(t) 200 100 150 450 450 用表上作业法解得该问题的最优运输方案为：x11=50，x12=100，x15=50，x23=50，x24=50，x33=100，x35=50。其中x15=50，x35=50表示A1，A3各有50个单位的物资库存。总运费为800元。

例3.4 某运输问题有三个产地和三个销地，产地的总供应量小于销地的最高需求量之和，但超过了销地的最小需求量之和。现在，各销地的最低需求必须满足，最低需求到最高需求的之间的需求若不能满足，会造成经济损失，其中B1销量必须满足，B2、B3不能满足的单位损失分别为3元和2元。单位运价、供应量与需求量见表3—14。求出最优调运方案。

表3—14 销 地 产地 A1 A2 A3 最低需求 最高需求

B1 5 6 3 600 600 B2 1 4 2 120 200 第三章——12

B3 7 6 5 300 430 供应量 200 800 150 1150 解 B2的最高需求与最低需求不相等，而B1的最低需求必须满足，因此可将B2看成两个销地B21和B22，其中B21的需求量为B2的最低需求量，该需求量必须全部满足；B22的需求量为B2的最高需求量减去最低需求量，即为200－120=80，该需求量可以不被满足。对销地B3也可作同样的处理。这样问题就变为一个三个产地、五个销地的运输问题，其中总产量为1150，总供应量为1230，因此是一个销大于产的问题。为解此问题，又要假设一个产地A4，其产量为1230－1150 = 80。为了使各销地的最低销量得到满足，可令A4运往B1、B21、B31的运价为M，即给出一个很高的运价。这样就可以得到如下产销平衡表，见表3—15。

表3—15 产销平衡表 销 地 产地 A1 A2 A3 A4 需求量 B1 5 6 3 M 600 B21 1 4 2 M 120 B22 1 4 2 3 80 B31 7 6 5 M 300 B32 7 6 5 2 130 供应量(t) 200 800 150 80 1230 1230

用表上作业法求解，可以得到如表3—16所示的调运方案。

表3—16 最优调运表 销 地 产地 A1 A2 A3 A4 需求量

从最优调运表中可以看出，B1和B2的需求量得到全部满足，而B3的需求量满足了350。总费用（包括缺货损失费160元）为8100元。

B1 B21 120 120 B22 80 80 B31 300 300 B32 50 80 130 供应量(t) 200 800 150 80 1230 1230 450 150 600 二、生产与存储问题

例3.5 某高科技企业生产某种光电通讯产品，现要安排今后4个季度的生产计划。已知今后四个季度的合同签定数，企业各季度生产能力以及各季度的生产成本

第三章——13

如表3—15所示。考虑资金的机会成本，预计每件产品每存储一个季度的费用为0.1千元。在完成合同的条件下，试安排这四个季度的生产计划，使生产成本与存储费用之和最小。

表3—17 季 度 1 2 3 4 解 设xij表示第i季度生产第j季度交货的该种产品的数量，考虑生产成本与存储费用后，xij所对应的目标函数中的价格系数cij如表3—18所示。

表3—18 xij所对应的价格系数cij j i 1 2 3 4 这样问题的数学模型可以描述为：

min f = 3.2x11+3.3x12+3.4x13+3.5x14+3.33x22+3.43x23

+3.53x24+3.31x33+3.41x34+3.42x44 x11+x12+x13+x14≤270 x22+x23+x24≤260

x33+x34≤280

x44≤270

x11 =230 x12+x22 =265 x13+x23+x33 =255 x14+x24+x34+x44 =245

xij≥0，i=1，?，4；j=1，?，4；i≥j

模型中，前4个条件为生产能力约束，后四各条件为合同限制约束。观察该模型，若将x21、x31、x32、x41、x42、x43等变量补齐，则模型变为一个标准的运输问题数学模型。为了保证模型的性质不变，必须使这些补齐的变量为0。为此，可在目标函数中令这些变量的系数为M，这样就得到一个产销不平衡的运输问题。此时，

1 3.2 2 3.3 3.33 3 3.4 3.43 3.31 4 3.5 3.53 3.41 3.42 合同签定数（台） 230 265 255 245 生产能力（台） 270 260 280 270 生产成本（千元） 3.2 3.33 3.31 3.42 第三章——14

可假设一个销地，变成产销平衡问题。产销表及运价表如表3—19所示。

表3—19 销地 产地 1 2 3 4 销量

用表上作业法，可求得四个季度的生产计划如表3—20所示。 表3—20 销地 产地 1 2 3 4 销量 从最优调运表中可以看出，第1季度生产270台，其中40台用于满足第季度需要，第2季度生产225台，第3季度生产260台，其中5台用于满足第4季度的需要，第4季度则生产240台。总费用为3299.15千元。

1 230 230 2 40 225 265 3 255 255 4 5 240 245 5 55 30 85 产量 270 280 260 270 1080 1080 1 3.2 M M M 230 2 3.3 3.33 M M 265 3 3.4 3.43 3.31 M 255 4 3.5 3.53 3.41 3.42 245 5 0 0 0 0 85 产量 270 280 260 270 1080 1080 三、转运问题

例3.6 某公司生产某种高科技产品。该公司在大连和广州设有两个分厂生产这种，在上海和天津设有两个销售公司负责对南京、济南、南昌和青岛四个城市进行产品供应。因大连与青岛相距较近，公司同意也可以向青岛直接供货。各厂产量、各地需要量、线路网络及相应各城市间的每单位产品的运费均标在图4—1中，单位为百元。现在的问题是：如何调运这种产品使公司总的运费最小？

解 如图所示，给各城市编号，即i=1，2，?，8分别代表广州、大连、上海、天津、南京、济南、南昌和青岛。

设xij表示从i到j的调运量（台），则问题的目标函数为

min f = 2x13+3x14+3x23+x24+4x28+2x35+6x36+3x37

+6x38+4x45+4x46+6x47+5x48

第三章——15

1 2 2 600 广 州 3 6 3 上 海 3 6 4 4 4 3 6 天津 2 5 1 400 大 连 4

↑

供应量

图 3—1 公司运输网络

对于发点1、2有供应量约束

x13+x14≤600 x23+x24+x28≤400

对于中转点3、4有平衡约束

x13+x23 ??x35 ??x36 ??x37 ??x38 = 0 x14+x24 ??x45 ??x46 ??x47 ??x48 = 0

对于需求点5、6、7、8有需求量约束

x35+x45 = 200 x36+x46 = 150 x37+x47 = 350 x38+x48 +x28 = 300

由此可得该问题的线性规划模型

min f = 2x13+3x14+3x23+x24+4x28+2x35+6x36+3x37

+6x38+4x45+4x46+6x47+5x48 x13+x14≤600 x23+x24+x28≤400

x13+x23 ??x35 ??x36 ??x37 ??x38 = 0 x14+x24 ??x45 ??x46 ??x47 ??x48 = 0 x35+x45 = 200 x36+x46 = 150 x37+x47 = 350 x38+x48 +x28 = 300

xij≥0，对于所有i、j

第三章——16

5 南京 200

6 济 南 150 350

7 南昌 8 青 岛 300 ↑

需求量

对于上述模型，用单纯形法可以得到最优解，但如果将其转化成运输问题模型，用表上作业法求解不仅简单而且直观。具体做法是：每个中转站对于发点来说可以看作是销地，其销量为所有可以运到该地的产量之和；每个中转站对于销地来说可以看作是产地，其产量等于其销量。这样，该问题就变成了4个产地、6个销地的运输问题。产地到销地的单位运价的处理办法是：中转站自己到自己的运价为0，网络图中，不能直接运输的产地到销地之间的运价为M，其余运价直接用网络图中标明的数字。问题的产销平衡表如下表所示。

表3—21 销地 产地 1（广州） 2（大连） 3（上海） 4（天津） 需求量

用表上作业法，可求得该问题的最优调运方案如表3—22所示。 表3—22 销地 产地 1（广州） 2（大连） 3（上海） 4（天津） 需求量 即，广州向中转站上海运550台，天津运50台；大连向中转站天津运100台，直接向青岛运300台；中转站上海向南京和南昌分别运200台和350台；中转站天津向济南运150台。最小运费为4600元

3(上海) 4(天津) 5(南京) 6(济南) 7(南昌) 8(青岛) 550 450 1000 50 100 850 1000 200 200 150 150 350 350 300 300 供应量 600 400 1000 1000 3000 3000 3(上海) 4(天津) 5(南京) 6(济南) 7(南昌) 8(青岛) 2 3 0 M 1000 3 1 M 0 1000 M M 2 4 200 M M 6 4 150 M M 3 6 350 M 4 6 5 300 供应量 600 400 1000 1000 3000 3000 第三章——17

习 题 三

1．判断表3—23、表3—24中给出的调运方案能否作为表上作业法求解的初始基可行解？为什么？

表3—23 销 地 产地 A1 A2 A3 需求量

表3—24 销 地 产地 A1 A2 A3 需求量

2．用表上作业法求解下面运输问题

表3—25 销地 单价 产地 A1 A2 A3 需求量 3．产地A1、A2及销地B1、B2、B3的有关数据如下表。销地B1、B2、B3允许缺货，产地A1、A2允许存储。问怎样调配，使总费用最少？建立其数学模型，并用表上作业法求解。

第三章——18

B1 50 0 50 B2 100 100 B3 150 150 B4 0 50 50 供应量 200 100 50 B1 60 10 70 B2 100 100 B3 140 10 150 B4 50 50 供应量 200 100 70 B1 3 12 6 300 B2 9 20 11 500 B3 8 7 13 900 B4 6 10 14 600 供应量 600 1000 700 表3—26 销地 单价 产地 A1 A2 需求量 单位缺货费 B1 4 6 50 3 B2 6 2 100 8 B3 8 4 100 5 供应量 200 200 单位存储费 5 4 4．某百货公司去外地采购A、B、C、D四种规格的服装，数量分别为A——1500套；B——2000套，C——3000套，D——3500套。有三个城市可供应上述规格服装，供应数量为城市I——2500套，II——2500套，III——5000套。由于这些城市的服务质量、运价等销售情况不一，预计售出后的利润（元/套）也不同，详见表3-52。

表3—27

I II III A 10 8 9 B 5 2 3 C 6 7 4 D 7 6 8 请帮助该公司确定一个预期盈利最大的采购方案。

5．甲、乙、丙三个城市每年分别需煤炭320、250、350万吨，由A、B两处煤矿负责供应。已知煤炭年供应量为A——400万吨，B——450万吨。由煤矿至各城市的单位运价（万元/万吨）见表3—28。

表3—28

A B 甲 15 12 乙 18 25 丙 22 16 由于需大于供，经研究平衡决定，甲城市供应量不少于280万吨，乙城市需要量应全部满足，丙城市供应量不少于270万吨。此外甲城市每缺1万吨煤损失10万元，丙城市每缺1万吨煤损失12万元。试求将供应量分配完又使总费用（包括缺货费）为最低的调运方案。

6．某厂要完成合同规定的三个时期的某产品订货任务，现已知各时期工厂的生产能力、合同任务、生产单位产品的成本等数据如表3—29所示。又已知单位产品每时期存储费为1，现要求：建立该问题的LP数学模型；将其化为运输问题，并用表上作业法求解该问题。

第三章——19

表3—29 时期 1 2 3

生产能力 30 20 25 定货量 20 15 20 生产成本 8 12 11 第三章——20

本文来源：https://www.bwwdw.com/article/o6oo.html