P66： 8.某部门有3个生产同类产品的工厂（产地），生产的产品由4个销售点出售，各工厂A 1， A 2，A 3的生产量、各销售点B 1，B 2，B 3，B 4的销售量（假定单位为t ）以及各工厂到销售点的单位运价（元/t ）示于下表中，问如何调运才能使总运费最小？表解：一、该运输问题的数学模型为：可以证明：约束矩阵的秩为r (A) = 6. 从而基变量的个数为 6.34333231242322213141141312116115893102114124min x x x x x x x x x x x x x c z i j ij ij +++++++++++==∑∑==⎪⎪⎪⎪⎪⎩⎪⎪⎪⎪⎪⎨⎧==≥=++=++=++=++=+++=+++=+++4,3,2,1;3,2,1,01412148221016342414332313322212312111343332312423222114131211j i x x x x x x x x x x x x x x x x x x x x x x x x x ij 111213142122232431323334x x x x x x x x x x x x 712111111111111111111111111⨯⎛⎫ ⎪⎪⎪ ⎪⎪⎪ ⎪⎪ ⎪⎝⎭二、给出运输问题的初始可行解（初始调运方案）1. 最小元素法思想：优先满足运价（或运距）最小的供销业务。

其余（非基）变量全等于零。

此解满足所有约束条件，且基变量（非零变量）的个数为6（等于m+n-1=3+4-1=6).总运费为（目标函数值） ,1013=x ,821=x ,223=x ,1432=x ,834=x ,614=x ∑∑===3141i j ijij x c Z2. 伏格尔（Vogel)法伏格尔法的基本思想：运输表中各行各列的最小运价与次小运价之差值（罚数）应尽可能地小。

或者说：优先供应罚数最大行（或列）中最小运费的方格，以避免将运量分配到该行（或该列）次小运距的方格中。

246685143228116410=⨯+⨯+⨯+⨯+⨯+⨯=131421243234其余（非基）变量全等于零。

此解满足所有约束条件，且基变量（非零变量）的个数为6（等于m+n-1=3+4-1=6)。

总运费为（目标函数值）： ∑∑===3141i j ij ij x c Z 244685149228114412=⨯+⨯+⨯+⨯+⨯+⨯=三、解的最优性检验⒈ 闭回路法（以下的闭回路都是顺时针方向）看非基变量的检验数是否满足：（1）首先对用最小元素法所确定的初始基本可行解进行检验。

参见前面的计算结果，可知非基变量分别为：x 11，x 12，x 22，x 24，x 31，x 33。

σ11 = C 11 + C 23 - (C 13 + C 21) = 4 + 3 –( 4 + 2 ) =1σ12 = C 12 + C 34 - (C 14 + C 32) = 12 + 6 –( 11 + 5 ) =2σ22= C 22 + C 13 + C 34 - (C 23 + C 14 + C 32) = 10 + 4 + 6 – ( 3 + 11 + 5 ) = 20 – 19 =1.0≥ij σσ24 = C24 + C13 - (C14 + C23) = 9 + 4 –( 11 + 3 ) = -1σ31= C31 + C14 + C23 - (C34 + C13 + C21) = 8 + 11 + 3 – ( 6 + 4 + 2 ) = 22 – 12 = 10σ33 = C33 + C14 - (C13 + C34) = 11 + 11 –( 4 + 6 ) =12由于σ24 = C24 + C13 - (C14 + C23) = 9 + 4 –( 11 + 3 ) = -1 < 0，所以当前方案不是最优方案。

（2）然后对用伏格尔法所确定的初始基本可行解进行检验。

参见前面的计算结果，可知非= C23 + C14 - (C13 + C24) = 3 + 11– ( 4 + 9 ) = 14-13=123= C33 + C14 - (C13 + C34) = 11 + 11– ( 4 + 6 ) = 22-10 = 1233由于所有非基变量的检验数都大于零，说明当前方案是最优方案，最优解为：x11=12，x14=4，x21=8，x24=2，x32=14，x34=8。

2位势法（1）首先对用最小元素法所确定的初始基本可行解进行检验。

参见前面的计算结果，可知基变量分别为：x构造方程组：+ v3 = c13 = 4uu1 + v4 = c14 = 11u2 + v1 = c21 = 2u2 + v3 = c23 = 3u3 + v2 = c32 = 5u3 + v4 = c34 = 6令自由变量u1 = 0 ，将其代入方程组，得：u1 = 0，v3 = 4，v4 = 11，u3 = -5，v2 = 10，u2 = -1，v1 = 3，将其代入非基变量检验数：σij=C ij - (u i+ v j)，得：σ11=C11 - (u1 + v1) = 4 – ( 0 + 3 ) = 1σ12=C12 - (u1 + v2) = 12 – ( 0 + 10 ) = 2σ22=C22 - (u2 + v2) = 10 – ( -1 + 10 ) = 1σ24=C24 - (u2 + v4) = 9 – ( -1 + 11 ) = -1σ31=C31 - (u3 + v1) = 8 – ( -5 + 3 ) = 10σ33=C33 - (u3 + v3) = 11 – ( -5 + 4 ) = 12与闭回路法计算的结果相同。

（2）然后对用伏格尔法所确定的初始基本可行解进行检验。

参见前面的计算结果，可知基变量分别为：x13，x14，x21，x24，x32，x34。

构造方程组：+ v3 = c13 = 4uu1 + v4 = c14 = 11u2 + v1 = c21 = 2u2 + v4 = c24 = 9u3 + v2 = c32 = 5u3 + v4 = c34 = 6令自由变量u1 = 0 ，将其代入方程组，得：u1 = 0，v3 = 4，v4 = 11，u3 = -5，v2 = 10，u2 = -2，v1 = 4，将其代入非基变量检验数：σij=C ij - (u i+ v j)，得：σ11=C11 - (u1 + v1) = 4 – ( 0 + 4 ) = 0σ12=C12 - (u1 + v2) = 12 – ( 0 + 10 ) = 2σ22=C22 - (u2 + v2) = 10 – ( -2 + 10 ) = 2σ23=C23 - (u2 + v3) = 3 – ( -2 + 4 ) = -1σ31=C31 - (u3 + v1) = 8 – ( -5 + 4 ) = 9σ33=C33 - (u3 + v3) = 11 – ( -5 + 4 ) = 12与闭回路法计算的结果相同。

四、解的改进（用闭回路法调整）在使用最小元素法求得的初始方案中，由于σ24<0，说明当前方案不是最优，需要改进或调整。

见表1中非基变量x 24所在的闭回路，调整量为ε = min{2,6} = 2。

调整过程见表2：调整后的结果如表3所示，此结果正好与使用伏格尔法求得的结果相同，因此最优性检验过程同前，由于非基变量的检验系数都大于等于零，因此该方案是最优方案，最优解为： x 13=12，x 14=4，x 21=8，x 24=2，x 32=14，x 34=8。

将最优解代入到目标函数中，得总运费为（目标函数值）：∑∑===3141max i j ij ij x c Z 244685149228114412=⨯+⨯+⨯+⨯+⨯+⨯=P66： 9.解：首先列出这一问题的产销平衡表，见表1。

表1一、该运输问题的数学模型为：可以证明：约束矩阵的秩为r (A) = 6. 从而基变量的个数为 6.二、给出运输问题的初始可行解（初始调运方案） 1. 最小元素法343332312423222131411413121151047829103113min x x x x x x x x x x x x x c z i j ij ij +++++++++++==∑∑==⎪⎪⎪⎪⎪⎩⎪⎪⎪⎪⎪⎨⎧==≥=++=++=++=++=+++=+++=+++4,3,2,1;3,2,1,06563947342414332313322212312111343332312423222114131211j i x x x x x x x x x x x x x x x x x x x x x x x x x ij 111213142122232431323334x x x x x x x x x x x x 712111111111111111111111111⨯⎛⎫ ⎪⎪⎪ ⎪⎪⎪ ⎪⎪ ⎪⎝⎭第1步，从表1中找出最小运价为1，表示应先将A2的产品供应B1。

在表中A2和B1的交叉格处填上3，得表2。

将表2中的B1列运价划去，得表3第2步，2 1 t物资供应B3。

得表4。

将表4的A2行运价划去，得表5第31B3。

得表6。

将表6的B3列运价划去，得表7。

第4步，在表7未划去的元素中再找出最小运价为4，确定A3的6 t物资供应B2。

得表8。

将表8的B2列运价划去，得表9。

第5步，在表9未划去的元素中再找出最小运价为5，确定A3的3 t物资供应B4。

得表10。

将表10的A3行运价划去，得表11。

第6步，在表11未划去的元素中再找出最小运价为10，确定A1的3 t物资供应B4。

得表12。

将表12的A3行运价划去，得表13。

在表13中，所有元素都被划去，说明在产销平衡表上已得到一个调运方案，即初始基可行解，x13 = 4, x14 = 3, x21 = 3,x23 = 1, x32 = 6, x34 = 5。

（基变量个数：3 + 4―1 = 6）基变量对应的运输量为零，非基变量对应的运输量为零。

运输费用为：Z = 3×4 + 10×3 +1×3 +2×1 +4×6 +5×3 = 12+30+3+2+24+15 = 862. 伏格尔（Vogel)法第1步：在表1中分别计算出各行、各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行，见表2。

表1表2第2步：从行或列差额中选出最大者，选择它所在行或列中的最小元素。

在表2中，可确定A3的产品应首先供应B2，得表3。

将单位运价表中的列的数字划去，得表4。