§2.1单纯形法原理.ppt

p11-1,2.1 单纯形法原理,一、构造初始可行基, 1947年, 美国数学家丹捷格提出了求解线性规划的单纯形法.,1. 引入附加变量, 化数学模型为标准型; 2. 若A中含有m阶单位阵, 则该单位阵即为一个初始可行基; 否则, 须引入人工变量, 以构成初始可行基; 3. 目标函数中, 附加变量的系数为0, 人工变量的系数为M (很大的正数, 称为罚因子)大M法或罚函数法., 以求解下述线性规划 问题为例,p11-2,2.1 单纯形法原理,一、构造初始可行基,1. 引入附加变量, 化数学模型为标准型; 2. 若A中含有m阶单位阵, 则该单位阵即为一个初始可行基; 否则, 须引入人工变量, 以构成初始可行基; 3. 目标函数中, 附加变量的系数为0, 人工变量的系数为M (很大的正数, 称为罚因子)大M法或罚函数法.,二、求出一个基本可行解,1. 用非基变量表示基变量和目标函数; 2. 求出一个基本可行解和相应的函数值;,p11-3,2.1 单纯形法原理,一、构造初始可行基,二、求出一个基本可行解,1. 用非基变量表示基变量和目标函数; 2. 求出一个基本可行解和相应的函数值;,三、最优性检验判断基本可行解是否为最优解,1. 最优性检验的依据检验数 用非基变量表示目标函数之后, 目标函数中各非基变量 的系数即为非基变量的检验数. 基变量的检验数为0.,2. 最优解判别定理 在极小化问题中, 对于某个基本可行解, 若所有检验数0, 且人工变量=0, 则该基本可行解为最优解.,p11-4,2.1 单纯形法原理,一、构造初始可行基,二、求出一个基本可行解,三、最优性检验判断基本可行解是否为最优解,1. 最优性检验的依据检验数,2. 最优解判别定理 在极小化问题中, 对于某个基本可行解, 若所有检验数0, 且人工变量=0, 则该基本可行解为最优解.,3. 无穷多最优解判别定理 在极小化问题中, 对于某个基本可行解, 若所有检验数0, 又存在某个非基变量的检验数=0, 且人工变量=0, 则该线性 规划问题有无穷多最优解.,p11-5,2.1 单纯形法原理,一、构造初始可行基,二、求出一个基本可行解,三、最优性检验判断基本可行解是否为最优解,2. 最优解判别定理 在极小化问题中, 对于某个基本可行解, 若所有检验数0, 且人工变量=0, 则该基本可行解为最优解.,3. 无穷多最优解判别定理 在极小化问题中, 对于某个基本可行解, 若所有检验数0, 又存在某个非基变量的检验数=0, 且人工变量=0, 则该线性 规划问题有无穷多最优解.,4. 无可行解判别定理 在极小化问题中, 对于某个基本可行解, 若所有检验数0, 但某个人工变量0, 则该线性规划问题无可行解.,p11-6,2.1 单纯形法原理,三、最优性检验判断基本可行解是否为最优解,3. 无穷多最优解判别定理 在极小化问题中, 对于某个基本可行解, 若所有检验数0, 又存在某个非基变量的检验数=0, 且人工变量=0, 则该线性 规划问题有无穷多最优解.,4. 无可行解判别定理 在极小化问题中, 对于某个基本可行解, 若所有检验数0, 但某个人工变量0, 则该线性规划问题无可行解.,5. 无有限最优解(无界解)判别定理 在极小化问题中, 对于某个基本可行解, 若存在某个非基变 量的检验数0, 但相应的列中没有正元素, 且人工变量=0, 则该线性规划问题无有限最优解(具有无界解).,p11-7,2.1 单纯形法原理,一、构造初始可行基,二、求出一个基本可行解,三、最优性检验判断基本可行解是否为最优解,2. 最优解判别定理,3. 无穷多最优解判别定理,4. 无可行解判别定理,四、基变换,1. 换入变量的确定 负检验数中的小者所对应的非基变量为换入变量. 2. 换出变量的确定 按最小非负比值原则确定换出变量.,p11-8,2.2 单纯形法的表格形式,四、基变换,1. 换入变量的确定 负检验数中的小者所对应的非基变量为换入变量. 2. 换出变量的确定 按最小非负比值原则确定换出变量.,例 用大M法求解下述线性规划问题.,最优解为X*=(1, 2)T , 最优值为z*= -1,p11-9,2.3 大M法和两阶段法,一、两阶段法,1. 第一阶段: 判断原线性规划问题是否有可行解. 目标函数取全部人工变量之和. 若最小值为0, 则转入第二 阶段. 否则, 原线性规划问题无可行解. 2. 第二阶段: 求解原线性规划问题的最优解.,例 用两阶段法求解下述线性规划问题.,最优解为X*=(1, 2)T , 最优值为z*= 7,p11-10,2.4 退化问题,一、何谓退化,对