第三章运输问题 前两章讨论了一般线性规划的解法，但在实际工作中，往往 碰到有些线性规划问题，它们的约束方程组的系数矩阵具有很特 殊的结构，这就有可能找到比单纯形法更为简便的求解方法。本 章讨论的运输问题就是这样一类特殊的线性规划问题。 §1运输问题 在经济活动中，经常碰到大宗物资的调运问题。如煤、钢铁、 木材、粮食等物资，在全国有若干生产基地，根据已有的交通网， 制定调运方案，将这些物资运到各消费地点，而总运费最省。 这类问题的一般提法是：设某物资有m个产地A1,A2,,Am, 其产量分别为a1,a2,,am,有n个销地B1,B2,,Bn,其销量分别 是b1,b2,,b,己知产地A到销地B的单位运费是Ci,这些数据可用 产销平衡表和单位运价表表示如下：
第三章 运输问题 前两章讨论了一般线性规划的解法，但在实际工作中，往往 碰到有些线性规划问题，它们的约束方程组的系数矩阵具有很特 殊的结构，这就有可能找到比单纯形法更为简便的求解方法。本 章讨论的运输问题就是这样一类特殊的线性规划问题。 §1 运输问题 在经济活动中，经常碰到大宗物资的调运问题。如煤、钢铁、 木材、粮食等物资，在全国有若干生产基地，根据已有的交通网， 制定调运方案，将这些物资运到各消费地点，而总运费最省。 这类问题的一般提法是：设某物资有m个产地A1，A2，…，Am， 其产量分别为a1,a2,…,am，有n个销地B1，B2，…，Bn，其销量分别 是b1，b2,…,bn,已知产地Ai到销地Bj的单位运费是Cij，这些数据可用 产销平衡表和单位运价表表示如下：
产销平衡表 单位运价表 销地 产 销地 产地 B1 B2...Bn 量 产地 B1B2…Bn A X11X12…X1n ai 2 a2 A C11C12… Cin X21X22… X2n 2 C21C22"C2n 。 Am Xml Xma2…Xmm am 销量 bi b2...bn Cmi Cm2 ....Cmn 若总产量等于总销量（产销平衡），试确定总运费最省的调运方案。 建模：设x表示从产地A到销地B,的运量(i=1,2,…,mj=1,2,n) 则运输闲题的数学模型如下：mnZ- X11+X12+……+X1n=a1 X11+X21+…+xm1=b1 X21+X22+……+X2n=a2 X12+X22+·…+xm2=b2 Xn1X2十……+Xmn=a X1n+x2n+……+Xm=bn xi≥0，i-1,2..m;j=1,2.n
销地 产地 B1 B2 … Bn 产 量 A1 A2 a1 … a … 2 Am am 销量 b1 b2 … bn 销地 产地 B1 B2 … Bn A1 A2 C11 c12 … c1n … C21 c22 … c2n … … … … Am Cm1 cm2 … cmn 产销平衡表 单位运价表 x11 x12 … x1n x21 x22 … x2n … … … … xm1 xm2 … xmn 若总产量等于总销量（产销平衡），试确定总运费最省的调运方案。 建模：设xij表示从产地Ai到销地Bj的运量（i=1,2, …,m;j=1,2, …,n） 则运输问题的数学模型如下： = = = m i n 1 j 1 min ij ij Z c x x11+x12+‥‥+x1n ＝a1 x11+x21+‥‥+xm1 ＝b1 x21+x22+‥‥+x2n ＝a2 x12+x22+‥‥+xm2 ＝b2 … … … … … … … … … … … … xm1+xm2+‥‥+xmn ＝am x1n+x2n+‥‥+xmn ＝bn xij≥0,i=1,2…m;j=1,2…n
minZ= 记 (X11,,X1nX21,,X2n3,Xa1,,Xmn） 1+X12十……+X1n=a1则 1..1 +X22+……+X2n=a2 1..1 1■■ Xml+Xm2+…+Xmm=an X11+X21+……+Xm1=b1 X12+X22+……+X2=b2 1..1 A= 1. 1 X1ntx2n+…+Xnm=bn x1j≥0，i-1,2.m;j=1,2n A是m+n行，m×n列的矩阵 显然，模型是具有m×n个变量， 色比较稀疏；除有2h×n个 m+n个约束的线性规划，可以用一般 1以外，其余元素皆为0，变 的单纯形法求解，但是当m与n较大时量x对应的系数列向量P 模型的规模比较大，计算比较困难。 中，除第i个和第m+j个为1 为了进一步研究针对运输问题的特殊 外，其余都为0，即 解法，下面考察它的约束系数矩阵。 P=(01.1.0）=e+em+j
= = = m i n 1 j 1 min ij ij Z c x x11+x12+‥‥+x1n ＝a1 x21+x22+‥‥+x2n ＝a2 … … … … … … xm1+xm2+‥‥+xmn ＝am x11+x21+‥‥+xm1 ＝b1 x12+x22+‥‥+xm2 ＝b2 … … … … … … x1n+x2n+‥‥+xmn ＝bn xij≥0,i=1,2…m;j=1,2…n 显然，模型是具有m×n个变量， m+n个约束的线性规划，可以用一般 的单纯形法求解，但是当m与n较大时， 模型的规模比较大，计算比较困难。 为了进一步研究针对运输问题的特殊 解法，下面考察它的约束系数矩阵。 记 X=(x11,…,x1n,x21,…,x2n,…,xm1,…,xmn) T 则 A= 1…1 1…1 … … 1…1 1 1 … … 1 1 1 … … 1 A是m+n行，m×n列的矩阵， 它比较稀疏，除有2m×n个 1以外，其余元素皆为0，变 量xij对应的系数列向量Pij 中，除第i个和第m+j个为1 外，其余都为0，即 P=(0…1…1…0)T =ei+em+j
容易证明，秩A=m+n-1 事实上，由于A的前m行之和恰好等于后n行之和，因此， 秩A≤m+n-1;又，取A的前m+n-1行， 变量X1,,X1,X2n,X3,,Xm对应的列所构成的A的子式为 1..1 1.1 m行 1..1 n-1行A= 1..1 1 n-1列 m列 1 由此易知，这个m+n-1阶子式的值为1或-1，所以，A的秩恰为 m+n-1。可见，运输问题的基可行解中，基变量的个数应为m+n-1 个。 由于运输问题的数学模型具有以上特点，所以求解运输问题时， 可以采用比较简单的计算方法—表上作业法
容易证明，秩A=m+n-1 事实上，由于A的前m行之和恰好等于后n行之和，因此， 秩A≤m+n-1；又，取A的前m+n-1行， 变量x11,…,x1n,x2n,x3n,…,xmn对应的列所构成的A的子式为 1 … 1 1 1 1 1 m行 n-1行 n-1列 m列 由此易知，这个m+n-1阶子式的值为1或-1，所以，A的秩恰为 m+n-1。可见，运输问题的基可行解中，基变量的个数应为m+n-1 个。 由于运输问题的数学模型具有以上特点，所以求解运输问题时， 可以采用比较简单的计算方法——表上作业法。 A= 1 …1 1 …1 …… 1 …1 1 1 …… 1 1 1 …… 1
§2表上作业法 表上作业法的思想和单纯形法类似，即首先确定一个初 始方案，也就是找出一个基可行解，然后根据判别准则来检 查这个初始方案是不是最优的，如果不是最优的，那么对该 方案进行调整，直至求出最优方案止。下面介绍它的计算步 骤。 2.1确定初始调运方案 确定初始调运方案的方法很多，我们介绍两种：最小元素法和 西北角法。 1.最小元素法 这个方法的基本思想是就近供应，即从运价表中最小运价开始 确定调运量，然后次小，一直到给出初始调运方案为止。具体操作 方法如下： 1°找出运价表中最小元素CuK,确定XK=min{aL,bk},若xK=aL, 则令bk'=bkxK,划掉运价表的第L行；反之，若xLK=bk,则令 aL'=aLXK,划掉运价表的第K列。 2°在运价表剩余元素中重复1°，直至运价表中元素全被划掉止
§2 表上作业法 表上作业法的思想和单纯形法类似，即首先确定一个初 始方案，也就是找出一个基可行解，然后根据判别准则来检 查这个初始方案是不是最优的，如果不是最优的，那么对该 方案进行调整，直至求出最优方案止。下面介绍它的计算步 骤。 2.1 确定初始调运方案 确定初始调运方案的方法很多，我们介绍两种：最小元素法和 西北角法。 1.最小元素法 这个方法的基本思想是就近供应，即从运价表中最小运价开始 确定调运量，然后次小，一直到给出初始调运方案为止。具体操作 方法如下： 1°找出运价表中最小元素CLK，确定xLK=min{aL，bk}，若xLK = aL， 则令bk ′=bk-xLK，划掉运价表的第L行；反之，若xLK= bk ，则令 aL ′=aL-xLK，划掉运价表的第K列。 2°在运价表剩余元素中重复1°，直至运价表中元素全被划掉止