"求线性规划问题可行基的一种方法"的再注记

文[1]给出一个求线性规划问题可行基的方法，文[2]指出其判定条件（3）有误，然而所用的反例并不正确。本文给出三个正确的反例；此外，还给出反例表明文[1]的判定条件（2）也不正确的。     

线性规划求基可行解的一种方法

本文通过增加一个特殊约束，贯彻对偶单纯形法检验数全非正的思想，迭代求优；然后再去掉该约束，结果却可得到一个基可行解。上述过程经简化处理后，增减约束可以不必出现，它仅使单纯形表矩阵增加几次初等变换而已，足见其方法之简捷及有效性。     

直接求线性规划可行基的一种方法

本文给出直接求线性规划问题基可行解的一种简易方法,该方法既避免了引入人工变量,减少存储,一般又能较快地得到一个较好的基可行解.     

关于求线性规划初始可行基的生成算法

本文用反例证明了文「１」提出的求线性规划寝可行基的生成算法有错误,并给出了修正的生成算法。     

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

Smale 证明了采用单纯形法求解线性规划问题,在概率平均意义下转轴次数为变量数目的线性函数.下面介绍不引进人工变量,直接由所给问题的标准形式     

一类线性规划问题初始可行基产生的新方法

本对一类特殊的线性规划问题提出了利用最优基的启发性刻划产生初始基,进而用无比检验规则产生初始可行基的方法,并给出了此方法在单纯形表上实现的步骤。     

避免引入人工变量求线性规划可行基的一个新方法

讨论了线性规划的单纯形解法,给出了不须加人工变量就可得到一个可行基的算法.通过大量的算例表明此法比传统的单纯形方法具有算法结构简单,计算量小的优点.     

线性规划的目标函数最速递减算法

在对偶单纯形方法的基础上，提出了线性规划的目标函数最速递减算法。它避开求初始可行基或初始基，以目标函数全局快速递减作为选基准则，将选基过程与换基迭代合二为一，从而大大减少了迭代次数。数值算例显示了该算法的有效性和优越性。     

线性规划的最钝角松弛算法

本文提出一个基于最钝角原理的松弛算法求解线性规划问题。该算法依据最钝角原理略去部分约束得到一个规模较小的子问题,用原始单纯形算法解之;再添加所略去的约束恢复原问题,若此时全部约束条件均满足则已获得一个基本最优解,否则用对偶单纯形算法继续求解。初步的数值试验表明,新算法比传统两阶段单纯形算法快得多。     

与"求线性规划问题可行基的一种方法"的再商榷

再次说明文[1]提出的方法不能直接使用，仍须按文[2]的修正结果实行才是正确的。同时指出最近提出的某些算法的不实之处，以飨读者，避免误导。     

基于遗传算法的二层线性规划问题的求解算法

本研究了下层以最优解返回上层的二层线性规划问题的遗传算法。在提出可行度概念的基础上，构造了二层线性规划上层规划问题的适应度函数，由此设计了求解二层线性规划问题遗传算法。为了提高遗传算法处理约束的能力，在产生初始种群时将随机产生的初始种群变为满足约束的初始种群，从而避免了使用罚函数处理约束带来的困难，最后用实例验证了本提出的二层线性规划的遗传算法的有效性。     

含自由变量LP问题的改进单纯形法

对于含自由变量的LP问题,为了得到比单纯形法[1]更有效的算法,通过研究在单纯形法迭代过程中,将自由变量化为非负变量再实施运算的规律,提出一种能节省存贮空间和提高运算速度的改进单纯形法。数值实验表明新算法是有效的。     

A Dual Projective Pivot Algorithm for Linear Programming

Recently, a linear programming problem solver, called dual projective simplex method, was proposed (Pan, Computers and Mathematics with Applications, vol. 35, no. 6, pp. 119–135, 1998). This algorithm requires a crash procedure to provide an initial (normal or deficient) basis. In this paper, it is recast in a more compact form so that it can get itself started from scratch with any dual (basic or nonbasic) feasible solution. A new dual Phase-1 approach for producing such a solution is proposed. Reported are also computational results obtained with a set of standard NETLIB problems.     

线性规划两阶段法的改进算法

将单纯形法与对偶单纯形法及其思想结合运用,对两阶段法引进人工变量的方式进行了改进,探索出一种最多引入一个人工变量,即可求得线性规划初始可行基的新算法,能有效地节约计算机的存储量和计算量。     

Maximum Feasibility Problem for Continuous Linear Inequalities with Applications to Fuzzy Linear Programming

Systems of linear inequalities are important tools to formulate optimization problems. However, the feasibility of the whole system was often presumed true in most models. Even if an infeasible system could be detected, it is in general not easy to tell which part of the system caused it. This motivates the study of continuous linear inequalities, given no information whether it is feasible or not, what is the largest possible portion of the system that can be remained in consistency? We first propose a bisection-based algorithm which comes with an auxiliary program to answer the question. For further accelerating the algorithm, several novel concepts, one called “constraint weighting” and the other called “shooting technique”, are introduced to explore intrinsic problem structures. This new scheme eventually replaces the bisection method and its validity can be justified via a solid probabilistic analysis. Numerical examples and applications to fuzzy inequalities are reported to illustrate the robustness of our algorithm.     

线性双层规划的改进PCP全局求解算法

本文采用K-T条件将线性双层规划模型改写为单层规划后,将参数引入上层目标函数,构造了含参线性互补问题(PLCP)并给出它的一些性质。进而通过改进Lemke算法的进基规则,在保持互补旋转算法原有优势的基础上,引入充分小正数ε,设计了改进参数互补旋转(PCP)算法求取全局最优解,最后通过两个算例说明了其有效性。     

基于凹性割的线性双层规划全局优化算法

通过对线性双层规划下层问题对偶间隙的讨论,定义了一种凹性割,利用该凹性割的性质,给出了一个求解线性双层规划的割平面算法。由于线性双层规划全局最优解可在其约束域的极点上达到,提出的算法能求得问题的全局最优解,并通过一个算例说明了算法的有效性。     

Certificates of Primal or Dual Infeasibility in Linear Programming

In general if a linear program has an optimal solution, then a primal and dual optimal solution is a certificate of the solvable status. Furthermore, it is well known that in the solvable case, then the linear program always has an optimal basic solution. Similarly, when a linear program is primal or dual infeasible then by Farkas's Lemma a certificate of the infeasible status exists. However, in the primal or dual infeasible case then there is not an uniform definition of what a suitable basis certificate of the infeasible status is.In this work we present a definition of a basis certificate and develop a strongly polynomial algorithm which given a Farkas type certificate of infeasibility computes a basis certificate of infeasibility. This result is relevant for the recently developed interior-point methods because they do not compute a basis certificate of infeasibility in general. However, our result demonstrates that a basis certificate can be obtained at a moderate computational cost.     

线性规划问题的规范型算法

提出了线性规划问题的两种规范标准形式；证明了任意一个线性规划问题都可化为这两种形式之一；给出了不需引入人工变量的线性规划问题的求解算法。     

Solving Bilevel Linear Programs Using Multiple Objective Linear Programming

We present an algorithm for solving bilevel linear programs that uses simplex pivots on an expanded tableau. The algorithm uses the relationship between multiple objective linear programs and bilevel linear programs along with results for minimizing a linear objective over the efficient set for a multiple objective problem. Results in multiple objective programming needed are presented. We report computational experience demonstrating that this approach is more effective than a standard branch-and-bound algorithm when the number of leader variables is small.