《线性规划运输问题.docx》由会员分享，可在线阅读，更多相关《线性规划运输问题.docx（42页珍藏版）》请在三一办公上搜索。
1、第四章 运输问题第四章 运输问题Chapter 4Transportation Problem4.1 运输问题的定义设有同一种货物从m个发地1，2，m运往n个收地1，2，n。第i个发地的供应量（Supply）为si（si0），第j个收地的需求量（Demand）为dj（dj0）。每单位货物从发地i运到收地j的运价为cij。求一个使总运费最小的运输方案。我们假定从任一发地到任一收地都有道路通行。如果总供应量等于总需求量，这样的运输问题称为供求平衡的运输问题。我们先只考虑这一类问题。im1jn1c11c1jc1nnci1cijcincm1cmjcmn图4.1图4.1.1是运输问题的网络表示形式。运输
2、问题也可以用线性规划表示。设xij为从发地i运往收地j的运量，则总运费最小的线性规划问题如下页所示。运输问题线性规划变量个数为nm个，每个变量与运输网络的一条边对应，所有的变量都是非负的。约束个数为m+n个，全部为等式约束。前m个约束是发地的供应量约束，后n个约束是收地的需求量约束。运输问题约束的特点是约束左边所有的系数都是0或1，而且每一列中恰有两个系数是1，其他都是0。运输问题是一种线性规划问题，当然可以用第一章中的单纯形法求解。但由于它有特殊的结构，因而有特殊的算法。在本章中，我们将在单纯形法原理的基础上，根据运输问题的特点，给出特殊的算法。在运输问题线性规划模型中，令X=（x11，x1
3、2，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，amnT=b=（s1，s2，sm，d1，d2，dn）T则运输问题的线性规划可以写成：min z=CTXs.t. AX=b X0其中A矩阵的列向量aij=ei+em+jei和em+j是m+n维单位向量，元素1分别在在第i个分量和第m+j个分量的位置上。A矩阵中的行与运输网络中的节点对应，前m行对应于发地，后n行对应于收地；A矩阵的列与运输网络中的边对应。运输问题除了用网络表示及线性规划表示
4、外，还可以用运输表表示：12n1c11c12c1ns1x11x12x1n2c21c22c2ns2x21x22x2nmcm1cm2cmnsmxm1xm2xmnd1d2dn表 4.1表的行与发地对应，列与收地对应。第i行与第j列交叉的一格与网络的一条边对应（也就是与线性规划约束矩阵的一列对应），每一格的左上角小方格内的数字表明从相应的发地i到收地j的运价cij，每一格右下角表明从相应的发地i到收地j的运量xij。表右方表明各发地的供应量si，表下方表明各需求第的需求量dj。每一行运量之和表示从该发地运往各收地的运量之和，它应该等于该发地的供应量；同样，每一列运量之和表示从各发地运往该收地的运量之和
5、，它应该等于该收地的需求量。运输问题的网络图、线性规划模型以及运输表之间的关系可以用下表表示：网络图线性规划模型运输表节点发点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,x230122311525102010856749图4.2123185615x1
6、1x12x13274925x21x22x23102010表 4.21684.2 运输问题约束矩阵的性质4.2.1 约束矩阵的秩运输问题约束矩阵A的秩为m+n-1。证明：因为A矩阵的前m行和后n行之和分别等于向量（1，1，1），因此秩Am+n。考虑A的一个子矩阵A=a1n，a2n，amn，a11，a12，a1n，即A=删除A中的第m+n行和第m+n列，得到A=容易看出，秩A=m+n-1。由此m+n-1=秩A秩A秩Adj，取xij=dj，并将发地i的供应量改为si-dj，将收地j的需求量改为0；如果sidj，取xij=si，并将发地i的供应量改为0，将收地j的需求量改为dj-si；如果si和dj中
7、有一个为0，则不分配运量给xij。分配完最小运价的运量后，用同样的方法分配运价次小的运量，依次类推，直到每一个发地的供应量和每一个收地的需求量都为0。以下是用最小元素法确定运输问题的初始可行解的例子。例4.8 给出运输表如下。最小运价为c33=7，发地3的供应量为50，收地3的需求量为31，安排运量x33=31。发地3和收地3的供应量和需求量分别变为19和0。123411011915302131216945311871050-313141413121325152031-3184对于c32=8，发地3的供应量为19，收地2的需求量为20，安排x32=19，发地3的供应量为0，收地2的需求量为1。
8、123411011915302131216945311871019-191931414131213251520-19084对于c13=9，c24=9，可以任选一个，但是（1，3）中收地3的需求量为0，安排x24=45，发地2的供应量为0，收地4的需求量为39。123411011915302131216945-454531187100193141413121325151084-45对于c11=10和c34=10，由于发地3的需求量已经为0，安排x11=15，发地1的供应量为15，收地1的需求量为0；12341101191530-1515213121690453118710019314141312
9、132515-151039对于c12=11，安排x12=1，发地1的供应量为14，收地2的需求量为0；12341101191515-1151213121690453118710019314141312132501-1039对于c44=13，安排x44=25，发地4的供应量为0，收地4的需求量为14。123411011915141512131216904531187100193141413121325-252500039-25最后安排x14=14，所有发地和收地的供应量、需求量都等于0。12341101191514-14=0151142131216904531187100193141413121
10、302500014-14=0这样就得到一个运输问题的初始基础可行解。这个初始基础可行解的目标函数值为z=1015+111+1514+945+819+731+1325=1470比用西北角法得到的初始基础可行解的目标函数值小。4.6.2 计算非基变量的检验数zij-cij4.5.2.1闭回路法对于非基变量xij，检验数为其中向量Yij可由该非基变量与基变量形成的闭回路来确定，这个闭回路转角处的基变量对应于y=1，其余的基变量对应于y=0。这样就等于转角处基变量对应的cij依次加减的值。例4.9 在例4.7中，用西北角法得到初始基础可行解，计算各非基变量的检验数zij-cij123411011915
11、3015152131216945531931187105050414131213252515203184非基变量（1，3）相应的闭回路为1234+6110119153015152131216945531931187105050414131213252515203184因此x13的检验数z13-c13=(c12-c22+c23)-c13=(11-12+16)-9=+6。非基变量（1，4）相应的闭回路为1234-7110119153015152131216945531931187105050414131213252515203184因此x14的检验数z14-c14=(c12-c22+c24)-c1
12、4=(11-12+9)-15=-7非基变量（2，1）相应的闭回路为123411011915301515-22131216945531931187105050414131213252515203184因此x21的检验数z21-c21=(c11-c12+c22)-c21=(10-11+12)-13=-2非基变量（3，1）相应的闭回路为12341101191530151521312169455319+131187105050414131213252515203184因此x31的检验数z31-c31=(c11-c12+c22-c24+c34)-c31=(10-11+12-9+10)-11=+1用同样的
13、方法可以求得其他非基变量的检验数z32-c32=(c22-c24+c34)-c32=(12-9+10)-8=+5z33-c33=(c23-c24+c34)-c33=(16-9+10)-7=+10z41-c41=(c11-c12+c23-c24+c44)-c41=(10-11+12-9+13)-14=+1z42-c42=(c22-c24+c44)-c42=(12-9+13)-13=+3z43-c43=(c23-c24+c44)-c43=(16-9+13)-12=+8将以上检验数填入运输表，用“”表示。1234+3+1+1+8-2+6+5-71101191530151521312169455319+1031187105050414131213252515
