第5章1单纯形法20071009.ppt

第五章 单纯形法 在求解LP问题时,有人给出了图解法,但对多维变量时,却无能为力,于是 美国数学家G·B·Dantgig(丹捷格)发明了一种“单纯形法”的代数算法，尤其是方便于计算机运算。这是运筹学史上最辉煌的阶段。 本章主要内容 线性规划问题解的基本概念 单纯形解法 解的最优性检验 表解形式的单纯形法 单纯形解法的一些问题及其处理方法 第1节 单纯形解法的基本原理与思路 线性规划问题解的基本概念 单纯形解法 解的最优性检验 一、线性规划问题解的基本概念 可行解 最优解 基及基本解 可行基及基本可行解 代数解与几何解的关系 单纯形法的要点 一、线性规划问题解的基本概念 可行解:满足所有约束条件(包括非负条件)的解称为可行解.即可行域内所有点. 一、线性规划问题解的基本概念 可行解:满足所有约束条件(包括非负条件)的解称为可行解.即可行域内所有点. 最优解: 达到最优的可行解.?最优解. 基本可行解:可行域内的顶点(边界). 一、线性规划问题解的基本概念 一、线性规划问题解的基本概念 例子 例子的标准型 标准型 线性方程组的增广矩阵表示 它的初始可行基 初始基本可行解 初始基变量 是松弛变量。 初始可行解（只要满足非负条件） 初始基本可行解 目标函数与最优性检验 第一次迭代 确定入基变量，应当是 ，它的系数是4。 确定出基变量 ，方法如下，得 确定新基和求解新的基本可行解 新基 新的基变量： 新的基本可行解 新的基本可行解和目标函数 基本可行解 目标函数 第二次迭代 确定入基变量： 确定出基变量： 确定新基和求解新的基本可行解 新的基本可行解和目标函数 第三次迭代 确定新基和求解新的基本可行解 新基 新的基变量： 新的基本可行解 新的基本可行解和目标函数 基本可行解 目标函数 这是最优解。最大目标函数值为2600。 复习 2006-10-19 线性规划的标准化： LP解的基本概念： 单纯形表格形式求解 标准型 标准型 标准型 第2节、单纯形表格解法 建立基本可行解 计算变量的检验数 判断是否最优 若不是最优解，换基 计算新的基本可行解 迭代计算直到求得最优解或可判断无最优解为止 建立初始基本可行基 对于小于等于情况，通过标准化，每个约束条件的左边加上了一的松弛变量，该松弛变量的系数矢量是单位矢量。 当约束条件的右手项都大于等于零时，可令松弛变量为初始基本可行基。 关于解的最优性检验 设线性规划模型为 令基为B，并作相应的矩阵分割，从约束条件得 代入目标函数 得 令 则目标函数可写成 所以可用σj 判断是否最优解，它叫做检验数。 单纯形解法 例子: 表解形式的单纯形法 例子: 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 第3节 求目标函数值最小的线性规划的问题的单纯形表解法 第3节 求目标函数值最小的线性规划的问题的单纯形表解法 第3节 求目标函数值最小的线性规划的问题的单纯形表解法 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 第4节几种特殊情况 一.无可行解 二.无界解 三.无穷多最优解. 四.退化问题 §4.几种特殊情况 一、无可行解： 目标函数：max z=20x1+30x2 约束条件：3x1+10x2≤150 x1≤ 30 x1+x2≥40 x1,x2≥0 §4.几种特殊情况 max z=20x1+30x2-Ma 3x1+10x2+s1=150 x1+ s2= 30 x1+x2-s3 +a1=40 x1,x2,s1,s2,s3,a1≥0 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 §4.几种特殊情况 x1=30,x2=6,s1=0,s2=0,s3=0,a1=4≠0， 其最大目标函数为780-4M，由于a1 ≠0, 故所得解不是最优解。 人工变量非0，表明原模型无最优解。 §4.几种特殊情况 二、无界解 目标函数：max z=x1+x2 约束条件：x1－x2≤1 -3x1+2x2≤ 6 x1,x2≥0