运筹学运输问题..ppt

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

1、第六章运输问题前面几章中，我们讨论了线性规划的一般形式及求解方法，对偶线性规划问题与灵敏度分析等问题。但在实际工作中，常常遇到很多线性规划问题，由于它们约束条件变量的系数矩阵具有特殊的结构，有可能找到比单纯形法更为简便的方法求解，从而可以大量节约计算的时间和费用。本章讨论的运输问题就是这一类特殊的线性规划问题。结构安排第一节运输问题的数学模型第二节表上作业法★第三节产销不平衡的运输问题及应用举例第一节运输问题的数学模型在社会经济生活中，经常会碰到大宗物资的调运问题。如煤、钢铁、木材、粮食等物资，在全

2、国有若干生产基地，根据已有的交通网络，制定调运方案，将这些物资运到各消费地点，这样调运的目的，不仅是要把这些物资供给各地消费，而且我们也希望调运的费用最省，这类问题就是所谓的运输问题。一、运输问题案例例：某公司从两个产地A1，A2将物品运往三个销地B1，B2，B3，各产地的产量、各销地的销量和各产地运往各销地的每件物品的运费如表所示，问应如何调运，使得总运输费最小？销地运费单价产地B1B2B3产量（件）A1646200A2655300销量150150200解：因为此问题中产量和销量都是500，所以这

3、是一个产销平衡问题。设xij表示从产地Ai调运到销地Bj的运输量（i=1，2；j=1，2，3），例如，x12表示由A1调运到B2的物品数量，现将安排的运输量列表如下：销地运费单价产地B1B2B3产量（件）A1x11x12x13200A2x21x22x23300销量150150200500此运输问题的线性规划模型如下：二、运输问题的一般情形假设某物资有m个产地A1，A2，...，Am，n个销地B1，B2，...，Bn，已知这m个产地的产量为a1，a2，...，am；n个销地的销量分别为b1，b2，..

4、.，bn，从第i个产地到第j个销地的单位物资运价为cij,这些数据可用产销平衡表和单位运价表表示如下。产销平衡表销地产地B1B2...Bn产量A1A2...Ama1a2...am销量b1b2...bn单位运价表销地产地B1B2...BnA1A2...Amc11c21...cm1c12c22...cm2.........c1nc2n...cmn若总产量等于总销量（产销平衡），试确定总运费最省的调运方案。建模：设xij为从产地Ai运往销地Bj的物资数量（i=1，…m；j=1，…n。销地产地B1B2...

5、Bn产量A1A2...AmX11X21...Xm1X12X22...Xm2............X1nX2n...Xmna1a2...am销量b1b2...bn则运输问题的数学模型如下：显然，模型是具有m×n个变量，m+n个约束的线性规划，可以用一般的单纯形法求解，但是当m与n较大时，模型的规模比较大，计算比较困难。为了进一步研究针对运输问题的特殊解法，下面考察它的约束系数矩阵。约束方程组的系数矩阵具有特殊的结构写出上式的系数矩阵A，形式如下：m行n行矩阵的元素均为1或0；每一列只有两个元素为1

6、，其余元素均为0；列向量Pij=(0,…，0，1，，…,0,1,0,…0)T，其中两个元素1分别处于第i行和第m+j行，ei+em+j。将该矩阵分块，特点是：前m行构成m个m×n阶矩阵，而且第k个矩阵只有第k行元素全为1，其余元素全为0（k=1，…，m）；后n行构成m个n阶单位阵。容易证明，秩A=m+n-1。事实上，由于A的前m行之和等于后n行之和，因此，秩A≤m+n-1;又，取A的前m+n-1行，变量对应的列所构成的A的子式为由此易知，这个m+n-1阶子式的值为1或-1，所以，A的秩恰为m+n

7、-1。可见运输问题的基可行解中，基变量的个数应为m+n-1个。根据运输问题数学模型结构上具有的上述特征，在前面所讲的单纯形方法的基础上，逐渐创造出一种专门用来求解运输问题线性规划模型的运输单纯形方法，一般称其为表上作业法。第二节表上作业法表上作业法是一类比较特殊的单纯形法。它必须首先确定一个初始方案，也就是找出一个基可行解，然后根据判别准则来检查这个初始方案是不是最优的，如果不是最优的，那么对初始方案加以改进，直到找出最优方案。确定初始方案(初始基本可行解)改进调整（换基迭代）否判定是否最优？是结束

8、最优方案下面通过例子介绍它的计算步骤。运输问题求解思路图一、初始方案的给定1、最小元素法★2、Vogel法★1、最小元素法基本思路是：就近供应，即从运价表中最小运价开始确定调运量，然后次小，一直到给出初始调运方案为止。（1）找出运价表中最小元素，确定，若，则令，划掉运价表的第L行；反之，若，则令，划掉运价表的第k列。（2）在运价表剩余元素中重复（1），直至运价表元素全部被划掉。例：某糖果公司下设三个工厂，每日产量分别为：A1—7吨、A2—4吨、A3—9吨。该公司将这些