共查询到18条相似文献,搜索用时 140 毫秒
1.
2.
3.
针对球约束凸二次规划问题,利用Lagrange对偶将其转化为无约束优化问题,然后运用单纯形法对其求解,获得原问题的最优解。最后,对文中给出的算法给出了论证。 相似文献
4.
5.
6.
7.
8.
9.
凹二次规划问题的一个融合割平面方法的分支定界混合算法 总被引:4,自引:2,他引:2
把割平面方法融于分支定界方法之中,本文提出了求解凹二次规划问题的一个融合割平面方法的分支定界混合算法,证明了该算法是收敛的.数值例子也表明这个算法是有效的,并且好于单纯形分支定界算法。 相似文献
10.
垂直互补约束数学规划问题在工程设计、生产计划、优化控制等方面有很多应用.本文提出了一种求解垂直互补约束数学规划问题的松弛方法,并证明了:在垂直互补约束数学规划问题线性独立的约束规范条件下,松弛问题稳定点的任何聚点是原问题的C-稳定点.如果进一步还满足二阶必要性条件,则这些聚点是M-稳定点.基本数值结果表明提出的方法可以很好的求解垂直互补约束数学规划问题. 相似文献
11.
带非凸二次约束的二次规划问题的全局优化方法 总被引:1,自引:1,他引:1
利用二次函数的线形下界函数对带有非凸二次约束的二次规划(QP)提出一种新的求其全局最优解的分支定界算法.为改进算法的收敛性,根据问题的最优性和可行性提出一新的区域剪枝准则以排除(QP)的可行域中不存在全局解的部分.数值算例表明该准则能有效地加速算法的收敛性. 相似文献
12.
This paper describes the optimization of a load-bearing thermal insulation system characterized by hot and cold surfaces with a series of heat intercepts and insulators between them. The optimization problem is represented as a mixed variable programming (MVP) problem with nonlinear constraints, in which the objective is to minimize the power required to maintain the heat intercepts at fixed temperatures so that one surface is kept sufficiently cold. MVP problems are more general than mixed integer nonlinear programming (MINLP) problems in that the discrete variables are categorical; i.e., they must always take on values from a predefined enumerable set or list. Thus, traditional approaches that use branch and bound techniques cannot be applied.In a previous paper, a linearly constrained version of this problem was solved numerically using the Audet-Dennis generalized pattern search (GPS) method for MVP problems. However, this algorithm may not work for problems with general nonlinear constraints. A new algorithm that extends that of Audet and Dennis by incorporating a filter to handle nonlinear constraints makes it possible to solve the more general problem. Additional nonlinear constraints on stress, mass, and thermal contraction are added to that of the previous work in an effort to find a more realistic feasible design. Several computational experiments show a substantial improvement in power required to maintain the system, as compared to the previous literature. The addition of the new constraints leads to a very different design without significantly changing the power required. The results demonstrate that the new algorithm can be applied to a very broad class of optimization problems, for which no previous algorithm with provable convergence results could be applied. 相似文献
13.
This paper addresses the problem of scheduling, on a two-machine flow shop, a set of unit-time operations subject to the constraints that some conflicting jobs cannot be scheduled simultaneously on different machines. In the context of our study, these conflicts are modelled by general graphs. The problem of minimising the maximum completion time (makespan) is known to be NP-hard in the strong sense. We propose a mixed-integer linear programming (MILP) model. Then, we develop a branch and bound algorithm based on new lower and upper bound procedures. We further provide a computer simulation to measure the performance of the proposed approaches. The computational results show that the branch and bound algorithm outperforms the MILP model and can solve instances of size up to 20,000 jobs. 相似文献
14.
D. T. Eliiyi 《国际生产研究杂志》2013,51(20):4343-4365
In this study, we consider the operational fixed job scheduling problem on identical parallel machines. We assume that the jobs have fixed ready times and deadlines, and spread time constraints are imposed on machines. Our objective is to select a set of jobs for processing so as to maximise the total weight. We show that the problem is strongly NP-hard, and we investigate several special polynomially solvable cases. We propose a branch and bound algorithm that employs size reduction mechanisms, dominance conditions, and powerful lower and upper bounds. The computational results reveal that the branch and bound algorithm returns optimal solutions for problem instances with up to 100 jobs in reasonable solution times. 相似文献
15.
Computerized Layout Design: A Branch and Bound Approach 总被引:3,自引:1,他引:2
Mokhtar S. Bazaraa 《IIE Transactions》1975,7(4):432-438
This paper presents a computerized procedure for layout design. The layout problem is formulated as a quadratic set covering problem. A branch and bound method for optimizing the resulting problem is devised. As a result, optimal and suboptimal layouts can be provided to the layout engineer for consideration and modification. 相似文献
16.
The purpose of this paper is to formulate and solve a nonlinear mixed zero-one integer programming problem aimed to maximize total output by scheduling the operational time of N non-identical machines. Properties of the optimal solution are identified under restrictions imposed on machine availability and various budget constraints. A branch and bound algorithm to solve the problem is suggested. 相似文献
17.
This article considers a single machine scheduling problem with batch setups, positional deterioration effects, and multiple optional rate-modifying activities to minimize the total completion time. This problem is formulated as an integer quadratic programming problem. In view of the complexity of optimally solving this problem, a two-phase heuristic algorithm is proposed where an optimal but non-integer solution is obtained in the first phase by solving a continuous relaxed version of the problem. This solution serves as a lower bound for the optimal value of the total completion time. The second phase of the algorithm generates an integer solution using a simple rounding scheme that is optimum or very close to optimum for this problem. Empirical evaluation and comparison with an existing heuristic algorithm show that the proposed heuristic algorithm is substantially more effective in solving large-size problem instances. 相似文献
18.
多车辆直运越库调度问题的目标是最小化所有客户中的最晚到货时间.首先,建立了描述该问题的混合整数线性规划模型,并使用运筹优化工具ILOG CPLEX进行求解;其次,构造了基于LPT规则的启发式算法,为精确算法提供了初始可行解,并对分支定界算法进行详细的分析;最后,在数值实验部分,通过数学模型与分支定界的比较及算法性能的分析后,得出分支定界算法具有更高的效率,该分支定界算法在合理的时间内能够求解到11个供应商规模的问题. 相似文献