运筹学讲义 1234 15100 b5151 (TP)的一个基本格子集为△={t1212,123,24,x4} 故从B=(P1,P12,P2,P23,P24,P4)中去掉一个多余的行,即得(TP)的一个基B,相应的基本可 行解为x1=5,x12=10,x2=5,x23=15,x24=5,x34=5,其它x=0 注:当最后仅剩下一个格子时,不能画x,只能填数圈起,以使得被圈起的元素的个数(基变量 的个数)为m+n-1 最小元素法 基本思想:优先安排运输表中的单位运费最小的格子对应的发点与收点之间的运输业务(当最小 单位运费不唯一时,可任选其一) 使用条件:已知c,d 步骤 1.令cp=mmcn},x四=mmn{ap,b} 将x,填入格子tn中,并圈起 2.令an:=日n一x四,b:=b-xp 当an=0时,删去第P行,并在格子1(≠qJ=12,…,n)内画x 当b=0时,删去第q列,并在格子l(≠p,=1,2,…,m)内画x 当an=b=0时,删去第p行(或第q列),并在格子tn(≠q,j=12,…,n)(或 t(≠p,l=12,…,m))内画x运 筹 学 讲 义 3  (TP) 的一个基本格子集为 { , , , , , } 11 12 22 23 24 34  = t t t t t t . 故从 ( , , , , , ) B = P11 P12 P22 P23 P24 P34 中去掉一个多余的行，即得 (TP) 的一个基 B ，相应的基本可 行解为 x11 = 5, x12 =10, x22 = 5, x23 =15, x24 = 5, x34 = 5 ，其它 xij = 0 .▍ 注：当最后仅剩下一个格子时，不能画  ，只能填数圈起，以使得被圈起的元素的个数（基变量 的个数）为 m+ n −1. 二 最小元素法 基本思想：优先安排运输表中的单位运费最小的格子对应的发点与收点之间的运输业务（当最小 单位运费不唯一时，可任选其一）. 使用条件：已知 c, d . 步骤： 1.令 min { } 1 1 ij j n i m pq c c     = , min{ , } pq ap bq x = . 将 pq x 填入格子 pq t 中，并圈起. 2.令 p p pq a := a − x ， q q pq b : = b − x . 当 a p = 0 时，删去第 p 行，并在格子 t ( j q, j 1,2, ,n) pj  =  内画  ； 当 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  =  ）内画 