运输问题的求解方法.ppt

第3节运输问题的求解方法——表上作业法一、产销平衡表与单位运价表运输问题还可用产销平衡表与单位运价表进行描述。假设某种物资有m个生产地点Ai（i=12…m）其产量（供应量）分别为ai（i=12…m）有n个销地Bj（j=12…n）其销量（需求量）分别为bj（j=12…n）。从Ai到Bj运输单位物资的运价（单价）为Cij。将这些数据汇总可以得到产销平衡表和单位运价表5.3.1。销地产地运输这一类特殊问题可用更加简便的求解方法———表上作业法求解实质仍是单纯形法步骤如下：（1）确定初始调运方案即找出初始基可行解在产销平衡表上给出m+n-1个数字格。（2）求非基变量的检验数即在表上计算空格的检验数判别是否达到最优解：是否存在负的检验数？如果存在负的检验数则初始调运方案不是最优方案；如果所有检验数都非负则初始调运方案已经是最优方案了。如果已经得到最优调运方案则停止计算否则转入下一步。（3）确定换入变量和换出变量找出新的调运方案（新的基可行解）即在表上用闭回路法进行调整。(4）重复（1）～（2）直到求出最优解为止。（一）确定初始可行基的方法最小元素法从单位运价表中最小的运价开始确定供销关系然后考虑运价次小的一直到给出初始基可行解为止。伏格尔法采用最小元素法可能造成其他处的更多浪费伏格尔法考虑最小运费与次小运费之间的差额差额越大就按次小运费调运。（二）最优解的判别闭回路如图5.3.1的（a）、（b）、（c）等所示。从每一个空格出发一定存在并且可以找到唯一的闭回路。因为m+n-1个数字格（基变量）对应的系数向量是一个基任一空格（非基变量）对应的系数向量是这个基的线性组合。举例说明：可表示为位势法一种较为简便的求检验数的方法。设是对应运输问题的m+n个约束条件的对偶变量。B是含有一个人工变量Xa的初始基矩阵。Xa在目标函数中的系数Ca由线性规划的对偶理论可知而每一个决策变量Xij的系数向量所以由单纯形法可知所有基变量的检验数等于0即例1：假设某种物资共有3个产地其日产量分别是：A1为7tA2为4tA3为9t；该种物资的4个销售地其日销量分别：B1为3tB2为6tB3为5tB4为6t；各产地到销售地的单位物资的运价如表5.3.2所示。在满足各销售点需要量的前提下如何调运该种物资才能使总运费达到最小？解：首先列出这一问题的产销平衡表见表5.3.3。表5.3.3某物资运输的产销平衡表⑴用最小元素法求解：第1步从表5.3.4中找出最小运价为1表示应先将A2的产品供应B1。在表5.3.3中（A2B1）的交叉格处填上3得表5.3.4。将表5.3.4中的B1列运价划去得表5.3.5。销地产地销地产地第3步按照上述方法直到单位运价表上的所有元素被划去为止。最后在产销平衡表上得到一个调运方案即初始基可行解见表5.3.8。⑵伏格尔法的步骤是：第1步：在表5.3.2中分别计算出各行、各列的最小运费和次最小运费的差额并填入该表的最右列和最下行见表5.3.9。第2步：从行或列差额中选出最大者选择它所在行或列中的最小元素。在表5.3.9中可确定A3的产品应首先供应B2得表5.3.10。将单位运价表中的列的数字划去得表5.3.11。表5.3.10第3步对表5.3.11中余下的元素再分别计算出各行、各列的最小运费和次最小运费的差额重复第1、第2步直到给出初始基可行解为止。初始基可行解列于表5.3.12。表5.3.12⑶用闭回路法判别检验：闭回路法计算检验数的经济解释为在已给出初始基可行解的表中可从任一空格出发如（A1B1）若让A1的产品调运1t给B1为了保持产销平衡就要依次进行调整就构成了以（A1B1）空格为起点其他为数字格的闭回路如表5.3.13中的虚线所示。闭回路各顶点所在格的右上角数字是单位运价。表5.3.13将“1”填（A1B1）格中这就是检验数。按上述办法可找出所有空格的检验数见表5.3.14。当检验数还有负数时需要对原方案进行改造。表5.3.14⑷用位势法检验:第1步按最小元素法给出表5.3.8的初始基可行解作表5.3.15。在对应表5.3.8的数字格处填入单位运价。第2步在上表增加一行一列在列中填入