共查询到20条相似文献,搜索用时 984 毫秒
1.
2.
本通过分析两用阶段法求解线性规划初始可行解的一个例子,归纳了线性规划问题退化的最优基可行解的性质,包括同一退化最优基可行解不同表示,有无穷多最优解的表示。 相似文献
3.
本文引入契贝晓夫多项式作为基函数,利用Galerkin方法研究了一类Fredholm-Volterra积分方程的数值解,并进行了数值模拟.结果表明,该方法可行且有效. 相似文献
4.
5.
6.
本文指出两点:1.按照最速下降规则确定进基和离基变量,既能避免迭代循环,又常减少迭代次数;2.可不直接引入人工变量求初始基可行解,并从一开始就考虑按一定意义下使原目标函数下降最多的原则选择基变量,使得到的初始基可行解尽可能的好。 1.关于最速下降规则设所论线性规划问题由表1给出: 最速下降规则可叙述如下: (A)设R={j|λ_j>0},对每一j∈R,计算 相似文献
7.
求基可行解一种概率意义下的多项式算法 总被引:4,自引:0,他引:4
本文对求线性规划问题的基可行解,给出一种改型算法,证明它对m个约束、n个变量的问题,当n≥2m时,为使求得一个基可行解的概率大于0.98,对m>24,所需迭代次数不超过(m+3),而对m≥76,迭代次数已不超过(m+1). 相似文献
8.
9.
10.
单纯形法的旋转迭代算法及影子价格 总被引:4,自引:3,他引:1
本文对线性规划问题提出一种寻找初始可行基和判定可行解的统一方法,它在运用单纯形法时,在若干情况下不必引入人工变量而可在一种表格之下直接应用旋转运算而获得,之后就在同一张表格下完全和常规单纯形法一样求最优解,此法我们称之为“单纯形法的旋转迭代算法”,应用此法,我们容易求出影子价格。 相似文献
11.
M. C. Cheng 《Mathematical Programming》1980,19(1):230-236
The standard linear programming problem with a finite optimum value is considered. We derive new criteria which guarantee that(i) a non-basic variable of a basic feasible solution will remain a non-basic variable of an optimal basic solution; (ii) a basic variable of a basic feasible solution will remain a basic variable of an optimal basic solution. 相似文献
13.
《Optimization》2012,61(8):1283-1295
In this article we present the fundamental idea, concepts and theorems of a basic line search algorithm for solving linear programming problems which can be regarded as an extension of the simplex method. However, unlike the iteration of the simplex method from a basic point to an improved adjacent basic point via pivot operation, the basic line search algorithm, also by pivot operation, moves from a basic line which contains two basic feasible points to an improved basic line which also contains two basic feasible points whose objective values are no worse than that of the two basic feasible points on the previous basic line. The basic line search algorithm may skip some adjacent vertices so that it converges to an optimal solution faster than the simplex method. For example, for a 2-dimensional problem, the basic line search algorithm can find an optimal solution with only one iteration. 相似文献
14.
We discuss a finite method of a feasible direction for linear programming problems. The method begins with a feasible basic vector for the problem, constructs a profitable direction to move using the updated column vectors of the nonbasic variables eligible to enter this basic vector. It then moves in this direction as far as possible, while retaining feasibility. This move in general takes it though the relative interior of a face of th set of a feasible solutions. The final point, , obtained at the end of this move will not in general be a basic solution. Using the method then constructs a basic feasible solution at which the objective value is better than, or the same as that at . The whole process repeats with the new basic feasible solution. We show that this method can be implemented using basis inverses. Initial computer runs of this method in comparison with the usual edge following primary simplex algorithms are very encouraging. 相似文献
15.
L. Brosius 《Mathematical Programming》1981,21(1):229-232
In a recent paper M.C. Cheng proposed new criteria for the simplex algorithm which guarantee that (i) a nonbasic variable of a basic feasible solution will remain nonbasic in an optimal basic solution, (ii) a basic variable of a basic solution will remain basic in an optimal basic solution. This comment gives (i) a slight generalization of the first result and (ii) a counterexample to the second proposition. 相似文献
16.
The simplex method, created by George Dantzig, optimally solves a linear program by pivoting. Dantzig’s pivots move from a basic feasible solution to a different basic feasible solution by exchanging exactly one basic variable with a nonbasic variable. This paper introduces the double pivot simplex method, which can transition between basic feasible solutions using two variables instead of one. Double pivots are performed by identifying the optimal basis in a two variable linear program using a new method called the slope algorithm. The slope algorithm is fast and allows an iteration of DPSM to have the same theoretical running time as an iteration of the simplex method. Computational experiments demonstrate that DPSM decreases the average number of pivots by approximately 41% on a small set of benchmark instances. 相似文献
17.
A class of methods is presented for solving standard linear programming problems. Like the simplex method, these methods move from one feasible solution to another at each iteration, improving the objective function as they go. Each such feasible solution is also associated with a basis. However, this feasible solution need not be an extreme point and the basic solution corresponding to the associated basis need not be feasible. Nevertheless, an optimal solution, if one exists, is found in a finite number of iterations (under nondegeneracy). An important example of a method in the class is the reduced gradient method with a slight modification regarding selection of the entering variable. 相似文献
18.
A. Ebrahimnejad 《Applied Mathematical Modelling》2011,35(9):4526-4540
In a recent paper, Ganesan and Veermani [K. Ganesan, P. Veeramani, Fuzzy linear programs with trapezoidal fuzzy numbers, Ann. Oper. Res. 143 (2006) 305–315] considered a kind of linear programming involving symmetric trapezoidal fuzzy numbers without converting them to the crisp linear programming problems and then proved fuzzy analogues of some important theorems of linear programming that lead to a new method for solving fuzzy linear programming (FLP) problems. In this paper, we obtain some another new results for FLP problems. In fact, we show that if an FLP problem has a fuzzy feasible solution, it also has a fuzzy basic feasible solution and if an FLP problem has an optimal fuzzy solution, it has an optimal fuzzy basic solution too. We also prove that in the absence of degeneracy, the method proposed by Ganesan and Veermani stops in a finite number of iterations. Then, we propose a revised kind of their method that is more efficient and robust in practice. Finally, we give a new method to obtain an initial fuzzy basic feasible solution for solving FLP problems. 相似文献
19.
In this article,the authors discuss the optimal conditions of the linear fractional programming problem and prove that a locally optional solution is a globally optional so- lution and the locally optimal solution can be attained at a basic feasible solution with constraint condition. 相似文献
20.
We present an exterior point simplex type algorithm that possesses a new monotonic property. A dual feasible basic solution is required to start with. Intermediate solutions are neither primal nor dual feasible. Cycling-free pivoting rules and an exponentional example are presented. 相似文献