第4章 单纯形法ppt课件.ppt

《第4章 单纯形法ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章单纯形法§1　单纯形法的基本思路和原理§2　单纯形法的表格形式§3　求目标函数值最小的线性规划的问题的单纯形表解法§4　几种特殊情况1§1　单纯形法的基本思路和原理单纯形法的基本思路：从可行域中某一个顶点开始，判断此顶点是否是最优解，如不是,则再找另一个使得其目标函数值更优的顶点，称之为迭代，再判断此点是否是最优解。直到找到一个顶点为其最优解，就是使得其目标函数值最优的解，或者能判断出线性规划问题无最优解为止。2通过第二章例1的求解来介绍单纯形法:在加上松弛变量之后我们可得到标准型如下：目标函数：max50x1+100

2、x2约束条件：x1+x2+s1=300，2x1+x2+s2=400，x2+s3=250.xj≥0（j=1，2）,sj≥0（j=1，2,3）3它的系数矩阵,其中pj为系数矩阵A第j列的向量。A的秩为3,A的秩m小于此方程组的变量的个数n，为了找到一个初始基本可行解，先介绍以下几个线性规划的基本概念。可行解：满足所有约束条件的解最优解：是目标函数达到最大（小）的可行解非可行解：至少一个约束条件不被满足的解可行域：所有可行解的集合（包括边界）顶点可行解（CPF）：位于可行域顶点的解基：已知A是约束条件的m×n系数矩阵，其秩为m

3、。若B是A中m×m阶非奇异子矩阵（即可逆矩阵），即子矩阵B的行列式不为零，是矩阵A中的一个满秩子矩阵，则称B是线性规划问题中的一个基。§1　单纯形法的基本思路和原理对于线性方程组：当R（A）=R（A’）=r=n时，方程组有唯一解；当R（A）=R（A’）=r

4、即标准化以后的所有变量）非基变量：与非基向量pj相应的变量xj叫非基变量，非基变量有n－m个。x1+x2+s1=3002x1+x2+s2=400x2+s3=2505由线性代数的知识知道，如果我们在约束方程组系数矩阵中找到一个基，令这个基的非基变量(n-m个)为零，再求解这个m元线性方程组就可得到唯一的解了，这个解我们称之为线性规划的基本解（基解）。在此例中我们不妨找到了为A的一个基，令这个基的非基变量x１，s2为零。这时约束方程就变为基变量的约束方程：基本解中变量取非零值的个数不大于m。§1　单纯形法的基本思路和原理x1+x2+

5、s1=3002x1+x2+s2=400x2+s3=2506x2+s1=300，x2=400，x2+s3=250.求解得到此线性规划的一个基本解：x1=0，x2=400，s1=－100，s2=0，s3=－150由于在这个基本解中s1=－100，s3=－150，不满足该线性规划s1≥0，s3≥0的约束条件，显然不是此线性规划的可行解，一个基本解可以是可行解，也可以是非可行解，它们之间的主要区别在于其所有变量的解是否满足非负的条件。我们把满足非负条件的一个基本解叫做基本可行解，并把这样的基叫做可行基。§1　单纯形法的基本思路和原

6、理78基本解和角点解（或者基本可行解和角点可行解）的唯一区别在于是否包括松弛变量。对任何一个基本解而言，相应的角点解仅需通过删除松弛变量获得。9一般来说判断一个基是否是可行基，只有在求出其基本解以后，当其基本解所有变量的解都是大于等于零，才能断定这个解是基本可行解，这个基是可行基。那么我们能否在求解之前，就找到一个可行基呢？也就是说我们找到的一个基能保证在求解之后得到的解一定是基本可行解呢？由于在线性规划的标准型中要求bj都大于等于零，如果我们能找到一个基是单位矩阵，或者说一个基是由单位矩阵的各列向量所组成（至于各列向量的前后顺

7、序是无关紧要的事）例如，那么显然所求得的基本解一定是基本可行解，这个单位矩阵或由单位矩阵各列向量组成的基一定是可行基。实际上这个基本可行解中的各个变量或等于某个bj或等于零。§1　单纯形法的基本思路和原理不一定都能找到，当找不到时，可以人工构造。10在本例题中我们就找到了一个基是单位矩阵。在第一次找可行基时，所找到的基或为单位矩阵或为由单位矩阵的各列向量所组成，称之为初始可行基，其相应的基本可行解叫初始基本可行解。如果找不到单位矩阵或由单位矩阵的各列向量组成的基作为初始可行基，我们将构造初始可行基，具体做法在以后详细讲述。§1

8、　单纯形法的基本思路和原理11练习：在下列线性规划问题中，列出全部基、基解、基可行解。MaxZ=2x1+3x2+0x3+0x4+0x5s.t.2x1+2x2+x3=124x1+x4=165x2+x5=15xj≥0（j=1,2,3,4,5）提示：首先列出约束方程组