线性规划与单纯形法清华大学运筹学件PPT学习教案

1、会计学1线性规划与单纯形法清华大学运筹学件线性规划与单纯形法清华大学运筹学件第1页/共39页第2页/共39页第3页/共39页n图1-7(d) 第4页/共39页kii11第5页/共39页第6页/共39页njjjjxbxPXD10,第7页/共39页njjjjnjxbxP1, 2 , 1, 0,的所有点(可行解)组成的集合是凸集，只要证明D中任意两点连线上的点必然在D内即可。设是D内的任意两点；X(1)X(2)。TnTnxxxXxxxX222212112111,第8页/共39页则有 njjjjnjjjjnjxbxPnjxbxP122111, 2 , 1, 0, 2 , 1, 0, 令 X=(x1，x

2、2，xn)T为 x(1),x(2)连线上的任意一点，即 X=X(1)+(1-)X(2) (01) X 的每一个分量是 21)1 (jjjxxx，将它代入约束条件， 得到 第9页/共39页 bbbbxPxPxPxxPxPnjnjjjjjnjjjnjnjjjjjj11221111211又因 01 , 0, 0,21jjxx，所以 xj0，j=1,2,n。 由此可见 XD，D 是凸集。 证毕。 第10页/共39页证证: : (1) 必要性由基可行解的定义可知。 (2) 充分性若向量P1，P2，Pk线性独立， 则必有 km；当 k=m 时，它们恰构成一个基，从而 X=(x1,x2,xk,00)为相应的

3、基可行解。当 km 时， 则一定可以从其余的列向量中取出 m-k 个与 P1，P2，Pk 构成最大的线性独立向量组，其对应的解恰为 X， 所以根据定义它是基可行解。 第11页/共39页mjjjbxP1现在分两步来讨论，分别用反证法。（1-8）第12页/共39页别与(1-8)式相加和相减，。第13页/共39页这样得到(x1-1)P1+(x2-2)P2+(xm-m)Pm=b(x1+1)P1+(x2+2)P2+(xm+m)Pm=b 现取X(1)=(x1-1),(x2-2),(xm-m),0,，0X(2)=(x1+1),(x2+2),(xm+m),0,，0由X(1),X(2)可以得到X=（1/2）X(

4、1)+（1/2）X(2)，即X是X(1)，X(2)连线的中点第14页/共39页第15页/共39页第16页/共39页 mjmjjjjjbxPbxP1121与 mjjjjxxP1210将这两式相减，即得第17页/共39页第18页/共39页第19页/共39页n=X(1)+(1-)X(3)+(1-)X(2)第20页/共39页第21页/共39页 kikiiiiiixX1101, 0,第22页/共39页第23页/共39页 kikiiiiiCXXCCX110在所有的顶点中必然能找到某一个顶点X(m)，使CX(m)是所有CX(i)中最大者。并且将X(m)代替(1-10)式中的所有X(i)，这就得到（1- 10） mkimikiiiCXCXCX11第24页/共39页称这种线性规划问题有无限多个最优解。第25页/共39页 1X， 2X， kX kikiiiiiXX111, 0,于是 kiiikiiiXCXCXC11 kimXCi, 2 , 1,设：第26页/共39页mmXCkii1第27页/共39页第28页/共39页第29页/共39页第30页/共39页