运筹学 第3章 运输问题

《运筹学 第3章 运输问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第三章运输问题在生产实际中，经常需要将某种物资从一些产地运往一些销地，因而存在如何调运使总的运费最小的问题。这类问题一般可用线性规划模型来描述，当然可以用单纯形法求解。但由于其模型结构特殊，学者们提供了更为简便和直观的解法——表上作业法。此外，有些线性规划问题从实际意义上看，并非运输问题，但其模型结构类似运输问题，也可以化作运输问题进行求解。第一节运输问题及其数学模型首先来分析下面的问题。例3.1农产品经销公司有三个棉花收购站，向三个纺织厂供应棉花。三个收购站A1、A2、A3的供应量分别为50kt、45kt和65kt，三个纺织厂B1、B2、B3的需求量分别为20kt、70k

2、t和70kt。已知各收购站到各纺织厂的单位运价如表3—1所示（单位：千元/kt），问如何安排运输方案，使得经销公司的总运费最少？表3—1纺织厂收购站B1B2B3A1A2A3462835567设xij表示从Ai运往Bj的棉花数量，则其运输量表如下表所示。表3—2纺织厂收购站B1B2B3供应量（kt）A1A2A3x11x21x31x12x22x32x13x23x33504565需求量（kt）207070160由于总供应量等于总需求量，因此，一方面从某收购站运往各纺织厂的总棉花数量等该收购站的供应量，即x11+x12+x13=50x21+x22+x23=45x31+x32+x33

3、=65第三章——8另一方面从各收购站运往某纺织厂的总棉花数量等该纺织厂的需要量，即x11+x21+x31=20x12+x22+x32=70x13+x23+x33=70因此有该问题的数学模型为minf=4x11+8x12+5x13+6x21+3x22+6x23+2x31+5x32+7x33x11+x12+x13=50x21+x22+x23=45x31+x32+x33=65x11+x21+x31=20x12+x22+x32=70x13+x23+x33=70xij≥0，i=1，2，3；j=1，2，3生产实际中的一般的运输问题可用以下数学语言描述。已知有m个生产地点Ai，i=1，…

4、，m，可供应某种物资，其供应量（产量）为ai，i=1，…，m；有n个销售地点Bj，j=1，…，n，需要该种物资，其需要量（销量）为bj，j=1，…，n；从Ai到Bj运输单位物资的运价（单价）为cij；设Σai=Σbj，这些数据可汇总于如下产销平衡表，现要制定一个使总运费最小的调运方案。表3—3运输问题产销平衡表销地产地B1B2…Bn产量A1c11c12…c1na1A2c21c22…c2na2………………Amcm1cm2…cmnam销量b1b2…bnΣaiΣbj若用xij表示从Ai到Bj的运量，在产销平衡的条件下，要求得总运费最小的调运方案，其数学模型如下（模型Y）第三章——

5、8该模型中，包含了m×n个变量，（m+n）个约束条件，且有特殊结构的系数矩阵，即  上述矩阵的列向量可用pij来描述，显然pij中除第i个元素和第m+j个元素为1以外，其余元素均为0。第二节表上作业法一、运输问题数学模型的基本概念对于运输问题的数学模型（模型Y）有如下定理。定理3.1运输问题的数学模型必有最优解。首先，运输问题一定有可行解；而任何单位运价cij≥0，因此对于任一可行解必有目标函数值大等于零，即目标函数有下界。因此，对于极小化的运输问题必有最优解。定理3.2运输问题约束方程系数矩阵A的秩为m+n－1，即R（A）=m+n－1。由定理3.1可知，我们在求解运输问题

6、时就不需要进行无最优解的判别；另外从定理3.2可知，运输问题任一基可行解的非零分量的个数不能多于m+n－1，或者说基变量的个数为m+n－1。定义3.1（闭回路的定义）在运输问题的调运表中，凡能排成xi1j1，xi1j2，xi2j3，…，xisjs，xisj1第三章——8形式的变量集合，称为一个闭回路，其中诸变量称为该闭回路的顶点。下表中即为两个闭回路。表3—4B1B2B3B4B5B6B7A1x11x12x13x14x15x16x17A2x21x22x23x24x25x26x27A3x31x32x33x34x35x36x37闭回路1：x11，x12，x22，x23，x33，x

7、31，x11；闭回路2：x15，x16，x36，x37，x27，x25，x15；闭回路有如下特点：①每个顶点都是转角；②每行或每列只有且仅有两个顶点；③每个顶点的连线都是水平的或垂直的。定理3.3运输问题m+n－1个变量xi1j1，xi2j2，…，xisjs（s=m+n－1）构成某一基可行解的基变量的充要条件是：不包含以这些变量为顶点的闭回路。该定理能帮助我们简便地求出基可行解或判别某一可行解是否为基可行解。二、表上作业法和一般线性规划一样，运输问题的最优解也一定可以在其基可行解中找到。类似于单纯形法，表上作业法仍