用表上作业法求解运输问题课件

第13章 运输问题（Transportation Problem）在线性规划问题中，有一类特殊类型的问题运输问题。这类问题主要研究把某种物资从若干个产地调运到若干个销地，每个产地的供应量和每个销地的销售量及从一个产地到一个销地的运输费用已知，要求确定一个总运费最少的方案。第13章 运输问题 在线性规划问题中，有一类1第13章运输问题（TransportationProblem）物资调配问题（MaterialTransferringProblem）n运输问题及数学模型（ModelforTransportation）n用表上作业法求解运输问题（SolveTransportationProblembyTable）n运输问题的进-步讨论（FurtherDiscussionaboutTransportationProblem）n应用问题举例（Parexample）第13章 运输问题（Transportation Prob2物资调配问题物资调配问题 在经济建设中，经常会碰到大宗物资调运问题，如煤、钢铁，木材、粮食等物，在全国有若干生产基地，根据已有交通网络，应如何制订调运方案，将这些物资运到各销售地点，而运费最小，效率最高。在物流系统中，物资的调拨和配送是物流管理决策的一项主要工作。在市场经济条件下，对资源实行市场实行优化配置，有利于国民经济持续发展。物资调配问题 在经济建设中，经常会碰到大宗物3n运输问题及数学模型运输问题及数学模型 本章研究单一品种物资的运输调度问题。其典型情况是：设某种物品有个产地（或供方）Ai（i=1，2，m），各产地的产量分别是ai（i=1，2，m），有n个销地Bj（j=1，2，n）,各销地的销量分别为bj（j=1，2，n）。假定从Ai（i=1，2，m）产地向销地Bj（j=1，2，n）运输单位物品的运价是。问怎样调运这些物品才能使总运费最小?1.运输问题数学模型运输问题数学模型 运输问题及数学模型 本章研究单一品种物资的运4这是由多个产地供应多个销地的单品种物品运输问题。为直观起见，可列出该问题的运输表（见下页）。表中的变量Xij（i=1，2，m；j=1，2，n）为由产地Ai运往销地Bj的物品数量。cij为Ai到Bj的单位运价。有时，将单位运价单独列入另一个表中，并称其为运价表。运输单价cij销售地Bi供应量B1B2Bnai产地AiA1c11c12c1na1A2c21c22 c2na2Amcm1cm2 cmnam销售量bjb1b2bn分布变量表A1x11x12x1nA2x21x22 x2nAmxm1xm2 xmn 这是由多个产地供应多个销地的单品种物品运输问5产销平衡运输问题的数学模型可表示如下：其中，约束条件右侧常数ai和bj满足如果运输问题的总产量等于其总销量，即有则称该运输问题为产销平衡运输问题；反之，称产销不平衡运输问题。产销平衡运输问题的数学模型可表示如下：其中，约束条件右侧常数6（1）运输问题有有限最优解2.运输问题数学模型的特点运输问题数学模型的特点 对前述运输问题，若令其变量其中，则xij就是前述述运输问题的一个可行解；另一方面，其目标函数有下界。目标函数值不会趋于-。由此可知，运输问题必存在有限最优解。（1）运输问题有有限最优解2.运输问题数学模型的特点 对前7（2）运输问题约束条件的系数矩阵即除第i个和第m+j个分量为l外，其它分量全等于0。其系数列向量的结构是：（2）运输问题约束条件的系数矩阵 即除第i个和第m+j个分量8由此可知，运输问题具有下述特点：（1）约束条件系数矩阵的元素等于0或1。（2）约束条件系数矩阵的每一列有两个非零元素，这对应于每一个变量在前m个约束方程中出现一次，在后n个约束方程中也出现一次。对产销平衡运输问题，除上述两个特点外，还有以下特点：所有结构约束条件都是等式约束，各产地产量之和等于各销地销量之和。由此可知，运输问题具有下述特点：9例1：三煤矿A1，A2，A3运往B1，B2，B3，B4三个城市销售，各煤矿的供应量和需求量如下页表，各城市的需求量其间的距离(或单位运价)cij如表下页表方格中的数据所示，试建立使总运输量(或总运费)最小的运输问题数学模型。单价cij销售地Bj供应量aiB1B2B3B4供应地AiA11621020A2735820A3329440需求量bj302510158080例1：三煤矿A1，A2，A3运往B1，B2，B3，B4三个城10解：设Xij为第i煤矿向第j城市的供应量，cij表示为第i煤矿向第j城市供应煤的单位运价。i=1，2，3；j=1，2，3，4。本例中a1+a2+a3=b1+b2+b3+b4=80，故是产销平衡运输问题。则可写出其数学模型。解：设Xij为第i煤矿向第j城市的供应量，cij表示为第i煤11根据运输问题的数学模型求出的运输问题的解X=(xij)，代表着一个运输方案，其中每一个变量xij的值表示由Ai调运数量为xij的物品给Bij。前已指出运输问题是一种线性规划问题，可设想用迭代法进行求解，即先找出它的某一个基可行解，再进行解的最优性检验，若它不是最优解，就进行迭代调整，以得到一个新的更好的解，继续检验和调整改进，直至得到最优解为止。3.运输问题的解运输问题的解 根据运输问题的数学模型求出的运输问题的解X=(xij12例1的一个基可行解：单价cij销售地Bj供应量aiB1B2B3B4供应地AiA11621020 x11=20A2735820 x21=10 x22=10A3329440 x32=15x33=15x34=15需求量bj302510158080例1的一个基可行解：单价cij销售地Bj供应量aiB1B2B13n用表上作业法求解运输问题用表上作业法求解运输问题 表上作业法是求解运输问题的一种简便而有效的方法，其求解工作在运输表上进行。表上作业法是一种迭代法，迭代步骤为：先按某种规则找出一个初始解(初始调运方案)；再对现行解作最优性判别；若这个解不是最优解，就在运输表上对它进行调整改进，得出一个新解；再判别，再改进；直至得到运输问题的最优解为止。如前所述，迭代过程得出的所有解都要求是运输问题的基可行解。用表上作业法求解运输问题 表上作业法是求解运输问题的14步骤：（1）找出初始即可行解，即在产销平衡表上分配初始调运方案，保证xij0，并且xij0的格（又称实格）必须有m+n-1个；（2）求出各非基变量的检验数ij（空格检验数），ij0时停止计算；ij0时在继续调整调运方案（换基迭代法）；（3）确定进基变量（空格换入变量）和出基变量（实格调出变量），找出新的基可行解（用空格闭回路法调整）；（4）重复第1-3步，直至获得ij0，输出xij*和minZ=Z*为止。步骤：151.给出运输问题的初始基可行解给出运输问题的初始基可行解(初始调运方案初始调运方案)结合例1详细说明表上作业法的解题步骤:（1）画出运输问题的求解作业表（见例1），由于，可以转入（2）；（2）找出初始基可行解（又称分配初始调运方案）。确定初始调运方案的方法很多，下面介绍三种常用的方法。单价cij销售地Bj供应量aiB1B2B3B4供应地AiA11621020 x11=20A2735820 x21=10 x22=10A3329440 x32=15x33=15x34=15需求量bj3025101580801.给出运输问题的初始基可行解(初始调运方案)16 a.最小元素法最小元素法容易直观想到，为了减少运费，应优先考虑单位运价最小(或运距最短)的供销业务，最大限度地满足其供销量。即对所有i和j，找出ci0j0=min(cij)，并将xi0j0=min(ai0,bj0)的物品量由Ai0供应给Bj0；若xi0j0=ai0，则产地Ai0的可供物品己用完，以后不再继续考虑这个产地，且Bj0的需求量由bj0减少为bj0-ai0。如果xi0j0=bj0，则销地bj0的需求已全部得到满足，以后不再考虑这个销地，且Ai0的可供量由ai0减少为ai0-bj0。a.最小元素法17然后，在余下的供、销点的供销关系中，继续按上述方法安排调运，直至安排完所有供销任务，得到一个完整的调运方案(完整的解)为止。这样就得到了运输问题的一个初始基可行解(初始调运方案)。由于该方法基于优先满足单位运价(或运距)最小的供销业务故称为最小元素法。然后，在余下的供、销点的供销关系中，继续按上述18最小元素法分配的初始调运方案单价cij销售地Bj供应量aiB1B2B3B4供应地AiA11621020 x11=20A2735820 x23=10 x24=10A3329440 x31=10 x32=25x34=5需求量bj302510158080最小元素法分配的初始调运方案 单价cij销售地Bj供应B1B19b.西北角法西北角法西北角法与最小元素法不同，它不是优先考虑具有最小单位运价的供销业务，而是优先满足运输表中西北角(即左上角)上空格的供销需求。b.西北角法20西北角法分配初始调运方案单价cij销售地Bj供应量aiB1B2B3B4供应地AiA11621020 x11=20A2735820 x21=10 x22=10A3329440 x32=15x33=15x34=15需求量bj302510158080西北角法分配初始调运方案 单价cij销售地Bj供应B1B2B21c.沃格尔法沃格尔法使用最小元素法有时按某一最小单位运价优先安排调运时，可能导致不得不采用运费很高的其它供销点对，使整个运输费用增加。对每一个供应地或销售地，均可由它到各销售地或到各供应地的单位运价中找出最小单位运价和次小单位运价，并称这两个单位运价之差为该地的罚数。若罚数的值不大，当不能按最小单位运价安排运输时造成的运费损失不大；反之，如果罚数的值很大，不按最小运价组织运输就会造成很大损失，故应尽量按最小单位运价安排运输。沃格尔法就是基于这种考虑提出来的。c.沃格尔法22沃格尔法分配初始调运方案单价cij销售地Bj供应量ai行罚数B1B2B3B412345供应A116210201100 x11=10 x13=10地AiA2735820224x22=20A332944011111x31=20 x32=5x34=15需求量bj30251015列罚数1213221032100441005200沃格尔法分配初始调运方案 单价cij销售地Bj供应量 ai23对比以上3种方法的初始调运方案，可看出，伏格尔法优于其他方法，也就是说伏格尔法确定的初始解得目标函数距离最优解目标函数最近，因而迭代运算数为最少，效率高。方法西北角法最小元素法伏格尔法目标函数Z300250220 对比以上3种方法的初始调运方案，可看出，伏格242.解的最优性检验解的最优性检验 要判定运输问题的某个解是否为最优解，可仿照一般单纯形法，检验这个解的各非基变量(对应于运输表中的空格)的检验数，苦有某空格的检验数为负，说明将变为基变量将使运输费用减少，故当前这个解不是最优解。若所有空格的检验数全非负，则不管样变换解均能使运输费用降低，即目标函数值已无法改进，这个解就是最优解。a.闭回路法2.解的最优性检验 要判定运输问题的某个解25现结合例1中用最小元素法给出的初始解，说明检验数的计算方法。其中一条闭回路检验数表销售地供应地B1B2B3B4A112=613=314=8A221=022=-3*A333=8因22=30，故知该解不是最优解，还有待调整改正。现结合例1中用最小元素法给出的初始解，说明检26闭回路可以是一个简单的矩形，也可以是由水平和竖直边线组成的其它更为复杂的封闭多边形.闭回路可以是一个简单的矩形，也可以是由水平和27n运输问题的进运输问题的进步讨论步讨论 上节讲述的运输问题的算法，是以总产量等于总销量(产销平衡)为前提的。实际上在很多运输问题中，总产量不等于总销量。这时，为了使用前述表上作业法求解，就需将产销不平衡运输问题化为产销平衡运输问题。1.产销不平衡的运输问题运输问题的进步讨论 上节讲述的运输问题的28如果总产量大于总销量，即这时的数学模型是如果总产量大于总销量，即29为借助于产销平衡时的表上作业法求解，可增加一个假想的销地Bn+1，由于实际上它不存在，因而由产地Ai(i=1,2,m)调运到这个假想销地的物品数量xi,n+1(相当于松弛变量)，实际上是就地存贮在Ai的物品数量。就地存贮的物品不经运输，故其单位运价ci,n+1(i=1,2,m)。为借助于产销平衡时的表上作业法求解，可增加一个假想的30若令假想销地的销量为bn+1，且则模型变为对应的运输表见下页。若令假想销地的销量为bn+1，且对应的运输表见下页。31单价cij销售地Bj供应量aiB1BnBn+1供应地AiA1C11c12c1n0a1X11A2c21c22c2n0a2x21x22Amcm1cm2cmn0amx32x33x34需求量bjb1Bn单价cij销售地Bj供应B1BnBn+1供A1C11c1232总销量大于总产量的情形可仿照上述类似处理，即增加一个假想的产地Am+1，它的产量等于由于这个假想的产地并不存在，求出的由它发往各个销地的物品数量，实际上是各销地所需物品的欠缺额，显然有 总销量大于总产量的情形可仿照上述类似处理，即33单价cij销售地Bj供应量aiB1B2B2B4供应地AiA1413459A21236106A3782610需求量bj5467 2522例：由各煤厂到各用户的单位运价如表所示，请确定总运费最少的调运方案。单价cij销售地Bj供应B1B2B2B4供A1413459A34单价cij销售地BjB1B2B2B4供应地AiA141345A2123610A37826需求量bj546725-22=3 供应量ai9610 555B5单价cij销售地BjB1B2B2B4 35在以上讨论中，假定物品由产地直接运送到销售目的地，不经中间转运。但是，常常会遇到这种情形：需先将物品由产地运到某个中间转运站(可能是另外的产、销地或中间转运仓库)，然后再转运到销售地。有时，经转运比直接运到目的地更为经济。总之，很多情况下，在决定运输方案时有必要把转运也考虑进去。显然考虑转运将使运输问题变得更为复杂。2.有转运的运输问题 在以上讨论中，假定物品由产地直接运送到销售目36假定m个产地A1,A2,Am和n个销地B1,B2,Bn都可以作为中间转运站使用，从而发送物品的地点相接收物品的地点都有m+n个。这样一来，我们就得到了一个扩大了的运输问题。为建立其数学模型，令：ai：第个i产地的产量(净供应量)；bj：第j个销地的销量(净需要量)；xij：由第i个发送地运到第j个接收地的物品数量；cij：由第i个发送地到第j个接收地的单位运价；ti：第i个地点转运物品的数量；ci：第i个地点转运单位物品的费用。假定m个产地A1,A2,Am和n个销地B37现将产地和销地统一编号，并把产地排在前面，销地排在后面，则有假定为平衡运输问题，即有现将产地和销地统一编号，并把产地排在前面，销地排在后面，则有38根据前面对平衡运输问题的讨论，可得该扩大了的运输问题的数学模型如下：根据前面对平衡运输问题的讨论，可得该扩大了的运输问题的数学模39将上述模型中的各约束等式右侧的ti或tj移到等号左侧，然后在各式等号两端分别加上Q，并今，则可把模型写成：将上述模型中的各约束等式右侧的ti或tj移到等号左侧，然后在40要特别注意，在此模型中，对所有i=j，cij=-ci。由于目标函数中这一项为常数，它不影响求最优解，在优化过程中可不予考虑。该模型的运输表和运价表见下页。当不考虑转运费时，可令。要特别注意，在此模型中，对所有i=j，cij41运输表接收地供应地供应地销售地发送量1mm+1m+n供应地1x11x1mx1,m+1x1,m+nQ+a1mxm.,1xmmxm,m+1xm,m+nQ+am销售地m+1xm+1,1xm+1,mxm+1,m+1xm+1,m+nQm+nxm+n,1xm+1,n+mxm+n,m+1xm+n,m+nQ接收量QQQ+bm+1Q+bm+n运输表 接收地 供应地 销售地42运价表接收地供应地供应地销售地发送量1mm+1m+n供应地1-c1c1mc1,m+1c1,m+nQ+a1mcm.,1-cmcm,m+1cm,m+nQ+am销售地m+1cm+1,1cm+1,mcm+1cm+1,m+nQm+ncm+n,1cm+n,mvm+n,m+1-cm+nQ接收量QQQ+bm+1Q+bm+n运价表 接收地 供应地 销售地发送量1m43例2：已知A1，A2，A3三个饮料厂生产同一规格的饮料，用相同价格供应B1，B2，B3三个销售网点销售。有两个转运站T1，T2，并且产品运输可以在各产地，各销售地及各转运站之间转运。已知各产地、销地、中转站相互之间每吨货物的单位运价和产量，见下页表。例2：已知A1，A2，A3三个饮料厂生产同一44各产地、销地、中转站之间的关系产地转运站销售地产量A1A2A3T1T2B1B2B3产地A1862410830A2851395910A3654228720转运站T12148463T2328232销售地B1492425B2105863 4B38973254销售量153510（1）对扩大的运输问题建立运价表。对于没有运输路线的去任意大的正数M；对自己运输的运价cij=0。（2）所有转运站的转运量等于销量，即Q=30+20+10=15+35+10=60,取T1，T2的产量与运量均为60t。（3）在原来的产量与销量的数值在加上调运量，三个产地的产量为90t，70t，80t,销量均为60t；三个销量为75t,95t,70t,产量均为60t.如下页表所示。各产地、销地、中转站之间的关系产地转运站销售地产量A1A2A45用表上作业法求解的最优方案运量销售地产量A1A2A3T1T2B1B2B3产地A160151590A2551570A3602080T15451060T2402060B16060B26060B36060销售量6060606060759570用表上作业法求解的最优方案 运量销售地产量A1A246实际最优方案及最优运输路线如图，最小费用为300。A1A2A3B1B2B3T1T2实际最优方案及最优运输路线如图，最小费用为300。A1A2A47第第11、12、13章章 知识小结知识小结预测概述预测概述n时间序列预测技术时间序列预测技术 移动平均预测法移动平均预测法 指数平滑预测法指数平滑预测法n回归分析预测技术回归分析预测技术 一元线性回归预测法一元线性回归预测法 多元线性回归预测分析多元线性回归预测分析库存优化库存优化n确定性库存模型确定性库存模型 确定性库存基本模型确定性库存基本模型 缺货事后补足的模型缺货事后补足的模型 批量折扣库存模型批量折扣库存模型运输问题运输问题n物资调配问题物资调配问题运输问题及数学模型运输问题及数学模型用表上作业法求解运输问题用表上作业法求解运输问题运输问题的进运输问题的进-步讨论步讨论应用问题举例应用问题举例第11、12、13章 知识小结预测概述库存优化运输问题48