共查询到19条相似文献,搜索用时 109 毫秒
1.
2.
张连生 《应用数学与计算数学学报》1993,7(2):54-60
1.引言关于线性规划的多项式算法,哈奇扬于1979年首先把一个线性规划问题化成一个线性不等式组的求解问题,然后用椭球方法求解线性不等式组,并证明是多项式时间可解的。Karmarkar于1984年也给出了一个求解线性规划的多项式时间解法,他 相似文献
3.
4.
对非线性规划问题的处理通常采用罚函数法,使用罚函数法的困难在于参数的选取.本文提出了一种解非线性规划问题非参数罚函数多目标正交遗传算法,对违反约束的个体进行动态的惩罚以保持群体中不可行解的一定比例,从而不但有效增加种群的多样性,而且避免了传统的过度惩罚缺陷,使群体更好地向最优解逼近.数据实验表明该算法对带约束的非线性规划问题求解是非常有效的. 相似文献
5.
为求线性比试和问题的全局最优解,本文给出了一个分支定界算法.通过一个等价问题和一个新的线性化松弛技巧,初始的非凸规划问题归结为一系列线性规划问题的求解.借助于这一系列线性规划问题的解,算法可收敛于初始非凸规划问题的最优解.算法的计算量主要是一些线性规划问题的求解.数值算例表明算法是切实可行的. 相似文献
6.
指数跟踪问题的广义双线性规划模型 总被引:2,自引:0,他引:2
劳剑勇 《应用数学与计算数学学报》2004,18(1):85-91
本文对指数跟踪问题建立了一种广义的双线性规划模型,其中考虑了交易费用、持仓限制与重平衡问题.根据该模型的特殊结构,本文给出了近似规划算法,通过逐次逼近的线性规划求解最优指数跟踪问题. 相似文献
7.
针对多目标分式线性规划问题,提出利用上(下)界表示目标期望水平及允许上(下)限,且利用一阶泰勒公式逼近隶属函数,将多目标分式规划转化为线性规划问题,并用单纯形法求解,通过实验算例说明了所提出的方法的有效性. 相似文献
8.
本文提出具有线性等式约束多目标规划问题的一个降维算法.当目标函数全是二次或线性但至少有一个二次型时,用线性加权法转化原问题为单目标二次规划,再用降维方法转化为求解一个线性方程组.若目标函数非上述情形,首先用线性加权法将原问题转化为具有线性等式约束的非线性规划,然后,对这一非线性规划的目标函数二次逼近,构成线性等式约束二次规划序列,用降维法求解,直到满足精度要求为止. 相似文献
9.
最近Peng等人使用新的搜索方向和自正则度量为求解线性规划问题提出了一个原始对偶内点法.本文将这个长步法延伸到凸二次规划.在线性规划情形时,原始空间和对偶空间中的尺度Newton方向是正交的,而在二次规划情形时这是不成立的.本文将处理这个问题并且证明多项式复杂性,并且得到复杂性的上界为O(n√log n log (n/ε)). 相似文献
10.
11.
多约束非线性整数规划是一类非常重要的问题,非线性背包问题是它的一类特殊而重要的问题.定义在有限整数集上极大化一个可分离非线性函数的多约束最优化问题.这类问题常常用于资源分配、工业生产及计算机网络的最优化模型中,运用一种新的割平面法来求解对偶问题以得到上界,不仅减少了对偶间隙,而且保证了算法的收敛性.利用区域割丢掉某些整数箱子,并把剩下的区域划分为一些整数箱子的并集,以便使拉格朗日松弛问题能有效求解,且使算法在有限步内收敛到最优解.算法把改进的割平面法用于求解对偶问题并与区域分割有效结合解决了多约束非线性背包问题的求解.数值结果表明了改进的割平面方法对对偶搜索更加有效. 相似文献
12.
A Dinkelbach-type algorithm is proposed in this paper to solve a class of continuous-time linear fractional programming problems.
We shall transform this original problem into a continuous-time non-fractional programming problem, which unfortunately happens
to be a continuous-time nonlinear programming problem. In order to tackle this nonlinear problem, we propose the auxiliary
problem that will be formulated as parametric continuous-time linear programming problem. We also introduce a dual problem
of this parametric continuous-time linear programming problem in which the weak duality theorem also holds true. We introduce
the discrete approximation method to solve the primal and dual pair of parametric continuous-time linear programming problems
by using the recurrence method. Finally, we provide two numerical examples to demonstrate the usefulness of this practical
algorithm. 相似文献
13.
A numerical algorithm based on parametric approach is proposed in this paper to solve a class of continuous-time linear fractional max-min programming problems. We shall transform this original problem into a continuous-time non-fractional programming problem, which unfortunately happens to be a continuous-time nonlinear programming problem. In order to tackle this nonlinear problem, we propose the auxiliary problem that will be formulated as a parametric continuous-time linear programming problem. We also introduce a dual problem of this parametric continuous-time linear programming problem in which the weak duality theorem also holds true. We introduce the discrete approximation method to solve the primal and dual pair of parametric continuous-time linear programming problems by using the recurrence method. Finally, we provide two numerical examples to demonstrate the usefulness of this algorithm. 相似文献
14.
Christakis Charalambous 《Mathematical Programming》1977,12(1):195-225
Over the past few years a number of researchers in mathematical programming became very interested in the method of the Augmented Lagrangian to solve the nonlinear programming problem. The main reason being that the Augmented Lagrangian approach overcomes the ill-conditioning problem and the slow convergence of the penalty methods. The purpose of this paper is to present a new method of solving the nonlinear programming problem, which has similar characteristics to the Augmented Lagrangian method. The original nonlinear programming problem is transformed into the minimization of a leastpth objective function which under certain conditions has the same optimum as the original problem. Convergence and rate of convergence of the new method is also proved. Furthermore numerical results are presented which illustrate the usefulness of the new approach to nonlinear programming.This work was supported by the National Research Council of Canada and by the Department of Combinatorics and Optimization of the University of Waterloo. 相似文献
15.
The note demonstrates that modeling a nonlinear minimax problem as a nonlinear programming problem and applying a classical differentiable penalty function to attempt to solve the problem can lead to convergence to a stationary point of the penalty function which is not a feasible point of the nonlinear programming problem. This occurred naturally in an application from statistical reliability theory. The note resolves the problem through modification of both the problem formulation and the iterative penalty function method. 相似文献
16.
A FEASIBLE DIRECTION ALGORITHM WITHOUT LINE SEARCH FOR SOLVING MAX-BISECTION PROBLEMS 总被引:2,自引:0,他引:2
Feng-min Xu Cheng-xian Xu Hong-gang Xue 《计算数学(英文版)》2005,23(6):619-634
This paper concerns the solution of the NP-hard max-bisection problems. NCP func-tions are employed to convert max-bisection problems into continuous nonlinear program-ming problems. Solving the resulting continuous nonlinear programming problem generatesa solution that gives an upper bound on the optimal value of the max-bisection problem.From the solution, the greedy strategy is used to generate a satisfactory approximate so-lution of the max-bisection problem. A feasible direction method without line searches isproposed to solve the resulting continuous nonlinear programming, and the convergenceof the algorithm to KKT point of the resulting problem is proved. Numerical experimentsand comparisons on well-known test problems, and on randomly generated test problemsshow that the proposed method is robust, and very efficient. 相似文献
17.
将0-1离散规划通过一个非线性等式约束表示为[0,1]区间上等价的连续变量非线性规划列式.对非线性等式约束的问题进行了两种方法的处理.第一种方法使用乘子法,第二种方法将非线性的等式约束近似为一个非线性的不等式约束,均利用遗传算法程序GENOCOP进行了求解.对多个算例进行了计算,结果表明了该方法的可行性和有效性. 相似文献
18.
Yibing Lv Tiesong Hu Zhongping Wan 《Journal of Computational and Applied Mathematics》2008,220(1-2):175-180
In order to consider the inverse optimal value problem under more general conditions, we transform the inverse optimal value problem into a corresponding nonlinear bilevel programming problem equivalently. Using the Kuhn–Tucker optimality condition of the lower level problem, we transform the nonlinear bilevel programming into a normal nonlinear programming. The complementary and slackness condition of the lower level problem is appended to the upper level objective with a penalty. Then we give via an exact penalty method an existence theorem of solutions and propose an algorithm for the inverse optimal value problem, also analysis the convergence of the proposed algorithm. The numerical result shows that the algorithm can solve a wider class of inverse optimal value problem. 相似文献
19.
Cheng-xian Xu Xiao-liang Feng-min Xu 《计算数学(英文版)》2006,24(6):749-760
An effective continuous algorithm is proposed to find approximate solutions of NP-hardmax-cut problems.The algorithm relaxes the max-cut problem into a continuous nonlinearprogramming problem by replacing n discrete constraints in the original problem with onesingle continuous constraint.A feasible direction method is designed to solve the resultingnonlinear programming problem.The method employs only the gradient evaluations ofthe objective function,and no any matrix calculations and no line searches are required.This greatly reduces the calculation cost of the method,and is suitable for the solutionof large size max-cut problems.The convergence properties of the proposed method toKKT points of the nonlinear programming are analyzed.If the solution obtained by theproposed method is a global solution of the nonlinear programming problem,the solutionwill provide an upper bound on the max-cut value.Then an approximate solution to themax-cut problem is generated from the solution of the nonlinear programming and providesa lower bound on the max-cut value.Numerical experiments and comparisons on somemax-cut test problems(small and large size)show that the proposed algorithm is efficientto get the exact solutions for all small test problems and well satisfied solutions for mostof the large size test problems with less calculation costs. 相似文献