第四章 运筹学运输问题ppt课件.ppt

第四章 运输问题,第四章 运输问题,第1节 运输问题的数学模型第2节 表上作业法第3节 产销不平衡的运输问题及其求解方法第4节 应用问题举例,第1节 运输问题的数学模型,一、运输问题运输问题属于线性规划问题，因为其约束方程组的系数矩阵A具有特殊的结构，所以专门介绍一种比单纯形法更简便的求解方法，以节约计算时间和费用。,第1节 运输问题的数学模型,例1：某公司经销甲产品。它下设三个加工厂。每日的产量分别是：A1为7吨，A2为4吨，A3为9吨。该公司把这些产品分别运往四个销售点。各销售点每日销量为：B1为3吨，B2为6吨，B3为5吨，B4为6吨。已知从各工厂到各销售点的单位产品的运价如下表所示。问该公司应如何调运产品，在满足各销点的需要量的前提下，使总运费为最少。,二表合一,第1节 运输问题的数学模型,二、运输问题的数学模型已知有m个生产地点（简称产地） 可供应某种物资，其供应量（产量）分别为 ；有n个销售地点（简称销地） ，其需要量（销量）分别为 ，从 到 运输单位物资的运价（单位运价）为 ，将这些数据表示在如下页的两个表中。问应如何调运，在满足各销地销量的情况下，使总的运费支出最少？,第1节 运输问题的数学模型,产销平衡表 两个表合二为一,单位运价表,第1节 运输问题的数学模型,产销平衡表 单位运价表,二表合一,第1节 运输问题的数学模型,例1：解：设xij为第i加工厂向第j销售点的甲产品的供应量，cij表示第i加工厂向第j销售点供应甲产品的单位运费,第1节 运输问题的数学模型,产销平衡 运输问题的数学模型：设xij表示从产地Ai运往销地Bj的产品数量,对偶问题,第1节 运输问题的数学模型,特征（1）决策变量：mn（2）约束方程：mn；都是等式约束（3）目标函数：最小化,第1节 运输问题的数学模型,系数矩阵A,基变量数目,解的类型,第1节 运输问题的数学模型,（4）约束方程组系数矩阵AA中只有数字0或1A的每一列只有两个非零元素1,第1节 运输问题的数学模型,（6）基变量：mn1（7）对于产销平衡的运输问题必有可行解和最优解,第2节 表上作业法,一、表上作业法的解题思路表上作业法的实质是单纯形法在求解运输问题时的一种简化方法，属于单纯形法，又称为运输单纯形法。,第2节 表上作业法,二、表上作业法的特点表上作业法是一种迭代法用表上作业法求解运输问题，直接在表上进行，不必写出数学模型,第2节 表上作业法,三、表上作业法的解题步骤（一）找出初始基可行解：在产销平衡表上找出 (m+n-1)个数字格，形成初始产销平衡表方法（二）求非基变量检验数：计算初始产销平衡表中空格的检验数，判别是否达到最优解，如果已达到，停止计算；否则转入3方法（三）确定换入变量和换出变量，找出新的基可行解方法：闭回路调整法（四）重复（二）（三），直到求出最优解说明：以例1为例解释表上作业法的解题步骤,第2节 表上作业法,产销平衡表 单位运价表,二表合一,最小元素法确定初始解,伏格尔法确定初始解,第2节 表上作业法,表上作业法解题步骤（一）：确定初始基可行解方法一：最小元素法1、基本思路从运费上考虑，优先安排单位运价最小的产地和销地之间的运输业务，最大限度地满足其产销量，从而实现“就近供应”。,第2节 表上作业法,例2：用最小元素法找出例1的初始基可行解。,第2节 表上作业法,例2：解： 初始产销平衡表,闭回路法求检验数,位势法求检验数,第2节 表上作业法,2、求解步骤第一，从单位运价表中找出最小运价，（有两个或两个以上的最小单位运价，则任选其一），比较产量和销量：产量销量，则划去该运价所在列；产量销量，则划去该运价所在行。并在初始产销平衡表上填上相应的数字。第二，从单位运价表中未被划去的运价中再找最小运价，重复第一第二，直到单位运价表中所有运价都被划去，并找出(m+n-1)个数字格。,第2节 表上作业法,3、小结（1）在初始产销平衡表上每填入一个数字，在单位运价表上就划去一行或一列（当表中只剩一个元素时，在初始产销平衡表上填数字时，在单位运价表上同时划去一行和一列）（2）在单位运价表上共划去（mn）条直线，（相当于单位运价表上所有cij都被划去两次）（3）在初始产销平衡表上填了（mn1）个数字格，每行数字之和该行产量，每列数字之和该列销量,第2节 表上作业法,例3：用最小元素法求出下述运输问题的初始基可行解。,表上作业法求解例3,第2节 表上作业法,例3：解： 初始基可行解,出现退化解,第2节 表上作业法,例4：判断下表给出的运输方案能否作为用最小元素法 求解出的初始基可行解？,第2节 表上作业法,表上作业法解题步骤（一）：确定初始基可行解方法二：伏格尔法1、基本思路按某一最小单位运价优先安排物品调运时，可能导致其他产销点不得不采用很高的单位运价进行运输，从而使整个运输费用增加。对每一个产地或销地，找出最小单位运价和次小单位运价，求二者之差。若差值不大，当不能按最小单位运价安排运输时造成的运费损失不大；反之，若二者之差很大，不按最小单位运价组织运输就会造成很大损失，所以应尽量按最小单位运价安排运输。,第2节 表上作业法,例5：用伏格尔法找出例1的初始基可行解。,第2节 表上作业法,例5：解： 初始产销平衡表,闭回路法求检验数,位势法求检验数,第2节 表上作业法,2、求解步骤第一，在单位运价表中分别计算各行和各列的最小运价与次小运价的差额，并填在该表的最右列和最下行。第二，从行或列差额中选出最大者，（有两个或两个以上的最大差额，则选择差额所在行（或列）中的最小单位运价），选择它所在行或列中的最小运价，按照最小元素法确定初始基可行解。第三，对单位运价表中未被划去的运价再计算各行和各列的最小运价与次小运价的差额，并仍填入该表的最右列和最下行，重复第二、三，直至给出初始基可行解为止，即找出（m+n-1）个数字格。,第2节 表上作业法,3、小结（1）伏格尔法和最小元素法仅在确定产销关系的原则上不同，其余步骤都相同（伏格尔法是在最小元素法的基础上改进的一种方法）（2）伏格尔法给出的初始基可行解比用最小元素法给出的初始基可行解更接近最优解（伏格尔法给出的解的目标函数值比最小元素法给出的解的目标函数值小）（3）伏格尔法得出的初始基可行解常作为运输问题最优解的近似解,作业4-1,作业4-1：1、用最小元素法找出下述运输问题的初始基可行解。2、找出下述运输问题的近似最优解。（其中M为任意大正数，表示含义为从A4到B4不存在运输路线）,第2节 表上作业法,表上作业法解题步骤（二）：求检验数，判别最优解基本思路计算空格（非基变量）的检验数，（运输问题的目标函数要求实现最小化）当所有检验数0时，所得的解是最优解，否则要进行解的改进。,第2节 表上作业法,表上作业法解题步骤（二）：求检验数，判别最优解方法一：闭回路法例6：用闭回路法求例2所得的初始基可行解的检验数。,第2节 表上作业法,例6：解： 检验数表,第2节 表上作业法,1、检验数的含义检验数表示变化的运费。即：若某空格（Ai，Bj）的检验数0，表示将该空格变为数字格使运输费用减少，则当前这个解不是最优解；反之，若所有空格的检验数都0，表示不管怎样变换，都使运输费用增加，则目标函数已无法改进，当前这个解就是最优解,第2节 表上作业法,2、求解步骤第一，在初始产销平衡表上，从每一空格出发找一条闭回路：以某空格为起点，用水平或垂直线向前画，碰到一数字格转90（有些情况下也可以不改变方向），然后继续前进，直到回到起始空格为止。第二，在一闭回路上，令某空格取值为+1，表示增加的运量，然后变化相应数字格的值，并计算该闭回路上运费的变化值，即为该空格的检验数，填入检验数表。,第2节 表上作业法,例7：用闭回路法求例5所得的初始基可行解的检验数。,第2节 表上作业法,例7：解： 检验数表,第2节 表上作业法,3、小结（1）闭回路的顶点，除出发点为空格外，其他均为数字格（2）每个空格唯一存在一条闭回路（3）对于产销点过多的运输问题，空格的数目很大，计算检验数很繁琐,第2节 表上作业法,表上作业法解题步骤（二）：求检验数，判别最优解方法二：位势法1、基本思路,第2节 表上作业法,原问题 对偶问题,第2节 表上作业法,2、求解步骤第一，仿照初始产销平衡表做一个表，在对应的数字格处填入单位运价cij。第二，在表的最右列和最下行分别增加一列ui和一行vj，使表中的单位运价等于它所在行和列的ui与vj之和，求出所有的ui和vj，并填写在表中。第三，计算各空格的检验数，填入检验数表。,第2节 表上作业法,例8：用位势法求例2所得的初始基可行解的检验数。,第2节 表上作业法,例8：解： 检验数表,第2节 表上作业法,例9：用位势法求例5所得的初始基可行解的检验数。,第2节 表上作业法,例9：解： 检验数表,第2节 表上作业法,2、小结当运输问题的产地和销地很多时，空格的数目很大，采用位势法计算检验数简便,第2节 表上作业法,（三）确定换入和换出变量，找出新的基可行解，直至求出最优解方法：闭回路调整法1、基本思想在初始产销平衡表中，选取检验数为负的所有空格中的最小者作为换入格，以对应空格为出发点画出闭回路，在经过的数字格中选择（-1）的最小者，对应的数字格为换出格，然后对闭回路上各顶点的数据进行调整，得到另一个更好的基可行解。,第2节 表上作业法,2、求解步骤第一，确定换入格。在初始产销平衡表上，最小的负检验数所在的空格为换入格，（有两个或两个以上的最小者，则任选其一），并以此空格为出发点，作一闭回路。第二，确定换出格：选择闭回路上标记为-1的数字格中的最小者，记做，则该数字格为换出格。第三，调整：将闭回路上标记为+1的数字格加，标记为-1的数字格减，得到新的基可行解。第四，采用闭回路法或位势法求空格的检验数，若所有检验数都0，则获得最优解；否则重复第一第三，直至求出最优解。,表上作业法求解例1,第2节 表上作业法,最优解 检验数表 z*=85,无穷多（多重）最优解,第2节 表上作业法,例10：用表上作业法求解例3。,第2节 表上作业法,最优解 检验数表 z*=61,唯一最优解,第2节 表上作业法,四、表上作业法的解1、唯一最优解所有空格（非基变量）的检验数大于0，该运输问题有唯一最优解。,第2节 表上作业法,最优解 检验数表 z*=61,例3最优解的情况,第2节 表上作业法,2、无穷多（多重）最优解某个空格（非基变量）的检验数为0时，该运输问题有无穷多（多重）最优解。在已求得一个最优解的表中，以这样的空格出发做闭回路重新进行调整，得到另一个最优解。,第2节 表上作业法,例1最优解的情况 无穷多最优解 检验数表 z*=85,第2节 表上作业法,例1最优解的情况 无穷多最优解 检验数表 z*=85,第2节 表上作业法,3、退化解某个数字格（基变量）为0时，该运输问题为退化解。退化解出现的情况：确定初始解的各供需关系时，若在某格填入某数字后，出现该处的供应量与需求量相等。用闭回路调整法调整时，在闭回路上出现两个或两个以上的具有（-1）标记的相等的最小值。,第2节 表上作业法,例11：已知某初始产销平衡表，如下表：空格A2B4格的检验数0，其余空格的检验数均0 ，试确定换入、换出格，求出新的基可行解。,第2节 表上作业法,例11：解： 下一个基可行解,第2节 表上作业法,五、表上作业法计算步骤框图,第2节 表上作业法,例12：已知三个产地A1，A2，A3，四个销地B1，B2，B3，B4的产销量即单位运价如下表所示，求使总运费最少的调运方案。,第2节 表上作业法,例12：解： 无穷多最优解、退化解 z*=6000,作业4-2,作业4-2：用表上作业法求解下列运输问题的最优解。1、要求采用伏格尔法、 位势法求解 2、要求采用伏格尔法、 闭回路法求解,第3节 产销不平衡的运输问题及其求解方法,一、求解思路总产量不等于总销量，为使用表上作业法求解，将产销不平衡运输问题转化为产销平衡运输问题。,第3节 产销不平衡的运输问题及其求解方法,二、求解方法1、总产量总销量（ ）,第3节 产销不平衡的运输问题及其求解方法,数学模型：,第3节 产销不平衡的运输问题及其求解方法,解题思路：为借助于产销平衡的表上作业法求解，增加一个假想的销地Bn+1，由于实际上它不存在，因而由产地Ai（i=1，2，m）调运到这个假想销地的物品数量xi,n+1，就是就地存贮在Ai的物品数量。就地存贮的物品未经运输，所以其单位运价ci,n+1=0（i=1，2，m）。,第3节 产销不平衡的运输问题及其求解方法,第3节 产销不平衡的运输问题及其求解方法,数学模型：,第3节 产销不平衡的运输问题及其求解方法,数学模型变化： ,第3节 产销不平衡的运输问题及其求解方法,2、总产量总销量（ ）,第3节 产销不平衡的运输问题及其求解方法,数学模型：,第3节 产销不平衡的运输问题及其求解方法,解题思路：为借助于产销平衡的表上作业法求解，增加一个假想的产地Am+1，由于实际上它不存在，因而由它发往各个销地的物品数量xm+1,j（j=1，2，n），就是各销地Bj所需物品的欠缺额。欠缺的物品未经运输，所以其单位运价cm+1,j=0（j=1，2，n）。,第3节 产销不平衡的运输问题及其求解方法,第3节 产销不平衡的运输问题及其求解方法,数学模型：,第3节 产销不平衡的运输问题及其求解方法,数学模型变化： ,第3节 产销不平衡的运输问题及其求解方法,例13：用表上作业法求解下述运输问题的最优解。,第3节 产销不平衡的运输问题及其求解方法,例13：解： 产销不平衡产销平衡,第3节 产销不平衡的运输问题及其求解方法,无穷多最优解 z*=35,第3节 产销不平衡的运输问题及其求解方法,小结采用最小元素法或伏格尔法求初始基可行解时，由于虚拟产地或销地不存在，所以尽管二者的单位运价ci,n+1=0或cm+1,j=0，但不能作为最小运价（元素）优先使用。应从有实际运输任务的产地或销地之间安排运量，最后再考虑虚拟产、销地的0运价。,作业4-3,作业4-3：用表上作业法求解下列运输问题的最优调运方案和最小总运费。1、要求采用最小元素法、 位势法求解 2、要求采用最小元 素法、闭回路法求解,第4节 应用问题举例,例14：设有三个化肥厂（A，B，C）供应四个地区1，2，3，4的农用化肥。假定等量的化肥在这些地区使用效果相同。各化肥厂年产量，各地区需要量及从各化肥厂到各地区运送单位化肥的运价如下表所示。试求出总的运费最节省的化肥调运方案。,第4节 应用问题举例,例14：解： 产销不平衡产销平衡,第4节 应用问题举例,简化表格,第4节 应用问题举例,退化最优解 z*=2460,第4节 应用问题举例,例15：某工厂有B1，B2，B3三个分厂，在生产中需要用的热水分别由A1，A2两个锅炉房供应。每月各分厂的需求量、锅炉房的供应量及输送热水的单位费用见下表。由于需求量大于供应量，工厂正在建设新的锅炉房。但是在新锅炉房投入使用之前，经总厂协调后决定：保证B1分厂的需求量，B2分厂的供应量最多可减少90t（吨），B3分厂的供应量不能少于180t。应如何安排给三个分厂的供热水方案，在保证各分厂基本需求的情况下，使输送总费用最低。,第4节 应用问题举例,例15：解： 产销不平衡产销平衡,第4节 应用问题举例,简化表格,第4节 应用问题举例,无穷多、退化最优解 z*=3490,