第13章运输问题（transportationproblem）

《第13章运输问题（transportationproblem）》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第13章运输问题（TransportationProblem）在线性规划问题中，有一类特殊类型的问题－－运输问题。这类问题主要研究把某种物资从若干个产地调运到若干个销地，每个产地的供应量和每个销地的销售量及从一个产地到一个销地的运输费用已知，要求确定一个总运费最少的方案。第13章运输问题（TransportationProblem）物资调配问题（MaterialTransferringProblem）运输问题及数学模型（ModelforTransportation）用表上作业法求解运输问题（SolveTransportationProblembyTable）运输问题的进-步讨论（Further

2、DiscussionaboutTransportationProblem）应用问题举例（Parexample）物资调配问题在经济建设中，经常会碰到大宗物资调运问题，如煤、钢铁，木材、粮食等物，在全国有若干生产基地，根据已有交通网络，应如何制订调运方案，将这些物资运到各销售地点，而运费最小，效率最高。在物流系统中，物资的调拨和配送是物流管理决策的一项主要工作。在市场经济条件下，对资源实行市场实行优化配置，有利于国民经济持续发展。运输问题及数学模型本章研究单一品种物资的运输调度问题。其典型情况是：设某种物品有个产地（或供方）Ai（i=1，2，…，m），各产地的产量分别是ai（i=1，2，…，m），

3、有n个销地Bj（j=1，2，…，n）,各销地的销量分别为bj（j=1，2，…，n）。假定从Ai（i=1，2，…，m）产地向销地Bj（j=1，2，…，n）运输单位物品的运价是。问怎样调运这些物品才能使总运费最小?1.运输问题数学模型这是由多个产地供应多个销地的单品种物品运输问题。为直观起见，可列出该问题的运输表（见下页）。表中的变量Xij（i=1，2，…，m；j=1，2，…，n）为由产地Ai运往销地Bj的物品数量。cij为Ai到Bj的单位运价。有时，将单位运价单独列入另一个表中，并称其为运价表。运输单价cij销售地Bi供应量B1B2…Bnai产地AiA1c11c12…c1na1A2c21c22…

4、c2na2┆┆┆…┆┆Amcm1cm2…cmnam销售量bjb1b2…bn分布变量表A1x11x12…x1nA2x21x22…x2n┆┆┆…┆Amxm1xm2…xmn产销平衡运输问题的数学模型可表示如下：其中，约束条件右侧常数ai和bj满足如果运输问题的总产量等于其总销量，即有则称该运输问题为产销平衡运输问题；反之，称产销不平衡运输问题。（1）运输问题有有限最优解2.运输问题数学模型的特点对前述运输问题，若令其变量其中，，则xij就是前述述运输问题的一个可行解；另一方面，其目标函数有下界。目标函数值不会趋于-∞。由此可知，运输问题必存在有限最优解。（2）运输问题约束条件的系数矩阵即除第i个和第

5、m+j个分量为l外，其它分量全等于0。其系数列向量的结构是：由此可知，运输问题具有下述特点：（1）约束条件系数矩阵的元素等于0或1。（2）约束条件系数矩阵的每一列有两个非零元素，这对应于每一个变量在前m个约束方程中出现一次，在后n个约束方程中也出现一次。对产销平衡运输问题，除上述两个特点外，还有以下特点：所有结构约束条件都是等式约束，各产地产量之和等于各销地销量之和。例1：三煤矿A1，A2，A3运往B1，B2，B3，B4三个城市销售，各煤矿的供应量和需求量如下页表，各城市的需求量其间的距离(或单位运价)cij如表下页表方格中的数据所示，试建立使总运输量(或总运费)最小的运输问题数学模型。单价c

6、ij销售地Bj供应量aiB1B2B3B4供应地AiA11621020A2735820A3329440需求量bj302510158080解：设Xij为第i煤矿向第j城市的供应量，cij表示为第i煤矿向第j城市供应煤的单位运价。i=1，2，3；j=1，2，3，4。本例中a1+a2+a3=b1+b2+b3+b4=80，故是产销平衡运输问题。则可写出其数学模型。根据运输问题的数学模型求出的运输问题的解X=(xij)，代表着一个运输方案，其中每一个变量xij的值表示由Ai调运数量为xij的物品给Bij。前已指出运输问题是一种线性规划问题，可设想用迭代法进行求解，即先找出它的某一个基可行解，再进行解的最优

7、性检验，若它不是最优解，就进行迭代调整，以得到一个新的更好的解，继续检验和调整改进，直至得到最优解为止。3.运输问题的解例1的一个基可行解：单价cij销售地Bj供应量aiB1B2B3B4供应地AiA11621020x11=20A2735820x21=10x22=10A3329440x32=15x33=15x34=15需求量bj302510158080用表上作业法求解运输问题表上作业法是求解运输问题