运筹学第四章运输问题.doc

《运筹学第四章运输问题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章运输问题主要内容：1、运输问题及其数学模型；2、表上作业法；3、运输问题的进一步讨论。重点与难点：表上作业法的原理、求解步骤，产销不平衡运输问题的求解方法。要求：理解运输问题的基本概念及表上作业法的原理，掌握表上作业法确定初始可行解、最优解的判别与改进的方法。§1运输问题及其数学模型一、运输问题引例，设有m个生产地，可供应（产量）分别为;有n个销地其需要量分别为。已知从到运输单位物资的运价（单价）为，试问如何调运物资才能使总费用最小？设用表示从到的运量，可将这些数据汇总于下表：产销平衡表销地产地产量销量单价运价表销地产地注：有时将两表合二为一。（1）若各产地的总产量等于各销地的总销

2、量，即，则称之为产销平衡的运输问题（或平衡运输问题）；（2）若所有产地的总产量不等于所有销地的总销量，即，则称之为产销不平衡的运输问题（或不平衡的运输问题）；（3）若在运输途中，还存在中间转运点（转运点即是产地，又是销地），则称之为有转运的运输问题（或扩大的运输问题）。二、平衡运输问题的数学模型在产销平衡的条件下，要求得总运费最小，可建立以下数学模型：该运输问题也属于线性规划问题，包括：（1）个决策变量；（2）m+n个约束条件；由于有，所以模型只有m+n–1个独立约束条件，基变量中含有m+n–1个变量；（3）系数矩阵的秩（4）系数矩阵为阶矩阵，该系数矩阵中对应于变量的系数向量，其分量中除

3、第i个和第m+j个为1以外，其余的都为零。§2表上作业法求解步骤：（1）找出初始可行解，即在产销平衡表上给出个数字格；（2）求各非基变量的检验数，即在表上计算空格的检验数。判别是否达到最优解，如已是最优解，则停止计算；（3）确定换入变量和换出变量，找出新的基可行解，在表上用闭回路法调整；（4）重复（2）、（3）直至得到最优解为止。例1某公司有三个工厂生产一种产品，每日的产量分别为7T、4T、9T。该公司把这些产品运往四个销点，各销点的日销量为--3T、--6T、--5T、--6T。已知从各工厂到各销售点的单位产品的运价见下表。问该公司应如何调运产品，在满足各销点需要量的前提下，使总运费最

4、少？单位运价表单位：元/T销地加工厂311310192874105（二）确定初始基可行解（初始调运方案）（一）最小元素法思路：就近供应，即从单位运价表中最小的运价开始确定供销关系，然后次小，直到给出初始基可行解为止。以例1为例进行讨论：第一步：从单位运价表中找出最小运价为1，表示先将的产品供应给。因，除满足全部需要外，还多余1T产品。在与的交叉格处填上3，并将列的运价划去。第二步：在未划去的元素中再找出最小运价2，确定多余的1吨供应，并将行的运价划去。第三步：在未划去的元素中划出最小运价3，直到单位运价表上的所有元素都划去为止，最后在产销平衡表上得到一个调运方案，空格为非基变量。单位运价

5、表单位：T销地加工厂311310192874105产销平衡表单位：T销地加工厂产量437314639销量3656注意：（1）在用最小元素法确定初始方案时，在产销平衡表上每填一个数，在单位运价表上划去一行或一列（当产大于销时；划去元素所在列；当产小于销时，划去元素所在行）。运价表中有行和列，需要划+条线，填最后一个数划去一行和一列，这样共填上个数。（2）当在产销平衡表上填上某个数时，行和列都平衡，需在单位运价表上划去一行和一列（这就出现了退化问题），为保持个基变量，需在行或列的任一空格处填上零，表示该基变量取值为零。（二）伏格尔法思路：一产地的产品，假如不能按最小运费就近供应，就考虑次小运

6、费，这样就要有一差额。差额越大，说明不能按最小运费调运时，运费增加越多，因而对差额最大处，就采用最小运费调运。第一步：计算各行和各列的最小运费和次小运费的差额销地加工厂行差额311310019281741051列差额2513第二步：从行或列差额中选出最大者，选择它所在行或列中的最小元素，在上表中，列是最大差额所在列，列中最小元素为4，可确定的产品先供应的需要，同时将运价表中的列数字划去。单位运价表销地产地311310192874105产销平衡表销地产地产量7469销量3656第三步：对表中未划去的元素再分别计算出各行、各列的最小运费和次最小运费的差额，重复第一、二步，直到给出初始解为止。

7、最后结果见下表。产销平衡表销地产地产量527314639销量3656注意：（1）伏格尔法与最小元素法除确定供求关系的原则不同外，其余相同；（2）伏格尔法给出的初始解更接近最优解。二、最优解的判别判别方法：计算空格检验数，当时，为最优解。下面介绍两种求空格检验数的方法：（一）闭回路法在给出调运方案的表上，从每一空格出发找一条闭回路。它是以某一空格为起点。用水平或垂直线向前划，每碰到一数字格转90度后，继续前进，直到回到开始空格为止。对