一种改进的无人工变量单纯形算法

对Arsham的算法作了重要改进以便使其运行得更好,目标使所有基人工变量之和最小。首先,对非基变量按其简约价值系数从大到小逐列向前搜寻,将满足条件的变量带入基变量集,当简约价值系数为非正时终止。然后,以目标当前值与最优值的均值作为临界值,应用经典单纯形算法求解,当目标值超过临界值时,重复上述过程,直至基变量集处于完全状态。在计算机上对24个标准测试问题进行初步数值试验,计算结果表明,本文提出的改进算法比经典单纯形算法所用的总迭代次数要少得多,在22个问题上耗费更少的计算时间,大大改进了Arsham算法的计算效率,比Gao的一种改进算法的计算性能更稳定,因而是有价值的。

目标超平面上的一种对偶单纯形算法

提出求解第一阶段线性规划问题的对偶单纯形算法.首先,将具有最优值的辅助目标函数作为新约束加入第一阶段问题中;然后,以该约束所在行为枢轴行进行旋转变换产生辅助超平面上的一个极顶点,如果这个点可行,第一阶段对偶单纯形算法结束,否则,迭代固定在辅超平面上极行;接下来,以右手项取负值的所有约束之和为目标(约束),通过对偶迭代使右手边的值单调增加,同时保持右手项为非负的约束仍然可行,一旦右手边取负值的约束变为可行,就将其从目标约束中删除,直至获得一个可行解或者得到原问题无可行解的结论;最后,从NETLIB和MIPLIB测试数据库中选取一些标准的中大规模算例,通过MATLAB编程在计算机上实现数值试验,初步计算结果表明与经典单纯形算法相比,提出的算法在大部分问题上使用更少的迭代次数和执行时间,因而具有更高的计算效率.