§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