建模作业内点法.doc

建模作业内点法.doc内点法求解线性规划问题
内点法简介：
单纯形法及其变型一直是实际应用中极其有效的计算方法。但是，在实际计算中单纯形 法有不少缺点。随着约束条件和变量数目的增加，迭代次数也迅速增加，在最坏情况下，单纯 形法的迭代次数会按指数上升，收敛很慢ol979年,Khachian提出了线性规划问题的第一个多 项式时间算法一椭球法，取得了理论上的重大突破。但是由于受有限精度计算的限制，椭球 法的应用效果还不能与单纯形法相比拟。现代内点理论的基木思想是：起点在“宇宙中心”, 用梯度法从起点寻找一个下降方向，因为从起点走出去第一步效果最好，则设法使每一次走 出去都是第一步（用非线性的投影变换有回到新的宇宙中心，就不会碰到边界）。Karmarkar提 出的内点法是建立在单纯形结构之上的，但与单纯形法沿着可行域边界寻优不同，内点法从初 始内点出发，沿着最速下降方向，从可行域内部直接走向最优解。内点法是在可行域内部寻优, 对于大规模线性规划问题，当约束条件和变量数目增加时，内点法的迭代次数变化较少。内点 法是一种具有多项式时间复杂性的线性规划算法，其收敛性和计算速度均优于单纯形法，计 算时间比单纯形法快50倍。内点法在形式上与经典障碍法等价，而且对于线性、非线性问题 可以统一解法。
内点算法主要有三大类：
（1） 投影尺度法，它是Karmarkar算法的原型。这个方法要求问题具有特殊的单纯形结构 和最优目标值为零，在实际计算过程中，需要用复杂的变换将实际问题转换为这种标准形式。 因此，投影尺度法在实际中应用较少。
（2） 仿射尺度法，这是一种已经比较成熟和广泛的算法。目前原仿射尺度法和对偶仿射 尺度法虽然应用较多，但这两种方法的多项式时间复杂性还不能从理论上得到证明。
（3）路径跟踪法，又称为跟踪中心轨迹法。这种方法将对数壁垒函数与牛顿法结合起来应 用到线性规划问题，并且已经从理论上证明具有多项式时间复杂性。路径跟踪法收敛迅速，鲁 棒性强，对初值的选择不敏感，现在已经被推广应用到二次规划领域，正被进一步发展为从复杂 性角度研究一般非线性规划的内点算法，是目前最有发展潜力的一类内点算法。内点法在收敛 性、计算速度等方面具有单纯形法无法替代的优势，因此人们纷纷采用仿射尺度法和路径跟踪 法研究各种大规模、复杂的线性规划问题，并将其推广应用于求解各种二次规划和非线性规划 问题。近年来，仿射尺度法和路径跟踪法在求解电力系统优化问题中也得到广泛的应用，如水 库优化调度、安全约束的经济调度、安全控制、状态估计、静态电压稳定分析、实时电价计 算、无功优化和最优潮流等。但投影尺度法的应用相对较少。
一、椭球形算法
1、变换问题提法
「原问题：min CTX
AX >b
X >0
对偶问题max yTZ?
yta<ct
y >o
CTX<YTb
于是知，若有最优解，则构造的下述复合不等式必成立：
A A A
AX<b
A
x no
。然后 AX<b+s
构造一个大的球体，使其必包含不等式可行解（若存在的话）对球心判断是否为可行解，若 是，结束；否则，切割球体，（切去肯定不包含可行解部分）直至找到可行解，或证明无可行 解。
、Karmrkar算法思路
出发点：与单纯形法不同，不沿边走，而从内部寻优。
1995年Fri