线性规划运输问题.doc

线性规划运输问题.doc

ID:48443491

大小:637.50 KB

页数:42页

时间:2020-01-29

线性规划运输问题.doc_第1页
线性规划运输问题.doc_第2页
线性规划运输问题.doc_第3页
线性规划运输问题.doc_第4页
线性规划运输问题.doc_第5页
资源描述:

《线性规划运输问题.doc》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、第四章运输问题第四章运输问题Chapter4TransportationProblem§4.1运输问题的定义设有同一种货物从m个发地1,2,…,m运往n个收地1,2,…,n。第i个发地的供应量(Supply)为si(si≥0),第j个收地的需求量(Demand)为dj(dj≥0)。每单位货物从发地i运到收地j的运价为cij。求一个使总运费最小的运输方案。我们假定从任一发地到任一收地都有道路通行。如果总供应量等于总需求量,这样的运输问题称为供求平衡的运输问题。我们先只考虑这一类问题。im1jn1c11c1jc1nnci1cijc

2、incm1cmjcmn图4.1图4.1.1是运输问题的网络表示形式。运输问题也可以用线性规划表示。设xij为从发地i运往收地j的运量,则总运费最小的线性规划问题如下页所示。运输问题线性规划变量个数为nm个,每个变量与运输网络的一条边对应,所有的变量都是非负的。约束个数为m+n个,全部为等式约束。前m个约束是发地的供应量约束,后n个约束是收地的需求量约束。运输问题约束的特点是约束左边所有的系数都是0或1,而且每一列中恰有两个系数是1,其他都是0。运输问题是一种线性规划问题,当然可以用第一章中的单纯形法求解。但由于它有特殊的结构,

3、因而有特殊的算法。在本章中,我们将在单纯形法原理的基础上,根据运输问题的特点,给出特殊的算法。168第四章运输问题在运输问题线性规划模型中,令X=(x11,x12,…,x1n,x21,x22,…,x2n,……,xm1,xm2,…,xmn)TC=(c11,c12,…,c1n,c21,c22,…,c2n,……,cm1,cm2,…,cmn)TA=[a11,a12,…,a1n,a21,a22,…,a2n,……,am1,am2,…,amn]T=b=(s1,s2,…,sm,d1,d2,…,dn)T则运输问题的线性规划可以写成:minz=C

4、TXs.t.AX=bX≥0其中A矩阵的列向量aij=ei+em+jei和em+j是m+n维单位向量,元素1分别在在第i个分量和第m+j个分量的位置上。A矩阵中的行与运输网络中的节点对应,前m行对应于发地,后n行对应于收地;A矩阵的列与运输网络中的边对应。168第四章运输问题运输问题除了用网络表示及线性规划表示外,还可以用运输表表示:12…n1c11c12…c1ns1x11x12…x1n2c21c22…c2ns2x21x22…x2n…………………………mcm1cm2…cmnsmxm1xm2…xmnd1d2…dn表4.1表的行与发

5、地对应,列与收地对应。第i行与第j列交叉的一格与网络的一条边对应(也就是与线性规划约束矩阵的一列对应),每一格的左上角小方格内的数字表明从相应的发地i到收地j的运价cij,每一格右下角表明从相应的发地i到收地j的运量xij。表右方表明各发地的供应量si,表下方表明各需求第的需求量dj。每一行运量之和表示从该发地运往各收地的运量之和,它应该等于该发地的供应量;同样,每一列运量之和表示从各发地运往该收地的运量之和,它应该等于该收地的需求量。运输问题的网络图、线性规划模型以及运输表之间的关系可以用下表表示:网络图线性规划模型运输表节

6、点发点i约束前m个约束表的行收点j后n个约束表的列边从节点i到节点j变量xij,列向量aij表中的一格例4.1以下的运输问题线性规划、网络图和运输表表示同一运输问题。minz=8x11+5x12+6x13+7x21+4x22+9x23s.t.x11+x12+x13=15x21+x22+x23=25x11+x21=10x12+x22=20x13+x23=10x11,x12,x13,x21,x22,x23≥0168第四章运输问题122311525102010856749图4.2123185615x11x12x13274925x21

7、x22x23102010表4.2168第四章运输问题§4.2运输问题约束矩阵的性质4.2.1约束矩阵的秩运输问题约束矩阵A的秩为m+n-1。证明:因为A矩阵的前m行和后n行之和分别等于向量(1,1,…,1),因此秩A

8、了使运输问题系数矩阵行满秩,在A矩阵中增加一个列向量em+n形成增广矩阵这样增广矩阵的秩就等于m+n,因而是行满秩的。并且中任何一个基矩阵,都必定包含单位向量em+n。例4.2.1设一个运输网络如右图,它的系数矩阵为增广矩阵为12231图4.3增加的单位列向量em+n=e5相

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

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

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