求解双背包约束下下模集函数最大问题的近似算法及其性能保证

对双背包约束条件下下模函数最大值问题用近似算法求解,其性能保证为1-e-1,该算法的时间复杂性为ο(n5).     

求解具有均匀拟阵约束下下模函数的最大值问题的贪婪算法及其性能保证

下模函数的最值问题在组合优化问题中有着广泛的应用,本文给出了具有均匀拟阵约束下下模函数最大值问题的贪婪近似算法,并讨论了所给算法的性能保证.     

求解组合拍卖问题的一种贪婪算法

为有效解决组合拍卖问题,从下模集函数最大值问题的基本结论出发,将部分穷举法与贪婪算法相结合,给出了一种求解组合拍卖问题的新算法——改进的贪婪算法,并从理论上证明了所给算法具有更好的性能保证.     

求解下模集函数最大值问题的局部搜索算法

给出了求解具有简单约束的下模集函数最大值问题的一种局部搜索算法,并讨论了所给算法的性能保证．该算法的基本思想是：算法每次迭代总是在当前近似解集的邻域内,求出使目标函数取得最大的集合,将其作为新的近似解集．分析表明,所给算法是一种多项式时间近似算法．     

拟阵约束下非负非减下模函数最大值问题的近似算法及其性能保证

下模函数的最值问题在组合优化问题中有着广泛的应用,给出了具有剥分拟阵约束下非负非减下模函数最大值问题的近似算法,并讨论了所给算法的性能保证.     

构造新函数 巧解一类题

<正>近几年各地调研、模考试卷中经常出现这样一类题,即给出含有导数式子的不等式,求解(或判断)相关不等式的问题.这类问题一般都涉及到抽象函数,往往比较抽象难以求解.如果能想到利用导数的运算法则构造新函数,然后再运用导数性质确定其单调性,那么此类问题就迎刃而解了.本文从2013年、2014年各地调研、模考试题中精选几例进行分析,供大家参考.例1若函数y=f(x)在R上可导且满     

关于Carathéodory不等式的注记

最大模定理是正则函数的一个重要性质,它叙述如下:设函数f(z)在闭围线C的内部为正则,并连续到C上,如果|f(z)|在C的上界为M,则不等式|f(z)|≤M对C内的任一Z都成立。又若对C内某一点Z,有|f(z)|=M,则f(z)恒为常数。 这定理给出了区域D内的正则函数,若它连续到D的边界C时,则f(z)在D内的模可以由它在边界上模的最大值M所控制。     

线性规划应用题讲解(高一)

线性规划应用问题的一般求解步骤是: (1)根据题意,建立数学模型,作出不等式组所表示的可行区域; (2)设所求目标函数f(x,y)的值为m; (3)将各顶点坐标代入目标函数,即可得到m的最大值与最小值,或求直线f(x,y)=m在y轴上截距的最大值(最小值),从而求得m的最大值与最小值;     

构造函数求解数列不等式的基本策略

一、整体构造例1已知函数f(x)=log3(ax b)图象过点A(2,1)和B(5,2).记an=3f(n),n∈N .求使得(1 1/a1)(1 1/a2)·…·(1 1/an)≥k1/2(2n 1)对一切n∈N 均成立的k的最大值.解析易知:an=2n-1.整体构造正整数集上的函数:构造函数求解数列不等式的基本策略@周丹~~     

混沌粒子群算法在0-1背包问题中的应用

给出了基于混沌粒子群优化算法(CPSO)背包问题的一种新的求解方法.首先将背包问题对应到粒子群算法中的位置与速度问题的表示,然后为了抑制早熟停滞现象,将混沌理论引进优化,使得背包问题更接近最优解.