第3章 线性规划单纯形方法(2).ppt

1、由图解法的例可看出： 线性规划的最优解在极点上,凸集,凸集,不是凸集,极点,(顶点),线性规划问题基本定理,定理一 若线性规划问题存在可行解，则问题的可行 域是凸集。,定理二 线性规划问题的基本可行解 X 对应线性规划 问题可行域（凸集）的顶点。,定理三 若线性规划问题有最优解，一定存在一个基 可行解是最优解(即最优解一定在某顶点上)。,从上述三个定理可以看出，要求线性规划问题的最优解，只要比较可行域（凸集）各个顶点(或者说基可行解)对应的目标函数值即可，最大的就是我们所要求的最优解。,3.2 单纯形方法,思路： 从一个基可行解（极点）出发（如何去找一个基可行解？），判断其是否为最优解，（如何

2、判断？）， 若不是，则转换到相邻的基可行解（另一个极点），并使目标函数值不断增大，一直找到最优解为止。,单纯形法：先找到一个初始基可行解，如果不是最优解，设法转换到另一个基可行解（换基迭代，即从极点到极点），并使目标 函数不断增大，一直到 找到最优解为止。,B1 X(1),B1 X(1),B2 X(2),B3 X(3),Bn X(n),XN=0 X=(XB,XN),2.3.1 单纯形表,单纯形法的具体步骤： （一）确定初始基可行解 在L.P问题的标准型： 中，不妨设B是一个可行基，于是A=（B,N) 不失一般性假定B=（P1,Pm),基变量XB=（x1,xm)T N =(Pm+1,Pn),非基

3、变量XN=（xm+1,xn)T.则 X= XB , XN T相应有C=(CB,CN),于是，原问题化为：,初始基可行解,o,I,检验数,为什么？,。,对上面分析过程进行总结： （1）在标准型中，找一个单位基矩阵并求出该基对应的基可行解。 当L.P问题的约束条件全部为“”时，在变换为标准型的过程引进松驰变量，就自然得到了一个单位矩阵-初始可行基和初始基可行解。 （2）检验该基可行解是否最优？通过非基变量的检验数。 （3）若不是最优，则另找一个基产生一个基可行解-换基迭代。直到最优。 对此原理，我们可以通过单纯形表来实现。,单纯形表,说明,1、表中基变量所在位置并不一定正好在前m个位置上，但总可以

4、通过调换重新排成上表形式。 2、表中最下一行称为检验数行，对应于非基变量的检验数为：（用于检验是否还须继续迭代） 3、不难看出，基变量 的检验数均为0,2.3.2 单纯形法的步骤,引例 ：解L.P问题,第一步：把模型化为标准形式后找出初始可行基，建立初始单纯形表（见下表）。 本例中取初始基B1=(P3 ,P4)=I ,则,由表得基可行解:,（二）最优检验,第三步：换基迭代,1.上第一表中,x1为换入变量； 又由于比值=min(24/2，26/3）=26/3,确定x4为换出变量.x1所在列和x4所在行的交叉处为主元。进行迭代后， X(2)=(26/3,0,20/3,0)T， 目标函数值为Z（2）=104/3，但不是最优值。 2.第二次迭代x2为换入变量，x3为换出变量。进行迭代后，X(1)=(6，4，0，0)T,因最后一行的所有检验数都已是正数或零，因此 目标函数值为Z*= Z（3）=36是最优值。,该问题的最优解X*=（3，0，1，5，0）T最优值Z*=9 注意到： （1）最终表