im1jn1c11c1jc1nnci1cijcincm1 cmjcmn图 4.1第四章 运输问题Chapter 4Transportation Problem§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。运输问题是一种线性规划问题，当然可以用第一章中的单纯形法求解。但由于它有特殊的结构，因而有特殊的算法。在本章中，我们将在单纯形法原理的基础上根据运输问题的特点，给出特殊的算法。minz= 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则运输问题的线性规划可以写成：min z=CTXs.t. AX=b X≥0其中 A 矩阵的列向量aij=ei+em+jei和 em+j是 m+n 维单位向量，元素 1 分别在在第 i 个分量和第 m+j 个分量的位置上。A 矩阵中的行与运输网络中的节点对应，前 m 行对应于发地，后 n 行对应于收地；A 矩阵的列与运输网络中的边对应。运输问题除了用网络表示及线性规划表示外，还可以用运输表表示...
