第三章运输问题.ppt

第三章运输问题;第三章 运输问题;　　 　　若用xij表示从Ai到Bj的运量，那么在产销平衡条件下，要求得总运费最小的调运方案，可求解以下数学模型： ;第三章 运输问题;第三章 运输问题;　　系数矩阵中对应于变量xij的系数向量Pij，其分量除第i个和第m+j个为1外，其余的均为零。即 　　　　　Pij=（0…1…1…0）T=ei+em+j 　　对于产销平衡的运输问题由于存在： 　可以证明：只有m+n-1个独立约束方程。即系数矩阵的秩=m+n-1。由于以上特征，所以求解运输问题时，可用比较简便的计算方法，习惯上称为表上作业法。 　　3.2 表上作业法 　　表上作业法是单纯形法在求解运输问题的一种简化方法。其实质是单纯形法。但具体计算术语有所不同，可归纳为： 　　（1）找出初始基本可行解，即在（m×n）产销平衡表上给出m+n-1个独立的数字格。;　　（2）求各非基变量的检验数，即在表上计算空格的检验 　数，判别是否达到最优解。如已是最优解，则停止计算，否则转到下一步。 　　（3）确定调入变量和调出变量，找出新的基本可行解。在表上用闭合回路法调整。 　　（4）重复（2）（3），直到得到最优解。 　　以上算法都可以在表上完成。下面通过例子说明表上作业法的计算步骤。 　　例3.1 某公司经销一种产品，公司有三个加工厂A1、A2、A3，其产量分别为7t、4t、9t。公司有四个经销点B1、B2、B3、B4，其销量分别为3t、6t、5t、6t。已知各加工厂到各销售点的单位产品运费如下表所示，问公司应如何调运产品，在满足各销售点的需求量的前提下，使总运费最小。;　　解 先画出该问题的单位运价表和产销平衡表，如下：;　　设;　　1.最小元素法 　基本思想：就近供应，即从单位单价表中最小的运价开始确定供销关系，然后次小。一直到给出初始基本可行解为止。;　　2.伏格尔法 　　最小元素法的缺点：为了节省一处的费用，有时造成其他处要多花几倍的运费。伏格尔法考虑到，一产地的产品假如不能按最小运费就近供应，就考虑次小费用，这就有一个差额，差额越大，说明不能按最小运费调运时运费增加越多。因而对差额最大处，就应当采用最小运费调??。基于此，伏格尔法的步骤是： 　　第一步：分别计算出各行和各列的最小运费和次小运费之间的差额，并填入最右列和最下行。 　　第二步：从行和列差额中选择最大者，选择它所在的行或列的最小元素。 　　第三步：对未划的行和列再分别计算各行、各列的最小运费和次小运费的差额，重复一、二步。;第三章 运输问题;　　由上可见：伏格尔法与最小元素法除在确定供求关系的原则上不同外，其余步骤均相同。伏格尔法得出的初始解比最小元素法给出的初始解更接近最优解。 　　本例用伏格尔法给出的初始解即为最优解，最优值是85元。 　　3.2.2 最优解的判别 　　判别的方法是计算空格（非基变量）的检验数cij-CBB-1Pij都大于等于零（为什么？）。下面介绍两种求空格检验数的方法。 　　1.闭回路法 　　从每个空格出发找一条闭回路，它是以某空格为起点，用水平或垂直线向前划，每碰到一个数字时可以转90°后继续前进，直到回到起始空格为止。 ;　　可以证明：如果不区分闭回路的方向，每一个非基变量空格都存在唯一一个闭回路。 　　闭回路法是用来检查一个非基变量从零增加到大于零时能不能改变目标函数值的一种方法。 　　以上例采用最小元素法得出的调运表为例。;第三章 运输问题;　　例如在上表中，如果x22增加一个单位，那么要保持解的可行性，就要把x22回路中每个转角点的数字加以调整：减少一个x32，增加一个x34，减少一个x14，增加一个x13，减少一个x23。 　　这样的改变可以继续保持供求的平衡假如C22’表示增加一个单位x22后运费的增加数，那么由运费表可知： 　　c22’=c22-c32-+c34-c14+c13-c23= 　　　　　9-4+5-10+3-2=1 　　说明如果把x22增加一个单位，那么总运费要增加1元。 　　我们计算x24的检验数： 　　c24’=?;　　已知运输问题的产销平衡和单位运价表，试用伏格尔法求出一个调运方案，并判断该方案是否是最优的。;作业;　2.位势法 　　用闭回路法求检验数时，需要给每一空格找一条闭回路。当产销点多时，这种计算很繁琐。下面介绍一种更为简便的方法—位势法（乘数法）。 　　位势法的原理是线性规划的对偶理论。下面通过一个简单的例子来说明。 　　设有一个两个产地、三个销地的运输问题，其线性规划模型如下：;　 　　共有6个决策变量，在基本解中，应有四个基变量（为什么？），2个非基变量。设u1，u2为对应于产地的对偶变量，v1，v2，v3为对应于销地的对偶变量，则其对偶问题是：;　 　　如果原始问题得到一个调运方案（基本可行解），则对偶问题的