§72单纯形法 、几个基本概念 1.基、基变量、非基变量 设线性规划问题为 min s= cx AX= b (7.11) X>0 其中 C=(C2 C2.Cn
§7.2 单纯形法 一、几个基本概念 1. 基、基变量、非基变量 设线性规划问题为 min S = CX AX = b (7.11) X ≥0 其中 C = ( c2 c2 ··· cn ). s t
n 21 22 2n b= m2 mn n 且m 若B是矩阵A的m阶非奇异子矩阵,则称B是线性规 划问题(7的一个基
= = = m m m n m n n n x x x b b b a a a a a a a a a 2 1 2 1 1 2 2 1 2 2 2 1 1 1 2 1 A , b , X 且 m ≤ n, r(A) = m. 若B是矩阵A 的m 阶非奇异子矩阵, 则称B是线性规 划问题(7.11)的一个基
12 不妨设B=(P1,P2,…,Pm)=21 m2 mm N=(Pm+1,…,Pn) 则把P1,P2,…,Pm对应的变量x1,x2,…xn叫做对应基B的 基变量,Pm,…,Pn对应的变量xmH1xm+2,…xn叫做非基 变量
不妨设 B = (P1 , P2 , ···,Pm ) 则把P1 ,P2 , ···,Pm对应的变量x1 , x2 , ···,xm叫做对应基B的 基变量, Pm+1, ···,Pn对应的变量xm+1,xm+2, ···,xn叫做非基 变量. , = m m mm m m a a a a a a a a a 1 2 2 1 2 2 2 1 1 1 2 1 N (P , ,P ). = m+1 n
2.基础解、基础可行解、基础最优解 d 设 B N m+1 若X满足X=b且x=0,则称X=为(1)关 于基B的基础解
2. 基础解、基础可行解、基础最优解 设 若X 满足AX = b且xN = 0，则称X = 为(7.11)关 于基B 的基础解. = = + N B n m m x x x x x x x X 1 2 1 0 B x
若基础解X=≥0,则称此基础解为基础可 行解,此时B称为可行基 若基础可行解X是最优解,则称X为基础最优解, 此时相应的基B称为最优基. 3.线性规划问题的典式 对于线性规划问题
若基础解X= ≥0 , 则称此基础解为基础可 行解, 此时 B 称为可行基. 若基础可行解 X 是最优解, 则称 X 为基础最优解, 此时相应的基 B 称为最优基. 3. 线性规划问题的典式 对于线性规划问题 0 B x
minS=C1+C22+.+Crrn …+a b 21+ tax 2 (6.1 m11+ m2+ mm n 0(j=1,2,…,n) 设B=(P1P2,…,Pm)为其一个基则根据线性代数理 论可知
minS = c1x1 + c2x2 + ··· + cnxn a11x1 + a12x2 + ··· +a1nxn = b1 , a21x1 + a22x2 + ··· + a2nxn = b2 , ······ (6.1) am1x1 + am2x2 + ··· + amnxn = bm, xj≥0 ( j = 1, 2, ···, n). 设B = (P1 ,P2 , ···,Pm)为其一个基,则根据线性代数理 论可知 s t
(61)的约束方程组可化为 blm+m++, , . burn-di m+bmm+1xm+1+…+ mann 由此解出基变量x1,x2,…xm再代入(6,1)的目标函数, 则可得: Bm+im+ ∴+C.x
(6.1) 的约束方程组可化为 x1 + b1,m+1xm+1+ ··· + b1nxn = d1, ··· ··· ··· ··· xm+ bm,m+1 xm+1 + ··· + bmnxn = dm. 由此解出基变量 x1 , x2 , ···,xm,再代入(6.1)的目标函数, 则可得: , B m m n n S = S + c x + + c x +1 +1
其中Sg为常数,它与B有关,于是6,1)可简化 为如下的等价形式 min S=SB+Cmm+.+clrn tb burn=d (7.12) S·t xt b mmt] m+ …+b mrn ≥0(j=1,2,…,n) 我们把(712)这种形式称为6)对应于基B的典式
其中SB 为常数,它与B 有关,于是(6.1)可简化 为如下的等价形式 x1 + b1,m+1xm+1+ ··· + b1nxn = d1 ··· ··· ··· (7.12) xm+ bm,m+1xm+1+ ··· + bmnxn = dm. xj≥0 ( j = 1, 2, ···, n) 我们把(7.12)这种形式称为(6.1)对应于基B 的典式. s t min , B m 1 m 1 n n S = S + c x + + c x + +
由典式可立即得到对应的基础可行解和相应的目标 函数值,且可为求得另一个更好的基础可行解作准备,因 此典式概念非常重要 下面讨论典式的矩阵形式 设线性规划问题的矩阵形式为 min s= cX AX=b (7.13) St X>0
由典式可立即得到对应的基础可行解和相应的目标 函数值, 且可为求得另一个更好的基础可行解作准备, 因 此典式概念非常重要. 下面讨论典式的矩阵形式 设线性规划问题的矩阵形式为 min S = CX AX = b (7.13) X ≥0 st
B=( ,Pm)为其一个基,它是可逆的于是有 C B-IAX=CDB-1b 从而S-CX+CB-AX=CB-1b S+(crB-A-CXcrB-b 用B-1左乘AX=b得:B-1AX=B-1b 故可得(713)对应于基B的典式矩阵形式为 minS=CBB-b(CBB-A-CX B-IAX=B-16 (7.14 S·t X>0
B = (Pj1 ,Pj2 , ···,Pjm)为其一个基,它是可逆的,于是有 CBB– 1AX = CBB– 1 b 从而 S – CX + CBB– 1AX = CBB – 1b 即 S + (CBB – 1A – C )X= CBB – 1b 用 B – 1左乘 AX = b 得: B – 1AX = B – 1b 故可得(7.13)对应于基 B 的典式矩阵形式为 minS = CBB– 1 b – (CBB – 1A – C )X B – 1AX = B – 1b (7.14) X ≥ 0 s t
