共查询到20条相似文献,搜索用时 15 毫秒
1.
Jesús A. De Loera Bernd Sturmfels Cynthia Vinzant 《Foundations of Computational Mathematics》2012,12(4):509-540
The central curve of a linear program is an algebraic curve specified by linear and quadratic constraints arising from complementary slackness. It is the union of the various central paths for minimizing or maximizing the cost function over any region in the associated hyperplane arrangement. We determine the degree, arithmetic genus and defining prime ideal of the central curve, thereby answering a question of Bayer and Lagarias. These invariants, along with the degree of the Gauss image of the curve, are expressed in terms of the matroid of the input matrix. Extending work of Dedieu, Malajovich and Shub, this yields an instance-specific bound on the total curvature of the central path, a quantity relevant for interior-point methods. The global geometry of central curves is studied in detail. 相似文献
2.
C. C. Gonzaga 《Journal of Optimization Theory and Applications》2007,135(3):333-342
We present a method for constructing linear programming problems with randomly generated data. Besides the number of variables
and constraints, the dimensions of the primal and dual faces are given. We show that, for problems in which the constraint
matrix is carelessly constructed with random entries, with probability one only one between primal degeneracy and dual degeneracy
appears. 相似文献
3.
Hsien-Chung Wu 《Journal of Optimization Theory and Applications》2011,150(2):298-316
The weak and strong duality theorems in interval-valued linear programming problems are derived in this paper. The primal
and dual interval-valued linear programming problems are formulated by proposing the concept of a scalar (inner) product of
closed intervals. We introduce a solution concept that is essentially similar to the notion of nondominated solution in multiobjective
programming problems by imposing a partial ordering on the set of all closed intervals. Under these settings, the weak and
strong duality theorems for interval-valued linear programming problems are derived naturally. 相似文献
4.
5.
Pham Duy Khanh Tran Hong Mo Trinh T. T. Tran 《Numerical Functional Analysis & Optimization》2019,40(8):924-943
Necessary and sufficient conditions for qualitative properties of infinite dimensional linear programing problems such as solvability, duality, and complementary slackness conditions are studied in this article. As illustrations for the results, we investigate the parametric version of Gale’s example. 相似文献
6.
This paper revisits an efficient procedure for solving posynomial geometric programming (GP) problems, which was initially developed by Avriel et al. The procedure, which used the concept of condensation, was embedded within an algorithm for the more general (signomial) GP problem. It is shown here that a computationally equivalent dual-based algorithm may be independently derived based on some more recent work where the GP primal-dual pair was reformulated as a set of inexact linear programs. The constraint structure of the reformulation provides insight into why the algorithm is successful in avoiding all of the computational problems traditionally associated with dual-based algorithms. Test results indicate that the algorithm can be used to successfully solve large-scale geometric programming problems on a desktop computer. 相似文献
7.
运筹学中的线性目标规划和线性规划问题一直分别采用修正单纯形法和单纯形法求解.当变量稍多时计算还是有些繁琐、费时,最近作者通过研究发现,可应用人工智能-代数方法求得这两类问题的解,而且具有相当广泛的适用性.若干例题说明,本法的结果和传统方法的结果由于传统算法在计算中发生的错误,除少数例外大都是一致的.本文的一个 重要目的是希望和广大读者一起研究该方法是否具有通用性. 相似文献
8.
Ami Arbel 《The Journal of the Operational Research Society》1994,45(1):83-96
This paper presents a modification of one variant of Karmarkar's interior-point linear programming algorithm to Multiobjective Linear Programming (MOLP) problems. We show that by taking the variant known as the affine-scaling primal algorithm, generating locally-relevant scaling coefficients and applying them to the projected gradients produced by it, we can define what we refer to as anchoring points that then define cones in which we search for an optimal solution through interaction with the decision maker. Currently existing MOLP algorithms are simplex-based and make their progress toward the optimal solution by following the vertices of the constraints polytope. Since the proposed algorithm makes its progress through the interior of the constraints polytope, there is no need for vertex information and, therefore, the search for an optimal solution may prove less sensitive to problem size. We refer to the class of MOLP algorithms resulting from this variant as Affine-Scaling Interior Multiobjective Linear Programming (ASIMOLP) algorithms. 相似文献
9.
Summary. Let A be an n×m real matrix and consider the linear conic system
In [Cheung and Cucker 2001] a condition number 𝒞(A) for this system is defined. In this paper we let the coefficients of A be independent identically distributed random variables with standard Gaussian distribution and we estimate the moments of
the random variable ln𝒞(A). In particular, when n is sufficiently larger than m we obtain for its expected value E(ln𝒞(A))=max{ln m, ln ln n}+𝒪(1). Bounds for the expected value of the condition number introduced by Renegar [1994b, 1995a, 1995b] follow.
Received June 12, 2001 / Revised version received October 29, 2001 /
Published online November 27, 2002
RID="⋆"
ID="⋆" Partially supported by CERG grant City U 1085/02p.
Mathematics Subject Classification (1991): 65F35, 65K05 相似文献
10.
Jean-Pierre Dedieu Gregorio Malajovich Mike Shub 《Foundations of Computational Mathematics》2005,5(2):145-171
We prove a linear bound on the average total curvature of the
central path of linear programming theory in terms of the number
of independent variables of the primal problem, and independent of
the number of constraints. 相似文献
11.
12.
具有模糊变量的线性规划问题 总被引:3,自引:0,他引:3
讨论含模糊变量的线性规划问题,研究了其求解方法。利用新定义的模糊数序关系,将它转换成一个多目标线性规划问题,然后进一步转换成两层多目标线性规划问题,进而利用分层规划法求解。 相似文献
13.
Journal of the Operational Research Society - Multi-level programming is characterized as mathematical programming to solve decentralized planning problems. The decision variables are partitioned... 相似文献
14.
本文考虑具有模糊系数的模糊线性规划问题中各系数的模糊可能性分布,而用指数(或线性)的隶属函数来描述,然后使用模糊数集上的实值函数,使模糊数在模型均值的意义下对应于一个实数,借此,将原问题公式化为一个普通线性规划。 相似文献
15.
16.
Computational difficulties in solving the Integer Programming Problems (IPP) are caused to a considerable degree by the number of variables. If the number of variables is small, then even NP-complete problems usually can be solved with a reasonable expenditure of effort.A procedure is developed for the analysis of large scale IPP with the aim of reducing the number of variables prior to starting the solution method. The procedure is based on comparing pairs of columns of the constraint matrix of the IPP. If a pair of columns thus compared meets certain conditions, then the IPP has an optimal solution, in which a variable corresponding to one of the columns in the pair is equal to zero. Corresponding theorems for Knapsack and Multidimensional Knapsack problems and for general IPP are presented. The procedure is extended to Linear and Mixed Integer Programming Problems. The presented results of computational experiments illustrate the efficiency of the developed procedure. 相似文献
17.
Yonah Wilamowsky Sheldon Epstein Bernard Dickman 《The Journal of the Operational Research Society》1990,41(4):351-356
A decision-maker, using mathematical programming optimization models, is often faced with a choice of many alternative solutions optimizing the objective function. The decision may be based on secondary, tertiary or higher-order objectives. Such problems are usually handled using goal programming (GP) with pre-emptive priorities. Pre-emptive prioritization is discussed in the literature in the context of GP. This paper suggests that the two are separable, and presents algorithms to accomplish this. It argues that in a truly pre-emptive situation, direct lexicographical optimization of the objectives, without introduction of goals, has a number of advantages. In addition, when applied to special structure models such as transportation or assignment, this approach enables one to maintain the structure and hence the efficiency of those algorithms. 相似文献
18.
In this paper, we consider a multiobjective two-level linear programming problem in which the decision maker at each level has multiple-objective functions conflicting with each other. The decision maker at the upper level must take account of multiple or infinite rational responses of the decision maker at the lower level in the problem. We examine three kinds of situations based on anticipation of the decision maker at the upper level: optimistic anticipation, pessimistic anticipation, and anticipation arising from the past behavior of the decision maker at the lower level. Mathematical programming problems for obtaining the Stackelberg solutions based on the three kinds of anticipation are formulated and algorithms for solving the problems are presented. Illustrative numerical examples are provided to understand the geometrical properties of the solutions and demonstrate the feasibility of the proposed methods. 相似文献
19.
M. D. Bakes 《The Journal of the Operational Research Society》1966,17(4):425-445
This paper gives a method of solution for linear programming problems whose constraints can be split into two sets, the first having a special structure, such as that of the transportation problem for example, while the second set is quite general. A problem with only the first set of constraints is referred to as a favoured problem, while a problem with both sets is called a complete problem.The proposed method is basically the simplex procedure specialized for a problem with a particular structure, and the feasibility and optimality criteria and the rules for basis change are the same as those used in the simplex procedure. However, the method takes advantage of the simple algorithms developed for the favoured problem and uses them to solve the complete problem in an efficient manner.Such problems could also be solved by the Decomposition Principle and, vice versa, Decomposition problems can be solved by the present method. The two methods are, however, essentially different in their approach to the problem. 相似文献
20.
Artem’eva L. A. Vasil’ev F. P. Potapov M. M. 《Computational Mathematics and Mathematical Physics》2018,58(12):1919-1925
Computational Mathematics and Mathematical Physics - For a pair of dual inconsistent linear programming problems, the existence and uniqueness of a correction vector that is optimal in the norm is... 相似文献