运筹学讲义 §5.3最优性的检验 预备知识 对标准形线性规划问题 max 2=c x (LP) s.t. Ax=b 其对偶问题为 (DP):mn f=b'y st.Ay≥c (LP)的一个基B,作(LP)关于基B的单纯形表 B X xBI B-IN Blb z0 BN-xcEB-1b 则(LP)关于基B的对偶解为j=(cBB-),检验数为r=(r},r),其中 x为基变量 軎亚清非x3-d1=-dg=4“-N-2=0= 又y2c台yA2c7y(B.N)2=(c,c)(yB,yN)≥(c2c) B≥c {N2c→y3B2c→y2cB=y≥(cB-) 将(DP)的约束条件Ay≥C中基变量对应的不等式改为等式,即令Ay=C(x为基变量), 即得(LP关于基B的对偶解p=(cB-) 由对偶理论知,对运输问题
运 筹 学 讲 义 1 §5.3 最优性的检验 预备知识： 对标准形线性规划问题 = = 0 . . max ( ) : x st Ax b z c x LP T 其对偶问题为 = st A y c f b y DP T T . . min ( ) : (LP) 的一个基 B ，作 (LP) 关于基 B 的单纯形表 则 (LP) 关于基 B 的 对偶解为 T T y (cB B ) −1 = ， 检 验 数 为 ( , ) T N T B r = r r , 其 中 T N T B T N T B r = r = c B N − c −1 0, ，即 − = − = − 为非基变量 为基变量 j j j T j j T B j j c B P c y P c x x r , 0, 1 . 又 ( , ) ( , ) ( , ) ( , ) T N T B T T T N T B T N T T T T B c c y B y N c c c c A y c y A c y B N = T T B T B T T B T T N T T B T y B c y c B y c B y N c y B c ( ) −1 −1 ， 将 (DP) 的约束条件 A y c T 中基变量对应的不等式改为等式，即令 A y c T = （ j x 为基变量）， 即得 (LP) 关于基 B 的对偶解 T T y (cB B ) −1 = . 由对偶理论知，对运输问题
运筹学讲义 min max ∑x,=a1,l=12 st x=a1,l=1, ∑x=b,j=12,… ∑x=b,/=12…n x120,l=12,…,mj=12…,n > 1.2 引入对偶变量y,,=12,…,m;j=1,2,…n,得对偶问题为 8=>aiy ∑ y ming=-∑a-∑b 1,2,…,m;j=1,2,… v(TP)的一个基本格子集△,由§5.2知,从D4={P1tn∈A中去掉一个多余的行即得(P) 的一个基B,且(TP)关于基B的单纯形表为 b 则(TP)关于基B的对偶解为y=(cB-),检验数为r=(rl,r),其中 t.∈A r=0,r=c-cBBN,即r= c-cBP,tg△ 由预备知识知,将(P)的对偶问题的约束条件v1+v≤c,=1,2,…,m;j=1,2,…,n中的 n∈△的不等式改为等式,即令+v=cn(tn∈△),即得(TP)关于基B的对偶解j=(cB-)
运 筹 学 讲 义 2 = = = = = = = − = = = = = = = = = = = = = = = x i m j n x b j n st x a i m f c x x i m j n x b j n st x a i m z c x TP i j m i i j j i n j i j m i n j i j i j i j m i i j j i n j i j m i n j i j i j 0, 1,2, , ; 1,2, , , 1,2, , . . , 1,2, , max 0, 1,2, , ; 1,2, , , 1,2, , . . , 1,2, , min ( ) : 1 1 1 1 1 1 1 1 引入对偶变量 yi ,zj ,i = 1,2, ,m; j = 1,2, ,n ，得对偶问题为 + = = = − − + − = = = + = = =− =− = = st u v c i m j n g a u b v st y z c i m j n g a y b z i j ij n j j j m i i i v z u y i j ij n j j j m i i i j j i i . . , 1,2, , ; 1,2, , min . . , 1,2, , ; 1,2, , min 1 1 0 0 1 1 (TP) 的一个基本格子集 ，由§5.2 知，从 = { | } ij ij D P t 中去掉一个多余的行即得 (TP) 的一个基 B ，且 (TP) 关于基 B 的单纯形表为 则 (TP) 关于基 B 的 对偶解为 T T y (cB B ) −1 = ，检验数为 ( , ) T N T B r = r r , 其 中 r r c c B N T B T N T N T B 1 0, − = = − ，即 − = − ij ij T ij B ij ij c c B P t t r , 0, 1 . 由预备知识知，将 (TP) 的对偶问题的约束条件 ui + v j cij ,i = 1,2, ,m; j = 1,2, ,n 中的 t ij 的不等式改为等式，即令 + = ( ) i j ij ij u v c t ，即得 (TP) 关于基 B 的对偶解 T T y (cB B ) −1 =
运筹学讲义 v是自由变量,∴可令u1=0,解 1=0 .+v.=C..t.∈△ 得(TP)关于基B的对偶解 u=(u1u2…,un)2,v=(v1,v2,…,vn) n/=F=(2)y 定义称为(P)关于基本格子集△的位势( potential,) 由此,得(TP)关于基B的检验数为 =0,1∈△ iB-P y P lmn,V1,v2,…,V g△ 小结:求(TP)关于基B的检验数 先求位势:4=0 u. v t∈△ △ 再求检验数:=1cn--V列g△ 图示
运 筹 学 讲 义 3 i j u , v 是自由变量， 可令 u1 = 0 ，解 + = = i j ij ij u v c t u , 1 0 得 (TP) 关于基 B 的对偶解 T u u u um ( , , , ) = 1 2 ， T m v (v ,v , ,v ) = 1 2 ，即 T T y cB B v u ( ) −1 = = . 定义 称 v u 为 (TP) 关于基本格子集 的位势（potential）. 由此，得 (TP) 关于基 B 的检验数为 rij = 0,t ij ； = − − = − = − = − = − = − − i j m n i j i j i j i j T T i j i j T i j i j T i j i j T i j i j B c u v t j i c u u u v v v P c u v P v u r c c B P c y P c , 0 0 1 0 0 1 0 0 ( , , , , , , , ) ( , ) 1 2 1 2 1 小结：求 (TP) 关于基 B 的检验数 先求位势： + = = i j ij ij u v c t u , 1 0 再求检验数： − − = ij i j ij ij ij c u v t t r , 0, 图示：
运筹学讲义 =c-2 (∈A) 例1设(TP)中,m=3,n=4,d=(15,25.5151510),c=127920,试求(TP) 6141618 的一个基本可行解和相应的检验数 解:利用最小元素法求解 ④02510 0 8001Q (TP)的一个基本格子集为Δ={t1,l12,14,23,124,431},相应的基本可行解为 0,x12=15,x4=0,x23=15,x24=10,x31=5,其它xn=0 求位势: E10|601 9 求检验数
运 筹 学 讲 义 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 ，试求 (TP) 的一个基本可行解和相应的检验数. 解：利用最小元素法求解： (TP) 的一个基本格子集为 { , , , , , } 11 12 14 23 24 31 = t t t t t t ， 相应的 基 本 可 行 解 为 x11 = 0, x12 =15, x14 = 0, x23 =15, x24 =10, x31 = 5 ，其它 xij = 0 . 求位势： 求检验数：
运筹学讲义 106011 注:显然,将求位势和求检验数的计算可在同一张运输表上进行 同单纯形法一样,在运输表中,当求得(TP)的一个初始基本可行解和相应的检验数后,若所有 检验数均非负,则当前的基本可行解即为最优解;否则,应改进之(转轴),以使之更优 定义设①,若可将①中的诸格子排列为、1,LD,…,1,其中12…4互 异,j,2…,互异,则称是一个闭回路 闭回路的特点:任意两个相邻的格子的行指标相同时,其列指标必不相同:;列指标相同时,其行 指标必不相同.即任意两个相邻格子的行(列)指标不能同时相同,也不能同时不同 如对格子集T={tn|=12,3;j=1,2,34.5},令={14,15,12,l2,1214} 易见,可将④中的诸格子排列为1,41,13,12,12,1,ln,:①是一个闭回路 显然,闭回路在格子表的同一行(列)上均恰有两个格子 Lema设△是(TP)的一个基本格子集,tg△,则△∪{}中必存在唯一一个闭回路④,且 证明:从Δ∪{tmx}中递归地删去孤立格子,即得一个闭回路l 例1(续)求一个闭回路 解:△={1,2,t14,123,l24,131}
运 筹 学 讲 义 5 .▍ 注：显然，将求位势和求检验数的计算可在同一张运输表上进行. 同单纯形法一样，在运输表中，当求得 (TP) 的一个初始基本可行解和相应的检验数后，若所有 检验数均非负，则当前的基本可行解即为最优解；否则，应改进之（转轴），以使之更优. 定义 设 T ，若可将 中的诸格子排列为 1 1 1 2 2 2 2 3 1 , , , , , , i j i j i j i j i j i j k k k t t t t t t ，其中 k i ,i , ,i 1 2 互 异， k j , j , , j 1 2 互异，则称 是一个闭回路. 闭回路的特点：任意两个相邻的格子的行指标相同时，其列指标必不相同；列指标相同时，其行 指标必不相同.即任意两个相邻格子的行（列）指标不能同时相同，也不能同时不同. 如对格子集 T = {t | i = 1,2,3; j = 1,2,3,4,5} ij ，令 { , , , , , } 14 15 22 25 32 34 = t t t t t t . 易见，可将 中的诸格子排列为 14 15 25 22 32 34 14 t ,t ,t ,t ,t ,t ,t ， 是一个闭回路. 显然，闭回路在格子表的同一行（列）上均恰有两个格子. Lemma 设 是 (TP) 的一个基本格子集， t pq ，则 { } pq t 中必存在唯一一个闭回路 ，且 t pq . 证明：从 { } pq t 中递归地删去孤立格子，即得一个闭回路.▍ 例 1（续）求一个闭回路. 解： { , , , , , } 11 12 14 23 24 31 = t t t t t t
运筹学讲义 若取t四=t3,则从△U{n}中删去孤立格子12,即得一个闭回路 ={t1,t14,t24,t23,tmn,lt1,t1} 显然,四e 若取lm=l2,则从A∪{p}中递归地删去孤立格子12y124,414,即得一个闭回路 {t1,12,tm,131} 显然,t 其它情况略同. Th1设(TP)的一个基本格子集为△,相应的基本可行解为x tg△,△Utn}中的闭回路为④按如下规则将④划分为和④ t∈⑥:④的处在同一行、列的两个格子应分属①和④ 令 8=mn( xi It △=(△U})1{k}
运 筹 学 讲 义 6 若 取 33 t t pq = ，则从 { } pq t 中 删 去 孤 立 格 子 12 t ， 即 得 一 个 闭 回 路 { , , , , , , } 11 14 24 23 31 11 t t t t t t t = pq . 显然， t pq . 若 取 32 t t pq = ，则从 { } pq t 中 递 归 地 删 去 孤 立 格 子 23 24 14 t ,t ,t ， 即 得 一 个 闭 回路 { , , , } 11 12 31 t t t t = pq . 显然， t pq . 其它情况略同.▍ Th1 设 (TP) 的一个基本格子集为 ，相应的基本可行解为 x . t pq , { } pq t 中的闭回路为 .按如下规则将 划分为 和 : t pq ； 的处在同一行、列的两个格子应分属 和 . 令 = min{ xij | t ij rk x }= ， ( { }) \ { } pq rk = t t
运筹学讲义 +, 日 则Δ'仍是(TP的一个基本格子集,且x是相应的基本可行解■ 注:(1)mhl描述的是类似于单纯形法的转轴过程的运输问题的转轴过程:xm由非基变量变为 基变量,x/由基变量变为非基变量 (2)转轴后,新进入基本格子集的格子tn对应的基变量x的值为xn=0+6=6 例1(续)解:Δ={t1,12,14,123,l24,l31} 取tn=12,则△∪{m}中的一个闭回路为④ 将④划分为和④ 6=mn{15,5}=5=x31 修正 7
运 筹 学 讲 义 7 则 仍是 (TP) 的一个基本格子集，且 x 是相应的基本可行解.▍ 注：（1）Th1 描述的是类似于单纯形法的转轴过程的运输问题的转轴过程： pq x 由非基变量变为 基变量， rk x 由基变量变为非基变量. （2）转轴后，新进入基本格子集的格子 pq t 对应的基变量 pq x 的值为 x pq = 0 + = . 例 1（续）解： { , , , , , } 11 12 14 23 24 31 = t t t t t t . 取 32 t t pq = ，则 { } pq t 中的一个闭回路为 ： 将 划分为 和 : 5 31 = min{15,5} = = x . 修正： ▍