单纯形法原理ppt课件.ppt

运筹学 §2.1 单纯形法原理一、构造初始可行基一、构造初始可行基一、构造初始可行基一、构造初始可行基▲ 1947▲ 1947▲ 1947▲ 1947年年年年, , , , 美国数学家丹捷格提出了求解美国数学家丹捷格提出了求解美国数学家丹捷格提出了求解美国数学家丹捷格提出了求解线线性性性性规规划的划的划的划的单纯单纯形形形形法法法法. . . .1. 1. 引入附加引入附加引入附加引入附加变变量量量量, , 化数学模型化数学模型化数学模型化数学模型为规为规范型范型范型范型; ;2. 2. 假假假假设设A A中含有中含有中含有中含有mm阶单阶单位位位位阵阵, , 那么那么那么那么该单该单位位位位阵阵即即即即为为一个初始可一个初始可一个初始可一个初始可行基行基行基行基; ; 否那么否那么否那么否那么, , 须须引入人工引入人工引入人工引入人工变变量量量量, , 以构成初始可行基以构成初始可行基以构成初始可行基以构成初始可行基; ;3. 3. 目的函数中目的函数中目的函数中目的函数中, , 附加附加附加附加变变量的系数量的系数量的系数量的系数为为0, 0, 人工人工人工人工变变量的系数量的系数量的系数量的系数为为MM ( (很大的正数很大的正数很大的正数很大的正数, , 称称称称为罚为罚因子因子因子因子)——)——大大大大MM法或法或法或法或罚罚函数法函数法函数法函数法. .▲ ▲ 以求解下述以求解下述以求解下述以求解下述线线性性性性规规划划划划 问题为问题为例例例例 运筹学 §2.1 单纯形法原理一、构造初始可行基一、构造初始可行基一、构造初始可行基一、构造初始可行基1. 1. 引入附加引入附加引入附加引入附加变变量量量量, , 化数学模型化数学模型化数学模型化数学模型为规为规范型范型范型范型; ;2. 2. 假假假假设设A A中含有中含有中含有中含有mm阶单阶单位位位位阵阵, , 那么那么那么那么该单该单位位位位阵阵即即即即为为一个初始可一个初始可一个初始可一个初始可行基行基行基行基; ; 否那么否那么否那么否那么, , 须须引入人工引入人工引入人工引入人工变变量量量量, , 以构成初始可行基以构成初始可行基以构成初始可行基以构成初始可行基; ;3. 3. 目的函数中目的函数中目的函数中目的函数中, , 附加附加附加附加变变量的系数量的系数量的系数量的系数为为0, 0, 人工人工人工人工变变量的系数量的系数量的系数量的系数为为MM ( (很大的正数很大的正数很大的正数很大的正数, , 称称称称为罚为罚因子因子因子因子)——)——大大大大MM法或法或法或法或罚罚函数法函数法函数法函数法. .二、求出一个根本可行解二、求出一个根本可行解二、求出一个根本可行解二、求出一个根本可行解1. 1. 用非基用非基用非基用非基变变量表示基量表示基量表示基量表示基变变量和目的函数量和目的函数量和目的函数量和目的函数; ;2. 2. 求出一个根本可行解和相求出一个根本可行解和相求出一个根本可行解和相求出一个根本可行解和相应应的函数的函数的函数的函数值值; ; 运筹学 §2.1 单纯形法原理一、构造初始可行基一、构造初始可行基一、构造初始可行基一、构造初始可行基二、求出一个根本可行解二、求出一个根本可行解二、求出一个根本可行解二、求出一个根本可行解1. 1. 用非基用非基用非基用非基变变量表示基量表示基量表示基量表示基变变量和目的函数量和目的函数量和目的函数量和目的函数; ;2. 2. 求出一个根本可行解和相求出一个根本可行解和相求出一个根本可行解和相求出一个根本可行解和相应应的函数的函数的函数的函数值值; ;三、最三、最三、最三、最优优性性性性检验检验————判判判判别别根本可行解能否根本可行解能否根本可行解能否根本可行解能否为为最最最最优优解解解解1. 1. 最最最最优优性性性性检验检验的根据的根据的根据的根据——检验检验数数数数 用非基用非基用非基用非基变变量表示目的函数之后量表示目的函数之后量表示目的函数之后量表示目的函数之后, , 目的函数中各非基目的函数中各非基目的函数中各非基目的函数中各非基变变量量量量 的系数即的系数即的系数即的系数即为为非基非基非基非基变变量的量的量的量的检验检验数数数数. . 基基基基变变量的量的量的量的检验检验数数数数为为0. 0.2. 2. 最最最最优优解判解判解判解判别别定理定理定理定理 在极小化在极小化在极小化在极小化问题问题中中中中, , 对对于某个根本可行解于某个根本可行解于某个根本可行解于某个根本可行解, , 假假假假设设一切一切一切一切检验检验数数数数0, 0, 且人工且人工且人工且人工变变量量量量=0, =0, 那么那么那么那么该该根本可行解根本可行解根本可行解根本可行解为为最最最最优优解解解解. . 运筹学 §2.1 单纯形法原理一、构造初始可行基一、构造初始可行基一、构造初始可行基一、构造初始可行基二、求出一个根本可行解二、求出一个根本可行解二、求出一个根本可行解二、求出一个根本可行解三、最三、最三、最三、最优优性性性性检验检验————判判判判别别根本可行解能否根本可行解能否根本可行解能否根本可行解能否为为最最最最优优解解解解1. 1. 最最最最优优性性性性检验检验的根据的根据的根据的根据——检验检验数数数数2. 2. 最最最最优优解判解判解判解判别别定理定理定理定理 在极小化在极小化在极小化在极小化问题问题中中中中, , 对对于某个根本可行解于某个根本可行解于某个根本可行解于某个根本可行解, , 假假假假设设一切一切一切一切检验检验数数数数0, 0, 且人工且人工且人工且人工变变量量量量=0, =0, 那么那么那么那么该该根本可行解根本可行解根本可行解根本可行解为为最最最最优优解解解解. .3. 3. 无无无无穷穷多最多最多最多最优优解判解判解判解判别别定理定理定理定理 在极小化在极小化在极小化在极小化问题问题中中中中, , 对对于某个根本可行解于某个根本可行解于某个根本可行解于某个根本可行解, , 假假假假设设一切一切一切一切检验检验数数数数0, 0, 又存在某个非基又存在某个非基又存在某个非基又存在某个非基变变量的量的量的量的检验检验数数数数=0, =0, 且人工且人工且人工且人工变变量量量量=0, =0, 那么那么那么那么该线该线性性性性 规规划划划划问题问题有无有无有无有无穷穷多最多最多最多最优优解解解解. . 运筹学 §2.1 单纯形法原理一、构造初始可行基一、构造初始可行基一、构造初始可行基一、构造初始可行基二、求出一个根本可行解二、求出一个根本可行解二、求出一个根本可行解二、求出一个根本可行解三、最三、最三、最三、最优优性性性性检验检验————判判判判别别根本可行解能否根本可行解能否根本可行解能否根本可行解能否为为最最最最优优解解解解2. 2. 最最最最优优解判解判解判解判别别定理定理定理定理 在极小化在极小化在极小化在极小化问题问题中中中中, , 对对于某个根本可行解于某个根本可行解于某个根本可行解于某个根本可行解, , 假假假假设设一切一切一切一切检验检验数数数数0, 0, 且人工且人工且人工且人工变变量量量量=0, =0, 那么那么那么那么该该根本可行解根本可行解根本可行解根本可行解为为最最最最优优解解解解. .3. 3. 无无无无穷穷多最多最多最多最优优解判解判解判解判别别定理定理定理定理 在极小化在极小化在极小化在极小化问题问题中中中中, , 对对于某个根本可行解于某个根本可行解于某个根本可行解于某个根本可行解, , 假假假假设设一切一切一切一切检验检验数数数数0, 0, 又存在某个非基又存在某个非基又存在某个非基又存在某个非基变变量的量的量的量的检验检验数数数数=0, =0, 且人工且人工且人工且人工变变量量量量=0, =0, 那么那么那么那么该线该线性性性性 规规划划划划问题问题有无有无有无有无穷穷多最多最多最多最优优解解解解. .4. 4. 无可行解判无可行解判无可行解判无可行解判别别定理定理定理定理 在极小化在极小化在极小化在极小化问题问题中中中中, , 对对于某个根本可行解于某个根本可行解于某个根本可行解于某个根本可行解, , 假假假假设设一切一切一切一切检验检验数数数数0, 0, 但某个人工但某个人工但某个人工但某个人工变变量量量量0, 0, 那么那么那么那么该线该线性性性性规规划划划划问题问题无可行解无可行解无可行解无可行解. . 运筹学 §2.1 单纯形法原理三、最三、最三、最三、最优优性性性性检验检验————判判判判别别根本可行解能否根本可行解能否根本可行解能否根本可行解能否为为最最最最优优解解解解3. 3. 无无无无穷穷多最多最多最多最优优解判解判解判解判别别定理定理定理定理 在极小化在极小化在极小化在极小化问题问题中中中中, , 对对于某个根本可行解于某个根本可行解于某个根本可行解于某个根本可行解, , 假假假假设设一切一切一切一切检验检验数数数数0, 0, 又存在某个非基又存在某个非基又存在某个非基又存在某个非基变变量的量的量的量的检验检验数数数数=0, =0, 且人工且人工且人工且人工变变量量量量=0, =0, 那么那么那么那么该线该线性性性性 规规划划划划问题问题有无有无有无有无穷穷多最多最多最多最优优解解解解. .4. 4. 无可行解判无可行解判无可行解判无可行解判别别定理定理定理定理 在极小化在极小化在极小化在极小化问题问题中中中中, , 对对于某个根本可行解于某个根本可行解于某个根本可行解于某个根本可行解, , 假假假假设设一切一切一切一切检验检验数数数数0, 0, 但某个人工但某个人工但某个人工但某个人工变变量量量量0, 0, 那么那么那么那么该线该线性性性性规规划划划划问题问题无可行解无可行解无可行解无可行解. .5. 5. 无有限最无有限最无有限最无有限最优优解解解解( (无界解无界解无界解无界解) )判判判判别别定理定理定理定理 在极小化在极小化在极小化在极小化问题问题中中中中, , 对对于某个根本可行解于某个根本可行解于某个根本可行解于某个根本可行解, , 假假假假设设存在某个非基存在某个非基存在某个非基存在某个非基变变 量的量的量的量的检验检验数数数数<0, <0, 但相但相但相但相应应的列中没有正元素的列中没有正元素的列中没有正元素的列中没有正元素, , 且人工且人工且人工且人工变变量量量量=0, =0, 那么那么那么那么该线该线性性性性规规划划划划问题问题无有限最无有限最无有限最无有限最优优解解解解( (具有无界解具有无界解具有无界解具有无界解). ). 运筹学 §2.1 单纯形法原理一、构造初始可行基一、构造初始可行基一、构造初始可行基一、构造初始可行基二、求出一个根本可行解二、求出一个根本可行解二、求出一个根本可行解二、求出一个根本可行解三、最三、最三、最三、最优优性性性性检验检验————判判判判别别根本可行解能否根本可行解能否根本可行解能否根本可行解能否为为最最最最优优解解解解2. 2. 最最最最优优解判解判解判解判别别定理定理定理定理3. 3. 无无无无穷穷多最多最多最多最优优解判解判解判解判别别定理定理定理定理4. 4. 无可行解判无可行解判无可行解判无可行解判别别定理定理定理定理四、基四、基四、基四、基变换变换1. 1. 换换入入入入变变量确量确量确量确实实定定定定 负检验负检验数中的小者所数中的小者所数中的小者所数中的小者所对应对应的非基的非基的非基的非基变变量量量量为换为换入入入入变变量量量量. .2. 2. 换换出出出出变变量确量确量确量确实实定定定定 按最小非按最小非按最小非按最小非负负比比比比值值原那么确定原那么确定原那么确定原那么确定换换出出出出变变量量量量. . 运筹学 §2.2 单纯形法的表格方式四、基四、基四、基四、基变换变换1. 1. 换换入入入入变变量确量确量确量确实实定定定定 负检验负检验数中的小者所数中的小者所数中的小者所数中的小者所对应对应的非基的非基的非基的非基变变量量量量为换为换入入入入变变量量量量. .2. 2. 换换出出出出变变量确量确量确量确实实定定定定 按最小非按最小非按最小非按最小非负负比比比比值值原那么确定原那么确定原那么确定原那么确定换换出出出出变变量量量量. .例例例例 用大用大用大用大MM法求解下述法求解下述法求解下述法求解下述线线性性性性规规划划划划问题问题. .最最最最优优解解解解为为X*=(1, 2)T , X*=(1, 2)T , 最最最最优值为优值为z*= -1z*= -1 运筹学 §2.3 大M法和两阶段法一、两一、两一、两一、两阶阶段法段法段法段法1. 1. 第一第一第一第一阶阶段段段段: : 判判判判别别原原原原线线性性性性规规划划划划问题问题能否有可行解能否有可行解能否有可行解能否有可行解. . 目的函数取全部人工目的函数取全部人工目的函数取全部人工目的函数取全部人工变变量之和量之和量之和量之和. . 假假假假设设最小最小最小最小值为值为0, 0, 那么那么那么那么转转入入入入第二第二第二第二 阶阶段段段段. . 否那么否那么否那么否那么, , 原原原原线线性性性性规规划划划划问题问题无可行解无可行解无可行解无可行解. .2. 2. 第二第二第二第二阶阶段段段段: : 求解原求解原求解原求解原线线性性性性规规划划划划问题问题的最的最的最的最优优解解解解. .例例例例 用两用两用两用两阶阶段法求解下述段法求解下述段法求解下述段法求解下述线线性性性性规规划划划划问题问题. .最最最最优优解解解解为为X*=(1, 2)T , X*=(1, 2)T , 最最最最优值为优值为z*= 7z*= 7 运筹学 §2.4 退化问题一、何一、何一、何一、何谓谓退化退化退化退化 对对于退化情形于退化情形于退化情形于退化情形, , 即使存在最即使存在最即使存在最即使存在最优优解解解解, , 也能也能也能也能够够出出出出现现循循循循环环景象景象景象景象. .二、防止循二、防止循二、防止循二、防止循环环的方法的方法的方法的方法1. 1. 摄动摄动法法法法2. 2. 勃勃勃勃兰兰特特特特(Bland)(Bland)方法方法方法方法 下下下下标标最小原那么最小原那么最小原那么最小原那么( (两条两条两条两条) ) §2.5 改良单纯形法一、一、一、一、单纯单纯形法的矩形法的矩形法的矩形法的矩阵阵方式方式方式方式 运筹学 。