“纯真形法”的名字是如何来的?

 admin  2020-03-31    评论

  纯真形法

  纯真形法

  simplex method

  求解线性计划后果的通用方法。纯真形是美国数学家G.B.丹齐克于1947年起首提出来的。它的实际依据是:线性计划后果的可行域是 n维向量空间Rn中的多面凸集,其最优值假设存在必在该凸集的某顶点处到达。顶点所对应的可行解称为基本可行解。纯真形法的基本思维是:先找出一个基本可行解,对它停止辨别,看可否是最优解;若不是,则依照必然规律转换到另外一改良的基本可行解,再辨别;若仍不是,则再转换,按此重复停止。因基本可行解的个数有限,故经有限次转换必能得出后果的最优解。假设后果无最优解也可用此法辨别。纯真形法的通俗解题步调可归结以下:①把线性计划后果的束缚方程组表杀青榜样型方程组,找出基本可行解作为初始基本可行解。②若基本可行解不存在,即束缚条件有抵触,则后果无解。③若基本可行解存在,从初始基本可行解作为终点,依据最优性条件和可行性条件,引入非基变量代替某一基变量,找出目标函数值更优的另外一基本可行解。④按步调3停止迭代,直到对应考验数满足最优性条件(这时候目标函数值不能再改良),即掉掉落后果的最优解。⑤若迭代过程当中发明后果的目标函数值无界,则终止迭代。

  用纯真形法求解线性计划后果所需的迭代次数主要取决于束缚条件的个数。现在通俗的线性计划后果都是应用纯真形律例范软件在计算机上求解,关于具有106个决定计划变量和104个束缚条件的线性计划后果已能在计算机上解得。

  改良纯真形法 原纯真形法不是很经济的算法。1953年美国数学家G.B.丹齐克为了改良纯真形法每次迭代中积累起来的进位误差,提出改良纯真形法。其基本步调和纯真形法大年夜致相反,主要差别是在逐次迭代中不再以高斯消去法为基础,而是由旧基阵的逆去直接计算新基阵的逆,再由此肯定考验数。如许做可以增加迭代中的积累误差,提高计算精度,同时也增加了在计算机上的存储量。

  对偶纯真形法 1954年美国数学家C.莱姆基提出对偶纯真形法。纯真形法是从原始后果的一个可行解经过迭代转到另外一个可行解,直到考验数满足最优性条件为止。对偶纯真形规律是从满足对偶可行性条件出发经过迭代逐渐搜刮原始后果的最优解。在迭代过程当中一直保持基解的对偶可行性,而使不成行性逐渐消失。设原始后果为min{cx|Ax=b,x≥0},则其对偶后果为 max{yb|yA≤c}。当原始后果的一个基解满足最优性条件时,其考验数cBB-1A-c≤0。即知y=cBB-1(称为纯真形算子)为对偶后果的可行解。所谓满足对偶可行性,即指其考验数满足最优性条件。因此在保持对偶可行性的条件下,一当基解成为可行解时,便也就是最优解。


上一篇:SEO分类:白帽SEO,黑帽SEO,灰帽SEO,绿帽SEO
下一篇:没有了
版权信息
永久链接://a/xw/20200331-69.html
转载请注明转自》沙巴体育网址“纯真形法”的名字是如何来的?
    相关文章