B2 B3 B4 4 5 5 6 A 20 0 A2 8 6 5 30 3的 2 3 4 A3 10 10 20 0 403p b 10 10 20 0 020 90 表2.2.2由最小元素法确定的例2.2.2的初始方案 定理2.2.1利用最小元素法确定的x={x}为(2.1.2)的基本可行解，其中数字格对应的变量正好是 基变量。 证明：首先，由最小元素法具体步骤知x={x}为(21.2)的可行解，并且数学格的个数为r。由定理 2.1.2知，现在只需证明数学格对应的变量组不含闭回路。否则，不妨设含有闭回路 Xih 如果格子（么，）填数x时，划去的是行（若是列可类似讨论），则数字x一定比x先填，并且填后划 去了第方列，从而数字x6一定比xh先填，并且填后划去了第马行，从而又知X一定比x先填，并 且填后划去了第。由此知，格子(，)处根本不可能填数，矛盾。 2.伏格尔法 最小元素法的缺点是，为了节省一处的费用，可能会造成其他处多化更多的费用。伏格尔法考虑每 个产点到各销点的最小运价与次小运价之间的差额（行差额）、各产点到每个销点的最小运价与次小运价 之间的差额（列差额），对差额最大的产地或销点中运价最小的点采用优先考虑的思想确定方案。下面以 具体例子说明最小元素法的步骤。 例2.2.3设有运输表2.1.2，用伏格尔法确定其初始方案（写在中间）。 解：先求出各行各列的差额，分别写在最后一行和最后一列。从差额最大的第二列中运价最小C2对应 的变量x2开始考虑： x2=min{a3,b2}=min{9,6}=6=b 在格子(3,2)处填入6，并且x2=x2=0(不用填)，划去第2列，4=a-6=3。 对表中余下部分重新求出各行差额写在最后一列。从差额最大的第4列中运价最小℃4对应的变量 x4开始考虑： x=minfa,b)=min(3,6)=3=a 在格子(3,4)处填入3，并且x31=x3=0(不用填)，划去第3行，b=b-3=3。 对表中余下部分重新求出各列差额写在最后一行。从差额最大的第1列中运价最小c2!对应的变量 x21开始考虑：
6 B1 B2 B3 B4 ai A1 4 5 5 6 20 20 A2 8 67 5 30 30 A3 2 10 3 10 2 20 4 0 40 30 10 0 bj 10 10 20 50 50 20 90 表 2.2.2 由最小元素法确定的例 2.2.2 的初始方案 定理 2.2.1 利用最小元素法确定的 { }ij x = x 为(2.1.2)的基本可行解，其中数字格对应的变量正好是 基变量。 证明：首先，由最小元素法具体步骤知 { }ij x = x 为(2.1.2)的可行解，并且数学格的个数为 r。由定理 2.1.2 知，现在只需证明数学格对应的变量组不含闭回路。否则，不妨设含有闭回路 1 1 i j x 1 2 i j x 2 1 i j x 2 2 i j x 如果格子 1 1 (, ) i j 填数 1 1 i j x 时，划去的是行（若是列可类似讨论），则数字 1 2 i j x 一定比 1 1 i j x 先填，并且填后划 去了第 2j 列，从而数字 2 2 i j x 一定比 1 2 i j x 先填，并且填后划去了第 2 i 行，从而又知 2 1 i j x 一定比 2 2 i j x 先填，并 且填后划去了第 1 j 。由此知，格子 1 1 (, ) i j 处根本不可能填数，矛盾。 2．伏格尔法 最小元素法的缺点是，为了节省一处的费用，可能会造成其他处多化更多的费用。伏格尔法考虑每 个产点到各销点的最小运价与次小运价之间的差额(行差额)、各产点到每个销点的最小运价与次小运价 之间的差额(列差额)，对差额最大的产地或销点中运价最小的点采用优先考虑的思想确定方案。下面以 具体例子说明最小元素法的步骤。 例 2.2.3 设有运输表 2.1.2，用伏格尔法确定其初始方案(写在中间)。 解：先求出各行各列的差额，分别写在最后一行和最后一列。从差额最大的第二列中运价最小 c32 对应 的变量 x32 开始考虑： x32 3 2 2 = = == min{ , } min{9,6} 6 ab b 在格子(3,2)处填入 6，并且 12 22 x x = = 0 (不用填)，划去第 2 列， 3 3 a a ′ = − = 6 3。 对表中余下部分重新求出各行差额写在最后一列。从差额最大的第 4 列中运价最小 c34 对应的变量 x34 开始考虑： x34 3 4 3 = = == min{ , } min{3,6} 3 ab a ′ ′ 在格子(3,4)处填入 3，并且 31 33 x x = = 0 (不用填)，划去第 3 行， 4 3 b b ′ = − = 3 3。 对表中余下部分重新求出各列差额写在最后一行。从差额最大的第 1 列中运价最小 c21 对应的变量 x21 开始考虑：
x3:=min{a2,b}=min{4,3}=3=b 在格子(2,1)处填入3，并且x1=0(不用填)，划去第1列，d=a2-3=1。 对表中余下部分重新求出各行差额写在最后一列。从差额最大的第1行中运价最小℃13对应的变量 x13开始考虑： Xi3=min(a,b3)=min(7,5)=5=b 在格子(1,3)处填入5，并且x23=0(不用填)，划去第3列，a4=a,-5=2。 现在还剩下最后一列的第一、二个格子，从运价最小c24对应的变量x24开始考虑： x=min(az,b)min(1,3)=1=a 在格子(2,4)处填入1，划去第2行，b=b-1=2。 现在还剩下最后一列的第一个格子，考虑变量4： x=min (a,6)min(2,2)=2 在格子(1,4)处填入2，划去第1行和第4列。至此，得到了如下运输方案。 B B2 B3 B4 a 行差额 3 11 3 10 A 祁 才 9 A 3 1 牧 > 4 10 A3 6 3 非 h主 b 69平 20 列差额 表2.2.3由伏格尔法确定的例2.2.1的初始方案 2.2.2检验数的求法 对于己知的基本可行解，为判别其是否为最优解，需求出起检验数以判别是否均为非负。确定检验 数的方法有多种，下面介绍的方法称为位势法。 首先考虑标准形式的线性规划问题LP): min{cx|Ak=b,x≥0} 设B=(Pg,…,Pg)是其可行基，Ca=(Cg,,C)'是基向量对应的目标向量，则检验数 )=C,-cB-p,=C,-wp,其中w=cB称为关于B的对偶基解，即wB=c,也即w是方程 wpg=Cg,i=l…,m (2.2.1)） 的唯一解。根据(22.1)得到w后就可求出检验数r,=C,-wP,· 现在具体到问题(2.1.2)。由于(2.1.2)中有一个等式约束是多余的，故去掉(2.1.2)的第1个方程。设 XX,…,是关于可行基B=(P,P5,P)的基变量，其中卫为P,取掉第1个元素后得到的 向量，w=(,…,4,,,了为(4.12)关于B的对偶基解，则由(22.1)知wp=Ck=1…,r,即
7 x21 2 1 1 = = == min{ , } min{4,3} 3 ab b 在格子(2,1)处填入 3，并且 11 x = 0 (不用填)，划去第 1 列， 2 2 a a ′ = − =3 1。 对表中余下部分重新求出各行差额写在最后一列。从差额最大的第 1 行中运价最小 c13 对应的变量 x13 开始考虑： x13 1 3 3 = = == min{ , } min{7,5} 5 ab b 在格子(1,3)处填入 5，并且 23 x = 0 (不用填)，划去第 3 列， 1 1 a a ′ = − = 5 2 。 现在还剩下最后一列的第一、二个格子，从运价最小 c24 对应的变量 x24开始考虑： x24 2 4 2 = = == min{ , } min{1,3} 1 ab a ′ ′ ′ 在格子(2,4)处填入 1，划去第 2 行， 4 4 b b ′′ ′ = −=1 2 。 现在还剩下最后一列的第一个格子，考虑变量 x14： x ab 14 1 4 = == min{ , } min{2,2} 2 ′ ′′ 在格子(1,4)处填入 2，划去第 1 行和第 4 列。至此，得到了如下运输方案。 B1 B2 B3 B4 ai 行差额 A1 3 11 3 5 10 2 7 2 0 7 A2 1 3 9 2 8 1 4 1 1 7 A3 7 4 6 10 5 3 9 3 1 2 bj 3 6 5 6 3 2 20 列差额 2 5 1 3 2 表 2.2.3 由伏格尔法确定的例 2.2.1 的初始方案 2．2．2 检验数的求法 对于已知的基本可行解，为判别其是否为最优解，需求出起检验数以判别是否均为非负。确定检验 数的方法有多种，下面介绍的方法称为位势法。 首先考虑标准形式的线性规划问题(LP)： min{ | , 0} T cx x bx A = ≥ 设 1 ( ,, ) B Bm B = p p " 是其可行基， 1 (,, ) m T BB B c = c c " 是基向量对应的目标向量，则检验数 T T 1 j jB j j j rc B c − =− =− c p wp ，其中 T T 1 B B− w c = 称为关于 B 的对偶基解，即 T T w c B = B ，也即 w 是方程 , 1, , i i T B B w p = = ci m " (2.2.1) 的唯一解。根据(2.2.1)得到 w 后就可求出检验数 T jj j r c = − w p 。 现在具体到问题(2.1.2)。由于(2.1.2)中有一个等式约束是多余的，故去掉(2.1.2)的第 1 个方程。设 11 2 2 , ,, r r ij i j ij x x x " 是关于可行基 11 2 2 ( , ,, ) r r B ij i j ij = pp p ′′ ′ " 的基变量，其中 ij p′ 为 ij p 取掉第 1 个元素后得到的 向量， 2 1 (, , ,, , )T m n w = u uv v " " 为(4.1.2)关于 B 的对偶基解，则由(2.2.1)知 , 1, , kk kk T ij ij w p′ = = ck r " ，即