基于最钝角规则的亏基对偶单纯形Ⅰ阶段算法

对偶单纯形算法或原始对偶单纯形算法都需要一个初始对偶可行基.就此目的而言,基于最钝角行主元规则的对偶Ⅰ阶段算法非常有效[15].本文将其思想应用于亏基情形,建立一个不含比值检验的新的亏基对偶Ⅰ阶段算法.初步的数值实验表明,该算法可在总体上减少运行时间和迭代次数,极具竞争性.

传统选主元规则的变形及其在亏基方法中的应用

从几何直观入手,对传统单纯形两阶段方法加以分析,得到了变形传统选主元规则的思想和动态选主元策略的思想,并将两种思想在亏基架构下加以实现。由此给出了三种具有动态选主元策略的变形的选主元规则及其相应的亏基算法。数值试验结果表明,两种思相具有可行性。

有界变量亏基单纯形算法(英文)

为克服单纯形算法中退化现象带来的困扰,本文在文[1]的基础上进一步提出亏基有界变量单纯形算法,并证明了算法的收敛性。

亏基单纯形法的计算研究(英文)

报道了亏基单纯形法的计算研究结果 ,初步数值计算结果表明 ,在亏基情形下 ,利用

基于摄动的亏基对偶单纯形算法

将摄动对偶单纯形算法和亏基算法相结合,不仅为亏基的对偶单纯形算法提供了一个初始对偶可行基,还能有效的克服退化现象,并用matlab编制程序对22个标准NETLIB问题进行数值试验数值,结果表明,该算法可在总体上减少迭代次数,极具竞争性.

求解线性规划的亏基单人工变量大M算法

该文提出了求解线性规划问题的一种有效算法-亏基单人工变量大M算法。新算法主要建立在亏基思想的基础进行,不单只需引进单人工变量且是一阶段的,在此基础上研究了如何提前判别原问题的不可行性。理论和实例的结果都表明可以提高计算的效率。

基于最钝角主元标规则的亏基算法

在最钝角原理基础上建立了新的主元标规则,它按最钝角原理赋予一组非基本变量较高优先权,先在其中选择进基变量,直到其相应的检验数均满足符号条件;如果此时剩下的检验数均已满足条件,则已达到最优.在亏基架构中引入新的主元规则,能有效地减少每次迭代可选的非基变量的个数.数值试验表明,新算法的效率优于亏基原始单纯形算法,表明了最钝角原理的可行性和有效性.

基于亏基的最陡边主元标算法

在最陡边规则的基础上建立了新的主元标规则,并将其应用到亏基情形,在亏基的框架下建立了一个新的求对偶可行基的算法,数值结果表明,新算法能够减少迭代次数,算法效率较高,并且对于大规模问题的求解具有潜在优势,进一步表明了最陡边主元规则的可行性和有效性.

基于最陡边规则的亏基对偶Ⅰ阶段算法

将摄动算法和亏基原始单纯形算法相结合,采用最陡边的列主元规则,以充分发挥这两种算法的优势,从而为亏基对偶单纯形算法提供一个新的I阶段算法,以使其进一步克服了退化所带来的困扰.初步的数值试验表明,所提出的算法能有效地减少总迭代次数,其效率不仅远远优于传统的原始两阶段单纯形算法,且优于原有的亏基原始单纯形算法,是一个非常吸引人而充满希望的新尝试.

基于亏基的摄动原始单纯形Ⅰ阶段算法

通过摄动技术来使问题强制获得对偶可行性,执行亏基对偶单纯形算法得到一个原始可行基,并采用修正的主元规则,以充分发挥这两种算法的优势,从而为亏基原始单纯形算法提供一个新的I阶段算法,以使其进一步克服退化所带来的困扰.初步的数值试验表明,亏基和摄动两种算法优势的结合,能有效地克服退化的影响,能有效地减少总迭代次数和运行时间,其效率远远优于传统两阶段单纯形算法.

无比值检验的亏基原始Ⅰ阶段算法

首次将亏基和无比值检验列主元规则相结合,执行亏基对偶单纯形算法得到一个原始可行基,以充分发挥这两种算法的优势,从而为亏基原始单纯形算法提供一个新的I阶段算法,以使其进一步克服退化所带来的困扰.数值试验表明,亏基和无比值主元规则的结合,能有效地减少总迭代次数和运行时间,其效率远远优于传统两阶段单纯形算法.

基于LU分解的亏基摄动对偶Ⅰ阶段算法

将摄动算法和亏基单纯形算法相结合,以充分发挥这两种算法的优势,从而为亏基对偶单纯形算法提供一个新的Ⅰ阶段算法,以使其进一步克服退化所带来的困扰.数值试验结果表明,新算法能够降低退化带来的不良影响,减少总迭代次数和运算时间,其效率不仅远远优于传统的单纯形算法,且优于原有的亏基单纯形算法,是一个非常吸引人且充满希望的新尝试.