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 开始考虑：