§2.2表上作业法 2.2.1初始方案的求法 下面介绍平衡运输问题(2.12)的初始基本可行解即初始方案的两种确定方法。 1.最小元素法 最小元素法采用运价低的点优先考虑的思想确定方案。下面以具体例子说明最小元素法的步骤。 例2.2.1设有运输表如表2.1.2，用最小元素法确定其初始方案（写在中间）。 解：从表中运价最小c21对应的变量x2!开始考虑： 1=min{a2,b,}=min{4,3}=3=b 在格子(2,1)处填入3，并且x1=x1=0(不用填)，划去第1列，4=a2-3=1。 从表中余下部分运价最小c23对应的变量x23开始考虑： x23 min (a2,b)=min(1,5)=1=a 在格子(2,3)处填入1，并且x21=x24=0(不用填)，划去第2行，=b-1=4。 从表中余下部分运价最小C13对应的变量x13开始考虑： xi3 =min(a,b)min(7,4)=4=b 在格子(1,3)处填入4，并且x3=0(不用填)，划去第3列，4=4-4=3。 从表中余下部分运价最小c2对应的变量x32开始考虑： 2=min{a3,b2}=min9,6}=6=b2 在格子(3,2)处填入6，并且x2=0(不用填)，划去第2列，4=4-6=3。 从表中余下部分运价最小c4对应的变量x34开始考虑： x mina,b)=min(3,6)=3=a 在格子(3,4)处填入3，划去第3行，b=b,-3=3。 从表中余下部分运价最小c14对应的变量x14开始考虑： x=min(a,b)min(3,3)=3 在格子(1,4)处填入3，划去第1行和第4列。至此，得到了如下运输方案。 B2 B3 Ba ai 3 11 3 10 A 4 久 9 8 3 1 年 7 4 10 5 A3 6 3 9 b 6 B 20 表2.2.1由最小元素法确定的例2.2.1的初始方案 我们称填了数字的格子为数学格，未填数学的格子为空格。 例2.2.2用最小元素法确定如下运输问题的初始方案。5 §2．2 表上作业法 2．2．1 初始方案的求法 下面介绍平衡运输问题(2.1.2)的初始基本可行解即初始方案的两种确定方法。 1．最小元素法 最小元素法采用运价低的点优先考虑的思想确定方案。下面以具体例子说明最小元素法的步骤。 例 2.2.1 设有运输表如表 2.1.2，用最小元素法确定其初始方案(写在中间)。 解：从表中运价最小 c21对应的变量 x21 开始考虑： x21 2 1 1 = = == min{ , } min{4,3} 3 ab b 在格子(2,1)处填入 3，并且 11 31 x x = = 0 (不用填)，划去第 1 列， 2 2 a a ′ = − =3 1。 从表中余下部分运价最小 c23 对应的变量 x23 开始考虑： x23 2 3 2 = = == min{ , } min{1,5} 1 ab a ′ ′ 在格子(2,3)处填入 1，并且 21 24 x x = = 0 (不用填)，划去第 2 行， 3 3 b b ′ = − =1 4 。 从表中余下部分运价最小 c13 对应的变量 x13 开始考虑： x13 1 3 3 = = == min{ , } min{7,4} 4 ab b ′ ′ 在格子(1,3)处填入 4，并且 33 x = 0 (不用填)，划去第 3 列， 1 1 a a ′ = − = 4 3 。 从表中余下部分运价最小 c32 对应的变量 x32 开始考虑： x32 3 2 2 = = == min{ , } min{9,6} 6 ab b 在格子(3,2)处填入 6，并且 12 x = 0 (不用填)，划去第 2 列， 3 3 a a ′ = − = 6 3。 从表中余下部分运价最小 c34 对应的变量 x34 开始考虑： x34 3 4 3 = = == min{ , } min{3,6} 3 ab a ′ ′ 在格子(3,4)处填入 3，划去第 3 行， 4 4 b b ′ = −=3 3 。 从表中余下部分运价最小 c14 对应的变量 x14 开始考虑： x ab 14 1 4 = min{ , } min{3,3} 3 ′ ′ = = 在格子(1,4)处填入 3，划去第 1 行和第 4 列。至此，得到了如下运输方案。 B1 B2 B3 B4 ai A1 3 11 3 4 10 3 7 3 A2 1 3 9 2 1 8 4 1 A3 7 4 6 10 5 3 9 3 bj 3 6 5 4 6 3 20 表 2.2.1 由最小元素法确定的例 2.2.1 的初始方案 我们称填了数字的格子为数学格，未填数学的格子为空格。 例 2.2.2 用最小元素法确定如下运输问题的初始方案