共查询到20条相似文献,搜索用时 718 毫秒
1.
2.
3.
边界约束非凸二次规划问题的分枝定界方法 总被引:2,自引:0,他引:2
本文是研究带有边界约束非凸二次规划问题,我们把球约束二次规划问题和线性约束凸二次规划问题作为子问题,分明引用了它们的一个求整体最优解的有效算法,我们提出几种定界的紧、松驰策略,给出了求解原问题整体最优解的分枝定界算法,并证明了该算法的收敛性,不同的定界组合就可以产生不同的分枝定界算法,最后我们简单讨论了一般有界凸域上非凸二次规划问题求整体最优解的分枝与定界思想。 相似文献
4.
本文给出混合0-1线性规划问题的一个代理约束定界方法,利用代理约束构造一个定界函数,计算量较小,并提出一个分支定界算法,数值计算表明算法是有效的. 相似文献
5.
6.
7.
8.
为确定广义线性比式和规划问题(GFP)的全局最优解,提出一个新的分支定界方法.在算法中,分支过程采用单纯形对分规则,且界的估计通过一些线性规划问题的求解完成.给出算法的收敛性证明.数值试验结果显示算法是有效可行的. 相似文献
9.
10.
考虑具有机器适用限制的多个不同置换流水车间的调度问题. 机器适用限制指的是每个工件只能分配到其可加工工厂集合. 所有置换流水车间拥有的机器数相同但是具有不同的加工能力. 首先, 针对该问题建立了基于位置的混合整数线性规划模型; 进而, 对一般情况和三种特殊情况给出了具有较小近似比的多项式时间算法. 其次, 基于NEH方法提出了启发式算法NEHg, 并给出了以NEHg为上界的分支定界算法. 最后, 通过例子说明了NEHg启发式算法和分支定界算法的计算过程, 并进行大量的实验将NEHg与NEH算法结果进行比较, 从而验证了NEHg算法的有效性. 相似文献
11.
ZhuDetong 《高校应用数学学报(英文版)》2004,19(4):459-473
This paper proposes a nonmonotonic backtracking trust region algorithm via bilevel linear programming for solving the general multicommodity minimal cost flow problems. Using the duality theory of the linear programming and convex theory, the generalized directional derivative of the general multicommodity minimal cost flow problems is derived. The global convergence and superlinear convergence rate of the proposed algorithm are established under some mild conditions. 相似文献
12.
We consider two-stage stochastic programming problems with integer recourse. The L-shaped method of stochastic linear programming
is generalized to these problems by using generalized Benders decomposition. Nonlinear feasibility and optimality cuts are
determined via general duality theory and can be generated when the second stage problem is solved by standard techniques.
Finite convergence of the method is established when Gomory’s fractional cutting plane algorithm or a branch-and-bound algorithm
is applied. 相似文献
13.
根据值型线性双层规划的 Johri一般对偶的对偶性质 ,把对两类值型线性双层规划的求解问题转化为对有限个线性规划的求解问题 ,简化了双层规划的求解过程 ,给出了求解这两类值型线性双层规划的一种有效算法 相似文献
14.
M. Sun 《Journal of Optimization Theory and Applications》1993,79(2):405-413
We introduce a revised simplex algorithm for solving a typical type of dynamic programming equation arising from a class of finite Markov decision processes. The algorithm also applies to several types of optimal control problems with diffusion models after discretization. It is based on the regular simplex algorithm, the duality concept in linear programming, and certain special features of the dynamic programming equation itself. Convergence is established for the new algorithm. The algorithm has favorable potential applicability when the number of actions is very large or even infinite. 相似文献
15.
In this paper we present a robust duality theory for generalized convex programming problems in the face of data uncertainty within the framework of robust optimization. We establish robust strong duality for an uncertain nonlinear programming primal problem and its uncertain Lagrangian dual by showing strong duality between the deterministic counterparts: robust counterpart of the primal model and the optimistic counterpart of its dual problem. A robust strong duality theorem is given whenever the Lagrangian function is convex. We provide classes of uncertain non-convex programming problems for which robust strong duality holds under a constraint qualification. In particular, we show that robust strong duality is guaranteed for non-convex quadratic programming problems with a single quadratic constraint with the spectral norm uncertainty under a generalized Slater condition. Numerical examples are given to illustrate the nature of robust duality for uncertain nonlinear programming problems. We further show that robust duality continues to hold under a weakened convexity condition. 相似文献
16.
基于广义多品种最小费用流问题的性质,将问题转化成一对含有内、外层问题的双水平规划,内层规划实际是单品种费用流问题,而外层问题是分离的凸规划,使用相关的凸分析理论,导出了广义多品种最小费用流问题的对偶规划,对偶定理和Kuhn-Tucker条件。 相似文献
17.
Qinghong Zhang 《4OR: A Quarterly Journal of Operations Research》2011,9(4):403-416
It is known that the minimal cone for the constraint system of a conic linear programming problem is a key component in obtaining
strong duality without any constraint qualification. For problems in either primal or dual form, the minimal cone can be written
down explicitly in terms of the problem data. However, due to possible lack of closure, explicit expressions for the dual
cone of the minimal cone cannot be obtained in general. In the particular case of semidefinite programming, an explicit expression
for the dual cone of the minimal cone allows for a dual program of polynomial size that satisfies strong duality. In this
paper we develop a recursive procedure to obtain the minimal cone and its dual cone. In particular, for conic problems with
so-called nice cones, we obtain explicit expressions for the cones involved in the dual recursive procedure. As an example
of this approach, the well-known duals that satisfy strong duality for semidefinite programming problems are obtained. The
relation between this approach and a facial reduction algorithm is also discussed. 相似文献
18.
In this article, we present and validate a simplicial branch and bound duality-bounds algorithm for globally solving the linear sum-of-ratios fractional program. The algorithm computes the lower bounds called for during the branch and bound search by solving ordinary linear programming problems. These problems are derived by using Lagrangian duality theory. The algorithm applies to a wide class of linear sum-of-ratios fractional programs. Two sample problems are solved, and the potential practical and computational advantages of the algorithm are indicated. 相似文献
19.
《European Journal of Operational Research》1986,26(2):301-306
In this paper we develop a complete duality theory for a couple of disjunctive linear programming problems with absolute value functionals. The pair of dual problems constructed has no duality gap, and may be considered as a generalization of the duality theory for convex programming. 相似文献
20.
This paper presents a canonical duality theory for solving quadratic minimization problems subjected to either box or integer
constraints. Results show that under Gao and Strang’s general global optimality condition, these well-known nonconvex and
discrete problems can be converted into smooth concave maximization dual problems over closed convex feasible spaces without
duality gap, and can be solved by well-developed optimization methods. Both existence and uniqueness of these canonical dual
solutions are presented. Based on a second-order canonical dual perturbation, the discrete integer programming problem is
equivalent to a continuous unconstrained Lipschitzian optimization problem, which can be solved by certain deterministic technique.
Particularly, an analytical solution is obtained under certain condition. A fourth-order canonical dual perturbation algorithm
is presented and applications are illustrated. Finally, implication of the canonical duality theory for the popular semi-definite
programming method is revealed. 相似文献