文档介绍:线性规划单纯形方法线性规划问题基本定理定理一若线性规划问题存在可行解,则问题的可行域是凸集。定理二线性规划问题的基本可行解X对应线性规划问题可行域(凸集)的顶点。定理三若线性规划问题有最优解,一定存在一个基可行解是最优解(即最优解一定在某顶点上)。从上述三个定理可以看出,要求线性规划问题的最优解,只要比较可行域(凸集)各个顶点(或者说基可行解)对应的目标函数值即可,最大的就是我们所要求的最优解。§:从一个基可行解(极点)出发(如何去找一个基可行解?),判断其是否为最优解,(如何判断?),若不是,则转换到相邻的基可行解(另一个极点),并使目标函数值不断增大,一直找到最优解为止。单纯形法:先找到一个初始基可行解,如果不是最优解,设法转换到另一个基可行解(换基迭代,即从极点到极点),并使目标函数不断增大,一直到找到最优解为止。B1X(1)B1X(1)B2X(2)B3X(3)BnX(n)XN=0X=(XB,XN):(一):中,不妨设B是一个可行基,于是A=(B,N)不失一般性假定B=(P1,…,Pm),基变量XB=(x1,…,xm)TN=(Pm+1,…,Pn),非基变量XN=(xm+1,…,xn)=〔XB,XN〕T相应有C=()于是,原问题化为:初始基可行解oI检验数为什么?。对上面分析过程进行总结:(1)在标准型中,找一个单位基矩阵并求出该基对应的基可行解。“≤”时,在变换为标准型的过程引进松驰变量,就自然得到了一个单位矩阵----初始可行基和初始基可行解。(2)检验该基可行解是否最优?通过非基变量的检验数。(3)若不是最优,则另找一个基产生一个基可行解-----换基迭代。直到最优。对此原理,我们可以通过单纯形表来实现。