6.4单纯形法理论基础 也可用矩阵表示为 maxZ-CX aX=b X>0 其中X=(x1x2…xm1…xn C=(CI n0…0), 个0 A与原来相比,增添了一个m阶价单位阵In 这m个变量xm,…,X称为松弛变量
６．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+2x2<6x1,x2>0 引进x3,x4,得 maxZ=x1+2+0x2+0 2x1+3x2+x2=6 3x1+2x2+x4=6 X1,X,X2,x≥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单纯形法理论基础 1=0 66 (0,2,0,2 (5,5,0.,0) 0 00.66)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=(c1C n0…0), m个0 a 11a12 In a a 2142 2 ain A n2 mn X=(x1…xnx1…xmn b=(b1 b1b,…b
６．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=(an1)mxm的第列为A 有以下定理
６．4 单纯形法理论基础 则线性问题变成 maxZ＝CX AX＝b， X≥0 不难看出，S＝{ X｜AX＝b，X≥0}也是 凸多面体，它也有顶点． 设A＝( aij )m×(n+ m)的第j列为Aj． 有以下定理