管理运筹学（第三版）第五章.ppt

81管理运筹学第五章单纯形法§1§2§3§4单纯形法的基本思路和原理单纯形法的表格形式求目标函数值最小的线性规划问题的单纯形表解法几种特殊情况82管理运筹学§1单纯形法的基本思路和原理单纯形法的基本思路:从可行域中某一个顶点开始,判断此顶点是否是最优解,如不是,则再找另一个使得其目标函数值更优的顶点,称之为迭代,再判断此点是否是最优解,直到找到一个顶点为其最优解,就是使得其目标函数值最优的解,或者能判断出线性规划问题无最优解为止。一、找出一个初始基本可行解下面通过第二章例1 的求解来介绍单纯形法。在加上松弛变量之后我们可得到此线性规划的标准形式。目标函数:max 50x1+100x2约束条件:x1+x2+s1=300,2x1+x2+s2=400,x2+s3=250,xi ≥0(i=1,2),sj≥0(j=1,2,3)。83管理运筹学?????????????????????§1 单纯形法的基本思路和原理它的系数矩阵为:?1 1 1 0 0 , p , p , p , p 2 1 0 1 0?0 1 0 0 1 其中pj 为系数矩阵A 第j 列的向量。A 的秩为3,A 的秩m 小于此方程组的变量的个数n,为了找到一个初始基本可行解,先介绍以下几个线性规划的基本概念。基:已知A 是约束条件的m×n 系数矩阵,其秩为m。若B 是A 中m ×m阶非奇异子矩阵(即可逆矩阵),则称B 是线性规划问题中的一个基。基向量:基B 中的一列即称为一个基向量。基B 中共有m 个基向量。非基向量:在A 中除了基B 之外的一列则称之为基B 的非基向量。基变量:与基向量pi 相应的变量xi 叫基变量,基变量有m 个。84管理运筹学???????????§1 单纯形法的基本思路和原理非基变量:与非基向量pj 相应的变量xj 叫非基变量,非基变量有n?m 个。由线性代数的知识知道,如果我们在约束方程组系数矩阵中找到一个基,令这个基的非基变量为零,再求解这个m 元线性方程组就可得到唯一的解了,这个解我们称之为线性规划的基本解。1 1 0 1 0 01 0 1 为零。这时约束方程就变为基变量的约束方程。85管理运筹学§1 单纯形法的基本思路和原理x2+s1=300,x2=400,x2+s3=:x1=0,x2=400,s1=?100,s2=0,s3=?150由于在这个基本解中s1=?100,s3=?150,不满足该线性规划s1≥0,s3≥0 的约束条件,显然不是此线性规划的可行解,一个基本解可以是可行解,也可以是非可行解,它们之间的主要区别在于其所有变量的解是否满足非负的条件。我们把满足非负条件的一个基本解叫做基本可行解,并把这样的基叫做可行基。86管理运筹学????????????§1 单纯形法的基本思路和原理一般来说判断一个基是否是可行基,只有在求出其基本解以后,当其基本解所有变量的解都大于等于零时,才能断定这个解是基本可行解,这个基是可行基。那么我们能否在求解之前,就找到一个可行基呢?也就是说我们找到的一个基能保证在求解之后得到的解一定是基本可行解呢?由于在线性规划的标准型中要求bj 都大于等于零,如果我们能找到一个基是单位矩阵,或者说一个基是由单位矩阵的各列向量所组成(至于各列向量的前后顺序是无关紧要的事)例如:?0 0 1 1 0 0?0 1 0 那么显然所求得的基本解一定是基本可行解,这个单位矩阵或由单位矩阵各列向量组成的基一定是可行基。实际上这个基本可行解中的各个变量或等于某个bj 或等于零。87管理运筹学????????????§1 单纯形法的基本思路和原理在本例题中我们就找到了一个基是单位矩阵。?1 0 0 0 1 0?0 0 1 在第一次找可行基时,所找到的基或为单位矩阵或为由单位矩阵的各列向量所组成,称之为初始可行基,其相应的基本可行解叫初始基本可行解。如果找不到单位矩阵或由单位矩阵的各列向量组成的基作为初始可行基,我们将构造初始可行基。88管理运筹学§1 单纯形法的基本思路和原理二、最优性检验所谓最优性检验就是判断已求得的基本可行解是否是最优解。——检验数σj一般来说目标函数中既包括基变量,又包括非基变量。现在我们要求只用非基变量来表示目标函数,这只要在约束等式中通过移项等处理就可以实现,然后用非基变量的表示式代替目标函数中的基变量,这样目标函数中只含有非基变量了,或者说目标函数中基变量的系数都为零了。此时目标函数中所有变量的系数即为各变量的检验数,把变量xi 的检验数记为σi。显然所有基变量的检验数必为零。在本例题中目标函数为50x1