共查询到20条相似文献,搜索用时 15 毫秒
1.
Kurt M. Anstreicher 《Algorithmica》1986,1(1):483-498
We demonstrate that Karmarkar's projective algorithm is fundamentally an algorithm for fractional linear programming on the simplex. Convergence for the latter problem is established assuming only an initial lower bound on the optimal objective value. We also show that the algorithm can be easily modified so as to assure monotonicity of the true objective values, while retaining all global convergence properties. Finally, we show how the monotonic algorithm can be used to obtain an initial lower bound when none is otherwise available. 相似文献
2.
In this paper, we obtain the solution to bi-level linear fractional programming problem (BLFP) by means of an optimization algorithm based on the duality gap of the lower level problem. In our algorithm, the bi-level linear fractional programming problem is transformed into an equivalent single level programming problem by forcing the dual gap of the lower level problem to zero. Then, by obtaining all vertices of a polyhedron, the single level programming problem can be converted into a series of linear fractional programming problems. Finally, the performance of the proposed algorithm is tested on a set of examples taken from the literature. 相似文献
3.
Ching-Feng Wen Yung-Yih Lur Sy-Ming Guu E. Stanley Lee 《Computers & Mathematics with Applications》2010,59(2):829-852
In this paper, we develop a discrete approximation method for solving continuous-time linear fractional programming problems. Our method enables one to derive a recurrence structure which shall overcome the computational curse caused by the increasing numbers of decision variables in the approximate decision problems when the subintervals are getting smaller and smaller. Furthermore, our algorithm provides estimation for the error bounds of the approximate solutions. We also establish the convergence of our approximate solutions to the continuous-time linear fractional programming problems. Numerical examples are provided to illustrate the quality of the approximate solutions. 相似文献
4.
G. Rinaldi 《Algorithmica》1986,1(1-4):517-527
A specialization of the projective method for linear programming to problems with lower and upper bounds on the variables is proposed. 相似文献
5.
G. Rinaldi 《Algorithmica》1986,1(1):517-527
A specialization of the projective method for linear programming to problems with lower and upper bounds on the variables is proposed.This work was done while the author was visiting New York University. 相似文献
6.
7.
Interest in linear programming has recently been intensified by the publication and discussion of a projective method algorithm that is not only polynomial in complexity, but is also claimed by its inventor (N. Karmarkar) to be 50–100 times faster than the simplex method. This paper provides a survey of the projective method from a computational viewpoint. 相似文献
8.
A modification of karmarkar's linear programming algorithm 总被引:3,自引:0,他引:3
We present a modification of Karmarkar's linear programming algorithm. Our algorithm uses a recentered projected gradient approach thereby obviatinga priori knowledge of the optimal objective function value. Assuming primal and dual nondegeneracy, we prove that our algorithm converges. We present computational comparisons between our algorithm and the revised simplex method. For small, dense constraint matrices we saw little difference between the two methods. 相似文献
9.
We present a modification of Karmarkar's linear programming algorithm. Our algorithm uses a recentered projected gradient approach thereby obviatinga priori knowledge of the optimal objective function value. Assuming primal and dual nondegeneracy, we prove that our algorithm converges. We present computational comparisons between our algorithm and the revised simplex method. For small, dense constraint matrices we saw little difference between the two methods. 相似文献
10.
In this paper we formulate necessary and sufficient conditions for an arbitrary polyhedral set to be a positively invariant set of a linear discrete-time system. Polyhedral cones and linear subspaces are included in the analysis. A linear programming algorithm is presented that enables practical application of the results stated in this paper. 相似文献
11.
12.
We compare the projective methods for linear programming due to de Ghellinck and Vial, Anstreicher, Todd, and Fraley. These algorithms have the feature that they approach feasibility and optimality simultaneously, rather than requiring an initial feasible point. We compare the directions used in these methods and the lower-bound updates employed. In many cases the directions coincide and two of the lower-bound updates give the same result. It appears that Todd's direction and Fraley's lower-bound update have slight advantages, and this is borne out in limited computational testing.This research was partially supported by NSF Grant DMS-8904406 and by ONR Contract N00004-87-K0212. The computations were carried out in the Cornell Computational Optimization Laboratory with support from NSF Grant DMS-8706133. 相似文献
13.
14.
Zhong-Fei Li Shou-Yang Wang Xiao-Tie Deng 《International journal of systems science》2013,44(1):107-117
We study the optimal portfolio selection problem with transaction costs. In general, the efficient frontier can be determined by solving a parametric non-quadratic programming problem. In a general setting, the transaction cost is a V-shaped function of difference between the existing and the new portfolio. We show how to transform this problem into a quadratic programming model. Hence a linear programming algorithm is applicable by establishing a linear approximation on the utility function of return and variance. 相似文献
15.
高效求解整数线性规划问题的分支算法 总被引:1,自引:0,他引:1
为了提高求解一般整数线性规划问题的效率,提出了一种基于目标函数超平面移动的分支算法。对于给定的目标函数整数值,首先利用线性规划松弛问题的最优单纯形表确定变量的上、下界,然后将变量的上、下界条件加入约束条件中对相应的目标函数超平面进行切割,最后应用分支定界算法中的分支方法来搜寻目标函数超平面上的可行解。通过对一些经典的数值例子的求解计算并与经典的分支定界算法进行比较,结果表明,该算法减少了分支数和单纯形迭代数,具有较大的实用价值。 相似文献
16.
《Computers & Operations Research》1987,14(5):341-347
This paper describes a modified Karmarkar algorithm for solving linear programming problems. This algorithm overcomes the problem of maintaining feasibility during the projective step and uses a constraint partitioning scheme which greatly improves the efficiency of the projective step. The new algorithm proves to be two to three times as fast as the IMSL FORTRAN subroutine ZX4LP in solving moderate size linear programs. 相似文献
17.
Andrés Marcos Author Vitae Declan G. Bates Author Vitae Author Vitae 《Automatica》2007,43(7):1211-1218
In this paper an algorithm that provides an equivalent, but of reduced order, representation for multivariate polynomial matrices is given. It combines ideas from computational symbolic algebra, polynomial/matrix algebraic manipulations and information logic. The algorithm is applied to the problem of finding minimal linear fractional transformation models. Statistical performance analysis of the algorithm reveals that it consistently outperforms currently available algorithms. 相似文献
18.
M. Duran Toksar? 《Information Sciences》2008,178(4):1189-1204
This paper presents the use of a Taylor series for fuzzy multiobjective linear fractional programming problems (FMOLFP). The Taylor series is a series expansion that a representation of a function. In the proposed approach, membership functions associated with each objective of fuzzy multiobjective linear fractional programming problem transformed by using a Taylor series are unified. Thus, the problem is reduced to a single objective. Practical applications and numerical examples are used in order to show the efficiency and superiority of the proposed approach. 相似文献
19.
Ching-Ter Chang 《International journal of systems science》2013,44(8):867-874
Fuzzy multiple objective fractional programming (FMOFP) is an important technique for solving many real-world problems involving the nature of vagueness, imprecision and/or random. Following the idea of binary behaviour of fuzzy programming (Chang 2007), there may exist a situation where a decision-maker would like to make a decision on FMOFP involving the achievement of fuzzy goals, in which some of them may meet the behaviour of fuzzy programming (i.e. level achieved) or the behaviour of binary programming (i.e. completely not achieved). This is turned into a fuzzy multiple objective mixed binary fractional programming (FMOMBFP) problem. However, to the best of our knowledge, this problem is not well formulated by mathematical programming. Therefore, this article proposes a linearisation strategy to formulate the FMOMBFP problem in which extra binary variable is not required. In addition, achieving the highest membership value of each fuzzy goal defined for the fractional objective function, the proposed method can alleviate the computational difficulties when solving the FMOMBFP problem. To demonstrate the usefulness of the proposed method, a real-world case is also included. 相似文献
20.
The Lx norm has been widely studied as a criterion for curve-fitting problems. This procedure is well suited to problems in numerical analysis [7], where errors due to round-off are assumed to have an underlying uniform distribution. TheLx norm, or Chebychev problem, allows for the “worst case”, in the sense of requiring the largest absolute error to be a minimum. Stiefel [9] developed a method called the “exchange method” for finding Chebychev estimates. The method presented here differs from the exchange method in several important respects: We use a “reduced basis” although determinants are used instead of finding an explicit basis inverse; and we develop a procedure for multiple pivots, or skipping extreme point solutions. The algorithm is specialized to solve the problem with an intercept term and a single independent variable. Results of the computational experience with a computer code version of the algorithm are presented. 相似文献