线性规划问题退化最优基可行解的性质

本通过分析两用阶段法求解线性规划初始可行解的一个例子,归纳了线性规划问题退化的最优基可行解的性质,包括同一退化最优基可行解不同表示,有无穷多最优解的表示。     

关于<用初等行变换解一类线性规划问题>一文的注记

本指出，在献[1]提出的求解线性规划的方法中，对于初始可行基、最优解和零解的存在性问题所得出的某些结论是错误的，特殊是如果含n个变量的约束条件的增广矩阵经初等行变换后，其中某行的前n个分量非正，而最后一个分量为0时，应认为该线性规划问题可能有非零解，且不一定存在零解，而非[1]所述的结论。     

线性规划问题的一种求解算法

本通过初等变换，并剔除常变量和零变量而对所给的线性规划问题进行预处理，得到的等价问题不仅易找初始可行基且初始可行解较优，易差别无可行解情形，而且可能使所含方程个数与变量个数减少，从而减少了求解问题的计算量和迭代次数。     

用初等行变换解一类线性规划问题

本文对用矩阵的初等行变换，求线性规划的初始可行基问题，作了初步探讨。最后用两个例子验证了所提方法是简便易行的。标准型的线性规划问题（以下简称问题）的一般解法是单纯形法，当问题无初始可行基时，由于换基迭代，需要先求一个初始可行基本文直接用矩阵的初等行变换（简称“行变换法”）求解，简便易行。     

用初等行变换解一类线性规划问题

本文对用矩阵的初等行变换求线性规划的无初始可行基问题进行了探讨,并用实例验证了所述方法是简便易行的。     

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

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

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

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

对单纯形算法的两点改进意见

本文指出两点:1.按照最速下降规则确定进基和离基变量,既能避免迭代循环,又常减少迭代次数;2.可不直接引入人工变量求初始基可行解,并从一开始就考虑按一定意义下使原目标函数下降最多的原则选择基变量,使得到的初始基可行解尽可能的好。 1.关于最速下降规则设所论线性规划问题由表1给出: 最速下降规则可叙述如下: (A)设R={j|λ_j>0},对每一j∈R,计算     

单纯形法的旋转迭代算法及影子价格

本文对线性规划问题提出一种寻找初始可行基和判定可行解的统一方法，它在运用单纯形法时，在若干情况下不必引入人工变量而可在一种表格之下直接应用旋转运算而获得，之后就在同一张表格下完全和常规单纯形法一样求最优解，此法我们称之为“单纯形法的旋转迭代算法”，应用此法，我们容易求出影子价格。     

浅析大M法与两阶段法的一致性

分析了大M法与两阶段法在思想方法、辅助线性规划问题的构造、初始可行基、初始单纯形表、最优性检验和算法步骤等方面的一致性.     

优化方法解决无上层约束的线性双层规划问题

In this paper we propose an optimal method for solving the linear bilevel programming problem with no upper-level constraint. The main idea of this method is that the initial point which is in the feasible region goes forward along the optimal direction firstly. When the iterative point reaches the boundary of the feasible region, it can continue to go forward along the suboptimal direction. The iteration is terminated until the iterative point cannot go forward along the suboptimal direction and effective direction, and the new iterative point is the solution of the lower-level programming. An algorithm which bases on the main idea above is presented and the solution obtained via this algorithm is proved to be optimal solution to the bilevel programming problem. This optimal method is effective for solving the linear bilevel programming problem.     

Deriving the Properties of Linear Bilevel Programming via a Penalty Function Approach

For the linear bilevel programming problem, we propose an assumption weaker than existing assumptions, while achieving similar results via a penalty function approach. The results include: equivalence between (i) existence of a solution to the problem, (ii) existence of an exact penalty function approach for solving the problem, and (iii) achievement of the optimal value of the equivalent form of the problem at some vertex of a certain polyhedral convex set. We prove that the assumption is both necessary and sufficient for the linear bilevel programming problem to admit an exact penalty function formulation, provided that the equivalent form of the problem has a feasible solution. A method is given for computing the minimal penalty function parameter value. This method can be executed by solving a set of linear programming problems. Lagrangian duality is also presented.     

自对偶嵌入模型解拓展熵规划

本文把拓展熵规划转化为锥最优化问题,再对该锥最优化问题构造一个锥自对偶嵌入模型,证明了锥自对偶嵌入模型的障碍函数满足自协调性,这保证了用某些内点法求解时算法是多项式时间的.这种方法的另一个优点是不需要寻找初始可行解.     

线性规划中大M法的参数M估值问题

在线性规划的单纯形法中,为求初始的可行基有著名的大M法,即惩罚因子法.在通常的运筹学教材中,只说明当M充分大时,大M法是有效的,并没有给出参数M的确切估计值.现给出一个确定的常数M0,并证明当M>M0时,大M法收敛于原问题的最优解.     

Reducing quadratic programming problem to regression problem: Stepwise algorithm

Quadratic programming is concerned with minimizing a convex quadratic function subject to linear inequality constraints. The variables are assumed to be nonnegative. The unique solution of quadratic programming (QP) problem (QPP) exists provided that a feasible region is non-empty (the QP has a feasible space).A method for searching for the solution to a QP is provided on the basis of statistical theory. It is shown that QPP can be reduced to an appropriately formulated least squares (LS) problem (LSP) with equality constraints and nonnegative variables. This approach allows us to obtain a simple algorithm to solve QPP. The applicability of the suggested method is illustrated with numerical examples.     

Numerical solution of positive control problem via linear programming

The reachability problem for linear time-invariant discrete-time control systems with sign-restricted input is considered. The time-optimal control is constructed by an iterative procedure. Each step of the iteration is defined as a linear programming problem. This problem is solved by the simplex algorithm. The initial feasible solution for the simplex algorithm is provided by the preceding step of the iteration. The inversion of the basis matrix is reduced to a bordering procedure. The structural stability of the solution is investigated.     

Improved integer programming bounds using intersections of corner polyhedra

Consider the relaxation of an integer programming (IP) problem in which the feasible region is replaced by the intersection of the linear programming (LP) feasible region and the corner polyhedron for a particular LP basis. Recently a primal-dual ascent algorithm has been given for solving this relaxation. Given an optimal solution of this relaxation, we state criteria for selecting a new LP basis for which the associated relaxation is stronger. These criteria may be successively applied to obtain either an optimal IP solution or a lower bound on the cost of such a solution. Conditions are given for equality of the convex hull of feasible IP solutions and the intersection of all corner polyhedra.     

A path following method for box-constrained multiobjective optimization with applications to goal programming problems

We propose a path following method to find the Pareto optimal solutions of a box-constrained multiobjective optimization problem. Under the assumption that the objective functions are Lipschitz continuously differentiable we prove some necessary conditions for Pareto optimal points and we give a necessary condition for the existence of a feasible point that minimizes all given objective functions at once. We develop a method that looks for the Pareto optimal points as limit points of the trajectories solutions of suitable initial value problems for a system of ordinary differential equations. These trajectories belong to the feasible region and their computation is well suited for a parallel implementation. Moreover the method does not use any scalarization of the multiobjective optimization problem and does not require any ordering information for the components of the vector objective function. We show a numerical experience on some test problems and we apply the method to solve a goal programming problem.     

Modification of Karmarkar’s projective scaling algorithm

This paper presents a new conversion technique of the standard linear programming problem into a homogenous form desired for the Karmarkar’s algorithm, where we employed the primal–dual method. The new converted linear programming problem provides initial basic feasible solution, simplex structure, and homogenous matrix. Apart from the transformation, Hooker’s method of projected direction is employed in the Karmarkar’s algorithm and the modified algorithm is presented. The modified algorithm has a faster convergence with a suitable choice of step size.