管理运筹学-第5章 单纯形法.pptVIP

§4　几种特殊情况 从第二次迭代的检验数都小于零来看，可知第2次迭代所得的基本可行解已经是最优解了，其最大的目标函数值为780-4M。我们把最优解x1=30,x2=6,s1=0,s2=0,s3=0,a1=4,代入第三个约束方程得x1+x2-0+4=40,即有：x1+x2=36≤40. 并不满足原来的约束条件3，可知原线性规划问题无可行解，或者说其可行解域为空集，当然更不可能有最优解了。 像这样只要求线性规划的最优解里有人工变量大于零，则此线性规划无可行解。 二、无界解 在求目标函数最大值的问题中，所谓无 界解是指在约束条件下目标函数值可以取 任意的大。下面我们用单纯形表来求第二 章中的例子。 例2、用单纯形表求解下面线性 规划问题。 §4　几种特殊情况 迭代次数 基变量 CB x1 x2 s1 s2 b 比值 1 1 0 0 0 s1 s2 0 0 1 -1 1 0 -3 2 0 1 1 6 1 — zj cj-zj 0 0 0 0 1 1 0 0 0 1 x1 s2 1 0 1 -1 1 0 0 -1 3 1 1 9 zj cj-zj 1 -1 1 0 0 2 -1 0 1 填入单纯形表计算得： 解：在上述问题的约束条件中加入松驰变量，得标准型如下： §4　几种特殊情况 从单纯形表中，从第一次迭代的检验数等于2，可知所得的基本可行解x1=1,x2=0,s1=0,s2=9不是最优解。同时我们也知道如果进行第2次迭代，那么就选x2为入基变量，但是在选择出基变量时遇到了问题： =-1, =-1,找不到大于零的 来确定出基变量。事实上如果我们碰到这种情况就可以断定这个线性规划问题是无界的，也就是说在此线性规划的约束条件下，此目标函数值可以取得无限大。从1次迭代的单纯形表中，得到约束方程： 移项可得： 管 理 运 筹 学 第五章 单 纯 形 法 §1　单纯形法的基本思路和原理 §2　单纯形法的表格形式 §3　求目标函数值最小的线性规划的问题的 单纯形表解法 §4　几种特殊情况 §1　单纯形法的基本思路和原理 单纯形法的基本思路：从可行域中某一个顶点开始，判断此顶点是否是最优 解，如不是,则再找另一个使得其目标函数值更优的顶点，称之为迭代，再判断此 点是否是最优解。直到找到一个顶点为其最优解，就是使得其目标函数值最优的 解，或者能判断出线性规划问题无最优解为止。 通过第二章例1的求解来介绍单纯形法: 在加上松弛变量之后我们可得到标准型如下： 目标函数： max 50x1+100x2 约束条件：x1+x2+s1≤300， 2x1+x2+s2≤400， x2+s3≤250. xj≥0 （j=1，2）,sj≥0 （j=1，2,3） 它的系数矩阵 , 其中pj为系数矩阵A第j列的向量。A的秩为3,A的秩m小于此方程组的变 量的个数n，为了找到一个初始基本可行解，先介绍以下几个线性规划的 基本概念。 基： 已知A是约束条件的m×n系数矩阵，其秩为m。若B是A中m×m阶非 奇异子矩阵（即可逆矩阵），则称B是线性规划问题中的一个基。 基向量：基B中的一列即称为一个基向量。基B中共有m个基向量。 非基向量：在A中除了基B之外的一列则称之为基B的非基向量。 基变量：与基向量p