[理学]运筹学-第4章运输问题

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

1、第四章运输问题Transportation ProblemContents§4.1运输问题的数学模型§4.2求解运输问题的表上作业法§4.3表上作业法的特殊情况§4.4运输问题的应用某种物资有m个产地A1,A2,…,Am，联合供应n个销地B1,B2,…,Bn，各产地产量、各销地销量（单位：吨）、各产地到各销地的单位运价（单位：元/吨）如表1-1，应如何组织调运，才能使得总运费最省？表4-1一般运输问题的平衡表与运价表平衡表运价表销地产地B1B2…Bn产量（吨）B1B2…BnA1a1c11c12…

2、c1nA2a2c21c22…c2n………………Amamcm1cm2…cmn销量(吨)b1b2…bn§4.1运输问题的数学模型用矩阵形式表示为：设xij表示产地Ai供应销地Bj的数量(i=1,2,…,m;j=1,2,…,n)。当产销平衡()时，数学模型为(标准形)：§4.1运输问题的数学模型其中：§4.1运输问题的数学模型总有可行解Xij=ai*bj/Q矩阵的元素均为1或0；每一列只有两个元素为1，其余元素均为0；列向量Pij=(0,…，0，1，，…,0,1,0,…0)T，其中两个元素1分别处

3、于第i行和第m+j行，ei+em+j。将该矩阵分块，特点是：前m行构成m个m×n阶矩阵，而且第k个矩阵只有第k行元素全为1，其余元素全为0（k=1，…，m）；后n行构成m个n阶单位阵。§4.1运输问题的数学模型可以看出新组合成的子矩阵为对角矩阵，秩为m+n-1，即原矩阵的秩为m+n-1§4.1运输问题的数学模型容易证明，秩A=m+n-1。事实上，由于A的前m行之和等于后n行之和，因此，秩A≤m+n-1;又，取A的前m+n-1行，变量对应的列所构成的A的子式为由此易知，这个m+n-1阶子式的值为

4、1或-1，所以，A的秩恰为m+n-1。可见运输问题的基可行解中，基变量的个数应为m+n-1个。因此，运输问题的任何一个基含有个线性无关的列向量，即任何一个基可行解含有个基变量，这时对应的基可行解就是一个可行的调运方案。关于运输问题的求解，当然可以用单纯形方法，但由于它结构的特殊性，用特殊的方法求解比较方便。下面介绍求解运输问题的表上作业法。§4.1运输问题的数学模型表上作业法是一类比较特殊的单纯形法。它必须首先确定一个初始方案，也就是找出一个基可行解，然后根据判别准则来检查这个初始方案是不是最优

5、的，如果不是最优的，那么对初始方案加以改进，直到找出最优方案。§4.2求解运输问题的表上作业法确定初始方案(初始基本可行解)改进调整（换基迭代）否判定是否最优？是结束最优方案运输问题求解思路图§4.2求解运输问题的表上作业法例甲、乙两个煤矿供应A、B、C三个城市用煤，各煤矿产量及各城市需煤量、各煤矿到各城市的运输距离见表，求使总运输量最少的调运方案。有关信息表450200150100日销量（需求量）250756580乙2001007090甲日产量（供应量）CBA运距城市煤矿数学模型分别使用最小元

6、素法和西北角法求出初始方案。&最小元素法的基本思想是“就近供应”；&西北角法则不考虑运距（或运价），每次都选剩余表格的左上角（即西北角）元素作为基变量，其它过程与最小元素法相同；调销地运量产地B1B2B3产量A190X1170X12100X13200A280X2165X2275X23250销量100150200450用最小元素法确定初始调运方案150100100100100100100得到初始调运方案为：x11=100，x13=100，x22=150，x23=100调销地运量产地B1B2B3产量

7、A190X1170X12100X13200A280X2165X2275X23250销量100150200450用西北角法确定初始调运方案1001001005050200200得到初始调运方案为：x11=100，x12=100，x22=50，x23=2003、Vogel法基本思路是：从全局考虑。其方法是从运价表上分别找出每行与每列最小的两个元素之差，再从差值最大的行或列中找出最小运价确定供需关系和供需数量。当产地或销地中有一方数量上供应完毕或得到满足时，划去运价表中的行或列，再重复上述步骤。直到找

8、出最佳调运方案。Table3产销平衡表销地产地B1B2B3B4产量A1A2A3749销量3656Table4单位运价表销地产地B1B2B3B4两最小元素之差①②③④⑤A1A2A3311310192874105000701116012两最小元素之差①②③④⑤2513213212122365213例某种物资有3个产地、4个销地，各产地的产量、销地的销量以及各产销地之间的运价如表2-1，求最优的调运方案。表运输问题的平衡表与运价表平衡表(单位：t)运价表B1B2B3B4发量B1B2B3B4A14653