Easy Simplex (AHA Simplex) Algorithm

The purpose of this research paper is to introduce Easy Simplex Algorithm which is developed by author. The simplex algorithm first presented by G. B. Dantzing, is generally used for solving a Linear programming problem (LPP). One of the important steps of the simplex algorithm is to convert all unequal constraints into equal form by adding slack variables then proceeds to basic solution. Our new algorithm i) solves the LPP without equalize the constraints and ii) leads to optimal solution definitely in lesser time. The goal of suggested algorithm is to improve the simplex algorithm so that the time of solving an LPP will be definitely lesser than the simplex algorithm. According to this Easy Simplex (AHA Simplex) Algorithm the use of Big M method is not required.

关于使用最大改进规则的对偶单纯形算法

本文举例证明了文 [3]的定理 10 - 1是错误的。

关于求线性规划初始正则解的一个新方法的注记

在线性规划问题的求解中,对基变量取负值的情形,文献[6]提出一种求初始正则解的新方法.该文对这种方法作了进一步讨论,指出它实质上是由原有单纯形法和对偶单纯形法两个阶段组成.第一阶段通过引入非负右手边向量构造辅助线性规划问题,然后用单纯形法求解这个辅助问题获得原问题的一个正则解(如果存在);第二阶段由此正则解出发,用对偶单纯形法求得原问题的最优解(如果存在).通过大规模例子对这种算法进行数值试验,结果表明它的计算效率非常低,因而对这种方法进行了改进.

关于解线性规划问题的一种半单纯形法的注记

指出某文献解线性规划问题的一种半单纯形法的定理2是错误的,给出了理论分析和实例说明.进一步分析发现,所谓的"半单纯形法"与经典的两阶段法本质上是相同的,只不过人工变量没有显示出来,枢轴列的选择准则稍有不同.为此,本文在枢轴行和枢轴列的选择上对半单纯形法(或两阶段法第一阶段)进行了改进,数值试验结果表明,改进后的单纯形算法在计算效率上明显优于半单纯形法.

求多目标线性规划妥协解的旋转迭代算法

本文应用单纯形旋转迭代算法,求解多目标线性规划的妥协解,得到满意效果。

线性规划的原始松弛——对偶MBU单纯形算法

线性最优化广泛应用于经济与管理的各个领域.对于含有等式约束的线性规划问题,单纯形算法需要构造辅助的第一阶段问题求得问题的一个可行基.本文提出了一种原始松弛—对偶MBU单纯形算法(来求解第一阶段问题).首先,忽略不等式约束构造一个原始可行的松弛子问题,再用原始单纯形法求解该子问题;然后用对偶MBU单纯形法求解第一阶段问题.通过大规模数值试验对这种算法进行计算检验,数值结果表明,与经典单纯形算法相比,本文所提出的算法简便可行且具有更高的计算效率.

关于“单纯形法选择进出基变元的一个新准则”的计算效率

线性规划广泛应用于经济与管理的各个领域,单纯形法是求解线性规划实际问题非常有效的算法.对"单纯形法选择进出基变元的一个新准则"进行了分析,给出了详细的算法步骤,通过大规模的数值试验进一步揭示了该算法的计算效率.结果表明,这种改进的单纯形算法虽然在大部分问题上的迭代次数比经典的单纯形算法有所减少,但所耗费的计算时间却普遍增加,其计算效率随着问题规模的增大而不断下降.

一类非凸优化问题的遗传算法

线性二层规划是一类特殊的非凸优化问题,为了有效求解该问题,提出了一种基于单纯形方法的遗传算法。首先基于下层约束给出了一种新的编码方法;其次利用单纯形表的信息得到了下层问题的解函数,并结合最优性条件给出了适应度函数;最后基于个体编码的特点,设计了新的遗传算子。数值结果表明,所提出的算法是可行有效的。

关于“线性规划的符号跟踪算法”的注记

指出"线性规划的符号跟踪算法"实际上是第一阶段单纯形算法的一种变式,所获得的初始基有4种可能情况,并通过反例进行了说明。由此初始基出发,为使符号跟踪算法能正常运行下去,对该算法的步骤作了修正和补充。为了进一步验证符号跟踪算法的计算性能,通过MATLAB编程在计算机上实现大规模数值试验。结果表明,与经典单纯形算法相比,符号跟踪算法平均每次迭代花费更多的执行时间,计算效率较低。

对偶单纯形两阶段法

在用对偶单纯形法解线性规划问题时,必须找到初始正则解.为避免人工约束的引入,利用变量代换,给出不增加变量个数的对偶单纯形两阶段法.

Curet原始-对偶单纯形算法的推广

Curet原始-对偶单纯形算法的实质是在保持对偶可行性的前提下求解一系列原始松驰子问题,因此它必须有一个初始对偶可行解来启动.对于原问题目标函数存在负的价值系数的情形,提出引入人工约束通过简单的初等行变换产生新的目标函数,获得相应的对偶可行解,然后应用Curet原始-对偶单纯形算法获得问题的一个原始可行解.为了使这个原始可行解更接近最优解,在每次迭代中都对新的目标函数进行修正以逐步逼近原目标函数.在该基础上,通过实现互补松弛条件来取得问题的最优解.大规模数值试验结果表明,与经典两阶段单纯形算法相比,提出的算法在大部分问题上使用更少的迭代次数和执行时间,因而这种推广是有价值的.

线性规划的原有松弛-对偶单纯形算法

针对线性规划的单纯形算法中出现不可行基的情形,提出了一种原有松弛-对偶单纯形算法.忽略不可行基变量相应的约束构造一个原有可行的松弛子问题,根据最钝角原理作了进一步松弛,用原有单纯形法求解该子问题,然后用对偶单纯形法求解原问题.通过大规模数值试验对这种算法进行计算检验.结果表明,与经典单纯形算法相比,提出的算法简便且具有更高的计算效率.

全方位搜索的亚基迭代算法

文章改进了单纯形算法中的进基规则和迭代方式，与原始单纯形算法相比，能够有效地减少迭代次数。

一种求线性规划问题的初始基本可行解的新方法

单纯形法是求解线性规划问题的有效方法。本文给出用初等行变换求线性规划问题的初始基本可行解的新方法 ,该方法与传统的方法相比 ,具有计算量小且占用存储空间少的特点 。

线性规划问题的一解双优性

本文研究了线性规划问题的目标函数与约束条件互换的问题,给出了一解双优的结论.即:若目标函数在X^((h))点取得最大值c.且约束条件过X^((h))点,当二者互换后,得新规划问题的目标函数在X^((h))点必取得最小值b_k:反之,若原目标函数在X^((h))点取得最小值c.则互换后,新的目标函数在X^((h))点必取得最大值b_k.

线性规划通用解法──混合单纯形方法

在求解线性规划的单纯形方法和对偶单纯形方法原理的基础上，建立了求解线性规划的通用解法——混合单纯形方法。

A NEW ALGORITHM FOR PURX O-1 LINEAR PROGRAMS WITH INEQUALITY CONSTRAINTS

ＡＮＥＷＡＬＧＯＲＩＴＨＭＦＯＲＰＵＲＸＯ－１ＬＩＮＥＡＲＰＲＯＧＲＡＭＳＷＩＴＨＩＮＥＱＵＡＬＩＴＹＣＯＮＳＴＲＡＩＮＴＳ￥ＣＨＥＮＪｉａｎｆｅｉ（ＢｉｏｃｈｅｍｉｃａｌＥｎｇｉｎｅｅｒｉｎｇＳｔａｔｅＫｅｙＬａｂｏｒａｔｏｒｙ，Ｂｅｉｊｉｎｇ１０...

第一阶段原有单纯形和对偶单纯形算法的计算比较

线性最优化广泛应用于经济与管理的各个领域.在线性规划问题的求解中,如果一个初始基本可行解没有直接给出,则常采用经典的两阶段法求解.对含有"≥"不等式约束的线性规划问题,讨论了第一阶段原有单纯形法和对偶单纯形法两种算法形式,并根据第一阶段问题的特点提出了改进的对偶单纯形枢轴准则.最后,通过大规模数值试验对两种算法进行计算比较,结果表明,改进后的对偶单纯形算法在计算效率上明显优于原有单纯形算法.

一种原始——对偶单纯形算法的枢轴准则选择

Curet曾提出了一种有趣的原始一对偶技术,在优化对偶问题的同时单调减少原始不可行约束的数量,当原始可行性产生时也就产生了原问题的最优解.然而该算法需要一个初始对偶可行解来启动,目标行的选择也是灵活、不确定的.根据Curet的原始一对偶算法原理,提出了两种目标行选择准则,并通过数值试验进行比较和选择.对不存在初始对偶可行解的情形,通过适当改变目标函数的系数来构造一个对偶可行解,以求得一个原始可行解,再应用原始单纯形算法求得原问题的最优解.数值试验对这种算法的计算性能进行验证,通过与经典两阶段单纯形算法比较,结果表明,提出的算法在大部分问题上具有更高的计算效率.