运筹学讲义 §5.4算法步骤 综合以上讨论,设计平衡型运输问题算法如下: 表上作业法 1.利用最小元素法求(TP)的一个初始基本格子集Δ及相应的初始基本可行解x 2求(TP)关于基B的检验数:{41+v1=Cn 令厂四=m{} 若rm20,则x即为(TP)的最优解 否则,求出△∪{1n}中的一条闭回路,并将④划分为④和B,转4 4修正:令O=mm(x1∈①}=x,A=(△U{m)N{ x8+日,g∈ e ty e ,转2 注:(1)本算法实际上是单纯形法在运输问题上的具体体现,它从算法的思想,步骤,设计到执 行都体现了单纯形法的思想.∴表上作业法实质上就是单纯形法,只不过前者是在运输表上进行,而 后者则是在单纯形表上进行 (2)算法的步骤4实际上对应于单纯形法的转轴过程 例1求解运输问题(P):m=3n=4,d=(1525515150),c=127920 6141618 解:作运输表,并利用最小元素法解之运 筹 学 讲 义 1 §5.4 算法步骤 综合以上讨论，设计平衡型运输问题算法如下： 表上作业法： 1.利用最小元素法求 (TP) 的一个初始基本格子集  及相应的初始基本可行解 x . 2.求 (TP) 关于基 B 的检验数：      = − −   + =   = ij ij i j ij i j ij ij r c u v t u v c t u , , 1 0 . 3.令 min { } 1 1 ij j n i m pq r r     = . 若 rpq  0 ，则 x 即为 (TP) 的最优解； 否则，求出 { } pq   t 中的一条闭回路 ，并将 划分为 和 ，转 4. 4.修正：令  = min{ xij | t ij  rk x  }= ， ( { }) \ { } pq rk  =   t t ， ，转 2. 注：（1）本算法实际上是单纯形法在运输问题上的具体体现，它从算法的思想，步骤，设计到执 行都体现了单纯形法的思想. 表上作业法实质上就是单纯形法，只不过前者是在运输表上进行，而 后者则是在单纯形表上进行. （2）算法的步骤 4 实际上对应于单纯形法的转轴过程. 例 1 求解运输问题 (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 . 解：作运输表，并利用最小元素法解之