《单纯形法原》PPT课件.ppt

《《单纯形法原》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《单纯形法原》PPT课件.ppt（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 运筹学 2.1 2.1 单纯形法原理单纯形法原理单纯形法原理单纯形法原理一、构造初始可行基一、构造初始可行基一、构造初始可行基一、构造初始可行基 19471947年年年年,美国数学家丹捷格提出了求解线性规划的单纯形法美国数学家丹捷格提出了求解线性规划的单纯形法美国数学家丹捷格提出了求解线性规划的单纯形法美国数学家丹捷格提出了求解线性规划的单纯形法.1.1.引入引入引入引入附加变量附加变量附加变量附加变量,化数学模型为标准型化数学模型为标准型化数学模型为标准型化数学模型为标准型;2.2.若若若若A A中含有中含有中含有中含有mm阶单位阵阶单位阵阶单位阵阶单位阵,则该单位阵即为一个初始可行基则该

2、单位阵即为一个初始可行基则该单位阵即为一个初始可行基则该单位阵即为一个初始可行基;否则否则否则否则,须引入须引入须引入须引入人工变量人工变量人工变量人工变量,以构成初始可行基以构成初始可行基以构成初始可行基以构成初始可行基;3.3.目标函数中目标函数中目标函数中目标函数中,附加变量的系数为附加变量的系数为附加变量的系数为附加变量的系数为0,0,人工变量的系数为人工变量的系数为人工变量的系数为人工变量的系数为MM (很大的正数很大的正数很大的正数很大的正数,称为罚因子称为罚因子称为罚因子称为罚因子)大大大大MM法法法法或或或或罚函数法罚函数法罚函数法罚函数法.以求解下述线性规划以求解下述线性规划

3、以求解下述线性规划以求解下述线性规划 问题为例问题为例问题为例问题为例1 1 运筹学 2.1 2.1 单纯形法原理单纯形法原理单纯形法原理单纯形法原理一、构造初始可行基一、构造初始可行基一、构造初始可行基一、构造初始可行基1.1.引入引入引入引入附加变量附加变量附加变量附加变量,化数学模型为标准型化数学模型为标准型化数学模型为标准型化数学模型为标准型;2.2.若若若若A A中含有中含有中含有中含有mm阶单位阵阶单位阵阶单位阵阶单位阵,则该单位阵即为一个初始可行基则该单位阵即为一个初始可行基则该单位阵即为一个初始可行基则该单位阵即为一个初始可行基;否则否则否则否则,须引入须引入须引入须引入人工变

4、量人工变量人工变量人工变量,以构成初始可行基以构成初始可行基以构成初始可行基以构成初始可行基;3.3.目标函数中目标函数中目标函数中目标函数中,附加变量的系数为附加变量的系数为附加变量的系数为附加变量的系数为0,0,人工变量的系数为人工变量的系数为人工变量的系数为人工变量的系数为MM (很大的正数很大的正数很大的正数很大的正数,称为称为称为称为罚因子罚因子罚因子罚因子)大大大大MM法法法法或或或或罚函数法罚函数法罚函数法罚函数法.二、求出一个基本可行解二、求出一个基本可行解二、求出一个基本可行解二、求出一个基本可行解1.1.用用用用非基变量非基变量非基变量非基变量表示表示表示表示基变量基变量基

5、变量基变量和和和和目标函数目标函数目标函数目标函数;2.2.求出一个求出一个求出一个求出一个基本可行解基本可行解基本可行解基本可行解和和和和相应的函数值相应的函数值相应的函数值相应的函数值;2 2 运筹学 2.1 2.1 单纯形法原理单纯形法原理单纯形法原理单纯形法原理一、构造初始可行基一、构造初始可行基一、构造初始可行基一、构造初始可行基二、求出一个基本可行解二、求出一个基本可行解二、求出一个基本可行解二、求出一个基本可行解1.1.用用用用非基变量非基变量非基变量非基变量表示表示表示表示基变量基变量基变量基变量和和和和目标函数目标函数目标函数目标函数;2.2.求出一个求出一个求出一个求出一个

6、基本可行解基本可行解基本可行解基本可行解和和和和相应的函数值相应的函数值相应的函数值相应的函数值;三、最优性检验三、最优性检验三、最优性检验三、最优性检验判断基本可行解是否为最优解判断基本可行解是否为最优解判断基本可行解是否为最优解判断基本可行解是否为最优解1.1.最优性检验的依据最优性检验的依据最优性检验的依据最优性检验的依据检验数检验数检验数检验数 用非基变量表示目标函数之后用非基变量表示目标函数之后用非基变量表示目标函数之后用非基变量表示目标函数之后,目标函数中各非基变量目标函数中各非基变量目标函数中各非基变量目标函数中各非基变量 的系数即为非基变量的检验数的系数即为非基变量的检验数的系

7、数即为非基变量的检验数的系数即为非基变量的检验数.基变量的检验数为基变量的检验数为基变量的检验数为基变量的检验数为0.0.2.2.最优解判别定理最优解判别定理最优解判别定理最优解判别定理 在极小化问题中在极小化问题中在极小化问题中在极小化问题中,对于某个基本可行解对于某个基本可行解对于某个基本可行解对于某个基本可行解,若所有检验数若所有检验数若所有检验数若所有检验数 0,0,且人工变量且人工变量且人工变量且人工变量=0,=0,则该基本可行解为最优解则该基本可行解为最优解则该基本可行解为最优解则该基本可行解为最优解.3 3 运筹学 2.1 2.1 单纯形法原理单纯形法原理单纯形法原理单纯形法原理

8、一、构造初始可行基一、构造初始可行基一、构造初始可行基一、构造初始可行基二、求出一个基本可行解二、求出一个基本可行解二、求出一个基本可行解二、求出一个基本可行解三、最优性检验三、最优性检验三、最优性检验三、最优性检验判断基本可行解是否为最优解判断基本可行解是否为最优解判断基本可行解是否为最优解判断基本可行解是否为最优解1.1.最优性检验的依据最优性检验的依据最优性检验的依据最优性检验的依据检验数检验数检验数检验数2.2.最优解判别定理最优解判别定理最优解判别定理最优解判别定理 在极小化问题中在极小化问题中在极小化问题中在极小化问题中,对于某个基本可行解对于某个基本可行解对于某个基本可行解对于某

9、个基本可行解,若所有检验数若所有检验数若所有检验数若所有检验数 0,0,且人工变量且人工变量且人工变量且人工变量=0,=0,则该基本可行解为最优解则该基本可行解为最优解则该基本可行解为最优解则该基本可行解为最优解.3.3.无穷多最优解判别定理无穷多最优解判别定理无穷多最优解判别定理无穷多最优解判别定理 在极小化问题中在极小化问题中在极小化问题中在极小化问题中,对于某个基本可行解对于某个基本可行解对于某个基本可行解对于某个基本可行解,若所有检验数若所有检验数若所有检验数若所有检验数 0,0,又存在某个非基变量的检验数又存在某个非基变量的检验数又存在某个非基变量的检验数又存在某个非基变量的检验数=

10、0,=0,且人工变量且人工变量且人工变量且人工变量=0,=0,则该线性则该线性则该线性则该线性 规划问题有无穷多最优解规划问题有无穷多最优解规划问题有无穷多最优解规划问题有无穷多最优解.4 4 运筹学 2.1 2.1 单纯形法原理单纯形法原理单纯形法原理单纯形法原理一、构造初始可行基一、构造初始可行基一、构造初始可行基一、构造初始可行基二、求出一个基本可行解二、求出一个基本可行解二、求出一个基本可行解二、求出一个基本可行解三、最优性检验三、最优性检验三、最优性检验三、最优性检验判断基本可行解是否为最优解判断基本可行解是否为最优解判断基本可行解是否为最优解判断基本可行解是否为最优解2.2.最优解

11、判别定理最优解判别定理最优解判别定理最优解判别定理 在极小化问题中在极小化问题中在极小化问题中在极小化问题中,对于某个基本可行解对于某个基本可行解对于某个基本可行解对于某个基本可行解,若所有检验数若所有检验数若所有检验数若所有检验数 0,0,且人工变量且人工变量且人工变量且人工变量=0,=0,则该基本可行解为最优解则该基本可行解为最优解则该基本可行解为最优解则该基本可行解为最优解.3.3.无穷多最优解判别定理无穷多最优解判别定理无穷多最优解判别定理无穷多最优解判别定理 在极小化问题中在极小化问题中在极小化问题中在极小化问题中,对于某个基本可行解对于某个基本可行解对于某个基本可行解对于某个基本可

12、行解,若所有检验数若所有检验数若所有检验数若所有检验数 0,0,又存在某个非基变量的检验数又存在某个非基变量的检验数又存在某个非基变量的检验数又存在某个非基变量的检验数=0,=0,且人工变量且人工变量且人工变量且人工变量=0,=0,则该线性则该线性则该线性则该线性 规划问题有无穷多最优解规划问题有无穷多最优解规划问题有无穷多最优解规划问题有无穷多最优解.4.4.无可行解判别定理无可行解判别定理无可行解判别定理无可行解判别定理 在极小化问题中在极小化问题中在极小化问题中在极小化问题中,对于某个基本可行解对于某个基本可行解对于某个基本可行解对于某个基本可行解,若所有检验数若所有检验数若所有检验数若

13、所有检验数 0,0,但某个人工变量但某个人工变量但某个人工变量但某个人工变量 0,0,则该线性规划问题无可行解则该线性规划问题无可行解则该线性规划问题无可行解则该线性规划问题无可行解.5 5 运筹学 2.1 2.1 单纯形法原理单纯形法原理单纯形法原理单纯形法原理三、最优性检验三、最优性检验三、最优性检验三、最优性检验判断基本可行解是否为最优解判断基本可行解是否为最优解判断基本可行解是否为最优解判断基本可行解是否为最优解3.3.无穷多最优解判别定理无穷多最优解判别定理无穷多最优解判别定理无穷多最优解判别定理 在极小化问题中在极小化问题中在极小化问题中在极小化问题中,对于某个基本可行解对于某个基

14、本可行解对于某个基本可行解对于某个基本可行解,若所有检验数若所有检验数若所有检验数若所有检验数 0,0,又存在某个非基变量的检验数又存在某个非基变量的检验数又存在某个非基变量的检验数又存在某个非基变量的检验数=0,=0,且人工变量且人工变量且人工变量且人工变量=0,=0,则该线性则该线性则该线性则该线性 规划问题有无穷多最优解规划问题有无穷多最优解规划问题有无穷多最优解规划问题有无穷多最优解.4.4.无可行解判别定理无可行解判别定理无可行解判别定理无可行解判别定理 在极小化问题中在极小化问题中在极小化问题中在极小化问题中,对于某个基本可行解对于某个基本可行解对于某个基本可行解对于某个基本可行解

15、,若所有检验数若所有检验数若所有检验数若所有检验数 0,0,但某个人工变量但某个人工变量但某个人工变量但某个人工变量 0,0,则该线性规划问题无可行解则该线性规划问题无可行解则该线性规划问题无可行解则该线性规划问题无可行解.5.5.无有限最优解无有限最优解无有限最优解无有限最优解(无界解无界解无界解无界解)判别定理判别定理判别定理判别定理 在极小化问题中在极小化问题中在极小化问题中在极小化问题中,对于某个基本可行解对于某个基本可行解对于某个基本可行解对于某个基本可行解,若存在某个非基变若存在某个非基变若存在某个非基变若存在某个非基变 量的检验数量的检验数量的检验数量的检验数0,0,但相应的列中

16、没有正元素但相应的列中没有正元素但相应的列中没有正元素但相应的列中没有正元素,且人工变量且人工变量且人工变量且人工变量=0,0,则该线性规划问题无有限最优解则该线性规划问题无有限最优解则该线性规划问题无有限最优解则该线性规划问题无有限最优解(具有无界解具有无界解具有无界解具有无界解).).6 6 运筹学 2.1 2.1 单纯形法原理单纯形法原理单纯形法原理单纯形法原理一、构造初始可行基一、构造初始可行基一、构造初始可行基一、构造初始可行基二、求出一个基本可行解二、求出一个基本可行解二、求出一个基本可行解二、求出一个基本可行解三、最优性检验三、最优性检验三、最优性检验三、最优性检验判断基本可行解

17、是否为最优解判断基本可行解是否为最优解判断基本可行解是否为最优解判断基本可行解是否为最优解2.2.最优解判别定理最优解判别定理最优解判别定理最优解判别定理3.3.无穷多最优解判别定理无穷多最优解判别定理无穷多最优解判别定理无穷多最优解判别定理4.4.无可行解判别定理无可行解判别定理无可行解判别定理无可行解判别定理四、基变换四、基变换四、基变换四、基变换1.1.换入变量的确定换入变量的确定换入变量的确定换入变量的确定 负检验数中的负检验数中的负检验数中的负检验数中的小者小者小者小者所对应的非基变量为换入变量所对应的非基变量为换入变量所对应的非基变量为换入变量所对应的非基变量为换入变量.2.2.换

18、出变量的确定换出变量的确定换出变量的确定换出变量的确定 按按按按最小非负比值最小非负比值最小非负比值最小非负比值原则确定换出变量原则确定换出变量原则确定换出变量原则确定换出变量.7 7 运筹学 2.2 2.2 单纯形法的表格形式单纯形法的表格形式单纯形法的表格形式单纯形法的表格形式四、基变换四、基变换四、基变换四、基变换1.1.换入变量的确定换入变量的确定换入变量的确定换入变量的确定 负检验数中的负检验数中的负检验数中的负检验数中的小者小者小者小者所对应的非基变量为换入变量所对应的非基变量为换入变量所对应的非基变量为换入变量所对应的非基变量为换入变量.2.2.换出变量的确定换出变量的确定换出变

19、量的确定换出变量的确定 按按按按最小非负比值最小非负比值最小非负比值最小非负比值原则确定换出变量原则确定换出变量原则确定换出变量原则确定换出变量.例例例例 用大用大用大用大MM法求解下述线性规划问题法求解下述线性规划问题法求解下述线性规划问题法求解下述线性规划问题.最优解为最优解为最优解为最优解为X X*=(1,2)=(1,2)T T,最优值为最优值为最优值为最优值为z*=-1z*=-18 8 运筹学 2.3 2.3 大大大大MM法和两阶段法法和两阶段法法和两阶段法法和两阶段法一、两阶段法一、两阶段法一、两阶段法一、两阶段法1.1.第一阶段第一阶段第一阶段第一阶段:判断原线性规划问题是否有可行

20、解判断原线性规划问题是否有可行解判断原线性规划问题是否有可行解判断原线性规划问题是否有可行解.目标函数取全部人工变量之和目标函数取全部人工变量之和目标函数取全部人工变量之和目标函数取全部人工变量之和.若最小值为若最小值为若最小值为若最小值为0,0,则转入第二则转入第二则转入第二则转入第二 阶段阶段阶段阶段.否则否则否则否则,原线性规划问题无可行解原线性规划问题无可行解原线性规划问题无可行解原线性规划问题无可行解.2.2.第二阶段第二阶段第二阶段第二阶段:求解原线性规划问题的最优解求解原线性规划问题的最优解求解原线性规划问题的最优解求解原线性规划问题的最优解.例例例例 用两阶段法求解下述线性规划

21、问题用两阶段法求解下述线性规划问题用两阶段法求解下述线性规划问题用两阶段法求解下述线性规划问题.最优解为最优解为最优解为最优解为X X*=(1,2)=(1,2)T T,最优值为最优值为最优值为最优值为z*=7z*=79 9 运筹学 2.4 2.4 退化问题退化问题退化问题退化问题一、何谓退化一、何谓退化一、何谓退化一、何谓退化 对于退化情形对于退化情形对于退化情形对于退化情形,即使存在最优解即使存在最优解即使存在最优解即使存在最优解,也可能出现也可能出现也可能出现也可能出现循环循环循环循环现象现象现象现象.二、避免循环的方法二、避免循环的方法二、避免循环的方法二、避免循环的方法1.1.摄动法摄动法摄动法摄动法2.2.勃兰特勃兰特勃兰特勃兰特(Bland)(Bland)方法方法方法方法 下标最小下标最小下标最小下标最小原则原则原则原则(两条两条两条两条)2.5 2.5 改进单纯形法改进单纯形法改进单纯形法改进单纯形法一、单纯形法的矩阵形式一、单纯形法的矩阵形式一、单纯形法的矩阵形式一、单纯形法的矩阵形式1010 运筹学 1111