§2.1 单纯形法原理

《§2.1 单纯形法原理》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、§2.1单纯形法原理一、构造初始可行基▲1947年,美国数学家丹捷格提出了求解线性规划的单纯形法.1.引入附加变量,化数学模型为标准型;2.若A中含有m阶单位阵,则该单位阵即为一个初始可行基;否则,须引入人工变量,以构成初始可行基;3.目标函数中,附加变量的系数为0,人工变量的系数为M(很大的正数,称为罚因子)——大M法或罚函数法.▲以求解下述线性规划问题为例1§2.1单纯形法原理一、构造初始可行基1.引入附加变量,化数学模型为标准型;2.若A中含有m阶单位阵,则该单位阵即为一个初始可行基;否则,须引入人

2、工变量,以构成初始可行基;3.目标函数中,附加变量的系数为0,人工变量的系数为M(很大的正数,称为罚因子)——大M法或罚函数法.二、求出一个基本可行解1.用非基变量表示基变量和目标函数;2.求出一个基本可行解和相应的函数值;2§2.1单纯形法原理一、构造初始可行基二、求出一个基本可行解1.用非基变量表示基变量和目标函数;2.求出一个基本可行解和相应的函数值;三、最优性检验——判断基本可行解是否为最优解1.最优性检验的依据—检验数用非基变量表示目标函数之后,目标函数中各非基变量的系数即为非基变量的检验数.基

3、变量的检验数为0.2.最优解判别定理在极小化问题中,对于某个基本可行解,若所有检验数0,且人工变量=0,则该基本可行解为最优解.3§2.1单纯形法原理一、构造初始可行基二、求出一个基本可行解三、最优性检验——判断基本可行解是否为最优解1.最优性检验的依据—检验数2.最优解判别定理在极小化问题中,对于某个基本可行解,若所有检验数0,且人工变量=0,则该基本可行解为最优解.3.无穷多最优解判别定理在极小化问题中,对于某个基本可行解,若所有检验数0,又存在某个非基变量的检验数=0,且人工变量=0,则该线性

4、规划问题有无穷多最优解.4§2.1单纯形法原理一、构造初始可行基二、求出一个基本可行解三、最优性检验——判断基本可行解是否为最优解2.最优解判别定理在极小化问题中,对于某个基本可行解,若所有检验数0,且人工变量=0,则该基本可行解为最优解.3.无穷多最优解判别定理在极小化问题中,对于某个基本可行解,若所有检验数0,又存在某个非基变量的检验数=0,且人工变量=0,则该线性规划问题有无穷多最优解.4.无可行解判别定理在极小化问题中,对于某个基本可行解,若所有检验数0,但某个人工变量0,则该线性规划问题

5、无可行解.5§2.1单纯形法原理三、最优性检验——判断基本可行解是否为最优解3.无穷多最优解判别定理在极小化问题中,对于某个基本可行解,若所有检验数0,又存在某个非基变量的检验数=0,且人工变量=0,则该线性规划问题有无穷多最优解.4.无可行解判别定理在极小化问题中,对于某个基本可行解,若所有检验数0,但某个人工变量0,则该线性规划问题无可行解.5.无有限最优解(无界解)判别定理在极小化问题中,对于某个基本可行解,若存在某个非基变量的检验数<0,但相应的列中没有正元素,且人工变量=0,则该线性规划问

6、题无有限最优解(具有无界解).6§2.1单纯形法原理一、构造初始可行基二、求出一个基本可行解三、最优性检验——判断基本可行解是否为最优解2.最优解判别定理3.无穷多最优解判别定理4.无可行解判别定理四、基变换1.换入变量的确定负检验数中的小者所对应的非基变量为换入变量.2.换出变量的确定按最小非负比值原则确定换出变量.7§2.2单纯形法的表格形式四、基变换1.换入变量的确定负检验数中的小者所对应的非基变量为换入变量.2.换出变量的确定按最小非负比值原则确定换出变量.例用大M法求解下述线性规划问题.最优解为

7、X*=(1,2)T,最优值为z*=-18§2.3大M法和两阶段法一、两阶段法1.第一阶段:判断原线性规划问题是否有可行解.目标函数取全部人工变量之和.若最小值为0,则转入第二阶段.否则,原线性规划问题无可行解.2.第二阶段:求解原线性规划问题的最优解.例用两阶段法求解下述线性规划问题.最优解为X*=(1,2)T,最优值为z*=79§2.4退化问题一、何谓退化对于退化情形,即使存在最优解,也可能出现循环现象.二、避免循环的方法1.摄动法2.勃兰特(Bland)方法下标最小原则(两条)§2.5改进单纯形法一、

8、单纯形法的矩阵形式1011