多项式算法相关论文
网络最优化的理论和方法已经广泛地渗透于运筹学、信息论、控制论、管理科学和计算机科学等领域,并在工程技术、军事等方面有着极......
图的因子理论是图论的重要分支之一,是图论研究中的最活跃的课题之一.特别是图的因子分解研究是一个引人注目的课题,它在网络设计......
假设M是图G的一个完美匹配,M（G）是图G所有完美匹配的集合.图的完美匹配计数问题（即计算.M（G）的基数）是图论的一个重要研究课题.然而,Vali......
P vs.NP问题一直是理论计算机科学领域中最为复杂的一个问题,已经被列为世界七大数学难题之首。P vs.NP问题已经吸引了世界上许多......
反问题不仅有很重要的理论研究价值，而且有很大的实际应用价值．在求解一个组合优化问题的时候，我们通常假设问题中的参数均是确定的，而......
本文主要研究反瓶颈steiner树问题，Steiner树问题是组合最优化的重要组成部分。Steiner树的一系列问题来源于生活的实践，因此越来越......
排序问题是一类重要的组合优化问题。经典的排序理论中，通常假设一个工件在任何时刻至多只能在一台机器上得到加工，但在某些特定场合......
计算机科学、运筹学和控制理论等方面的大量问题都可以用极大极小系统来建立模型，例如数字电路、计算机网络、自动化制造厂等.对于......
Wythoffs游戏是公平组合游戏中比较重要的部分.此游戏模型可这样描述：有两堆石头都是若干个，两个游戏者轮流移动，有两种移法：要么从两......
针对一类存在并行工作站和可重入工作站的复杂无等待自动化制造系统的调度问题,提出了利用禁止区间法建立该问题的数学模型,并开发......
研究加权超前延误工件数问题.在单机存在非限制性共同宽容交货期(common due window,CDW)条件下,给出一个动态规划算法及一个近似......
给出了可分凸二次规划的不可行内点算法,并证明了该算法在O(n2L)次迭代之后,或者收敛到问题的一个近似最优解,或者说明该问题在某......
该文深入分析了主属性在关系模式中的结构特征,提出了化简独立复合环、独立简单环、化简双部属性函数依赖图等概念.在此基础上,给......
考虑一类在网络上点到路的距离意义下的最优干线选址问题,这是一类新型的选址问题.首先证明所讨论的两个问题是NP-hard,然后讨论树......
对于一类非单调线性互补问题给出一种新的内点算法.算法的每一步迭代,利用线性规划的原始--对偶内点算法的思想求解一个线性方程组......
本文首次提出了中国邮递员问题的推广问题－水灾地区邮递员问题，并对解的存在性给出了一系列的充分条件、必要条件及充要条件，得到了求......
本文根据一个实例建立了在赋双权的有向图中求带参数的双权树形图的网络模型,通过求解一系列的问题P2(λ),我们得到了求解该问题的......
本文研究了最小支撑树问题的一个变形--分区连接问题,即对给定的赋权图及其中若干个顶点,求赋权图的权最小支撑森林,使得它的每一......
本文讨论Caccetta-Haggkvist猜想的特殊情形猜想：如果有向图D的最小顶点出度δ^＋（D）≥ n/3,则D存在△。受无向图G的结合数bind（G）≥3/2是......
考虑在网络上点到路的距离意义下的最优干线选择问题——最小加权距离和问题和最小最大加权距离问题．首先证明所讨论的两个问题的判......
考虑了2个固定顶点的树划分问题,即固定k个顶点的最小和树划分问题和固定k个顶点的最小最大树划分问题,我们得到如下结果:①利用Gr......
对框式约束的可分凸二次规划提出了1个原始-对偶不可行内点算法,并证明了该算法是1个多项式时间算法.......
讨论目标函数为极小化加权完工时间和的调度问题.对于这类问题,平行机问题是NP-难的.基于对问题的分析,对工件的加工时间相等的恒......
文[5]建立了定理5-3、5-4、5-5,并据此证明了采用该文的最大改进规则的单纯形算法是多项式算法.本文举例证明了文[5]中的定理5-3、......
所考虑的供应链排序系统为：若干个不同的元件供应商向一产品加工商供应产品元件，产品加工商等所有的元件都加工完成后再开始最后阶段......
为解决无等待多机器人制造单元的调度问题，应用禁止区间法，建立了无等待多机器人制造单元调度的数学模型。在分析模型的基础上，证明了......
线性规划的多项式算法——Karmarkar方法，是近期国际运筹学界的著名成果．它在理论与实用上都有重要意义．本文希望用比较通俗的方式介......
期刊
线性规划的多项式算法--Karmarkar方法,是近期国际运筹学界的著名成果.它在理论与实用上都有重要意义.本文希望用比较通俗的方式介......
2000年初美国克雷数学研究所的科学顾问委员会选定了7个＂千年大奖问题＂,这7个＂千年大奖问题＂是：NP完全问题、霍奇猜想、庞加莱猜想、黎......
提出r-因子置换循环矩阵概念,得到其相似标准形,从而得到该类矩阵可逆的多项式充要条件以及算法的理论依据。同时,得到的逆矩阵与......
该文给出基因组Translocation排序问题的一个改进多项式算法.原算法所用存储空间为O(n),时间复杂度为O(n3).文中改进算法仍采用O(n......
强符号非异矩阵（简称S2NS矩阵）在定性矩阵理论的研究中有重意义，据此研究与S2NS矩阵直接相关的S2NS带号有向图的特刻画问题，一个带号有......
基于工作流的Petri网结构化建模方法，证明了工作流网的T-不变量和P-不变量的存在性、可覆盖性，给出了一个工作流模型完整性的充要条......
研究了工件操作长度为1或0的自由作业问题。在不同目标函数下，用数学规划及组合方法设计相应的多项式时间算法。......
考虑多资源组合应急调度问题,目标为在满足各类物资正常供给的情况下求解最早应急开始时间。针对多个出救点,且各类资源在区间上连......
讨论作业具有线性加工时间，作业间具有链约束的两台处理机流水作业排序问警，目标函数为极小化完工时间。在作业加工时间简单线性恶化......
寻找实际可行的多项式算法一直是Petri网应用的重要方面，给出了关于扩展强化对称选择网（extended strong asymmetric choice nets,简......
对具有两个权的有向网络的最优路径问题，从不同角度进行了探讨.给出了计算两个节点间的使费用与容量之比最小的路径的多项式算法.并......
以丁厂实际问题为背景,生产商对购买者规定了一个最小的购买规格,而当地的零售商提供购买者及时配送的承诺,但是需要较高的成本.本......
利用误差传播关系，比较了测速体制下逐点定轨算法和多项式定轨算法的精度，为多项式和样条算法在测速定轨体制中的应用提供理论依据。......
对于一类非单调线性互补问题给出了一种新的内点算法－预估校正算法，并讨论了其多项式的收敛性。......
针对一类带有准备时间和安装时间的单机成组排序问题，给出了求解最优排序的多项式算法。其中每个工件都具有自己的准备时间，组和组之......
本文研究排序问题中的E—T问题，工件在单台机器上加工，n个工件的加工时间都为整数P，相同的工期d为离散分布，满足∑i=1^mP（d=ξi）=1,其中......
从能力有限的动态批量问题出现开始，国内外众多学者全心致力于这类问题的研究。随着环境问题在制造业企业生产过程中的日益突出，资源......
本文研究两类平面选址问题:(1)求一直线到n个给定点的加权距离和为最小;(2)求一点到n条给定直线的加权距离和为最小.对这两个非线......
本文研究两类平面选址问题:(1)求一直线到n个给定点的最大加权距离为最小;(2)求一点到n条给定直线的最大加权距离为最小.对这两个......
本文讨论具有优势机器的无空闲同顺序Flow Shop排序问题的两种特殊情况.第一种情况是具有增减系列优势机器,第二种情况是具有减增......
提出一种工具之间带有扩充链的优先约束的分批排序问题,这种扩充链上既有优先序工件又有无约束工件（工件个数不定）。目标为极小化最......
