线性规划初始对偶可行基本解的一种求法

运用对偶单纯形法求解线性规划问题时,需要先给定一个初始对偶可行的基本解.然而在线性规划问题的约束条件Ax=b中,矩阵A一般不含m阶单位矩阵,此时初始对偶可行的基本解不易求得.文中通过对线性规划问题增加人工变量和一个约束条件,给出一步便能求出其初始对偶可行基本解的简便方法,进而通过对偶单纯形法进行迭代解决线性规划问题.

变量有广义界线性规划的直接对偶单纯形法

本文讨论变量有广义界线性规划问题借助标准形线性规划同单纯形法技术,建立问题的一个直接对偶单纯形法。分析了方法的性质,给出了初始对偶可行基的计算方法,并用实例说明方法的具体操作。

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

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

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

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