运筹学讲义 3.重复1,2,直至所有行、列均被删去,则得(TP)的一个基本格子集为△={m|xm被圈起}, 相应的基本可行解为x=10,其它 注:(1)在利用最小元素法得到的最终的运输表中,被圈起的元素为基变量的值,画×的元素为 非基变量的值,且被圈起的元素的个数必恰为m+n-1 (2)最小元素法和西北角法的唯一区别在于:(算法的步骤1)是否以单位运费为安排运输业务 的依据 Th2利用最小元素法必可求得(TP)的一个基本可行解x 1062011 例2设(TP)中,m=3,n=4,d=(15,2555151510),c=127920,试利用 最小元素法求(TP)的一个基本可行解 解: 234a2 ①5间⑩250 5|0 b,5151510 8001Q (TP)的一个基本格子集为△={t112,14,23,24,t31} 故从B=(P12P2B4,P23,P24,B31)中去掉一个多余的行,即得(TP)的一个基B,相应的基本可 行解为x1=0,x12=15,x14=0,x2=15,x24=10,x31=5,其它x=0 西北角法和最小元素法的优劣比较 最小元素法优先安排单位运费最小的发点与收点之间的运输业务 一般地,利用最小元素法求得的基本可行解常优于(目标函数值较小)利用西北角法求得的基 本可行解.故以后常用最小元素法求(TP)的一个初始基本可行解运 筹 学 讲 义 4 3.重复 1，2，直至所有行、列均被删去，则得 (TP) 的一个基本格子集为 pq pq  = {t | x 被圈起 } ， 相应的基本可行解为      = 0, 其它 , pq pq ij x t x . 注：（1）在利用最小元素法得到的最终的运输表中，被圈起的元素为基变量的值，画  的元素为 非基变量的值，且被圈起的元素的个数必恰为 m+ n −1. （2）最小元素法和西北角法的唯一区别在于：（算法的步骤 1）是否以单位运费为安排运输业务 的依据. Th2 利用最小元素法必可求得 (TP) 的一个基本可行解 x .▍ 例 2 设 (TP) 中， m = 3,n = 4 ， T d = (15,25,5,5,15,15,10) ，           = 6 14 16 18 12 7 9 20 10 6 20 11 c ，试利用 最小元素法求 (TP) 的一个基本可行解. 解：  (TP) 的一个基本格子集为 { , , , , , } 11 12 14 23 24 31  = t t t t t t . 故从 ( , , , , , ) B = P11 P12 P14 P23 P24 P31 中去掉一个多余的行，即得 (TP) 的一个基 B ，相应的基本可 行解为 x11 = 0, x12 =15, x14 = 0, x23 =15, x24 =10, x31 = 5 ，其它 xij = 0 .▍ 西北角法和最小元素法的优劣比较  最小元素法优先安排单位运费最小的发点与收点之间的运输业务，  一般地，利用最小元素法求得的基本可行解常优于（目标函数值较小）利用西北角法求得的基 本可行解.故以后常用最小元素法求 (TP) 的一个初始基本可行解