【数学规划问题与多项式时间算法】.pdf

杭州大学研究生论文稿纸摘要本文共分三个部兮:第一部分比较系统地介绍了近年来在用多项式内点算法求解张性规划问题上的研究成果.第二部分我们提出了一个对偶算法,该算法主“与对偶标度及位势函数的梯度相关,每次送代者取对偶步或者重敦计算原始变量,并且至多只 L)次送代就可收敛到线性规划问题的最优解集.第三部分我们提出3一个原始一对偶的位势下降算法。若初始为某一内部行解且在该的位势区数值不大于0(5L),那么该算法至多只需响 o(n)次算术运算就求得残性规划问题的精确解。

目录前言第一章求解线性规划问题多须式算法之概述.s1引言 2路经跟踪算法 S3位势函数算法第二章关于线性规划的一个 o(nL)次位势下降算达引引言 2线性规划和位势函数 53尊法及收敛性分析第三章关于线性规划的一个原始一对偶位势下降算适

后人们对各种算达进行了研空,看其是否为多项式算法。自然,对求解线性规划的单纯形法也进行了研空。19江年,V.klee和G.M树玲出一个例子,他们构造一个线性规划问题,用单纯形违求解,所需计算对间为 0。这个例子表明,单纯形算法虽然在实用中非常有效,至今占有绝对优势,但在望论上它还不是多项式算法.1979年苏联数学家π.又ay过第一个给出解线性规划的多项式算法,即所谓能椭球算法。安的计算复杂性为 0(nL2),其中几是变量的维数,上是输入卡度。这个算法在理论上是重安的,但计算结果却远不及单纯形选有效。那么,能否找到实用上也确实有放的多项式对问算法？