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