6.4单纯形法理论基础 也可用矩阵表示为 maxZ=CX aX=b X>0 其中X=(x1x2…xnxa+1…xn下 C=(c1C2…Cn0…0) m个0 A与原来相比,增添了一个m阶单位阵In 这m个变量xm,…,xm称为松弛变量
６．4 单纯形法理论基础 也可用矩阵表示为： maxZ＝CX AX＝b X≥0 其中X＝(x1x2···xnxn+1 ···xn+m) T C＝( c1 c2 ··· cn 0 ··· 0 )， m个0 A与原来相比，增添了一个m阶单位阵Im 这m个变量xn+1, ···,xn+m称为松弛变量．
6.4单纯形法理论基础 上一小节中的例:maxZ=x1+x2 2x1+3x2<6 3x1+2x,<6x1,x2≥0 引进x3,x4,得: maxz=X1+X2+ Ox3+ OX4 2x1+3x2+x3=6 3x1+2X2+x4=6 X1,x2,X3,X4=0
６．4 单纯形法理论基础 上一小节中的例: maxZ＝x1+ x2 2x1+ 3x2 ≤6 3x1+ 2x2 ≤6 x1 ,x2≥0 引进x3，x4，得： maxZ＝x1+ x2 + 0x3+ 0x4 2x1+ 3x2 + x3 ＝6 3x1+ 2x2 + x4 ＝6 x1 ,x2 ,x3 ,x4≥0
6.4单纯形法理论基础 0 (0,2,0,2) 5,5,0,0 0 (0,066)x2=0(2,02.0) 所有顶点都有2个坐标为0
６．4 单纯形法理论基础 (－,－, 0,0) 6 5 6 5 x2 = 0 x1= 0 x3 = 0 (0,2,0,2) x4= 0 (2,0,2,0) (0,0,6,6) 所有顶点都有２个坐标为０
6.4单纯形法理论基础 2.凸多面体 设C=(c1c2…cn0…0), 0 a11 a a In a1 a, a 0 22 A 0 a n2 a mn ⅹ=(x1 nan+1 ntm b=(b1b2…bn
６．4 单纯形法理论基础 C＝( c1 c2 ··· cn 0 ··· 0 )， m个0 2．凸多面体 设 a11 a12 ··· a1n 1 a21 a22 ··· a2n 1 ··· ··· ··· am1 am2 ··· amn 1 0 0 ··· A＝ X＝( x1 ···xn xn+1 ··· xn+m ) T b＝( b1 b2 ··· bm ) T
6.4单纯形法理论基础 则线性问题变成 maxZ=CX AX=b, XO 不难看出,S={X|AX=b,X≥0}也是 凸多面体,它也有顶点 设A=(a1)mx(m+m的第列为A 有以下定理
６．4 单纯形法理论基础 则线性问题变成 maxZ＝CX AX＝b， X≥0 不难看出，S＝{ X｜AX＝b，X≥0}也是 凸多面体，它也有顶点． 设A＝( aij )m×(n+ m)的第j列为Aj． 有以下定理