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 " ，即