运筹学讲义 §5.2初始基本可行解 本节来介绍求(TP)的一个初始基本可行解的两种方法:西北角法和最小元素法 如§5.1所言,运输问题的求解过程并不象一般线性规划问题一样借助于单纯形表,而是借助于 运输表来实现:但其算法在理论基础、基本思想、算法步骤(包括初始基本可行解的选取、最优性的 验证、转轴)等各方面都和单纯形法是一致的 供需平衡型运输问题的运输表: ∑b C2 3, b1 b2 运输表实际上是运输问题的单纯形表 西北角法 基本思想:优先安排运输表中的西北角处的格子(即编号小的格子)对应的发点与收点之间的运 输业务. 使用条件:已知d 北 水 步骤 1.令西北角格子tm对应的变量xp的值为xm=mman,b}.将x四填入格子lp中,并圈起 2.令 ba:=ba 当ap=0时,删去第P行,并在格子lm(≠qj=12,…,m)内画x
运 筹 学 讲 义 1 §5.2 初始基本可行解 本节来介绍求 (TP) 的一个初始基本可行解的两种方法：西北角法和最小元素法. 如§5.1 所言，运输问题的求解过程并不象一般线性规划问题一样借助于单纯形表，而是借助于 运输表来实现；但其算法在理论基础、基本思想、算法步骤（包括初始基本可行解的选取、最优性的 验证、转轴）等各方面都和单纯形法是一致的. 供需平衡型运输问题的运输表： = = = n j j m i ai b 1 1 运输表实际上是运输问题的单纯形表. 一.西北角法 基本思想：优先安排运输表中的西北角处的格子（即编号小的格子）对应的发点与收点之间的运 输业务. 使用条件：已知 d . 步骤： 1.令西北角格子 pq t 对应的变量 pq x 的值为 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 = 内画 ；
运筹学讲义 当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) 的一个基本 可行解. 解：
运筹学讲义 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 = ）内画
运筹学讲义 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) 的一个初始基本可行解