运筹学CH2运输规划

Chapter2运输规划(TransportationProblem)运输规划问题运输规划的数学模型表上作业法运输问题的应用运输规划模型的Excel解法本章主要内容：Page2教学要求教学要求：了解运输问题的数学模型及其特点；掌握表上作业法；了解MicrosoftExcel求解运输问题的方法。重难点：表上作业法Page3运输规划问题介绍人们在从事生产活动中，不可避免地要进行物资调运工作。如某时期内将生产基地的煤、钢铁、粮食等各类物资，分别运到需要这些物资的地区，根据各地的生产量和销售量及各地之间的运输费用，如何制定一个运输方案，使总的运输费用最小。这样的问题称为运输问题。Page4运输规划问题介绍物资调运是一个典型的线性规划问题。1939年前苏联经济学家康托洛维奇提出这一问题；1941年美国数学家F.L.Hitchcock提出运输问题数学模型；1951年Dantzig将此类问题的解法系统化,完善化,改为用表上作业法求解.Page5运输问题的分类分类：有转运与无转运运输问题无转运的运输问题:产销平衡问题:总产量=总销量产销不平衡问题:总产量总销量，则为产大于销情况总产量总销量，则为销大于产情况对于产销不平衡运输问题，可转化为产销平衡运输问题处理，而有转运问题可化为无转运问题处理。Page6运输问题——网络图A1A2Am产地B1B2Bn销地a1a2amb1b2bnc11c12c1nc21c22c2ncm1cm2cmn若则称该问题为平衡运输问题，否则称为非平衡运输问题。njjmiiba11Page7运输问题产销平衡问题Page8产销平衡问题几个术语：生产地（供应地，出发地）：产量（供应量）销售地（需求地，目的地）：销量（需求量）运价（单价）：单位产品运输费用运费：单价×运量Page9产销平衡问题的数学模型例2.1某公司从两个产地A1、A2将物品运往三个销地B1,B2,B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运价如下表所示，问：应如何调运可使总运输费用最小？B1B2B3产量A1646200A2655300销量150150200Page10产销平衡问题的数学模型解：产销平衡问题：总产量=总销量＝500设xij为从产地Ai运往销地Bj的运输量，得到下列运输量表：B1B2B3产量A1x11x12x13200A2x21x22x23300销量150150200B1B2B3产量A1646200A2655300销量150150200Page11)3,2,1;2,1(0200150150300200..556646min231322122111232221131211232221131211jixxxxxxxxxxxxxtsxxxxxxzij产销平衡问题的数学模型数学模型为：Page12产销平衡问题的数学模型产销平衡问题数学模型的一般形式：设某物品有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；问怎样调运这些物品才能使总运费最小？Page13产销平衡问题的数学模型这是一个线性规划问题，可以用单纯形法求解。但是，由于它所含变量多，求解极不方便。即使求解一个m＝3，n＝4的简单运输问题，变量数目也将达到19个之多。因此，必须寻找更简便的求解方法。njmixnjbxmiaxxczijjmiijnjiijminjijij,...,2,1;,...,2,1;0,...,2,1;,...,2,1;min1111产量约束销量约束非负约束总运输费用极小化由某一产地运往各个销地的物品数量之和等于该产地的产量由各个产地运往某一销地的物品数量之和等一该销地的销量非负条件Page14产销平衡问题数学模型的特点1.运输问题有最优解2.运输问题约束条件的系数矩阵111111111111111111212222111211mnmmnnxxxxxxxxxm行n行TijA0,,0,1,0,,0,1,0,,0第i个第(m+j)个系数列向量的结构：即除第i个和第(m+j)个分量为1外，其它分量全等于0。Page15约束条件系数矩阵的元素等于0或1；约束条件系数矩阵的每一列有两个非零元素，对应于每一个变量在前m个约束方程中出现一次,在后n个约束方程中也出现一次；所有结构约束条件都是等式约束；各产地产量之和等于各销地销量之和。产销平衡问题数学模型的特点Page16产销平衡问题的数学模型模型的变化：1）有时目标函数求最大。如求利润最大或营业额最大等；2）当某些运输线路上的能力有限制时，在模型中直接加入约束条件（等式或不等式约束)；3）产销不平衡时，可加入假想的产地（销大于产时）或销地（产大于销时）。P89\P90Page17产销平衡模型的求解-表上作业法表上作业法是求解运输问题的一种简便而有效的方法,其求解过程在运输表上进行,它是一种迭代法,其实质是单纯形法。步骤为：1.先按某种方法找出一个初始解(初始调运方案）；2.对现行解作最优性判别；3.若不是最优解,就在表上对它进行调整改进,得出一个新解；4.再判别,再改进,直到得到运输问题的最优解为止；※在迭代过程中,得出的所有解都要求是运输问题的基可行解。Page18表上作业法步骤步骤描述方法第一步求初始基行可行解（初始调运方案）最小元素法、元素差额法、第二步求检验数并判断是否得到最优解。当检验数σij全都非负时得到最优解；若存在检验数σij0，说明还没有达到最优，转第三步。闭回路法第三步调整运量，即换基，对原运量进行调整得到新的基可行解，转入第二步闭回路调整法Page19运输表产地销地B1B2…Bn产量x11x12…x1nA1c11c12…c1na1x21x22…x2nA2c21c22…c2na2…………………………xm1xm2…xmnAmcm1cm2…cmnam销量b1b2…bnPage20表上作业法例2.2某运输资料如下表所示：单位销地运价产地产量311310719284741059销量36564321BBBB321AAA问：应如何调运可使总运输费用最小？Page21表上作业法-初始方案解：第1步求初始方案方法1：最小元素法基本思想：就近供应，即从运价最小的地方开始供应（调运），然后次小，直到最后供完为止。Page22表上作业法-初始方案用最小元素法确定初始方案的步骤：1）从表中找出运价最小的单元格。2）从该单元格所对应的产量和销量中选择最小的值，作为该单元格的运量。3）调整该单元格所对应的产量和销量，同时划去产量或销量的剩余量为0的行或列。4）再在剩下的单元格中重复1），2），3）步，至产量（销量）的剩余量为0结束。注意：表上作业法要求，调运方案的有数字格必须为m+n-1个。一般，用最小元素法给出的方案符合这一要求。Page23表上作业法-初始方案总的运输费＝(3×1)+(6×4)+(4×3)+(1×2)+(3×10)+(3×5)=86元B1B2B3B4产量A17A24A39销量365631131019274105834163310403030Page24表上作业法-初始方案最小元素法的缺点：为了节省一处费用，有时可能造成其他处要多花费几倍费用。基本思想：元素差额法对最小元素法进行了改进，考虑到产地到销地的最小运价和次小运价之间的差额，如果差额很大，就选最小运价先调运，否则会增加总运费。方法2：Vogel法（伏格尔法、元素差额法）Page25表上作业法-初始方案Vogel法（伏格尔法、元素差额法）步骤：1）从运价表中分别计算出各行和各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行。B1B2B3B4产量行差额A170A241A391销量3656列差额2513311310192741058Page26表上作业法-初始方案2）再从差值最大的行或列中找出最小运价确定供需关系和供需数量。当产地或销地中有一方数量供应完毕或得到满足时，划去运价表中对应的行或列。重复1)和2)，直到找出初始解为至。B1B2B3B4产量行差额A170A241A391销量3656列差额2513311310192741058630Page27表上作业法-初始方案单位销地运价产地产量行差额311310719284741053销量3056列差额4321BBBB321AAA0213—216303Page28表上作业法-初始方案单位销地运价产地产量行差额311310719284741050销量3053列差额4321BBBB321AAA0—12—2163103Page29表上作业法-初始方案单位销地运价产地产量行差额311310719281741050销量0053列差额4321BBBB321AAA7—12—663203—5Page30表上作业法-初始方案单位销地运价产地产量行差额311310219281741050销量0003列差额4321BBBB321AAA——63203—512————Page31表上作业法-初始方案单位销地运价产地产量行差额311310719284741059销量3656列差额4321BBBB321AAA536312该方案的总运费:(1×3)＋(4×6)＋(3×5)＋(2×10)＋(1×8)＋(3×5)＝85元Page32表上作业法-初始方案用元素差额法求得的基本可行解更接近最优解。最小元素法：总的运输费=86元伏格尔法：总的运输费=85元用元素差额法求得的基本可行解更接近最优解。Page33表上作业法-最优解的判别第2步最优解的判别（检验数的求法）求出一组初始方案（基可行解）后，判断是否为最优解，仍然是用检验数来判断，记xij的检验数为λij，求最小值的运输问题的最优判别准则是：所有检验数都非负，则为最优运输方案（最优解）；所有检验数都0，则为唯一最优运输方案（唯一最优解）；存在检验数为0，其他检验数0，则为无穷多最优运输方案（无穷多最优解）。求检验数的方法：闭回路法Page34表上作业法-最优解的判别闭回路的概念},,,,,,{132222111jsisjsijijijijixxxxxx称集合),,,,,,(2121互不相同；其中ssjjjiii为一个闭回路，集合中的变量称为回路的顶点，相邻两个变量的连线为闭回路的边。如下表Page35表上作业法-最优解的判别B1B2B3B4B5A1X11X12A2X23X25A3X31X35A4X42X43从x11出发，用水平或垂直线段向前划，碰到数字格必须转90度，再继续向前，直到回到起点止。闭回路的变量集合是{x11,x12,x42,x43,x23,x25,x35,x31}。Page36表上作业法-最优解的判别闭回路法求空格检验数空格闭回路概念：从一空格出发，向数字格作直线，每遇数字格则转90度，直回到开始的空格。这种以一个空格为顶点，其余顶点全为数字格的闭合折线，被称为该空格的闭合回路。可以证明：按前面方法确定的调运方案，每一个空格都有惟一的闭合回路。Page37表上作业法-最优解的判别空格检验数概念：作出空格的闭合回路，令空格增加一个单位调运量(+1)，沿闭合回路进行减一(-1)增一(+1)方法进行平衡调整调运量得到新的调运方案，新方案总运费与前一方案总运费相比，总运费的改变量，就是该空格的检验数。最优性检验：所有空格检验数非负，则为最优解。下面以例子说明空格检验数的求法：Page38表上作业法-最优解的判别该空格检验数：λ11=(+1)×3+(-1)×1+(+1)×2+(-1)×3=1B1B2B3B4产量A1A2A3销量311310192741058341633+1-1+1-11Page39表上作业法-最优解的判别该空格检验数：λ12=(+1)×11+(-1)×4+(+1)×5+