§74改进单纯形法 改进单纯形法的基本思想 在单纯形法中,有很多运算是不必要的因为我们所 关心的只是下面数据: (1)各基变量的取值B1b=(d1,d2,…,dm) (2)非基变量列上的检验数=CB1PC (3)对应4>0的B1A中的一列B+P=(b1sb2, ,bms)T(其中为;>0中最大者或最先计算出的正 检验数
§7.4 改进单纯形法 一、改进单纯形法的基本思想 在单纯形法中,有很多运算是不必要的.因为我们所 关心的只是下面数据: (1) 各基变量的取值 B-1b = (d1 ,d2 , ···,dm) T. (2) 非基变量列上的检验数 λj = CBB-1Pj-Cj . (3) 对应 λs＞0 的 B-1A 中的一列 B-1Ps= (b1s , b2s , ···,bms) T ( 其中 λs 为λj ＞0 中最大者或最先计算出的正 检验数)
用(2)中数据,可作最优性判别.用(1)和(3)中数据 可确定主元素b以b为主元素进行换基迭代,就可 得新基B 当基B=(P1Pm,…,Pr-1,PP,…,Pm)变到新 基B=(Pn,P,…Pnr-1,P,Pm+,,Pm)时,B可从B1 得到.这是因为对T(B)中B14进行以bn为主元素 的换基迭代.得到T(B)中的BA就等于用初等矩阵
用(2)中数据,可作最优性判别. 用(1)和(3)中数据 可确定主元素 brs, 以 brs为主元素进行换基迭代, 就可 得新基 . 当基 B = (Pj1 ,Pj2 , ···,Pj,r－1 ,Pjr,Pj,r+1, ···,Pjm )变到新 基 = (Pj1 ,Pj2 , ···,Pj,r－1 ,Ps ,Pj,r+1, ···,Pjm )时, -1可从B-1 得到. 这是因为对 T(B) 中 B-1A 进行以 brs 为主元素 的换基迭代. 得到 T( ) 中的 A就等于用初等矩阵 B B B B −1 B
S rs r+1,s nS rS s列
列 行 s r b b b b b b b b b r s m s r s r s r s r s r s r s s 1 1 1 1 1 1, 1, 1 − − − − = + − Er s
左乘B14,即有BA=En(B14)=(EB)A 从而得B=EB1 再通过B-又可求出对应B的基础可行解与检验数 改进单纯形法的计算步骤 设线性规划问题71)已给定可行基B,求出B1 xB=B1b=(d1,d2,…dmn) (1)计算单纯形乘子兀=CB1
左乘 B-1A, 即有 A =Ers(B-1A) = (Ers B-1 )A, 从而得 = Ers B-1 . 再通过 又可求出对应 的基础可行解与检验数. 二、改进单纯形法的计算步骤 设线性规划问题(7.11)已给定可行基B，求出B-1 . xB = B-1b = (d1 ,d2 , ···,dm) T (1) 计算单纯形乘子 π =CBB-1 −1 B −1 B −1 B B
(2)依次计算检验数=zPG(为4中第列)若 所有≤0,则基B为最优基,否则,找出最大者或最左边 的一个正数设为 (3)计算P=B-P=(b1sb2,…bm),若P≤0, 则问题无最优解停止计算否则转入(4) (4)若P′中有正分量,则用正分量b去除B-1b 中对应元素d1,取d1b中最小者,设为d/bs (5)构造初等矩阵En
(2) 依次计算检验数λj = πPj－Cj (Pj为A中第j 列),若 所有λj≤0, 则基B为最优基, 否则, 找出最大者或最左边 的一个正数 λj设为 λs . (3) 计算 =B－1Ps=(b1s ,b2s , ···,bms) T , 若 ≤0 , 则问题无最优解,停止计算. 否则转入(4). (4) 若 中有正分量, 则用正分量bis 去除B－1b 中对应元素di , 取 di / bis中最小者,设为dr / brs . (5) 构造初等矩阵Ers . Ps Ps Ps
(6)计算新基B的逆B=EB-1及新基变量的 取值:x=Bb=EBb=EnxB 重复(1)至(6)有限次,必得最优解或判定无最优解 例用改进单纯形法求解线性规划问题 maxS=70x1+120x2 9x1+4x2<360 4x1+5x2≤200 S·t 3x1+10x2≤300 x≥0(i=1,2)
(6) 计算新基 的逆 = ErsB－1 及新基变量的 取值: 重复 (1) 至 (6) 有限次, 必得最优解或判定无最优解. 例 用改进单纯形法求解线性规划问题 maxS = 70x1+120x2 9x1 + 4x2 ≤360 4x1 + 5x2 ≤ 200 3x1 + 10x2 ≤ 300 xi≥0 ( i =1, 2) B −1 B . 1 1 xB = B b = Er sB b = Er sxB − − s t
解将线性规划问题化为标准形 mnS=-70x1-120x2 9x1+4x2+x3 360 4x1+5x,+x 200 S·t 3x1+10x2 +x=300 ≥0(j=1,2,…,5) 有现成可行基B1=(P3,P4,P)=l3,B1-=B1, B,=(0,0.0)xEB1b=b=(360,200,300)1
解 将线性规划问题化为标准形 minS′= -70x1-120x2 9x1 + 4x2 +x3 = 360 4x1 + 5x2 +x4 = 200 3x1 + 10x2 +x5 = 300 xj≥0 ( j =1, 2, ···,5) 有现成可行基B1 = (P3 , P4 , P5 ) = I3 , B1 -1= B1, = B1 -1b = b = (360, 200, 300)T. s t 1 1 (0 0 0 CB xB = , , )
第一次迭代 (1)丌=CE BI B1=(0,0,0) (2)1=B-C1=70,22=P-C2=120, 取入。=22=120. 4 (3)BP2=P2=5 10 (4)O=mn360/4,200/5300/10}=300/10=d3/b32 B2=(P3,P4,P2)
第一次迭代 ( , , ) (4) min 360 4,200 5,300 10 300 10 . 10 5 4 (3) 120. (2) 70, 120, (1) (0, 0, 0). 2 3 4 2 3 3 2 2 2 1 1 2 1 1 1 2 2 2 1 1 1 B P P P B P P λ π P C λ π P C π CB B = = = = = = = = = − = = − = = = − − d b s 取
4 10 10 5 (5)E2=0 01 10 10 2 0 5/360 240 (6)B2-1=E2x=0 200 50 2 300 30 00 10 B2 (0,0,-120)
1 2 32 1 2 32 4 2 1 0 1 0 10 5 5 1 (5) 0 1 0 1 10 2 1 1 0 0 0 0 10 10 2 1 0 5 360 240 1 (6) 0 1 200 50 2 300 30 1 0 0 10 (0,0, 120). B B E B E x C − − − = − = − − = = − = = −
第二次迭代 10 (1)z=Cn,B21=(0,-120)01 2/00-12) 10 4 (2)2=nP-C2=(00-12)5-(-120)=0 10 A1=P-C1=(0、0,-12)4-(-70)=340 3 取。=
第二次迭代 1 1 1 1 2 2 2 1 2 ( 70) 34 0. 3 4 9 (0,0, 12) ( 120) 0. 10 5 4 (2) (0,0, 12) (0,0, 12) 10 1 0 0 2 1 0 1 5 2 1 0 (1) (0,0, 120) 2 = − − = = − = − − − = = − = − = − − − = = − − 取 s π P C π P C π CB B ＞
