§2.1 单纯形法原理

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