[经管营销]2运输问题

《[经管营销]2运输问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、运筹学第二章运输问题XX大学经济与管理学院教授、博士生导师管理科学与工程系主任第二章运输问题前面讨论了一般线性规划问题的数学模型的建立和求解的方法,但在实际工作中，往往碰到有些线性规划问题,它们的约束条件的系数矩阵具有特殊的结构，这就使我们有可能找到比单纯形法更为简单的求解方法,从而节约大量的计算时间和费用。本章所讨论的运输问题就是属于这样一类特殊的线性规划问题，它在实践中具有重要的作用，具有广泛的应用。第一节运输问题的数学模型在经济建设中，经常会遇到大宗物资调拨中的运输问题。如煤炭、钢铁、木材、粮食等物资,在全国有若干生产基地,根据已有的交通网,应如何制定调运方案，将这些

2、物资运到各消费地点，而使总运费最小。这类问题可用以下数学语言来描述：运输问题：假设有m个生产地点,可以供应某种物资(以后称为产地)，用Ai表示，i=1,2,,m；有n个销售地，用Bj表示，j=1,2,,n；产地的产量和销售地的销售量分别为ai,i=1,2,,m和bjj=1,2,,n，从Ai到Bj运输单位物资的运价为cij，这些数据可汇总于如下表2—1。在假设产销平衡的条件下，即要求得总运费最小的调运方案。表2—1产销平衡表与单位运价表销地产地B1B2Bn产量A1c11c12c1na1A2c21c22c2na2

3、Amcm1cm2cmnam销量b1b2bn解:假设xij表示从Ai到Bj的运量,则所求的数学模型为:对于产销不平衡的情况，我们将另行处理。这就是运输问题的数学模型，它包含m·n变量,m+n个约束条件。如果用单纯形法求解，先得在各约束条件上加入一个人工变量(以便求出初始基可行解)。因此，即使是m=3，n=4这样的简单问题,变量数就有19个之多，计算起来非常复杂。因此，我们有必要针对运输问题的某些特点，来寻求更为简单方便的求解方法。第二节表上作业法1.表上作业法的基本概念与重要结论针对运输问题的数学模型结构的特殊性，它的约束方程组的系数矩阵具有如下

4、形式(具体见下一张幻灯片)，该矩阵中，每列只有两个元素为1，其余都是0。根据这个特点，在单纯形法的基础上，创造出一种专门用来求解运输问题的方法，这种方法我们称为表上作业法。运输问题也是一个线性规划问题，当用单纯形法进行求解时，我们首先应当知道它的基变量的个数；其次，要知道这样一组基变量应当是由哪些变量来组成。由运输问题系数矩阵的形式并结合第一章单纯形算法的讨论可以知道:运输问题的每一组基变量应由m+n-1个变量组成。(即基变量的个数=产地个数+销售地个数–1)进一步我们想知道,怎样的m+n-1个变量会构成一组基变量？为此我们需要引入一些基本概念，通过对这些基本概念的分析和讨

5、论，结合单纯形算法的基本结果，便可得出我们所需要的结论。定义1：例1：设m=3，n=4，如表2—2所示。表2—2销地产地B1B2B3B4A1x11x12A2x21x24A3x32x34x11、x12、x32、x34、x24、x21构成一个闭回路.这里有：i1=1，i2=3，i3=2；j1=1，j2=2，j3=4.若把闭回路的顶点在表中画出,并且把相邻两个变量用一条直线相连（今后就称这些直线为闭回路的边）。而表2—3，即顶点为{x12、x13、x23、x22}和表2—4，即顶点为{x11、x12、x22、x24、x34、x31}也分别构成两个闭回路。表2—3销地产地B1B2B

6、3B4A1x12x13A2x22x23A3表2—4销地产地B1B2B3B4A1x11x12A2x22x24A3x31x34从上面的几个例子中不难看出，如果把一个闭回路的所有顶点都在表中画出，并且把相邻的顶点都用一条直线连接起来，就可以得到一条封闭的折线，折线的每一条边或者是水平的，或者是垂直的。定理：m+n-1个变量构成基变量的充分和必要条件是它不包含有任何闭回路。以上的结果给出了运输问题的基的一个特征，这个结论是非常重要的，因为利用它来判断m+n-1个变量是否构成基变量比直接判断这些变量所对应的系数列向量组是否线性无关要简单和直观。另外，在以后还将看到利用基的这个特征可以

7、导出求运输问题的第一个基本可行解的一种简便的方法。2.表上作业法表上作业法是单纯形法在求解运输问题时的一种简化方法，其实质是单纯形算法。只是具体计算和术语有所不同，可归纳为：（1）找出初始基可行解，即在(mn)产销平衡表上给出m+n-1个有数字的格，这些有数字的格不能构成闭回路，且行和等于产量，列和等于销售量；（2）求各非基变量的检验数，即在表上求空格的检验数，判别是否达到最优解。如果达到最优解，则停止计算，否则转入下一步；（3）确定换入变量和换出变量，找出新的基可行解，在表上用闭回路法进行调整。（4）重复（2）