运输问题的求解方法

运输问题的求解方法第1页，共34页，2023年，2月20日，星期日一、产销平衡表与单位运价表

运输问题还可用产销平衡表与单位运价表进行描述。假设某种物资有m个生产地点Ai（i=1，2，…，m），其产量（供应量）分别为ai（i=1，2，…，m），有n个销地Bj（j=1，2，…，n），其销量（需求量）分别为bj（j=1，2，…，n）。从Ai到Bj运输单位物资的运价（单价）为Cij。将这些数据汇总可以得到产销平衡表和单位运价表5.3.1。第2页，共34页，2023年，2月20日，星期日销地产地产量销量表5.3.1产销平衡表与单位运价表第3页，共34页，2023年，2月20日，星期日运输这一类特殊问题可用更加简便的求解方法———表上作业法求解，实质仍是单纯形法，步骤如下：

（1）确定初始调运方案，即找出初始基可行解,在产销平衡表上给出m+n-1个数字格。二、表上作业法

第4页，共34页，2023年，2月20日，星期日

（2）求非基变量的检验数，即在表上计算空格的检验数，判别是否达到最优解：是否存在负的检验数？如果存在负的检验数，则初始调运方案不是最优方案；如果所有检验数都非负，则初始调运方案已经是最优方案了。如果已经得到最优调运方案，则停止计算，否则转入下一步。（3）确定换入变量和换出变量，找出新的调运方案（新的基可行解），即在表上用闭回路法进行调整。

(4）重复（1）～（2），直到求出最优解为止。

第5页，共34页，2023年，2月20日，星期日（一）确定初始可行基的方法最小元素法从单位运价表中最小的运价开始确定供销关系，然后考虑运价次小的，一直到给出初始基可行解为止。伏格尔法采用最小元素法可能造成其他处的更多浪费，伏格尔法考虑最小运费与次小运费之间的差额，差额越大，就按次小运费调运。

第6页，共34页，2023年，2月20日，星期日（二）最优解的判别

计算非基变量（空格）的检验数,当所有的检验数时，为最优解。求空格检验数的方法有：闭回路法

以某一空格为起点找一条闭回路，用水平或垂直线向前划，每碰到一数字格转900后，继续前进，直到回到起始空格为止。第7页，共34页，2023年，2月20日，星期日闭回路如图5.3.1的（a）、（b）、（c）等所示。从每一个空格出发一定存在并且可以找到唯一的闭回路。因为，m+n-1个数字格（基变量）对应的系数向量是一个基，任一空格（非基变量）对应的系数向量是这个基的线性组合。图5.3.1闭回路示意图

第8页，共34页，2023年，2月20日，星期日

举例说明：可表示为而这些向量构成了闭回路见图第9页，共34页，2023年，2月20日，星期日位势法

一种较为简便的求检验数的方法。设是对应运输问题的m+n个约束条件的对偶变量。B是含有一个人工变量Xa的初始基矩阵。Xa在目标函数中的系数Ca

，由线性规划的对偶理论可知而每一个决策变量Xij的系数向量，所以由单纯形法可知，所有基变量的检验数等于0，即第10页，共34页，2023年，2月20日，星期日例1：假设某种物资共有3个产地，其日产量分别是：A1为7t，A2为4t，A3为9t；该种物资的4个销售地，其日销量分别：B1为3t，B2为6t，B3为5t，B4为6t；各产地到销售地的单位物资的运价如表5.3.2所示。在满足各销售点需要量的前提下，如何调运该种物资，才能使总运费达到最小？销地产地B1B2B3B4A1A2A3317119432101085表5.3.2下面用具体例子说明表上作业法的计算步骤。第11页，共34页，2023年，2月20日，星期日解：首先列出这一问题的产销平衡表，见表5.3.3。

表5.3.3某物资运输的产销平衡表

销地产地B1B2B3B4产量A1A2A3749销量3656第12页，共34页，2023年，2月20日，星期日⑴用最小元素法求解：第1步，从表5.3.4中找出最小运价为1，表示应先将A2

的产品供应B1

。在表5.3.3中（A2

B1

）的交叉格处填上3，得表5.3.4。将表5.3.4中的B1

列运价划去，得表5.3.5。销地产地B1B2B3B4产量A1A2A33749销量3656表5.3.4第13页，共34页，2023年，2月20日，星期日销地产地B1B2B3B4A1A2A3119432101085表5.3.5第2步，在表5.3.5未划去的元素中再找出最小运价为2，确定A2多余的1t物资供应B3

。得表5.3.6。将表5.3.5的行运价划去，得表5.3.7。第14页，共34页，2023年，2月20日，星期日销地产地B1B2B3B4产量A1A2A331749销量3656表5.3.6销地产地B1B2B3B4A1A2A3119432101085表5.3.7第15页，共34页，2023年，2月20日，星期日第3步，按照上述方法直到单位运价表上的所有元素被划去为止。最后在产销平衡表上得到一个调运方案，即初始基可行解，见表5.3.8。销地产地B1B2B3B4产量A1A2A331749销量3656表5.3.8第16页，共34页，2023年，2月20日，星期日⑵伏格尔法的步骤是：第1步：在表5.3.2中分别计算出各行、各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行，见表5.3.9。销地产地B1B2B3B4行差额A1A2A3317119432101085011列差额2513表5.3.9第17页，共34页，2023年，2月20日，星期日第2步：从行或列差额中选出最大者，选择它所在行或列中的最小元素。在表5.3.9中，可确定A3的产品应首先供应B2，得表5.3.10。将单位运价表中的列的数字划去，得表5.3.11。第18页，共34页，2023年，2月20日，星期日表5.3.10销地产地B1B2B3B4产量A1A2A36749销量3656销地产地B1B2B3B4A1A2A331732101085表5.3.11第19页，共34页，2023年，2月20日，星期日第3步,对表5.3.11中余下的元素再分别计算出各行、各列的最小运费和次最小运费的差额，重复第1、第2步，直到给出初始基可行解为止。初始基可行解列于表5.3.12。表5.3.12销地产地B1B2B3B4产量A1A2A3365213749销量3656伏格尔法给出的初始基可行解更接近最优解。本例中用伏格尔法给出的初始基可行解就是最优解。第20页，共34页，2023年，2月20日，星期日⑶用闭回路法判别检验：闭回路法计算检验数的经济解释为,在已给出初始基可行解的表中，可从任一空格出发，如（A1,B1），若让A1的产品调运1t给B1，为了保持产销平衡，就要依次进行调整,就构成了以（A1,B1）空格为起点，其他为数字格的闭回路，如表5.3.13中的虚线所示。闭回路各顶点所在格的右上角数字是单位运价。第21页，共34页，2023年，2月20日，星期日表5.3.13调整的方案使运费增加第22页，共34页，2023年，2月20日，星期日将“1”填（A1,B1）格中，这就是检验数。按上述办法，可找出所有空格的检验数，见表5.3.14。当检验数还有负数时，需要对原方案进行改造。表5.3.14

第23页，共34页，2023年，2月20日，星期日⑷用位势法检验:

第1步,按最小元素法给出表5.3.8的初始基可行解，作表5.3.15。在对应表5.3.8的数字格处填入单位运价。销地产地B1B2B3B4A1A2A31432105表5.3.15第24页，共34页，2023年，2月20日，星期日第2步,在上表增加一行一列，在列中填入，在行中填入，得表5.3.16。销地产地B1B2B3B4A1A2A314321050-1-529310表5.3.16第25页，共34页，2023年，2月20日，星期日首先令u1=0,然后按可确定所有和的数值。第3步,按计算所有空格的检验数，特设计计算表5.3.17。表5.3.17第26页，共34页，2023年，2月20日，星期日

⑸

改进的方法——闭回路调整法:

在表5.3.17中，(A2,B4)为调入格，以此格为出发点，作一闭回路,得表5.3.18。表5.3.18

第27页，共34页，2023年，2月20日，星期日

格的调入量是选择闭回路上具有（-1）的数字格中的最小者即，然后，按闭回路上的正、负号，加、减此值得到调整方案，如表5.3.19所示。再用闭回路法或位势法求各空格的检验数，得表5.3.20。在表5.3.20中，因为所有检验数都非负，故得最优解，这时，得到最小运费为85（元）。第28页，共34页，2023年，2月20日，星期日销地产地B1B2B3B4产量A1A2A3365213749销量3656销地产地B1B2B3B4A1A2A30922112表5.3.19表5.3.20第29页，共34页，2023年，2月20日，星期日三、产销不平衡的运输问题的求解方法

前面求解运输问题的表上作业法，是以产销平衡为前提的，即实际情况需要把产销不平衡的问题化成产销平衡的问题。当产大于销运输问题的数学模型为求使第30页，共34页，2023年，2月20日，星期日且满足考虑多余的物资在哪一个产地就地储存的问题。设是产地Ai的储存量，于是有第31页，共34页，2023年，2月20日，星期日当时，令当时，令产销不平衡的运输问题就可以改写成：求