运筹学单纯形法计算步骤

1、,第四节 单纯形法的计算步骤,为书写规范和便于计算，对单纯形法的计算设计了单纯形表。每一次迭代对应一张单纯形表，含初始基可行解的单纯形表称为初始单纯形表，含最优解的单纯形表称为最终单纯形表。本节介绍用单纯形表计算线性规划问题的步骤。,单纯形表,在上一节单纯形法迭代原理中可知，每一次迭代计算只要表示出当前的约束方程组及目标函数即可。,B 基矩阵,N 非基阵,基变量XB,非基变量XN,0,单纯形表,单纯形表,2 1 0 0 0,检验数,单纯形表结构,单纯形表,C,已知,2 1 0 0 0, 24/6 5/1,C,检验数,单纯形表结构,单纯形表,基可行解：,单纯形表结构,单纯形表,有时不写此项,求,

2、单纯形表结构,单纯形表,求,单纯形表结构,单纯形表,求,不妨设此为主列,主行,单纯形表结构,单纯形表,主元,用单纯形表求解例1,表1：列初始单纯形表 （单位矩阵对应的变量为基变量）,2 3 0 0 0,000,8 1612,2 3 0 0 0,2 3 0 0 0,000,8 1612,2 3 0 0 0,正检验数中最大者对应的列为主列,最小的值对应的行为主行,主元化为1 主列单位向量 换出 换入,表1：列初始单纯形表 （单位矩阵对应的变量为基变量）,2 3 0 0 0,003,2 163,0 0 0,2,-3/4,正检验数中最大者对应的列为主列,最小的值对应的行为主行,主元化为1 主列单位向量

3、 换出 换入,表2：基变换 （初等行变换，主列化为单位向量，主元为1）,2 3 0 0 0,203,2 8 3,0 0 -2 0 1/4,表3：基变换 （初等行变换，主列化为单位向量，主元为1）,0 0 -3/2 -1/8 0,2 3 0 0 0,203,4 4 2,检验数=0,表4：最终单纯形表,用单纯形表求解LP问题例,解：化标准型,2 1 0 0 0,000,15245,2 1 0 0 0,表1：列初始单纯形表 （单位矩阵对应的变量为基变量）,2 1 0 0 0 0 15 0 5 1 0 0 0 24 6 2 0 1 0 0 5 1 1 0 0 1 2 1 0 0 0,主元化为1 主列单

4、位向量 换出 换入,正检验数中最大者对应的列为主列,最小的值对应的行为主行,表1：列初始单纯形表 （单位矩阵对应的变量为基变量）,2 1 0 0 0 0 15 0 5 1 0 0 2 4 1 2/6 0 1 /6 0 0 1 0 4/6 0 -1/6 1 0 1/3 0 -1/3 0,检验数0 确定主列,最小 确定主行,主元,表2：基变换 （初等行变换，主列化为单位向量，主元为1）,检验数=0,表3：基变换 （初等行变换，主列化为单位向量，主元为1）,2 1 0 0 0 0 15 0 5 1 0 0 0 24 6 2 0 1 0 0 5 1 1 0 0 1 2 1 0 0 0,思考:,一般主列

5、选择正检验数中最大者对应的列,也可选择其它正检验数的列.以第2列为主列,用单纯形法求解。,正检验数对应的列为主列,单纯形法的解的情况,单纯形法求解线性规划问题，解的情况也有四种： 唯一最优解：上面的情况，所有的检验数都小于等于0，并且非基变量的检验数都小于零 无穷多解 无界解 无解：下界讨论,单纯形法的解的情况,例2： 第一步：转换为标准形式,单纯形法的计算步骤,构造单纯形表,单纯形法解的情况,(8,0,14,0)和( 2.4,8.4,0,0)都是最优解。 当有一个非基变量的检验数（imp）值为0时，线性规划问题有多重最优解 任意最优解为(8,0,14,0) +(1-)( 2.4,8.4,0,

6、0),C,D,(1),(2),单纯形法的解的情况,单纯形法求解线性规划问题，解的情况也有四种： 唯一最优解：上面的情况，所有的检验数都小于等于0，并且非基变量的检验数都小于零 无穷多解：所有的检验数都小于等于0，至少有一个非基变量的检验数为0 无界解 无解：下界讨论,单纯形法解的情况,例： 转换为标准形式,单纯形法的基本思想,最优解的判断 若 为一基本可行解，有一个 ，并且对一切 ，有 ,那么该线性规划问题有无界解。,单纯形法解的情况,X3可以增长到无穷大，所以线性规划问题有无界解,单纯形法的解的情况,单纯形法求解线性规划问题，解的情况也有四种： 唯一最优解：上面的情况，所有的检验数都小于等于0，并且非基变量的检验数都小于零 无穷