多项式0—1整数规划的两个连续化途径

本文给出一种整系数多项式０－１整规划的两个连续化途径，能将含等式和不等式约束的０－１多项式规划转化成无约束多项式规划问题。     

框式可分凸二次规划的不可行内点算法

对框式约束的可分凸二次规划提出了1个原始－对偶不可行内点算法，并证明了该算法是1个多项式时间算法。     

对称多项式理论在初等数学中的应用

运用对称多项式基本定理解决下面问题：若已知一元n次方程xn＋a1xn－1＋…＋an-1x＋an＝0的根之间的关系，则可推导出方程系数a1,a2…,an＝0之间应满足的关系．     

几何规划的一种多项式时间算法

利用几何规划的特点，借助于对偶理论，把原始对偶道路跟踪内点算法，推广应用于正定式几何规划并证明了此算法对于无约束正定式几何规划是一种多项式间算法，可以预料，这种算法可推广应用于约束几何规划问题。     

多项式0-1整规划的两个连续化途径

本文给出一种整系数多项式０－１整规划的两个连续化途径,能将含等式和不等式约束的０－１多项式规划转化成无约束多项式规划问题     

正多项式规划的最大熵解与迭代Ⅰ－投影算法

指出可用最大熵原理给出正多项式规划的对偶解。不仅直接给出解的形式，而且可以用最大熵迭代Ⅰ－投影算法计算，大大减少计算量和求解困难度。     

单位操作长度的自由作业问题多项式时问算法

研究了工件操作长度为1或0的自由作业问题。在不同目标函数下，用数学规划及组合方法设计相应的多项式时间算法。     

一类机器带时间限制的分批排序问题及算法

机器带有时间约束的分批排序问题是一类新型排序问题。本文首次对1,R|B≥n|∑Cj问题进行了研究。并给出了一个伪多项式时间动态规划算法。     

单位操作长度的自由作业问题多项式时间算法

研究了工件操作长度为1或0的自由作业问题.在不同目标函数下,用数学规划及组合方法设计相应的多项式时间算法.     

域上多项式函数的一个性质及应用

定义在域ｋ上的代数簇之间的ｋ－态射将ｋ－有理点映为ｋ－有理点,反之一般不真,讨论了其逆在一定条件下成立,并用它研究多元置换多项式中的一个未解决的问题：若Ｆｇ上的多元多项式ｆ是Ｆｑ的某一扩域的置换多项式,ｆ是否一定是Ｆｑ的置换多项式。     

凸二次规划的一种宽邻域预估-校正算法

Zhao对线性规划提出了一种基于邻近度量函数最小值的宽邻域预估-校正算法, 并证明了算法的多项式复杂性。基于他的思路,将此方法拓展到凸二次规划,设计了一种新的基于邻近度量函数最小值的宽邻域预估-校正算法。由于新算法的迭代方向向量Δx,Δs不再满足正交性,因此算法的收敛性分析不同于线性规划的情形,同时也证明了新算法具有 已知的最好迭代复杂性Onln(x0)Ts0ε,初步数值实验验证了算法的有效性。     

A wide neighborhood arc-search interior-point algorithm for convex quadratic programming

In this paper, we propose an arc-search interior-point algorithm for convex quadratic programming with a wide neighborhood of the central path, which searches the optimizers along the ellipses that approximate the entire central path. The favorable polynomial complexity bound of the algorithm is obtained, namely O(nlog(( x~0)~TS~0/ε)) which is as good as the linear programming analogue. Finally, the numerical experiments show that the proposed algorithm is efficient.     

0-1型整数规划解法刍议

用穷举法和隐枚举法解0-1型整数规划问题时,常常遇到组合爆炸问题。本文从约束条件入手直接给出某些变量的值,从而将减少了运算次数有效的改善了这一问题。     

大型0—1目标规划的启发式算法

提出了一个０－１线性目标规划新的启发式算法,该算法以新的算法准则及评价标准,改进了旧算法中的系数限制,并能通用于任何０－１线性目标规划问题,特别能够有效地解决大规模０－１线性目标规划问题。     

自动优化露天矿短期进度计划的渐进细化法

分析了露天矿生产计划技术现状,提出计算机辅助设计法与数学规划法有机结合是制定露天生产进度计划的最佳手段.针对整数规划和具有前后时段顺序的0-1整数规划在露天矿生产进度计划应用中存在的问题,提出了渐进细化的生产进度计划优化方法,论述了渐进细化过程,建立了相应的0-1整数规划模型.在VC++环境下通过调用LindoAPI实现模型求解,该细化0-1整数规划方法,较前后时段0-1整数规划方法提高了计算速度,满足设计细化需要.     

求解凸二次规划的一种二阶Mehrotra型预估一校正算法

给出了求解凸二次规划的一种二阶Mehrotra型预估一校正算法。该算法受Salahi等人对线性规划提出的相应算法启发,引入了安全步策略,保证了校正步步长有适当下界,从而具有多项式复杂性。由于算法迭代方向不正交,算法在罚参数的校正和复杂性的分析上有别于线性规划的情形。最后,通过一些新的技术性引理,证明了算法在最坏情况下的迭代复杂性为O（n^3/2log（x^0）^TS^0/ε）.     

若干带拒绝费用的分批排序问题研究

首次考虑了工件可拒绝的单机串行分批排序问题.对于问题1,s｜s-batch,rej｜Cmax＋Σ j∈ ej,均给出了最优算法;对于问题1,s｜s-batch,rej｜Σ j∈s Cj＋Σj∈ ej,通过动态规划算法给出了多项式时间的精确算法.研究了问题1｜B〈n,rej｜Σj∈s wjCj＋Σj∈ ej中工件加工时间均相等的特殊情况.     

GENOCOP算法在0-1非线性整数规划模型中的应用

本文针对某公司电力容量扩展问题,采用一元线性回归模型拟合未来10年的需求量,再建立0-1非线性整数规划模型,并将该模型的0-1变量连续化处理,采用遗传算法中的GENOCOP算法求解。     

线性分式规划的多项式时间算法

线性规划（ＬＰ）各种形式的多项式时间算法的研究和成果已相当成熟，但对线性分式规划（ＬＦＰ）的研究甚少．在理论上，ＬＦＰ可转换为ＬＰ，但ＬＰ的多项式时间算法求得的多半为近似解，且ＬＦＰ转换为ＬＰ是通过一个非线性分式映射实现的．因此研究和分析ＬＰ的各种多项式时间算法对ＬＦＰ的稳定性具有理论和实际意义．本文首先系统地分析了从ＬＦＰ到ＬＰ的转换及各种性质．然后，将ＬＰ的一些多项式时间算法推广到ＬＦＰ，最后证明它们仍可在多项式时间内求得满足精度的近似解．