最优化运输问题

摘要：根据运输问题的基本特征，运用最优化的线性规划解决问题，通过实例对运输问题进行优化分析，建立运输问题的线性规划数学模型。将模型应用于一些特殊的运输问题，从而得到最优化的方案，提高实际运输工作中的经济效益。关键词：最优化；运输问题；线性规划1 运输问题的特征 运输问题关心的是以最低的总配送成本把供应中心的任何产品运送到每一个接收中心。每一个出发地都有一定供应量配送到目的地，每一个目的地都需要一定的需求量。 需求假设：从任何一个出发地到任何一个目的地的货物配送成本和所配送的数量成线性比例关系。 运输问题所需要的数据仅仅是供应量、需求量和单位成本。这些就是模型参数。如果一个问题可以完全描述成表1所示的参数表形式，并且符合需求假设和成本假设，那么这个问题（不管其中是否涉及到运输）都适用于运输问题模型，最终目的都是要使配送的总成本最小。这个模型的参数都包含在参数表中。 下面就通过例题来说明。 A公司是一家汽车生产商，A1、A2是它的工厂，生产的轿车用卡车把它们运送到三个分销仓库：A3、A4、A5。在下表中列有下列数据：每辆轿车从每个工厂到每个分销仓库所需的运输成本（Cij），每个工厂的供应量，以及每个经销商对轿车的需求量。求能使运输成本最低的从每个工厂到每个分销仓库运输轿车的数量以及最低的运输成本。表 1 A公司的运输数据表工厂每辆轿车的运输成本（元）轿车供应量A3A4A5A12001003003000A24003002005000轿车需求量300040001000解：设Xij（i=1,2；j=1,2,3）；为从每个工厂到每个经销商运输轿车的数量，目标是为了找出能使总运输成本最低的从每个工厂到每个经销商运输轿车的数量。所以，目标函数为C=200X11+100X12+300X13+400X21+300X22+200X23约束条件是： X11+X12+X13=3000 X21+X22+X23=5000 X11+X21=3000 X12+X22=4000 X31+X32=1000 Xij（i=1,2，j=1,2,3）0用微机很快就可以得出决策变量的下列最优值以及最低的运输成本200万元。表2 A公司决策变量的最优值表起运地点到达地点（成本最低的运输模式）总产量A3A4A5A1X11=3000X12=0X13=03000A2X21=0X22=4000X23=10005000总需求300040001000由上面的例题可以看出，对于一般的运输问题，首先是建立线性规划的模型，模型中包含的内容主要是目标函数和约束条件；然后再应用微机求解。2 选址许多公司的管理人员都面临着一个非常重要的决策：在什么地方设置一个新的重要设施。设施有可能是一个新的工厂、一个新的配送中心、一个新的管理中心或者其他的建筑物。一般来说，一个建筑物都有几个可供选择的地点。而且，在经济全球化的今天，这些可供选择的潜在地点很有可能已经超越了国界而在另一个国家中。在形成决策的过程之中包含了许多很重要的因素，其中一个就是运输成本。A公司是一家大型石油公司。公司拥有大型配送网络。把石油运送到公司的炼油厂，然后再把石油产品从炼油厂运送到公司的配送中心。A公司正在持续增加其几种主要产品的市场占有率，因此管理层决定建立一个新的炼油厂来增加公司的产量，接下来要作的决策就是确定在什么地方建设新的炼油厂。他们确定了三个非常有潜力和吸引力的备选地点。表中是A公司的一些相关数据，其中A1、A2是已有的炼油厂，B1、B2、B3是被选地点，C1、C2、C3是油田，D1、D2、D3、D4是配送中心。表3 A公司的相关数据炼油厂每年所需原油量（百万吨）油田每年原油产量（百万吨）被选地点每年的运营成本（百万元）A190C180B1620A270C260B2570新的炼油厂80C3100B3530总量240总量240表4 原油和石油制品的运输成本数据油田从油田向炼油厂或潜在炼油厂运输原油的运输成本（百万元每百万桶）炼油厂把石油制品从炼油厂运输到配送中心的单位成本（百万元）A1A2B1B2B3D1D2D3D4C124313A15268C245134A26435C357456B18632B25436B34315所需要的单位数60507060现在要确定的是每一个新炼油厂建造地点选择带来的总原油运输成本以及每一个新炼油厂建造地点选择带来的总石油制品运输成本。对于这两种成本来说，一旦确立了建造地点，最优的运输计划也就确定了。因此，为了找出潜在选择地点的每一种成本，有必要为每一种情况都作出一个最优运输计划，然后再计算出相应的成本。以选择在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公司每一个被选厂址所带来的年变动成本 单位：百万元地点运输原油的总成本运输石油制品的总成本新炼油厂的运营成本总变动成本B18407506202210B29009105702380B310607705302360 经过比较总变动成本，最终可以选择在B1建造新的炼油厂。3 结束语 所有经理都会遇到有约束条件下的最优化问题，因此线性规划在许多管理问题中都能应用，只要是对生产、制造、投资、财务、工程等求最大利润、最小成本等问题，就基本上可以用线性