运筹学CH2运输规划

Chapter2运输规划

(TransportationProblem)运输规划问题运输规划的数学模型表上作业法运输问题的应用运输规划模型的Excel

本章主要内容：教学要求教学要求：了解运输问题的数学模型及其特点；掌握表上作业法；了解MicrosoftExcel求解运输问题的方法。重难点：表上作业法运输规划问题介绍

人们在从事生产活动中，不可避免地要进行物资调运工作。如某时期内将生产基地的煤、钢铁、粮食等各类物资，分别运到需要这些物资的地区，根据各地的生产量和销售量及各地之间的运输费用，如何制定一个运输方案，使总的运输费用最小。这样的问题称为运输问题。运输规划问题介绍

物资调运是一个典型的线性规划问题。1939年前苏联经济学家康托洛维奇提出这一问题；1941年美国数学家F.L.Hitchcock提出运输问题数学模型；1951年Dantzig将此类问题的解法系统化,完善化,改为用表上作业法求解.运输问题的分类分类：有转运与无转运运输问题无转运的运输问题:

产销平衡问题:

总产量=总销量

产销不平衡问题:

总产量>总销量，则为产大于销情况总产量<总销量，则为销大于产情况对于产销不平衡运输问题，可转化为产销平衡运输问题处理，而有转运问题可化为无转运问题处理。运输问题——网络图A1A2Am产地B1B2Bn销地a1a2amb1b2bnc11c12c1nc21c22c2ncm1cm2cmn若则称该问题为平衡运输问题，否则称为非平衡运输问题。运输问题产销平衡问题产销平衡问题

几个术语：

生产地（供应地，出发地）：产量（供应量）

销售地（需求地，目的地）：销量（需求量）

运价（单价）：单位产品运输费用

运费：单价×运量产销平衡问题的数学模型例2.1某公司从两个产地A1、A2将物品运往三个销地B1,B2,B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运价如下表所示，问：应如何调运可使总运输费用最小？B1B2B3产量A1646200A2655300销量150150200产销平衡问题的数学模型解：产销平衡问题：总产量=总销量＝500

设xij

为从产地Ai运往销地Bj的运输量，得到下列运输量表：B1B2B3产量A1x11x12x13200A2x21x22x23300销量150150200B1B2B3产量A1646200A2655300销量150150200产销平衡问题的数学模型数学模型为：产销平衡问题的数学模型产销平衡问题数学模型的一般形式：设某物品有m个产地A1,A2,…,Am；各产地的产量分别是a1,a2,…,am；有n个销地B1,B2,…,Bn。各销地的销量分别是b1,b2,…,bn

；假如从产地Ai(i=1,2,…,m)向销地Bj(j=1,2,…,n)运输单位物品的运价是cij；问怎样调运这些物品才能使总运费最小？产销平衡问题的数学模型这是一个线性规划问题，可以用单纯形法求解。但是，由于它所含变量多，求解极不方便。即使求解一个m＝3，n＝4的简单运输问题，变量数目也将达到19个之多。因此，必须寻找更简便的求解方法。产量约束销量约束非负约束总运输费用极小化由某一产地运往各个销地的物品数量之和等于该产地的产量由各个产地运往某一销地的物品数量之和等一该销地的销量非负条件产销平衡问题数学模型的特点1.运输问题有最优解2.运输问题约束条件的系数矩阵m

行n

行第i

个第(m+j)个系数列向量的结构：即除第i个和第(m+j)个分量为1外，其它分量全等于0。约束条件系数矩阵的元素等于0或1；约束条件系数矩阵的每一列有两个非零元素，对应于每一个变量在前m个约束方程中出现一次,在后n个约束方程中也出现一次；所有结构约束条件都是等式约束；各产地产量之和等于各销地销量之和。产销平衡问题数学模型的特点产销平衡问题的数学模型模型的变化：

1）有时目标函数求最大。如求利润最大或营业额最大等；

2）当某些运输线路上的能力有限制时，在模型中直接加入约束条件（等式或不等式约束)；

3）产销不平衡时，可加入假想的产地（销大于产时）或销地（产大于销时）。P89\P90产销平衡模型的求解-表上作业法

表上作业法是求解运输问题的一种简便而有效的方法,其求解过程在运输表上进行,它是一种迭代法,其实质是单纯形法。步骤为：

1.先按某种方法找出一个初始解(初始调运方案）；

2.对现行解作最优性判别；

3.若不是最优解,就在表上对它进行调整改进,得出一个新解；

4.再判别,再改进,直到得到运输问题的最优解为止；※在迭代过程中,得出的所有解都要求是运输问题的基可行解。表上作业法步骤步骤描述方法第一步求初始基行可行解（初始调运方案）最小元素法、元素差额法、第二步求检验数并判断是否得到最优解。当检验数σij全都非负时得到最优解；若存在检验数σij<0，说明还没有达到最优，转第三步。闭回路法第三步调整运量，即换基，对原运量进行调整得到新的基可行解，转入第二步闭回路调整法运输表表上作业法例2.2某运输资料如下表所示：单位销地运价产地产量311310719284741059销量3656问：应如何调运可使总运输费用最小？表上作业法-初始方案解：第1步求初始方案方法1：最小元素法

基本思想：就近供应，即从运价最小的地方开始供应（调运），然后次小，直到最后供完为止。表上作业法-初始方案用最小元素法确定初始方案的步骤：1）从表中找出运价最小的单元格。2）从该单元格所对应的产量和销量中选择最小的值，作为该单元格的运量。3）调整该单元格所对应的产量和销量，同时划去产量或销量的剩余量为0的行或列。4）再在剩下的单元格中重复1），2），3）步，至产量（销量）的剩余量为0结束。注意：表上作业法要求，调运方案的有数字格必须为m+n-1个。一般，用最小元素法给出的方案符合这一要求。表上作业法-初始方案总的运输费＝(3×1)+(6×4)+(4×3)+(1×2)+(3×10)+(3×5)=86元B1B2B3B4产量A17A2

4A39销量365631131019274105834163310403030表上作业法-初始方案

最小元素法的缺点：为了节省一处费用，有时可能造成其他处要多花费几倍费用。

基本思想：

元素差额法对最小元素法进行了改进，考虑到产地到销地的最小运价和次小运价之间的差额，如果差额很大，就选最小运价先调运，否则会增加总运费。方法2：Vogel法（伏格尔法、元素差额法）表上作业法-初始方案Vogel法（伏格尔法、元素差额法）步骤：1）从运价表中分别计算出各行和各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行。B1B2B3B4产量行差额A170A2

41A391销量3656列差额2513311310192741058表上作业法-初始方案2）再从差值最大的行或列中找出最小运价确定供需关系和供需数量。当产地或销地中有一方数量供应完毕或得到满足时，划去运价表中对应的行或列。重复1)和2)，直到找出初始解为至。B1B2B3B4产量行差额A170A2

41A3

91销量3656列差额2513311310192741058630表上作业法-初始方案单位销地运价产地产量行差额311310719284741053销量3056列差额0213—216303表上作业法-初始方案单位销地运价产地产量行差额311310719284741050销量3053列差额0—12—2163103表上作业法-初始方案单位销地运价产地产量行差额311310719281741050销量0053列差额7—12—663203—5表上作业法-初始方案单位销地运价产地产量行差额311310219281741050销量0003列差额——63203—512————表上作业法-初始方案单位销地运价产地产量行差额311310719284741059销量3656列差额536312该方案的总运费:(1×3)＋(4×6)＋(3×5)＋(2×10)＋(1×8)＋(3×5)＝85元表上作业法-初始方案用元素差额法求得的基本可行解更接近最优解。

最小元素法：总的运输费=86元伏格尔法：总的运输费=85元用元素差额法求得的基本可行解更接近最优解。表上作业法-最优解的判别

第2步最优解的判别（检验数的求法）

求出一组初始方案（基可行解）后，判断是否为最优解，仍然是用检验数来判断，记xij的检验数为λij，求最小值的运输问题的最优判别准则是：所有检验数都非负，则为最优运输方案（最优解）；所有检验数都>0，则为唯一最优运输方案（唯一最优解）；存在检验数为0，其他检验数>0，则为无穷多最优运输方案（无穷多最优解）。求检验数的方法：闭回路法表上作业法-最优解的判别闭回路的概念为一个闭回路，集合中的变量称为回路的顶点，相邻两个变量的连线为闭回路的边。如下表表上作业法-最优解的判别B1B2B3B4B5A1X11X12A2X23X25A3X31X35A4X42X43

从x11出发，用水平或垂直线段向前划，碰到数字格必须转90度，再继续向前，直到回到起点止。闭回路的变量集合是{x11,x12,x42,x43,x23,x25,x35,x31}。表上作业法-最优解的判别闭回路法求空格检验数空格闭回路概念：

从一空格出发，向数字格作直线，每遇数字格则转90度，直回到开始的空格。这种以一个空格为顶点，其余顶点全为数字格的闭合折线，被称为该空格的闭合回路。

可以证明：

按前面方法确定的调运方案，每一个空格都有惟一的闭合回路。表上作业法-最优解的判别空格检验数概念：

作出空格的闭合回路，令空格增加一个单位调运量(+1)，沿闭合回路进行减一(-1)增一(+1)方法进行平衡调整调运量得到新的调运方案，新方案总运费与前一方案总运费相比，总运费的改变量，就是该空格的检验数。最优性检验：所有空格检验数非负，则为最优解。

下面以例子说明空格检验数的求法：表上作业法-最优解的判别该空格检验数：λ11=(+1)×3+(-1)×1+(+1)×2+(-1)×3=1B1B2B3B4产量A1A2

A3销量311310192741058341633+1-1+1-11表上作业法-最优解的判别该空格检验数：λ12=(+1)×11+(-1)×4+(+1)×5+(-1)×10=2B1B2B3B4产量A1A2

A3销量311310192741058341633+1-1+1-121表上作业法-最优解的判别该空格检验数：λ22=(+1)×9+(-1)×4+(+1)×5+(-1)×10+(+1)×3+(-1)×2=1B1B2B3B4产量A1A2

A3销量311310192741058341633+1-1+1-121+1-11表上作业法-最优解的判别该空格检验数：λ22=(+1)×8+(-1)×10+(+1)×3+(-1)×2=-1

故不是最优解。B1B2B3B4产量A1A2

A3销量311310192741058341633+1-121+1-11-1表上作业法-解的改进第3步解的改进闭回路调整法步骤:1、找出空格检验数最小的空格；2、作此空格的惟一闭合回路；3、确定θ值：闭回路中具有(-1)的数字格中运量最小的运量作为θ；4、按闭合回路上的正、负号，将该单元格的运量加减此θ值，调整运量得新调运方案；5、再对此方案用闭回路法进行最优性检验。表上作业法-解的改进1、空格(2,4)检验数最小；2、作此空格的惟一闭合回路；3、确定θ值为1；B1B2B3B4产量A1A2

A3销量311310192741058341633211-11012+1-1+1-1表上作业法-解的改进4、按闭合回路上的正、负号，将该单元格的运量加减此θ=1值，调整运量得新调运方案（新的运输表）；B1B2B3B4产量A1A2

A3销量311310192741058341633+1-1+1-11250总的运输费＝(3×1)+(6×4)+(5×3)+(2×10)+(1×8)+(3×5)=85元表上作业法-解的改进对新的运输表进行最优解的判定，所有检验数都非负，故为最优解，且总的运输费＝(3×1)+(6×4)+(5×3)+(2×10)+(1×8)+(3×5)=85元。B1B2B3B4产量A1A2

A3销量3113101927410583516322021912表上作业法-解的改进同时，发现单元格（1,1）的检验数为0，此问题（模型）有无穷多解。B1B2B3B4产量A1A2

A3销量3113101927410583516322021912表上作业法-退化解的处理表上作业法计算中的问题：退化解：

※表格中一般要有(m+n-1)个数字格。但有时在分配运量时则需要同时划去一行和一列，这时需要补一个0，以保证有(m+n-1)个数字格。一般可在划去的行和列的任意空格处加一个0即可。

※利用闭回路调整法对解进行调整时，标有负号的最小运量作为调整量θ，若最小运量超过2个相同，则选择任意一个最小运量标记为“0”。（换句话说，调整后有2个或2个以上运量为0的单元格时，只取1个单元格为空格，其他单元格运量填0。）表上作业法-小结表上作业法的计算步骤：分析实际问题列出产销平衡表及单位运价表确定初始调运方案（最小元素法或Vogel法）求检验数（闭回路法）所有检验数≥0找出最小检验数，用闭回路调整法调整，得到新的调运方案得到最优方案，算出总运价运输规划产销不平衡问题利用教材P90方法处理，变为产销平衡问题。Excel求解演示例2.2例题：某公司承担4条航线的运输任务，已知：（1）各条航线的起点城市和终点城市及每天的航班数见表1；（2）各城市间的航行时间见表2；（3）所有航线都使用同一种船只，每次装船和卸船时间均为1天。问该公司至少应配备多少条船才能满足所有航线运输的需要？应用举例P93例4应用举例表1航线起点城市终点城市每天航班数1ED32BC23AF14DB1表2各城市间的航行时间（天）

至从ABCDEFA0121477B1