最优化运输问题

摘要：根据运输问题的基本特征，运用最优化的线性规划解决问题，通过实例对运输问题进行优化分析，建立运输问题的线性规划数学模型。将模型应用于一些特殊的运输问题，从而得到最优化的方案，提高实际运输工作中的经济效益。 关键词：最优化；运输问题；线性规划

1 运输问题的特征

运输问题关心的是以最低的总配送成本把供应中心的任何产品运送到每一个接收中心。每一个出发地都有一定供应量配送到目的地，每一个目的地都需要一定的需求量。

需求假设：从任何一个出发地到任何一个目的地的货物配送成本和所配送的数量成线性比例关系。

运输问题所需要的数据仅仅是供应量、需求量和单位成本。这些就是模型参数。如果一个问题可以完全描述成表1所示的参数表形式，并且符合需求假设和成本假设，那么这个问题（不管其中是否涉及到运输）都适用于运输问题模型，最终目的都是要使配送的总成本最小。这个模型的参数都包含在参数表中。 下面就通过例题来说明。

A公司是一家汽车生产商，A1、A2是它的工厂，生产的轿车用卡车把它们运送到三个分销仓库：A3、A4、A5。在下表中列有下列数据：每辆轿车从每个工厂到每个分销仓库所需的运输成本（Cij），每个工厂的供应量，以及每个经销商对轿车的需求量。求能使运输成本最低的从每个工厂到每个分销仓库运输轿车的数量以及最低的运输成本。

表 1 A公司的运输数据表

解：设Xij（i=1,2；j=1,2,3）；为从每个工厂到每个经销商运输轿车的数量，目

标是为了找出能使总运输成本最低的从每个工厂到每个经销商运输轿车的数量。所以，

目标函数为C=200X11+100X12+300X13+400X21+300X22+200X23

约束条件是：

X11+X12+X13=3000

X21+X22+X23=5000

11+X21=3000 12+X22=4000 31+X32=1000 ij（i=1,2，j=1,2,3）≥0 用微机很快就可以得出决策变量的下列最优值以及最低的运输成本200万元。 表2 A公司决策变量的最优值表 由上面的例题可以看出，对于一般的运输问题，首先是建立线性规划的模型，模型中包含的内容主要是目标函数和约束条件；然后再应用微机求解。 2 选址

许多公司的管理人员都面临着一个非常重要的决策：在什么地方设置一个新的重要设施。设施有可能是一个新的工厂、一个新的配送中心、一个新的管理中心或者其他的建筑物。一般来说，一个建筑物都有几个可供选择的地点。而且，在经济全球化的今天，这些可供选择的潜在地点很有可能已经超越了国界而在另一个国家中。在形成决策的过程之中包含了许多很重要的因素，其中一个就是运输成本。

A公司是一家大型石油公司。公司拥有大型配送网络。把石油运送到公司的

炼油厂，然后再把石油产品从炼油厂运送到公司的配送中心。A公司正在持续增加其几种主要产品的市场占有率，因此管理层决定建立一个新的炼油厂来增加公司的产量，接下来要作的决策就是确定在什么地方建设新的炼油厂。他们确定了三个非常有潜力和吸引力的备选地点。表中是A公司的一些相关数据，其中A1、A2是已有的炼油厂，B1、B2、B3是被选地点，C1、C2、C3是油田，D1、D2、D3、D4是配送中心。

表3 A公司的相关数据

表4 原油和石油制品的运输成本数据

现在要确定的是每一个新炼油厂建造地点选择带来的总原油运输成本以及每一个新炼油厂建造地点选择带来的总石油制品运输成本。对于这两种成本来说，一旦确立了建造地点，最优的运输计划也就确定了。因此，为了找出潜在选择地点的每一种成本，有必要为每一种情况都作出一个最优运输计划，然后再计算出相

应的成本。

以选择在B1建造新的炼油厂为例。

（1） 确定最低的总原油运输成本。

设Xij（i=1,2,3, j=1,2,3）为从油田向炼油厂运输原油的数量。 目标函数为：

C1=2X11+4X12+3X13+4X21+5X22+1X23+5X31+7X32+4X33

约束条件： X11+X12+X13=80

X21+X22+X23=60

X31+X32+X33=100

X11+X21+X31=90

X12+X22+X32=70

X13+X23+X33=80

Xij(i=1,2, j=1,2,3) ≥0

通过微机可以得出决策变量的最优值为：

X11=10 X12=70 X13=0 X21=0 X22=0 X23=60 X31=80 X32=0 X33=20

最低的总原油运输成本为840万元。

（2） 确定最低的总石油制品运输成本

设Yij(i=1,2,3, j=1,2,3,4) 为从炼油厂运输到配送中心的石油制品数量。

目标函数为：

C=5Y11+2Y12+6Y13+8Y14+6Y21+4Y22+3Y23+5Y24+8Y31+6Y32+3Y33+2Y34

Y11+Y12+Y13+Y14=90

Y21+Y22+Y23+Y24=70

Y31+Y32+Y33+Y34=80

Y11+Y21+Y31=60

Y12+Y22+Y32=50

Y13+Y23+Y33=70

Y14+Y24+Y34=6

Xij(i=1,2, j=1,2,3) ≥0

通过微机可以得出决策变量的最优值为：

Y11=40 Y12=50 Y13=0 Y14=0 Y21=20 Y22=0 Y23=50 Y24=0 Y31=0 Y32=0 Y33=20 Y34=60

最低的总石油制品的运输成本为750万元。

同理如果选择在B2建造新的炼油厂可以得出最低的总原油运输成本为900万元，最低的总石油运输成本为910万元，如果选择在B3建造新的炼油厂可以得出最低的总原油运输成本为1060万元，最低的总石油运输成本为770万元。

表5 A公司每一个被选厂址所带来的年变动成本

单位：百万元

经过比较总变动成本，最终可以选择在B1建造新的炼油厂。

3 结束语

所有经理都会遇到有约束条件下的最优化问题，因此线性规划在许多管理