5.1单纯形法的基本思路和原理

《5.1单纯形法的基本思路和原理》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、管理运筹学第五章单纯形法北京理工大学韩伯棠教授本章内容12单纯形法的表格形式求目标函数值最小的线性规划问题的单3纯形表解法4几种特殊情况2本章内容12单纯形法的表格形式求目标函数值最小的线性规划问题的单3纯形表解法4几种特殊情况3§1单纯形法的基本思路和原理单纯形法的基本思路：选取可行域某顶点(更优顶点)是否为最优解是否否输出是否无最优解最优解是终止4§1单纯形法的基本思路和原理一、找出一个初始基本可行解下面通过第二章例1的求解来介绍单纯形法。在加上松弛变量之后得到此线性规划的标准形式。目标函数：max50x+100x12约束条件：x+x+s

2、=300，1212x+x+s=400，122x+s=250，23x≥0（i=1,2），s≥0（j=1,2,3）。ij5§1单纯形法的基本思路和原理该线性规划问题的系数矩阵为：11100A(,ppppp,,,)210101234501001其中p为系数矩阵A第j列的向量.A的秩为3,方程j组变量个数大于A的秩，从方程组的无数组解中找一个初始可行解。6§1单纯形法的基本思路和原理如何找初始基本可行解？基本概念A是约束条件系数矩阵，秩为m。若B是A的子阵，m×nm×m基且可逆，称B为一个基。基向量基B中的一列即称为一个基向量

3、。非基在A中除了基B之外的一列称之为基B的非基向量。向量基变量与基向量pi相应的变量xi叫基变量，基变量有m个。非基与非基向量p相应的变量x叫非基变量，非基变量有n‒m个。变量jj7§1单纯形法的基本思路和原理若在约束方程组系数矩阵中找到一个基，令其非基变量为零，再求解该m元线性方程组可得到唯一解，该解称之为线性规划的基本解。此例题找到A的一个基B（可逆子阵）：3110B1003101令非基变量x=0,s=0,约束方程变为基变量的方程。128§1单纯形法的基本思路和原理基变量的约束方程:x+s=300，21x=400，2

4、x+s=250，23求解得到此线性规划的一个基本解：x=0，x=400，s=−100，s=0，s=−150121239§1单纯形法的基本思路和原理由于该基本解中s=−100，s=−150,13不满足决策变量非负的约束条件，不是可行解。满足非负条件的基本解叫做基本可行解，并把这样的基叫做可行基。10§1单纯形法的基本思路和原理一般来说判断一个基是否是可行基，只有在求出其基本解以后。能否在求解之前，找到一个可行基呢？也就是能否找到的一个基保证在求解之后得到的解一定是基本可行解呢？11§1单纯形法的基本思路和原理由于线性规划的标准型中要求b≥0，若

5、能找到一j个基是单位矩阵（各列向量顺序无关重要），例如：001100010所得基本解一定是基本可行解，解中的各个变量或等于某个b或等于零。j12§1单纯形法的基本思路和原理第一次找到的可行基为单位矩阵（各列可以乱序），称之为初始可行基，相应的基本可行解叫初始基本可行解。本例中找到了一个基是单位矩阵：100B0102001令其非基变量x=x=0，得初始基本可行解：12x=0，x=0，s=300，s=400，s=25012123注：若找不到单位矩阵（各列可以乱序）的基作为初始可行基，需要构造初始可行基。1

6、3§1单纯形法的基本思路和原理二、最优性检验判断已求得的基本可行解是否是最优解。1．最优性检验的依据——检验数σj目标函数目标函数约束等式中，非基变量移到右边，用非基基变量&非基变量变量表示基变量非基变量则目标函数中变量系数即为其检验数，把x的检验数i记为σ。所有基变量检验数为0。i14§1单纯形法的基本思路和原理例题中找到一个初始可行基：100B0102001目标函数为50x+100x，由于初始可行解中x，x为1212非基变量，所以此目标函数已经用非基变量表示了，无需代换出基变量。各检验数为：σ=50，σ=100，σ=

7、0，σ=0，σ=01234515§1单纯形法的基本思路和原理2．最优解判别定理求最大目标函数的问题中，若某个基本可行解所有检验数σ≤0，则该解是最优解。j通俗地解释最优解判别定理，设用非基变量表示的目标函数如下所示：zz0jjxjJ注：对于求目标函数最小值的情况，只需把σ≤0改为σ≥0。jj16§1单纯形法的基本思路和原理当所有的x≥0，且σ≤0，此时jjjjx0jJ分析目标函数：zz00jxjz（ssx）（txt）jJxst为基向量x为非基向量基变量均≥0，只有检验数都为0，才有σx=0;非基变ss

8、量的检验数均≤0，只有非基变量都为0，才有σx=0。tt此时目标函数才能取最大值z。017§1单纯形法的基本思路和原理三、基变换例题中σ，σ>0，即该基本可行解不是