线性规划问题的单纯形法求解(第3讲)ppt课件.ppt

《线性规划问题的单纯形法求解(第3讲)ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、线性规划问题的单纯形法求解《运筹学》第三讲2011.03.01内容提要线性规划问题解的概念线性规划问题的几何意义线性规划问题的单纯形求解1.线性规划问题解的概念标准型可行解：满足约束条件的解称为可行解。最优解：使目标函数达到最大值的可行解称为最优解。基：若B是矩阵A中m×m阶非奇异子矩阵（

2、B

3、≠0），则B是线性规划问题的一个基。不妨设：,j=1，2，…,m——基向量。，j=1，2，…,m——基变量。,j=m+1,…,n——非基变量。线性规划问题解的概念线性规划问题解的概念为了进一步讨论线性规划问题的解，下面研究约束方程的求解问题。假设该方程组系数矩阵A的

4、秩为m,因m

5、量、非基向量、基解、基可行解、可行基例行列式基变量非基变量基向量非基向量对应于基B1的基解X1非基可行解例行列式基变量非基变量基变量非基变量对应于基B2的基解X2基可行解线性规划解的关系图非可行解可行解基可行解基解线性规划问题解的概念最优解？2.线性规划问题的几何意义基本概念凸集：线性规划问题的几何意义顶点:若K是凸集，X∈K；若X不能用不同的两点的线性组合表示为：则X为K的一个顶点。凸集线性规划问题的几何意义顶点定理1:若线性规划问题存在可行域,则其可行域:是凸集.基本定理证明:线性规划问题的几何意义只要验证X在D中即可引理：线性规划问题的可行解X为基可

6、行解的充要条件是X的正分量对应的系数列向量是线性独立的。定理3：若可行域有界，线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。定理2：线性规划问题的基可行解X对应于可行域D的顶点。证明：反证法。分两步。几点结论：线性规划问题的可行域是凸集。若线性规划问题有最优解，一定存在一个基可行解是最优解。基可行解与可行域的顶点一一对应，可行域有有限多个顶点。最优解必在顶点上得到。单纯形法单纯形法求解步骤：1、找一个基可行解作为X0初始解最容易得到的可行基是标准型线性规划的系数矩阵的单位矩阵。2、求检验数，检验X0是否为最优解（１）求检验数将约束方程组的基变量

7、的系数矩阵化为单位矩阵；通过代入或加减乘除消元法将目标函数中的基变量消去，则非基变量的系数即为检验数．（２）最优解的判别当检验数全部小于或等于0时，该基可行解为最优解,求解可结束.当存在正的检验数时,该基可行解就不是最优解,就要换到一个新的(与X0相邻的)基可行解（X1）．3、换基（迭代）(1)确定进基变量:凡是检验数大于0的非基变量都可进基;但一般选择最大的检验数对应的变量进基。(2)按最小比原则确定出基变量，就可得一新的（更接近于最优解的）基可行解（X1），对（X1）重复２－３的过程就可在有限步得到最优解，或判断出无最优解。求解下列的线性规划maxz=

8、2x1+3x2+0x3+0x4+0x5x1+2x2+x3=84x1+x4=161.124x2+x5=12x1,x2,x3,x4,x5≥0解：1、求一个初始基可行解可以看到x3,x4,x5的系数列向量组成一个单位矩阵，是约束方程组的一个可行基。这些向量构成一个可行解基，对应的基可行解为x0=（0，0，8，16，12），基对应于基B0的变量x3,x4,x5为基变量。为求检验数，将约束方程组的基变量的系数矩阵化为单位矩阵可以得到x3+x1+2x2=8x4+4x1=16x5+4x2=12或x3=8-x1-2x2x4=16-4x1x5=12-4x2将上式代入目标函数

9、z=2x1+3x2+0x3+0x4+0x5得到z=0+2x1+3x2。于是非基变量x1，x2的系数就为检验数，分别为2，3。2、求对应于X0的检验数最优性判别从目标函数可以看出，该基可行解X0=(0,0,8,16,12,)对应的目标值为0，但是非基变量x1,x2的系数为正，因此只要增加x1或x2的值，（最大化的）目标函数就可以增加。只要有正的检验数，该基可行解就不会是最优解，只有当全部的检验数都小于或等于零时，对应的基可行解才为最优解。3、换基（1）确定进基变量凡是检验数大于0的非基变量都可进基;但一般选择最大的检验数对应的变量进基。由于x2的系数为正，显

10、然当x2增大，则目标函数z的值也增大。当x2定为换入变量后，必须从