运筹学基础及应用第五版 胡运权第三章.ppt

1运输问题的典例和数学模型,2表上作业法,3产销不平衡的运输问题及其应用,第三章运输问题,1运输问题的典例和数学模型,例1某食品公司经销主要产品之一是糖果，它下面设有三个加工厂，每天的糖果生产量分别为：，。该公司把这些糖果分别运往四个地区的门市部销售，各地区每天的销售量：，。已知从每个加工厂到各销售门市部每吨糖果的运价如下表：,单位：元/t,现在把问题概括一下，在线性规划中我们研究这样一类运输问题：有某种物资需要调运，这种物资的计量单位可以是重量、包装单位或其他。已知有m个地点可以供应该种物资（以后通称产地，用表示），有n个地点需要该种物资（以后通称销地，用表示），又知这m个产地的可供量（以后通称产量）为（可通写为），n个销地的需要量（以后通称销量）分别为（通写为）,从第i个产地到第j个销地的单位物资运价为。,产销平衡表,单位运价表,如果用xij代表从第i个产地调运给第j个销地的物资的单位数量，那么在产销平衡的条件下，使总运费支出最小，其数学模型如下：,2表上作业法,用表上作业法求解运输问题时，首先给出一个初始方案，其次给出一个判别准则，然后对初始方案进行调整，直到求出最优解。,由上节例子来具体说明表上作业法的步骤，首先列出产销平衡表和单位运价表。,一、初始方案的给定,初始方案的给定方法很多，这里介绍两种：,1.最小元素法,基本思想是就近供应，即从单位运价表中最小的运价处开始确定供销关系，依次类推，直到求出全部方案,第一步：,第二步：,第三步：,第四步：,第五步：,第六步：,这时单位运价表中所有元素已经都划掉了，产销平衡表中数字就是一个调运方案，这个方案的总费用为：,在选定最小元素后，如果该元素所在行的产量与所在列的销量相同，这时须同时划掉一行一列，并在该行或列上最小元素对应位置之外添加一个0。即下述例题表格中红色的零，需要选择且仅选择一个保留。,2.Vogel法,用最小元素法给定初始方案只从局部观点考虑就近供应，可能造成总体的不合理。,2.Vogel法,Vogel法的步骤：从运价表上分别找出每行与每列的最小的两个元素之差；从差值最大的行或列中找到最小运价确定供需关系和供应数量；当产地或销地中有一方数量上供应完毕或得到满足时，划去运价表中对应的行或列；重复步骤1、2、3，直到划去所有元素为止。,二、最优性检验与方案的调整,1.闭回路法,闭回路是指调运方案中由一个空格，和有数字的格，用水平和竖直连线包围成的封闭回路。,利用前面最小元素法得到的初始方案为例：,计算x11的检验数,将上述检验数填入检验数表中：,计算x31的检验数,计算x12的检验数,以此类推，算出所有检验数：,如果检验数表中，所有数字大于等于零，则此时为最优解，如果有小于零的，在该格所对应的调运方案表中按闭回路进行调整。,闭回路调整：,由此得新的调运方案：,计算得该方案运费为85元。需要对该方案每一空格重新求出检验数，判断是否最优，如果不是最优，需继续调整，计算后可知该方案为最优。,注：若减少运量的地方有两个以上相等的最小数时，会出现多个变0成空格，此时应补0到(m+n-1)个基变量,调整得新的调运方案：,2.位势法,仍以上例中最小元素法确定的初始调运方案为例。,第一步：将调运方案中有数字的格内数字改换为单位运价表中对应格的运价。即由下述两表：,得：,第二步：在表格下方和右方增加一行和一列，并填上一些数字，使得格中数字正好等于它所在行与所在列数字之和。,依次计算填入各数：,最终得：,将vi与uj相加求出空格处数字：,用单位运价表中数字减掉上表中对应数字，得：,该表即检验数表，与闭回路法求出的检验数表相同。,当所得检验数不全非负的时候，仍然需要对方案进行调整，调整方法与前面提到的相同。,3.产销不平衡的运输问题及其应用,例2设有A1、A2、A3三个产地生产某种物资，其产量分别为7t、5t、7t，B1、B2、B3、B4四个销地需要该种物资，销量分别为2t、3t、4t、6t，又知各产销地之间的单位运价如下表，试决定总运费最少的调运方案。,解：产地总产量为19t，销地总销量为15t，所以这是一个产大于销的运输问题。此时我们假想一个销地，这个销地的销量等于前面的总产量与总销量的差4t，我们也可视其为库存量，这样使得产销达到平衡。这时对它的运费为0，现在我们建立与之对应的产销平衡表和单位运价表。,单位运价表,产销平衡表,利用表上作业法求解得：,例3设有三个化肥厂供应四个地区的农用化肥，假定等量的化肥在这些地区使用效果相同，已知各化肥厂年产量，各地区年需要量及从各化肥厂到各地区单位化肥的运价表如下，试决定使总的运费最节省的化肥调拨方案。,解：这是一个产销不平衡的运输问题，总产量为160万t，四个地区最低需求为110万t，最高需求为无限。当其它地区都是满足最低需求时，第地区每年最多能分配到60万t，这样最高需求就是210万t，大于产量。,产销平衡表,为建立产销平衡表，在表中增加一假想化肥厂D，其年产量为50万t。并把各地区的最低需求和额外需求区分开来，建立产销平衡表。,当一个产地的产量不能运往某一个销地的时候，认为运价为M(表示任意大正数)。额外需求部分的销量，由于是否满足都可以，所以假想厂运往这些销地的运价定为0。,单位运价表,利用表上作业法求解得：,例4某食品公司经销主要产品之一是糖果，它下面设有三个加工厂，每天的糖果生产量分别为：，。该公司把这些糖果分别运往四个地区的门市部销售，各地区每天销售量为：，。,如果假定：（1）每个工厂生产的糖果不一定直接发运到销售点，可以将其中几个产地的糖果集中起来一起运。,（2）运往各销地的糖果可以先运给其中几个销地，再转运给其他销地。,（3）除产地、销地外，中间还可以有几个转运站，在产地之间、销地之间或产地与销地之间转运。,已知各产地、销地、中间转运站之间的单位运价，求如何在各地之间进行调运，使总的运费最小。,产地、销地、中间转运站间运价表：,首先通过该表建立单位运价表，由于各个地点间糖果可以相互运送，因此都可以作为产地，也都可以作为销地来考虑，将产地和销地都扩大为11个，不能够直接运送到的地点间运价设为M，运送到本地的运价设为0。,单位运价表,下面考虑如何建立产销平衡表：,1.中间转运站产、销量的确定,由于中间转运站所有的糖果都不保留，所以我们认为产量等于销量，同时因为在运费最小时不可能出现一批糖果在两地见来回倒运的现象，并且已知总产量=总销量=20t