线性规划运输问题VIP免费

im1jn1c11c1jc1nnci1cijcincm1cmjcmn图4.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。求一个使总运费最小的运输方案。我们假定从任一发地到任一收地都有道路通行。如果总供应量等于总需求量，这样的运输问题称为供求平衡的运输问题。我们先只考虑这一类问题。图4.1.1是运输问题的网络表示形式。运输问题也可以用线性规划表示。设xij为从发地i运往收地j的运量，则总运费最小的线性规划问题如下页所示。运输问题线性规划变量个数为nm个，每个变量与运输网络的一条边对应，所有的变量都是非负的。约束个数为m+n个，全部为等式约束。前m个约束是发地的供应量约束，后n个约束是收地的需求量约束。运输问题约束的特点是约束左边所有的系数都是0或1，而且每一列中恰有两个系数是1，其他都是0。运输问题是一种线性规划问题，当然可以用第一章中的单纯形法求解。但由于它有特殊的结构，因而有特殊的算法。在本章中，我们将在单纯形法原理的基础上根据运输问题的特点，给出特殊的算法。127minz=c11x11+c12x12+⋯+c1nx1n+c21x21+c22x22+⋯+c2nx2n⋯+cm1xm1+cm2xm2⋯+cmnxmns.t.x11+x12+⋯+x1n¿s1x21+x22+⋯x2n¿s2⋯⋯xm1+xm2+⋯+xmn¿smx11+x21+xm1¿d1x12+x22+xm2¿d2⋯+⋯+⋯¿⋯x1n+x2n+xmn¿dnx11x12⋯x1nx21x22⋯x2n⋯xm1xm2⋯xmn¿0在运输问题线性规划模型中，令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=[11⋯111⋯1⋯11⋯111⋯1111⋱⋱⋱111]¿¿b=（s1，s2，…，sm，d1，d2，…，dn）T则运输问题的线性规划可以写成：minz=CTXs.t.AX=bX≥0其中A矩阵的列向量aij=ei+em+jei和em+j是m+n维单位向量，元素1分别在在第i个分量和第m+j个分量的位置上。A矩阵中的行与运输网络中的节点对应，前m行对应于发地，后n行对应于收地；A矩阵的列与运输网络中的边对应。128第四章运输问题运输问题除了用网络表示及线性规划表示外，还可以用运输表表示：12…n1c11c12…c1ns1x11x12…x1n2c21c22…c2ns2x21x22…x2n…………………………mcm1cm2…cmnsmxm1xm2…xmnd1d2…dn表4.1表的行与发地对应，列与收地对应。第i行与第j列交叉的一格与网络的一条边对应（也就是与线性规划约束矩阵的一列对应），每一格的左上角小方格内的数字表明从相应的发地i到收地j的运价cij，每一格右下角表明从相应的发地i到收地j的运量xij。表右方表明各发地的供应量si，表下方表明各需求第的需求量dj。每一行运量之和表示从该发地运往各收地的运量之和，它应该等于该发地的供应量；同样，每一列运量之和表示从各发地运往该收地的运量之和，它应该等于该收地的需求量。运输问题的网络图、线性规划模型以及运输表之间的关系可以用下表表示：网络图线性规划模型运输表节点发点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≥0129122311525102010856749图4.2第四章运输问题123185615x11x12x13274925x21x22x23102010表4.2130第四章运输问题§4.2运输问题约束矩阵的性质4.2.1约束矩阵的秩运输问题约束矩阵A的秩为m+n-1。证明：因为A矩阵的前m行和后n行之和分别等于向量（1，1，…，1），因此秩A