《运筹学》课程教学讲义（Operations Research）第五章（5.4）算法步骤

运筹学讲义 §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 . 解：作运输表，并利用最小元素法解之

运筹学讲义 A1234a 1|0 420 0 0001 (TP)的一个基本格子集为Δ={1214,l23,l24,l31234},相应的基本可行解为 5,x3=0,其它x=0 求位势和检验数: p=mn(1120.4.-8,1,9}=-8=n2 求△∪{tn}中的一条闭回路④,并划分为④和④ 修正:6=mn{15,10}=10=x2

运 筹 学 讲 义 2  (TP) 的一个基本格子集为 { , , , , , } 12 14 23 24 31 34  = t t t t t t ，相应的 基本可行解为 x12 =15, x14 = 0, x23 =15, x24 =10, x31 = 5, x34 = 0 ，其它 xij = 0 . 求位势和检验数： 8 22 r min{11,20,4, 8,1,9} r pq = − = − = . 求 { } pq   t 中的一条闭回路 ，并划分为 和 : 修正： 10 24  = min{15,10} = = x

运筹学讲义 1234 15 5 b,5|151510 求检验数: 1416 rp=mn{11212ly=1>0, (TP)的最优解为x12=5,x14=10,x2=10,x23=15,x31=5,x14=0,其它x=0,最优值 为6×5+11×10+7×10+9×15+6×5+18×0=375.I Ex求解运输问题(P):m=3,n=4,d=(74.9,3656),c=1928 74105 解:最优解为x1=0,x12=2,x2=2,x23=1x31=9,x3=12,其它x=0,最优值为85.l

运 筹 学 讲 义 3 求检验数： rpq = min{11,12,12,8,1,1} = 1  0 ，  (TP) 的最优解为 x12 = 5, x14 =10, x22 =10, x23 =15, x31 = 5, x34 = 0 ，其它 xij = 0 ，最优值 为 65+1110+ 710+915+ 65+180 = 375.▍ Ex.求解运输问题 (TP) ： m = 3,n = 4 ， T d = (7,4,9,3,6,5,6) ，           = 7 4 10 5 1 9 2 8 3 11 3 10 c . 解：最优解为 x11 = 0, x12 = 2, x22 = 2, x23 =1, x31 = 9, x33 =12 ，其它 xij = 0 ，最优值为 85 .▍