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

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

ID:39992526

大小:3.76 MB

页数:69页

时间:2019-07-16

[理学]运筹学-第4章运输问题_第1页
[理学]运筹学-第4章运输问题_第2页
[理学]运筹学-第4章运输问题_第3页
[理学]运筹学-第4章运输问题_第4页
[理学]运筹学-第4章运输问题_第5页
资源描述:

《[理学]运筹学-第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

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。