线性规划运输问题

1、第四章 运输问题Chapter 4Transportation Problem4.1 运输问题的定义设有同一种货物从 m 个发地 1，2， m 运往 n 个收地 1，2， n 。第 i 个发地的供应量（ Supply ）为 si（si0 ），第 j 个收地的需求量（ Demand ）为 dj （d j0 ）。每单位货物从发地 i 运到收地 j 的运价为 cij。求一个使总运费最小的运输方案。我们假定从任一发地到任一收地都有道路通行。如果总供应量等于总需求 量，这样的运输问题称为供求平衡的运输问题。我们先只考虑这一类问题。c11111jicincmcmjmn图 4.1图 4.1.1 是运输问题的

2、网络表示形式。 运输问题也可以用线性规划表示。设 xij为从发地 i 运往收地 j的运量，则总运费 最小的线性规划问题如下页所示。运输问 题线性规划变量个数为 nm 个，每个变量 与运输网络的一条边对应，所有的变量都 是非负的。 约束个数为 m+n 个，全部为等 式约束。前 m 个约束是发地的供应量约束， 后 n 个约束是收地的需求量约束。运输问 题约束的特点是约束左边所有的系数都是0 或 1，而且每一列中恰有两个系数是 1，其他都是 0 。运输问题是一种线性规划问题，当然可以用第一章中的单纯形法求解。但由于 它有特殊的结构，因而有特殊的算法。在本章中，我们将在单纯形法原理的基础上， 根据运输

3、问题的特点，给出特殊的算法。minz c11x11 c12x12s.t. x11 x12c1nx1n c21x21 c22x22c2nx2ncm1xm1 cm2xm2cmnxmnx1nx21x22x2ns2x12x22xm2x1nx2nxmnx11 x12x1nx21x22x2nxm1xm2xmn在运输问题线性规划模型中，令X= ( x 11 ，x 12 ， x 1n ， x21 ，x22 ，x2n ， xm1 ， xm2 ，C=(c11，c12 ， c1n ，c21 ，c22 ，c2n ， cm1 ， cm2 ，A=a11 ，a12 ， a 1n ， a21 ，a 22 ，a2n ， am1

4、 ， am2 ，111111m行=111111111n行111b=(s1，s2， sm， d1，d2，dn)Txm1xm2xmnx11x21xm1则运输问题的线性规划可以写成：xmn )cmn )amn smd1d2dn0min z= CTXs.t.AX=bX0其中 A 矩阵的列向量aij =ei+em+jei 和 em+j 是 m+n 维单位向量，1 分别在在第i 个分量和第 m+j个分量的位置上。 A 矩阵中的行与运输网络中的节点对应，前m行对应于发地，后n 行对应于收地； A 矩阵的列与运输网络中的边对应。运输问题除了用网络表示及线性规划表示外，还可以用运输表表示：1 2 nc11x11

5、c12x12c1nx1nc21c22c2nx21x22x2ncm1cm2cmnxm1xm2xmns1s2d1d2smdn表 4.1=20=10表的行与发地对应，列与收地对应。第 i 行与第 j 列交叉的一格与网络的一条 边对应 （也就是与线性规划约束矩阵的一列对应） ，每一格的左上角小方格的数字表 明从相应的发地 i到收地 j 的运价 cij，每一格右下角表明从相应的发地 i到收地 j 的 运量 xij 。表右方表明各发地的供应量 s i ，表下方表明各需求第的需求量 d j。每一行 运量之和表示从该发地运往各收地的运量之和， 它应该等于该发地的供应量； 同样， 每一列运量之和表示从各发地运往

6、该收地的运量之和， 它应该等于该收地的需求量。运输问题的网络图、线性规划模型以及运输表之间的关系可以用下表表示：网络图线性规划模型运输表节点发点 i约束前 m 个约束表的行收点 j后n 个约束表的列边从节点 i 到节点 j变量 x ij ，列向量 aij表中的一格例 4.1 以下的运输问题线性规划、网络图和运输表表示同一运输问题。minz=8x 11+5x 12+6x 13+7x 21+4x 22+9x 23s.t.x11+x 12+x 13=15x21+x 22+x 23=25x11+x 21=10x 12x 13+x 22+x 23x 11 ,x12,x13,x 21,x22 ,x2308

7、56x11x12x13749x21x22x231231152251020101020表 4.24.2 运输问题约束矩阵的性质4.2.1 约束矩阵的秩运输问题约束矩阵 A 的秩为 m+n-1 。证明：因为 A 矩阵的前 m 行和后 n 行之和分别等于向量（ 1 ，1， 1），因 此秩 A<m+n 。考虑 A 的一个子矩阵A' =a1n ，a 2n ， amn ，a11，a12 ， a1n，即11111m行1A'=11n行1111m列n列删除 A '中的第 m+n 行和第 m+n 列，得到1 1 1 11m 行1 1m 行A ''=11n 1行m列n

8、1列容易看出，秩 A'' =m+n -1 。由此m+n-1= 秩 A''秩 A'秩 A<m+n秩 A =m+n-1 。在线性规划问题中，约束的系数矩阵要求行满秩的，为了使运输问题系数矩阵 行满秩，在 A 矩阵中增加一个列向量 em+n 形成增广矩阵00A em nA0010这样增广矩阵 A 的秩就等于 m+n ，因而是行满秩的。并且 A 中任何一个基矩阵，都必定包含单位向量em+n 。例 4.2.1 设一个运输网络如右图，它的系数矩阵为x11 x12x13 x21x22x23111000s1000111s2A100100d1010010d20010

9、01d3增广矩阵为x11x12x13x21x22x23xe1110000s10001110s2Ad110010000100100d20010011d3增加的单位列向量em+n =e 5相当于在在网络图中增加一条边，它与收点3 关联，但不与任何发点关联，这条边称为人工边。设这条边上的运输量为xa，增广运输问题对应于第三个收点的约束称为x 13 +x 23 +x a=d 3由于图 4.3因此，对运输问题的任何一个可行解，都有xa=0 。4.2.2 A 矩阵的单位模性质运输问题的系数矩阵 A 具有以下性质： A 矩阵中任何一个 k 阶子矩阵 A（k k=1 ， 2， m+n ），都有 det Ak=

10、0 或± 1。证明：在 A 中任取一个 k 阶方阵 Ak ，有以下三种情况：1 、 A k中任何一列都有两个 1，这时 Ak上部的行属于 A矩阵的前 m 行，而下 部的行属于 A 矩阵的后 n 行，Ak 上部的各行之和以及 Ak下部各行之和都 等于向量（ 1，1， 1），因而 Ak的行线性相关，即 det Ak=0。2、 Ak 中至少有一列元素全为 0 ，这时显然有 det A k=0 。3 、 A k中至少有一列，其中只有一个 1 。这时可以将 det Ak 按这一列展开，设 对应于这个 1 的代数余子式为 Ak-1 ，则有det Ak=± det A k-1其中 Ak-

11、1 是 k-1 阶方阵。对 Ak-1 同样有det Ak-1 =0或者det Ak-1 =± det Ak-2最后有det Ak=0或者 det Ak=± det Ak-1 =± det Ak-2= =± det A1=0 或±1。4.2.3 基矩阵的三角性设 B 是 A 的一个基， B 中至少有一列只包含一个 1，否则， det B=0 不成为 个基。将 B 的行列交换，总可以使 B 成为PTBm n 11 ，对0其中 det Bm+n-1 0 ，因而 Bm+n-1 中也至少有一列只有一个Bm+n-1 再进行行列交换，得到1P01QTB

12、9;' 00Bm n 200依次不断对剩下的方阵进行行列交换，最后可以得到101RB0010 0 0 1是一个上三角矩阵。例 4.2 设一个运输问题的系数增广矩阵为x11x12x13x21x22x23xe1110000s1300001110s220A=1001000bd1150100100d2100010011d325取其中一个基x13x23x11x12xa10110s13001000s220B00100bd11500010d21011001d325对 B 进行行列交换，成为以下上三角矩阵xax13x23x11x1211100d32501010s130B00100bs22000010d

13、11500001d210求解相应的方程组11100xa2501011x133000100x232000010x111500001x1210xax13x2325x13x11x1230x2320x1115x1210x12 =10 ， x11 =15 ，x23 =20 ，x13 =5 ，xa=0由此得到由 A 的基矩阵的三角性以及 A 矩阵中仅含有元素 0 和 1 ，可以知道，如果运输问题 各发地的供应量和收地的需求量都是整数，运输问题的任何基础可行解都是整数， 因而最优解也是整数。4.3 基在网络图和运输表中的表示从前一节已经知道，运输问题的一个基是由 m+n 个列向量组成的，其中包括一个单位向量

14、 em+n 。在网络图上，这 m+n 个列向量对应 m+n 条边，其中与单位向量对应的是从最后一个收地 出发的人工边。 网络图中的一个基具有以下性质：1 、 一个基由 m+n 条边组成， 其中一条是人 工边，其余 m+n-1 条边是原网络中的边。2 、 组成基的边不能形成闭合回路。 若不然， 如果组成一个基的若干条边（ i，j），（k ，j），（i，l），（k ，l）组成一个闭合回路，则这些边对应的系数矩阵中的列向 量 aij，akj ，ail ，akl 的线性组合aij-akj+ail-akl=（ei+em+j）-（ek+em+k ）-（ei+em+l）+（ek+em+l）=0 这些列向量线

15、性相关，显然不能包含在一个基中。000B0 节点 k3 、 组成基的 m+n 条边必须到达网络的每一个节点。若不然，这 m+n 条边都 不与某一节点 k 关联，那么相应的基矩阵与节点 k 对应的一行全为 0，即 det B=0。 B 不可能成为一个基。 例 4.3 对于 2 个发点 3 个收点的运输问题， 网络图如图 4.5（a）所示。图 4.5（b ）、 （c）、（d ）都是这个问题的基， 这些基都由 m+n-1=2+3-1=4 条边组成， 都不构成 回路，并且与每一个节点关联。正如线性规划矩阵的列向量组成的基一样，一个网络的基的个数是非常多的， 以上只是这些基中的几个例子。(c)第二个基(

16、d)第三个基图 4.54.4 基在运输表中的表示我们已经知道，运输表中的一行对应于一个发地，一列对应于一个收地，表中i行j 列相交的格子表示网络从发地节点 i到收地节点 j的一条边。运输表中同一行 i 而不同列 j 和 k 的两个格子（ i，j）（i，k ），分别表示网络中从同一发地节点i 出 发到达不同收地节点 j 和节点 k 的两条边；同样，运输表中位于同一列 k 而不同行 i 和 l 的两个格子（ i，k）和（ l ，k ）分别表示从不同的发地节点出发，到达同一收地节点 j 的两条边（见下表和图）（i，j）（i，k）（l，k）j k表 4.3如果运输表中有若干个格子，他们中相邻的两个都分

17、别位于同一行或同一列，例如在下表中六个格子（ i，j），（i，k），（l，k），（l，n），（m，n）和（ m，j），将位于同一行和同一列的两个格子连结起来，在运输表中构成一个闭回路。在相应的网络图中，这六个格子对应的六条边也组成一个闭回路。（i，j）（i，k）（l，k）（l，n）（m ，n）（m，j）ilmj k n表 4.4图 4.7iknm运输表中的闭回路还可以出现更复杂的情况，如下表和下图所示。（i，j）（i，k）（l，j）（l，n）（m，k）（m ，n）kn表 4.5ilknm图 4.8综上所述，总结运输表中一个基必须具备的特点：1 、 一个基应占表中的 m+n-1 格；2 、 构成

18、基的同行同列格子不能构成闭回路；3 、 一个基在表中所占的 m+n-1 个格子应包括表的每一行和每一列。 例 4.4 在例 4.3.1 中的运输网络的几个基分别用网络和运输表的表示如下：（a）系数矩阵、网络图和运输表x11x12x13x21x22x23xa111000000011101001000010010000100111231（ 1,1 ）（1,2 ）（ 1,3 ）2（ 2,1 ）（2,2 ）（ 2,3 ）（b） 第一个基的矩阵、网络图和运输表x11 x12 x13 x21 xa11100 00010 10010 01000 001011 2 3（1,1）（1,2 ）（ 1,3 ）（2,

19、1）12（c） 第二个基的矩阵、网络图和运输表x11 x12x22 x23 x a0010000011（1,1）（ 1,2 ）（ 2,2 ）（2,3 ）1 2 312（d）第三个基的矩阵、网络图和运输表x11x13x22x23xa1100000110100000010001011图 4.12（1,1）（1,3 ）（ 2,2 ）（2,3 ）1 2 31a j BY j aB1 aB 2aBy2j4.5 非基列向量用基向量表示在线性规划中，设 B是A 矩阵的一个基，且 B=aB1，aB2，aBm，则A 中 的任一非基向量 aj（ j R）必定可以用基向量 aB1，aB2 ，a Bm 唯一地线性表出

20、， 其线性组合的系数就是 Yj，这是因为Yj=B-1aj即y1j y mjy1jaB1y2jaB2y mjaBm这就是说，向量 Yj 就是用基向量表出一个非基向量a j的系数。在运输问题中如果确定了一个基，非基向量aij 也可以由基向量唯一地表出， 由 于运输问题的特殊性，表出系数 Yij 可以很方便地确定。请看下一例子。例 4.5 以具有 2 个发地， 3 个收地的运输问题为例子，这个运输问题的网络图和系 数矩阵如下：(1,1)(1,2)(1,3)(2,1)(2,2)( 2,3) e11100000001110100100001001000010011图 4.13取基 B=a11 ，a12

21、，a13 ，a23 ，e a，非基向量为 a21 ，基矩阵、 网络图中的非基边 （用 虚线表示）、基边（用实线表示） ，并取从发地到收地的方向为各边的方向。(1,1)1(1,2)1(1,3)1(2,3)00B1由于任何一个非基向量总是与基向量实线性相关的，因此在网络图中任一条非基边a ij ，有必定与若干条基边形成闭回路。根据运输矩阵的结构，对任何一个列向量aij=ei+em+j 。在上面的问题中，非基向量a21=e2+e2+1=e2 +e3基向量 a11 ，a12 ， a13， a23 可以表示为a11=e1+e2+1=e1 +e3a12=e1+e2+2=e1 +e4a13=e1+e2+3=

22、e1 +e5a23=e2+e2+3=e2 +e5a21 可以表示为：因此a21 -a11 +a13 -a23 =(e2+e3)-(e1+e3)+(e1+e5)-(e2+e5)=0a21 =a11 -a13 +a23由于基向量 a12 和 ea 不在这个回路中，它在a12 的表达式中的系数是 0 ，因此非基向量 a21 用所有基向量的表出形式为：a21 1 a11 0 a12 ( 1) a13a230 eaa11a12 a13 a23eaBy 21图 4.15由此可以看出10Y21110从这个例子可以看出，非基向量由基向量表出的方法和表出的系数可以由该非 基向量与有关的基向量形成的回路来确定 （

23、见上图）。选定该非基边的方向作为闭回 路的方向，如果一个基边出现在该回路中，并且与回路的方向相同，则表出系数为 -1 ，如果基边的方向和回路的方向相反，则表出系数为 +1 ，如果基边不在回路中， 表出系数为 0 。从给定非基边的起点（发地）出发，沿着回路方向前进，第一次遇到的基边的 方向一定和回路方向相反，第二次遇到的基边方向一定和回路方向相同，同向和反 向交替出现，因此，各基边的表出系数一定是+1 ，-1 交替出现。与网络图对应，在运输表中非基向量用基向量表示的方法也可以相应得到。例 如以上的运输问题，相应的运输表如下左表所示。1231231( 1,1 )（1,2 ）( 1,3 )1B(+1

24、)B(0)B(-1)2( 2,1 )（2,2 ）( 2,3 )2NB(+1)表 4.6对应于基 B=a11 ，a12 ， a13 ，a23 ，ea的格子为用 B 表示，非基向量 a21 相应的格 子用 N 表示，见上面右表。运输表中非基向量用用基向量表出的系数是这样确定的： （按任一方向） 沿着表 中的闭回路前进，在第一个转角处基向量的表出系数为+1 ，下一个转角处基向量的表出系数为 -1 ，以后依次交替变化，由于沿闭回路回到出发的非基向量以前一定要 经过奇数次转角，因此最后一个转角处的基向量的表出系数一定也是 +1 。凡是不在 闭回路上或不在闭回路转角处的基向量的表出系数均为 0 。在上面的

25、表中，非基向量 N（2，1）与基向量 B（1，1）、B （1，3）、B（2， 3 ）构成一个闭回路，相应的表出系数依次为+1、-1 和+1 ；基向量 B（1，2）不在闭回路的转角处，表出系数为 0 。因此，非基向量 a21 的表出形式为： a21 1 a11 0 a12 ( 1) a13 1 a23例 4.6 设有 4 个发地， 5 个收地的运输问题，运输表和网络图如下：表 4.7取其中 m+n-1=4+5=9 个基向量 a11 ，a12 ，a14 ， a21 ，a31 ，a33 ，a34 ，a35 和 a45 ，非基向量 a42 与 基向量构成的闭回路 如右图。根据基向量的表出 系数由 +1

26、 开始， +1 、-1 交替的原则，以上非基向 量用这些基向量表出的形式为：a 42 =(+1) a12 +( -1) a 11 +(+1) a31 +( -1) a 35 +(+1) a 45 + 0ea如果所有基向量按以下次序排列B = a 11 ，a 12 ，a21 ，a 31 ，a33，a34，a35，a45， ea因而 a42 用这些基向量表示的表出系数图 4.17Y42 =-1 ，+1，0，+1，0，0，-1，+1，0T4.6 运输问题单纯形法运输问题单纯形法的基本步骤和线性规划一样，包括以下步骤，但具体实施是 在运输表上实现。1 、 求得一个初始基础可行解；2、 对非基变量 xi

27、j 计算检验数 zij-cij，根据各非基变量的检验数 zij-c ij 值，确定 最优性或选择进基变量；3、 当进基变量 xij进基时，根据基变量的变化，求出最先降为0 的基变量确定为离基变量；4 、 进行基变换，获得新的基础可行解并转步骤2。4.6.1 确定初始基础可行解1 、 西北角法 西北角法是按发地和收地的编号为序，依次顺序供给的原则获得初始基础可行 解的一种方法。它是从确定发地 1 到收地 1 的运量开始。这个位置按地图的方位来 说是西北角，因而得名。从发地 1 到收地 1 的运量取发地 1 的供应量（ 30 ）和收地1 的需求量（ 15 ）两者中小的一个安排，如果发地 1 的供应

28、量没有用完，则将剩余 的供应量向收地 2 发送，依次类推，直到最后一个发地的供应量全部运出，最 后一个收地的需求量全部满足为止。15 和 0 。例 4.7 给出运输表如下。发地 1 的供应量为 30 ，收地 1 的需求量为 15 ，在（ 1 ，10119151513121691187101413121330-11524535025415-152031841 ）上安排运量 15。发地 1和收地 1 的供应量和需求量分别变为1 2 3 4发地 1 的供应量为 15，收地 2 的需求量为 20，在（ 1 ， 2 ）上安排运量 15，1011915151513121691187101413121341

29、24535025415-15发地 1 的供应量变为 0 ，收地 2 的需求量变为 5 ；1 2 30 的需求量为 地 2 的供应量变为 40 ，1收地20-15 31 84 5，发地 2 的供应量为 45 ，在（ 2，2） 收地 2 的需求量变为 0 ；2 3上安排运量 5，发101191515151312169511871014131213410245-5350254发地0 5-5 31 84 的供应量为 40，收地 3 的需求量为 31，在（ 2 ， 3 ）上安排运量 31， 发地 3 的供应量变为 9 ，收地 3 的需求量变为 0 ；101191515151312169531118710

30、14131213410235025440-311 2 3发地 2 的供应量为 9。收地 4 的需求量为 84 ，在（ 2，4） 地 2 的供应量变为 0 ，收地 4 的需求量变为 75 ；1 2 3上安排运量 9 ，发10119151515131216953191187101413121341029-93502540 0 0 84-9收地 4 的需求量为 75 ，发地 3 的供应量为 50 ，安排（ 3 ， 发地 3 的供应量 0，收地 4 的需求量 25 ；1 2 34 ）上的运量为 50 ，1011915151513121695319118710501413121341020325450-

31、500 0 0 75-50的供应量为 25 ，收地 4 的需求量为 25 ，安排（ 4，发地 4 的供应量为 0 ，收地 4 的需求量为 0 ，供求和需求都得到满足。1 2 3 4发地 44 ）上的运量 25 ，5-25=000025-25=0用西北角法确定初始可行解方法简单，不会出现回路，而且一般情况下基变量 的个数恰为 m+n-1 个（退化的情况基变量可能少于 m+n-1 ，处理的方法在 4.7 节 中介绍），而且基变量位于每一行每一列，因而得到的是一个基础可行解。西北角法 的缺点是在安排运量时不考虑运价，因而得到的初始解可能离开最优解比较远。以 上例子中用西北角法得到的初始解的目标函数值

32、为z=cijxij=10 15+11 15+12 5+16 31+9 9+10 50+13 25=17772 、 最小元素法这种方法是按运价由小到大的顺序安排运量。先从各运价中找到最小运价，设 为 cij ，然后比较供应量 si和需求量 dj，如果 si>d j，取 xij=d j，并将发地 i 的供应量 改为 si-dj，将收地 j的需求量改为 0；如果 si<dj，取 xij =si，并将发地 i 的供应量改为 0，将收地 j 的需求量改为 dj-si；如果 si和 d j中有一个为 0，则不分配运量给 xij。 分配完最小运价的运量后，用同样的方法分配运价次小的运量，依次类推

33、，直到每 一个发地的供应量和每一个收地的需求量都为0 。以下是用最小元素法确定运输问题的初始可行解的例子。例 4.8 给出运输表如下。最小运价为c33=7，发地 3 的供应量为 50 ，收地3 的需求量为 31 ，安排运量 x33 =31 。发地3 和收地 3 的供应量和需求量分别变为19 和发地 30。10119151312169118710311413121312341302453254152031-318450-31对于 c32 =8 ，发地 3 的供应量为 19，收地 2 的需求量为 20，安排 x32 =19 ， 的供应量为 0 ，收地 2 的需求量为 1 。1 2101191513

34、1216911871019311413121324532541520-1908419-19对于 c13 =9，c24 =9 ，可以任选一个，但是（ 1 ， 3 ）中收地 3 的需求量为 0，安排x 24 =45 ，发地 2 的供应量为 0，收地 4 的需求量为 39 。10119151312169451187101931141312131234130230254151084-4545-45对于 c11 =10 和c34=10 ，由于发地 3 的需求量已经为 0，安排x 11 =15 ，发地 1 的供应量为101191515131216945118710193114131213341203025

35、430-1515，收地 1 的需求量为 0；1 2对于 c12 =11 ，安排 x12=1，发地 1的供应量为 14，收地 2 的需求量为 0；1234123415-1002501-103914。对于 c44 =13 ，安排 x44=25 ，发地 4的供应量为 0，收地 4 的需求量为10119151511312169451187101931141312132512341234140025-2500039-25最后安排 x 14 =14 ，所有发地和收地的供应量、需求量都等于0。101191515114131216945121 2 3 414-14 =001187101931141312132

36、5400014-14=00这样就得到一个运输问题的初始基础可行解。这个初始基础可行解的目标函数值为 z=10 15+11 1+15 14+9 45+8 19+7 31+13 25=1470 比用西北角法得到的初始基础可行解的目标函数值小。4.6.2 计算非基变量的检验数 zij -c ij4.5.2.1 闭回路法对于非基变量 xij ，检验数为zijcijCBB aijcijCBYijcij这个闭回路转角处的基其中向量 Yij 可由该非基变量与基变量形成的闭回路来确定， 变量对应于 y=± 1，其余的基变量对应于 y=0 。这样 CTBYij 就等于转角处基变量对 应的 cij 依次

37、加减的值。zij -c ij例 4.9 在例 4.7 中，用西北角法得到初始基础可行解，计算各非基变量的检验数10119151515131216953191187105014131213251234130245350415203184非基变量（ 1，3 ）相应的闭回路为1 234130245350254152031841，4 ）相应的闭回路为1 2非基变量（因此 x13 的检验数 z13 -c 13 =(c 12 -c 22 +c 23 )-c 13 =(11-12+16)-9=+6非基变量（因此 x14 的检验数 z14 -c 14 =(c 12 -c 22 +c 24 )-c 14 =(1

38、1-12+9)-15=-7101191515151312169-25319118710501413121325341302453502542 ， 1 ）相应的闭回路为1 215203184因此 x21 的检验数 z21 -c 21 =(c 11 -c 12 +c 22 )-c 21 =(10-11+12)-13=-2非基变量（343 ， 1 ）相应的闭回路为1 2因此 x31 的检验数z31-c 31 =(c 11 -c 12 +c 22 -c 24 +c 34 )-c 31 =(10-11+12-9+10)-11=+1用同样的方法可以求得其他非基变量的检验数z43-c 43 =(c 23 -

39、c 24 +c 44 )-c 43 =(16-9+13)-12=+8 将以上检验数填入运输表，用“”表示。1 24101511159+615 -713-212516319911+18+57+10105014+113+312+81325313024535025415203184z32 -c 32=(c 22 -c 24 +c34 )-c 32 =(12-9+10)-8=+5 z33-c 33 =(c 23 -c 24 +c 34 )-c 33 =(16-9+10)-7=+10 z41 -c 41=(c 11 -c 12 +c23 -c 24 +c 44 )-c 41 =(10-11+12-9+1

40、3)-14=+1 z42-c 42 =(c 22 -c 24 +c 44 )-c 42 =(12-9+13)-13=+3对用最小元素法得到的初始基础可行解，也可以用同样的方法求得各非基变量的检验数 zij-c ij，计算过程略，计算结果见下表。4.5.2.2 对偶变量法设运输问题的原始问题为：min z c11x11 c12x12c1nx1n c21x21 c22x22c2nx2ncm1xm1cm2xm2cmnxmns1s2s.t.x11 x12x1nx21x22x2nxm1xm2xmnsmx11x21xm1d1x12x22xm2d2x1nx2nxmnxadnx11 x12x1nx21x22x

41、2nxm1xm2xnm 0xa:unr其中 xa是为了使矩阵 A 满秩而增加的变量。设与前 m 个约束对应的对偶变量为 u1，u2， um，与后 n 个约束对应的对 偶变量为 v1，v 2， vn。则对偶问题为：max y=s 1u1+s2u2+smum+d1v1+d2v2+ +dnvns.t.u 1+v 1c11u 1+v nc1nu 2+v n c2nu m +v 1 cm1， u m，v1，v2， vn ：unr ndjvjj1u m +v n cmn vn=0 u1，u2， 以上对偶问题，可以简写成： m max ysi uii1ui+vjcij(i=1,2, ,m； j=1,2, ) ,nvn=0u i， vj： unr对偶问题中由 m+n 个变量， mn+1 个约束。T T -1 对于运输问题的一个基 B ，如果能够求出相应的对偶变量W T=CBTB-1，就可以计算非基变量 xij 的检验数 zij-c ij ：T -1 T T zij-c ij=CB B