九乡新闻网肯德基优惠券打印版:单纯形法
来源：百度文库 编辑：九乡新闻网 时间：2024/04/27 15:11:57
单纯形法的提出及依据[1]
单纯形法是美国数学家George Dantzig于1947年首先提出的。 其理论根据是：线性规划问题的可行域是n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到，该顶点所对应的可行解称为基本可行解。 [编辑]单纯形法的基本思想
单纯形法是一种多变量函数的寻优方法，其主要思想是先找一个基本可行解，判断是否为最优解，如果不是则找另外一个解，再进行判定，如此迭代运算，直至找到最优解或者判定其无界。 [编辑]单纯形法的特点
单纯形法是一种直接、快速的搜索最小值方法，其优点是对目标函数的解析性没有要求，收敛速度快，适用面较广。 单纯形法的一般解题步骤可归纳如下： 1.把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。 2.若基本可行解不存在，即约束条件有矛盾，则问题无解。 3.若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。 4.按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。 5.若迭代过程中发现问题的目标函数值无界，则终止迭代。 [编辑]改进的单纯形法[2]
原单纯形法不是很经济的算法。1953年美国数学家G.B.丹齐克为了改进单纯形法每次迭代中积累起来的进位误差，提出改进单纯形法。其基本步骤和单纯形法大致相同，主要区别是在逐次迭代中不再以高斯消去法为基础，而是由旧基阵的逆去直接计算新基阵的逆，再由此确定检验数。这样做可以减少迭代中的累积误差，提高计算精度，同时也减少了在计算机上的存储量。 改进的单纯形法是在单纯形操作中引入变异操作，以此来增强全局搜索能力。具体做法是： 首先，进行基本单纯形法操作，快速得到局部极小值，再对极小值点在取值范围内进行变异操作，并重新进行基本单纯形法操作，直到得到最优解为止。该算法的计算步骤如下： (1)选取初始单纯形，初始步长L，最大变异次数mmax，计数器m=0； (2)进行基本单纯形操作，找到一个极值点X1； (3)以极值点置作新的顶点，再选取初始单纯形，并进行新一轮的单纯形操作，得到新的极值点，两极值点对应的目标函数为R1,R2； (4)若R1 > R2,R1 = R2,X1 = X2, 代入： (i=1,2,…,t)(1) 式中，Ximax、Ximin为参数X_i的上、下限；为0到1之间的随机数。 (5)若，对进行变异操作，计数器m=m+1： (6)若计数器m < mmax，转(1)，否则输出结果X1。 [编辑]参考文献
↑ 刘勇,陈国东.基于单纯形法的LINGO求解一般指派问题的探讨[J].中国管理信息化.2008(6)
↑ 李春风,许承权,蒲文利.改进的单纯形法及其在非线性参数估计中的应用[J].海洋测绘,2009,29(6)
单纯形法是美国数学家George Dantzig于1947年首先提出的。 其理论根据是：线性规划问题的可行域是n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到，该顶点所对应的可行解称为基本可行解。 [编辑]单纯形法的基本思想
单纯形法是一种多变量函数的寻优方法，其主要思想是先找一个基本可行解，判断是否为最优解，如果不是则找另外一个解，再进行判定，如此迭代运算，直至找到最优解或者判定其无界。 [编辑]单纯形法的特点
单纯形法是一种直接、快速的搜索最小值方法，其优点是对目标函数的解析性没有要求，收敛速度快，适用面较广。 单纯形法的一般解题步骤可归纳如下： 1.把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。 2.若基本可行解不存在，即约束条件有矛盾，则问题无解。 3.若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。 4.按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。 5.若迭代过程中发现问题的目标函数值无界，则终止迭代。 [编辑]改进的单纯形法[2]
原单纯形法不是很经济的算法。1953年美国数学家G.B.丹齐克为了改进单纯形法每次迭代中积累起来的进位误差，提出改进单纯形法。其基本步骤和单纯形法大致相同，主要区别是在逐次迭代中不再以高斯消去法为基础，而是由旧基阵的逆去直接计算新基阵的逆，再由此确定检验数。这样做可以减少迭代中的累积误差，提高计算精度，同时也减少了在计算机上的存储量。 改进的单纯形法是在单纯形操作中引入变异操作，以此来增强全局搜索能力。具体做法是： 首先，进行基本单纯形法操作，快速得到局部极小值，再对极小值点在取值范围内进行变异操作，并重新进行基本单纯形法操作，直到得到最优解为止。该算法的计算步骤如下： (1)选取初始单纯形，初始步长L，最大变异次数mmax，计数器m=0； (2)进行基本单纯形操作，找到一个极值点X1； (3)以极值点置作新的顶点，再选取初始单纯形，并进行新一轮的单纯形操作，得到新的极值点，两极值点对应的目标函数为R1,R2； (4)若R1 > R2,R1 = R2,X1 = X2, 代入： (i=1,2,…,t)(1) 式中，Ximax、Ximin为参数X_i的上、下限；为0到1之间的随机数。 (5)若，对进行变异操作，计数器m=m+1： (6)若计数器m < mmax，转(1)，否则输出结果X1。 [编辑]参考文献
↑ 刘勇,陈国东.基于单纯形法的LINGO求解一般指派问题的探讨[J].中国管理信息化.2008(6)
↑ 李春风,许承权,蒲文利.改进的单纯形法及其在非线性参数估计中的应用[J].海洋测绘,2009,29(6)