运筹学讲义 当b=0时,删去第q列,并在格子t(≠P,=12…,m)内画x 当an=bq=0时,删去第P行(或第q列),并在格子tm(≠q=12…,m)(或 t2(≠P,=12,…m)内画x 3.重复1,2,直至所有行、列均被删去,则得(TP)的一个基本格子集为A={tm|xm被圈起}, 相应的基本可行解为x=∈A 0,其它 注:(1)在利用西北角法得到的最终的运输表中,被圈起的元素为基变量的值,画×的元素为非 基变量的值:而且,被圈起的元素的个数必恰为m+n-1.这是因为:被圈起的元素的个数=基变量 的个数=基B中的列向量的个数=r(D)=m+n-1. (2)西北角法仅用到(TP)的供应量和需求量d,并不涉及单位运费 Th利用西北角法必可求得(TP)的一个基本可行解x 证明:由算法步骤知,Δ是一个孤立格子集,且|△=m+n-1 故由§5.2命题知,Δ必是一个基本格子集 于是,从D4={P1∈A中去掉一个多余的行,即得(TP)的一个基B,相应的基本可行解为 x=(.其它 例1设(TP)中,m=3,n=4,d=(15,25,5,5,151510),试利用西北角法求(TP)的一个基本 可行解 解:运 筹 学 讲 义 2 当 bq = 0 时，删去第 q 列，并在格子 t (i p,i 1,2, ,m) iq  =  内画  ； 当 ap = bq = 0 时，删 去 第 p 行（或第 q 列 ）， 并 在 格 子 t ( j q, j 1,2, ,n) pj  =  （ 或 t (i p,i 1,2, ,m) iq  =  ）内画  . 3.重复 1，2，直至所有行、列均被删去，则得 (TP) 的一个基本格子集为 pq pq  = {t | x 被圈起 } ， 相应的基本可行解为      = 0, 其它 , pq pq ij x t x . 注：（1）在利用西北角法得到的最终的运输表中，被圈起的元素为基变量的值，画  的元素为非 基变量的值；而且，被圈起的元素的个数必恰为 m+ n −1.这是因为：被圈起的元素的个数=基变量 的个数=基 B 中的列向量的个数= r(D) = m+ n −1. （2）西北角法仅用到 (TP) 的供应量和需求量 d ，并不涉及单位运费. Th1 利用西北角法必可求得 (TP) 的一个基本可行解 x . 证明：由算法步骤知，  是一个孤立格子集，且 |  |= m + n −1. 故由§5.2 命题知，  必是一个基本格子集. 于是，从 = { |  }  ij ij D P t 中去掉一个多余的行，即得 (TP) 的一个基 B ，相应的基本可行解为      = 0, 其它 , pq pq ij x t x .▍ 例 1 设 (TP) 中， m = 3,n = 4 ， T d = (15,25,5,5,15,15,10) ，试利用西北角法求 (TP) 的一个基本 可行解. 解：