运筹学—运输问(一).ppt

运筹学—运输问题(一)一﹑运输问题的数学模型已知有m个生产地Aii=1,2,…,m。可供应某种物资,其供应量(产量)分别为ai,i=1,2,…,m,有n个销地Bj,j=1,2,…,n,其需要量分别为bj,j=1,2,…,n,从Ai到Bj运输单位物资的运价(单价)为cij,这些数据汇总于产销平衡表和单位运价表7—1,7—2。销地产地1,2,…,n产量1·ma1·am销量b1,…,bn销地产地1,2,…,n1·mc11,…,c1n…cm1,…,cmn表7-1表7-2若用xij表示从Ai到Bj的运量,那么在产销平衡的条件,要求得总运费最小的调运方案,可求以下数学模型:这就是运输问题的数学模型。它含有m×n个变量,(m+n)个约束方程。其系数矩阵如下:11…1·········x11x12…x1nx21x22…x2n…xm1xm2…xmn11…111…1111111·········111m行n行i=1m∑minz=j=1n∑cijxij=bjj=1,2,…,n()i=1m∑xij=aii=1,2,…,m()j=1n∑xijxij≥011…1·········x11x12…x1nx21x22…x2n…xm1xm2…xmn11…111…1111111·········111m行n行该系数矩阵中对应变量xij的系数向量pij,其分量除第i个和第m+j个为1,其余为零。即pij=(0,…,1,…,1,…,0)T=ei+em+j对产销平衡的运输问题,有以下关系式成立i=1m∑j=1n∑xij=j=1n∑bji=1m∑ai=j=1n∑i=1m∑xij=所以模型最多只有m+n-1个独立约束方程。即系数矩阵的秩≤m+n-1。二﹑表上作业法表上作业法是单纯形法在求解运输问题时的一种简化方法。其实质是单纯形法。其步骤是:⑴找出初始基可行解。即在(m×n)产销平衡表上给出m+n-1个数字格。⑵求各非基变量的检验数,即表上计算空格的检验数。判断是否达到最优解。如已是最优解,则停止计算,否则转下一步。⑶确定换入变量和换出,找出新的基可行解。在表上用闭回路调整法。⑷重复(2),(3)直到得到最优解。下面详细讨论在表上如何填上m+n-1个数字格?如何计算空格的检验数?如何用闭回路法实现基变换?1﹒确定初始基可行解(填上m+n-1个数字格)介绍两种方法:最小元素法和伏格尔法。下面通过一个例题来说明这两种方法。例1某公司经销甲产品。它下设三个加工厂。每日的产量分别为:A1-7吨,A2-4吨,A3-9吨。该公司把这些产品分别运往四个销售点。各销售点每日的销量为:B1-3吨,B2-6吨,B3-5吨,B4-6吨。已知从各工厂到各销售点的单位产品的运价为下表。问该公司应如何调运产品,在满足各销售点的需要量的前提下,使总费用为最小。销地产地B1B2B3B4A1A2A33171**********运价表(单位:元/吨)销地产地B1B2B3B4产量A1A2A3749销量3656产销平衡表(单位:吨)销地产地B1B2B3B4A1A2A33171**********运价表(单位:元/吨)销地产地B1B2B3B4产量A1A2A3749销量3656产销平衡表(单位:吨)⑴﹒最小元素法确定初始基可行解这种方法的基本思想是:从单位运价表中最小的运价开始确定供销关系,然后次小。一直到给出初始基可行解为止。3做法:①从运价表中挑选最小元素,并比较所在的行和列的产量和销量的大小,确定供应量。当产大于销,划去该元素所在列;当产小于销,划去该元素所在行。②然后在未划去的元素中再最小元素,再确定供应关系。重复①。14633总费用:86元⑵﹒伏格尔法①计算运价表中各行和各列中最小费用与次小费用的差额,并填入表的最右列和最下行。②从行和列差额中选出最大者,再选择它所在的列或行中的最小元素。若出现两个以上相同的最大值,则从这几个最大值所在的行和列中选出最小元素。依此确定供应关系及供应量。同时根据最小元素法中“划行或划列的规则”,划去该元素所在的行或列。③对表中未划去的元素再分别计算各行和各列的最小费用与次小费用的差额,并填入表的最右列和最下行。重复第②步工作。④重复②,③步。直到给出初始解。销地产地B1B2B3B4行差额A1A2A33171**********列差额运价表(单位:元/吨)销地产地B1B2B3B4产量A1A2A3749销量3656产销平衡表(单位:吨)2513011621301232120131276512这样我们利用伏格尔法得到一个运输方案(右表)。它的总运费为:83元2﹒最优解的判别利用最小元素法或伏格尔法可以求出一个基可行解。在产销平衡表中填数字的格对应基变量,空格对应非基变量。下面讨论计算空格的检验数cij-CBB-1pij,i,j∈N。由于运输问题的目标函数是要求实现