第三章第三章 运输问题运输问题第一节第一节 运输问题及其数学模型运输问题及其数学模型运输问题一般表述为：某种物资有m个产地（生产厂）Ai， 其产量分别为ai, i=1,2,…,m； n个销地（销 售商）Bj，其销售量分别为bj, j=1,2,…,n,从 Ai到Bj的每单位物资的运费为Cij.要求拟定 总运费最小的调运方案 一、运输问题销销地 产产地B1B2┄Bn产产量A1c11c12┄c1na1 A2c21c22┄c2na2 ┄┄┄┄┄┄ Amcm1cm2┄cmnam 销销量b1b2┄bn根据所给的数据可以列如下的运输表设从产地Ai，运往销地Bj的运量为Xij， 则运输问题的数学模型如下：产地约束条件销地约束条件非负约束即当产地的产量总和当产地的产量总和 a ai i与销地与销地 的销量总和的销量总和 b bj j相等时，称此运输相等时，称此运输 问题为平衡运输问题否则称此运问题为平衡运输问题否则称此运 输问题为非平衡运输问题输问题为非平衡运输问题若没有若没有 特别说明，均假定运输问题为平衡特别说明，均假定运输问题为平衡 的运输问题的运输问题二、产量平衡的运输问题的模型产销平衡的运输问题运输问题是一种特殊的线性规划问题， 其约束方程系数矩阵结构如下该矩阵的元素全部是0或1。
每一列 只有两个元素为1，其余为0若用Pij表示 xij的系数列向量，则在Pij中第i个和第m+j 个元素为1，其余为0即A 的增广矩阵的前m个行向量之和 减去后n个行向量之和为零向量，但可取 如下的一个不等于零的m+n-1阶子式， 故A 的增广矩阵的秩等于m+n-1第二节 表上作业法表上作业法是求解运输问题的一种 简便而有效的方法，其求解工作是在运输 表上进行的运输问题也是一个线性规划问题， 当用单纯形法进行求解时，我们首先应当 知道它的基变量的个数；其次，要知道这 样一组基变量应当是由哪些变量来组成 由运输问题系数矩阵的形式并结合第一章 单纯形算法的讨论可以知道：运输问题的 每一组基变量应由 m+n-1个变量组成 (即 基变量的个数 = 产地个数 + 销售地个数 – 1) 进一步我们想知道, 怎样的 m+n-1个变量会构成 一组基变量？计算步骤： （1）找出初始基可行解，即在 (mn) 产销平衡表上 给出m+n-1个有数字的格，其相应的调运量就是基变 量，格子中所填写的值即为基变量的值这些有数 字的格不能构成闭回路，且行和等于产量，列和等 于销售量； （2）求各非基变量的检验数，即在表上求空格的 检验数，判别是否达到最优解。
如果达到最优解， 则停止计算，否则转入下一步； （3）确定换入变量和换出变量，找出新的基可行 解，在表上用闭回路法进行调整 （4）重复（2）、（3）步，直到求得最优解为止 以下我们就具体给出求解运输问题表上作业法一、求初始基可行解的方法 1、最小元素法这种方法的基本思想就是就近供应， 在单位运价表中找出最小元素，尽最大可 能用完一个厂的产量，或满足一个商家的 销量得到满足者用线划去逐次寻找最小元素，直至分配完毕注意：如填写一个数字同时满足了 一厂一商，则需在同行或同列中填写一个 数字0，以保证恰好有m+n-1个数字 下面结合例子给出最小元素法的具体步骤销地 产地B1B2B3B4产量 A1 4A2 6A3 3销量2434136544765875433124032 2、伏格尔法、伏格尔法最小元素法是以就近供应为原则，确定初始基可行解，这可造成整体的不合理因为可能 有这样的情况，某单位运价在整个单位运价表中 可能不是最低，但他在所在的行或所在的列中是 最低的，而同行或同列中的次最低运价与其相差 很大，对这行或列而言，如果不按这行或列最低 运价安排运输，而采用次最低运价安排运输，则 总运费增加很多。
因此应优先考虑行或列次最低 运价与最低运价的差最大行或列，取其最低运价 安排运输这就是伏格尔法的基本思想伏格尔法的基本思想每次从当前运价表上，计算各行各列每次从当前运价表上，计算各行各列 中中次最低运价与最低运价的差，我们称它我们称它 为行或列得罚数优先取罚数最大的行或为行或列得罚数优先取罚数最大的行或 列中列中最低运价的格来确定运输关系，直到的格来确定运输关系，直到 求出初始方案下面仍以上例为例说明这求出初始方案下面仍以上例为例说明这 种方法销地 产地B1B2B3B4产量 A1 4A2 6A3 3销量24341365447658754321012121销地 产地B1B2B3B4产量 A1 4A2 6A3 3销量24341365447658754332111121销地 产地B1B2B3B4产量 A1 4A2 6A3 3销量24341365447658754332311211销地 产地B1B2B3B4产量 A1 4A2 6A3 3销量24341365447658754332131111销地 产地B1B2B3B4产量 A1 4A2 6A3 3销量243413654476587543312133最小元素法得到初始方案：最小元素法得到初始方案：X X1313=3=3，，X X1414=1=1，，X X2121=2=2，，X X2222=4=4，，X X3434=3=3，，总运费总运费=3=3××3+43+4××1+41+4× ×2+42+4× ×4+84+8× ×3=613=61（元）（元）伏格尔法伏格尔法得到得到初始方案如下：初始方案如下： X X1313=3=3，，X X1414=1=1，，X X2121=2=2，，X X2222=1=1，，X X2424=3=3，，X X3232=3=3，，总运费总运费=3×3+4×1+4×2+4×1+5×=3×3+4×1+4×2+4×1+5×* *3+6×3=583+6×3=58（元）（元）由以上结果可以看出，一般来说伏格尔法由以上结果可以看出，一般来说伏格尔法 求求得的得的初始方案比初始方案比最小元素法求得的初始方案最小元素法求得的初始方案 要好。
要好二、最优性检验检验解的最优性的方法有两种，闭回路法 和位势法 1、闭回路法 闭回路：在初始运输方案表中，从任意空格（闭回路：在初始运输方案表中，从任意空格（ 非基变量）出发，沿着纵向或横向行进，遇到非基变量）出发，沿着纵向或横向行进，遇到 适当基变量适当基变量9090度转弯，继续行进，总能回到原度转弯，继续行进，总能回到原 来空格这个封闭的曲线称为闭回路这个封闭的曲线称为闭回路闭回路法是通过寻找闭回路来找到非基变 量的检验数可以证明，如果对闭回路的方向不加区别 ，那么以每一个非基变量为起始顶点，以基变 量为其它顶点的闭回路就存在而且唯一 如果规定作为起始顶点的非基变量为第 一个顶点，闭回路的其他顶点依次为第二个 顶点、第三个顶点……，那么就有 检验数=奇数点单位运费之和－偶数点单位 运费之和若所有非基变量检验数≥0，则最优现结合上例中最小元素法给出的初始基 可行解说明闭回路法销地 产地B1B2B3B4产量 A1 4A2 6A3 3销量243413654476587543 312403x11检验数为 6-4+8-6+4-4=4销地 产地B1B2B3B4产量 A1 4A2 6A3 3销量243413654476587543 312403x12检验数为 5-4+8-6=3销地 产地B1B2B3B4产量 A1 4A2 6A3 3销量243413654476587543 312403x23检验数为 7-3+4-8+6-4=2销地 产地B1B2B3B4产量 A1 4A2 6A3 3销量243413654476587543 312403x24检验数为 5-8+6-4=-1销地 产地B1B2B3B4产量 A1 4A2 6A3 3销量243413654476587543 312133x11检验数为 6-4+5-4=3销地 产地B1B2B3B4产量 A1 4A2 6A3 3销量243413654476587543 312133x12检验数为 5-4+5-4=2销地 产地B1B2B3B4产量 A1 4A2 6A3 3销量243413654476587543 312133x23检验数为 7-3+4-5=3销地 产地B1B2B3B4产量 A1 4A2 6A3 3销量243413654476587543 312133x31检验数为 7-4+4-5=1销地 产地B1B2B3B4产量 A1 4A2 6A3 3销量243413654476587543 312133x33检验数为 5-3+4-5+4-6=-1销地 产地B1B2B3B4产量 A1 4A2 6A3 3销量243413654476587543 042430x11检验数为 6-4+5-4=3销地 产地B1B2B3B4产量 A1 4A2 6A3 3销量243413654476587543 042430x12检验数为 5-4+5-4=2销地 产地B1B2B3B4产量 A1 4A2 6A3 3销量243413654476587543 042430x23检验数为 7-3+4-5=3销地 产地B1B2B3B4产量 A1 4A2 6A3 3销量243413654476587543 042430x31检验数为 7-4+5-4+3-5=2销地 产地B1B2B3B4产量 A1 4A2 6A3 3销量243413654476587543 042430x33检验数为 6-5+3-4+5-4=1销地 产地B1B2B3B4产量 A1 4A2 6A3 3销量243413654476587543 042430x34检验数为 8-5+3-4=2销地 产地B1B2B3B4产量 A1 4A2 6A3 3销量243413654476587543 042430此解为最优解，最低运费为55（元）2、位势法当运输问题变量的格数较多时，用闭 回路法计算检验数比较麻烦，而位势法比 较简便。
对于运输问题minf=CXAX=bX≥0 设设B为为其一个可行基，则则xij的检验数为σij=CBB-1Pij-Cij对于运输问题的对偶问题maxf=YbYA≥ CY无限制 其中，Y =(u1,…, um,v1, …,vn)为为对偶变量 ，根据对偶理论有Y=CBB-1,因此有σij=YPij-Cij 又因为Pij的第个i元素和第个m+j元素为1 ，其它元素为0，所以有σij=(u1,…, um,v1, …,vn)Pij-Cij=ui+vj-cij因为所有基变量的检验数为0，因此有σij = ui+vj-cij=0 即ui+vj=cij 由此可得含有m+n-1个方程的方程组，其中 含有m+n个未知量，可令某一个变量等于零 ，解得方程组的解，然后可根据σij = ui+vj-cij 计算非基变量的检验数这种计算检验数的 方法称为位势法下面以上面利用伏格尔法 求得的初始基可行解为例说明位势法销地 产地B1B2B3B4产量 A1 4 A2 6A3 3 销量243413654476587543 312133u1+v3=3, u1+v4=4, u2+v1=4, u2+v2=4, u2+v4=5, u3+v2=6u1+v3=3, u1+v4=4, u2+v1=4, u2+v2=4, u2+v4=5, u3+v2=6令u1=0 由 u1+v3=3 得 v3=3 由 u1+v4=4 得 v4=4 由 u2+v4=5 得 u2=1 由 u2+v1=4 得 v1=3 由 u2+v2=4 得 v2=3 由 u3+v2=6 得 u3=3 σ11=u1+v1-c11=0+3-6=-3, σ12=u1+v2-c12=0+3-5=-2 σ23=u2+v3-c23=1+3-7=-4, σ31=u3+v1-c。