线性规划典型算法的研究

VIP免费
3.0 陈辉 2024-11-19 6 4 767.31KB 70 页 15积分
侵权投诉
摘 要
线性规划是运筹学的重要分支，无论在理论上还是实际应用中都有着非常重
要的意义。其算法是运筹学中研究地最成熟的，是运筹学其他规划算法研究的基
础。由于自协调理论的出现，其内点法能非常容易地推广到更为复杂的非线性优
化问题上，如非线性凸规划、非线性互补、变分不等式、半-定优化以及二阶-锥优
化等。而实际应用上，线性规划已渗透到社会经济生产的各行各业，成为生产制
造、市场营销、银行贷款、股票行情、出租车费、统筹运输、电话资费、电脑上
网等热点现实问题决策的依据。
目前，线性规划的典型算法主要有单纯形法、椭球法及内点法三类。这三类
算法各有优缺点。从理论上说，椭球法和内点法是多项式时间算法，优于单纯形
算法，但在实践中，单纯形算法的表现往往很好，尤其是当问题规模不太大的时
候。这些理论上或实践上的差异说明了当前线性规划的研究并不完善，还有大量
的工作有待我们去完成。
本文在现有线性规划典型算法的基础上，综合运用优化理论、数学分析、线
性空间理论等知识，将理论分析、数学模型和实例验证结合起来，从理论和实验
两方面探索算法的性能，希望得到更好的算法。主要有以下几个研究内容：一是
对线性规划典型算法的思想进行了适当地梳理，由于线性规划的理论成果十分丰
富，这样的梳理工作是非常必要的；二是在研究椭球法的思想后，分析其算法存
在的优劣对其进行改进；三是对自协调函数理论的思想和方法进行了深入分析的
基础上，提出了一种新的自协调函数，相对于常用的对数形式的自协调函数，这
种新的自协调函数具有全局的性质，从而可以避免内点的限制，设计出新的线性
规划的算法。最后通过特例来验证算法的可行性。
本文为系统科学、人工智能、优化理论以及复杂性科学等一系列跨学科领域
的发展提供了新的思想方法，同时为工程技术、社会经济等范畴内的相关问题提
供有效的解决工具和手段。
关键词：线性规划 计算复杂性 椭球法 内点法 自协调函数
ABSTRACT
Linear programming is an important branch of operations research, both in theory
and practical application. It’s the most mature part of operations research, and it's the
basis of other optimization algorithms. Since the self-coordination theory was
proposed, the interior point method can be very easily extended to more complex
nonlinear optimization problems, such as nonlinear convex programming, linear
complementarity, variational inequalities, semi-fixed optimization and two order-cone
optimization. And in practical applications field, linear programming has been a basis
for decision making in all kinds sectors of socio-economic production, such as
manufacturing, marketing, bank loans and so on.
Until now, the typical linear programming algorithms mainly include three
algorithms ,simplex method，ellipsoid method and interior point algorithm. These three
algorithms have their advantages and disadvantages. In theory, ellipsoid method and
interior point algorithm are better than simplex method, but the simplex method always
plays well, especially when the scale of problem is small. These differences between
theory and practice show that the study of linear programming is not perfect, and there
is a lot of work need us to do.
The paper study the typical linear programming algorithms by integrated appling
optimization theory, mathematical analysis, linear space theory so that to find a good
linear programming algorithm. The main content of this paper includes three points.
One is carding the idea of linear programming algorithms. Since the research of linear
programming algorithms is very numerous, the carding work is very necessary. The
second is to analy the advantages and disadvantages of the algorithm after studying the
ellipsoid method and then improve the algorithm. The finally, the paper have proposed
a new self–coordination function on the basis of the analies of the idea and method of
the self–coordination function, and has verified it valid by special case.
Key Words: computational complexity, linear programming,
Interior point method, ellipsoid method, self –
coordination function
目 录
中文摘要
ABSTRACT
第一章 绪 论............................................................................................................... 1
§1.1 研究背景及意义............................................................................................... 1
§1.2 研究内容及章节安排 ....................................................................................... 2
第二章 计算复杂性和算法研究现状 ......................................................................... 5
§2.1 引言................................................................................................................... 5
§2.2 计算复杂性....................................................................................................... 5
§2.3 研究现状 ..............................................................................................................................10
§2.4 小结................................................................................................................. 16
第三章 椭球法 ........................................................................................................... 17
§3.1 引 言............................................................................................................... 17
§3.2 椭球法 ............................................................................................................ 17
§3.2.1 割平面思想.............................................................................................. 17
§3.2.2 Khanchian椭球法 ..................................................................................... 19
§3.2.3 椭球法的改进........................................................................................... 21
§3.3 仿真实践 ......................................................................................................... 26
§3.4 小结 ................................................................................................................ 27
第四章 内点法 ........................................................................................................... 29
§4.1 引 言.............................................................................................................. 29
§4.2 内点法思想及主要概念 ................................................................................ 29
§4.2.1 投影法...................................................................................................... 29
§4.2.2 仿射尺度法............................................................................................... 32
§4.2.3 路径跟踪法.............................................................................................. 35
§4.3 原-对偶内点法................................................................................................ 35
§4.3.1 原-对偶算法基本思想 ............................................................................. 35
§4.3.2 原-对偶路径跟踪法 ................................................................................. 37
§4.4 本章小结 ........................................................................................................ 39
第五章 自协调函数 ................................................................................................... 41
§5.1 引 言.............................................................................................................. 41
§5.2 自协调函数 .................................................................................................... 41
§5.2.1 自协调函数描述...................................................................................... 41
§5.2.2 牛顿法...................................................................................................... 43
§5.2.3 收敛性证明.............................................................................................. 45
§5.2.4 自协调理论分析...................................................................................... 49
§5.3 构造自协调函数 ............................................................................................ 55
§5.4 本章小结 ........................................................................................................ 62
第六章 结论与展望 ................................................................................................... 63
§6.1 结 论.............................................................................................................. 63
第一章 绪 论
1
第一章 绪 论
§1.1 研究背景及意义
运筹学是以数学为基础，用数学的方法解决国民经济和工程应用问题的一门
学科，是系统工程学和现代管理科学的基础理论和不可缺少的方法、手段。随着
科学技术和生产的发展，运筹学已在现代企业建设管理中发挥了越来越重要的作
用。运筹学本身也在不断发展，至今已包括数学规划、图论、网络流、决策分析、
排队论、可靠性数学理论、库存论、对策论、搜索论、模拟等多个分支，其中数
学规划又分为线性规划、非线性规划、整数规划、组合规划等。
线性规划作为运筹学的一个重要分支，在运筹学的发展中起着至关重要的作
用，可以说运筹学规划领域的重大突破总是始于线性规划。线性规划这一概念是
在1947 年的军事行动计划有关实践中产生的,而相关问题 1823 年Fourier 和1911
年Poussin 就已经提出过。发展至今已有将近 100 年的历史了，现在已成为生产制
造、市场营销、银行贷款、股票行情、出租车费、统筹运输、电话资费、电脑上
网等热点现实问题决策的依据。线性规划就是在满足线性约束下，求线性函数的
极值。
线性规划的广泛应用以及其涉及的数学理论、计算方法吸引了一批有一批的
专家学者，发展至今，线性规划已形成了一套自己的理论算法体系。线性规划的
典型算法有：
¾ 单纯形法（simplex method）
¾ 椭球法（Ellipsoid Method）
¾ 内点法（Interior-point Method）
¾ 由上述算法改进变形得到的算法
¾ 一些人工智能算法，如遗传算法、蚂蚁算法、神经网络等
单纯形法实施简单，特别对小规模问题效果显著。然而 1972 年Klee 等人证明
了单纯形法求解线性规划的计算复杂度是指数型的，这就吸引大量学者研究 是否
存在某种单纯形法的变形或改进使其在求解线性规划问题时的时间复杂度为多项
式时间。
椭球法第一次证明线性规划问题理论上是存在多项式时间算法的。与线性规
划的其他解法如单纯形法、内点法相比，椭球法的计算较简单，单纯形法、内点
法的迭代算法都需要从一个基础解出发，然后确定迭代方向、迭代步长，而且每
次迭代都需要计算目标函数和所有约束函数，椭球法则不需要。因而理论上来说
椭球法对于约束条件多的问题更有效。这也为我们在研究数学规划的求解算法时
线性规划典型算法的研究
2
提供了一个思维方向。
内点法最初由 Karmarkar 提出，比椭球法要好的是，这个算法就算是在最坏的
情况下在时间复杂度上也优于单纯形法，在大型实际问题中也有潜力与单纯形法
竞争。内点法的提出是线性规划发展的一个高峰，而 1994 年自协调函数理论
（Self-Concordant）的提出为线性规划的发展带来了另一个高峰，它使基于对数障
碍函数的线性规划内点法很容易推广到更为复杂的非线性优化问题上，如非线性
凸规划、非线性互补、变分不等式、半-定优化以及二阶-锥优化等。
目前，一方面学者们对线性规划的研究仍然是从理论与实践两方面展开的。
上述三种算法各有优点，实践上单纯形法与内点法优于椭球法，而理论上椭球法
又与内点法优于单纯形法，对于小规模问题单纯形法优于内点法，大规模问题内
点法优于单纯形法，且对于线性多目标规划、参数线性规划、线性规划的灵敏度
分析，目前单纯形法的效用还是其他线性规划算法不可替代的 [1]。这就说明了当
前的线性规划研究理论分析与实际效果之间存在巨大间隙，进而说明了在理论上
进一步改进算法的计算复杂性是可能的。
另一方面整数规划、0-1 规划、非线性规划等都是数学规划领域的难题，线性
规划算法研究对非线性规划算法发展的推动效果是明显的，而整数规划与 0-1 规划
的模型都是线性规划的模型，这两类问题已被确认为 NP 难题，因而研究线形规划
的算法，对这些问题的算法研究都是有启示及推动作用的。
§1.2 研究内容及章节安排
本文在现有线性规划典型算法的基础上，综合运用优化理论、数学分析、线
性空间理论等知识，将理论分析、数学模型和实例验证结合起来，从理论和实验
两方面探索算法的性能，希望得到更好的算法。主要有以下几个研究内容：一是
对线性规划典型算法的思想进行了适当地梳理，由于线性规划的理论成果十分丰
富，这样的梳理工作是非常必要的；二是在研究椭球法的思想后，分析其算法存
在的优劣对其进行改进；三是对自协调函数理论的思想和方法进行了深入分析的
基础上，提出了一种新的自协调函数，相对于常用的对数形式的自协调函数，这
种新的自协调函数具有全局的性质，从而可以避免内点的限制，设计出新的线性
规划的算法。最后通过特例来验证算法的可行性。其整体框架内容如1-1所示。
第一章 绪 论
3
图 1-1 论文整体框架内容
各章主要内容简述如下：
第二章是介绍了计算复杂性，并从计算复杂性的角度给出了线性规划算法的
综述，介绍了目前常用几种线性规划算法：单纯形法，基线法（一种基于优面的
算法，相对于单纯形法提出的），椭球法及内点法。
第三章介绍了椭球算法基本原理，从其本质出发给出了割平面法基本思想的
描述。对经典椭球法进行了分析与改进，并给出了用改进算法求解的基本步骤以
及算法的时间复杂度。
第四章介绍了内点法的基本原理，介绍了常见的三类内点算法的基本思想，
并对目前最受欢迎、应用最多的原-对偶内点法进行了分析及研究。
第五章从牛顿法的收敛性函数的计算复杂度出发，介绍了自协调函数的概念、
效用及常用几种形式。并分析了自协调框架下原-对偶内点法的计算复杂度。最后
根据自协调函数的概念构造了一个新的自协调函数形式，并以特例形式，对其实
用性进行了探讨。
第六章对本论文的研究结果进行了总结，并对后续工作的研究方向进行了展
望。
第一章 绪论
第二章 计算复杂性和
线性规划算法
第四章 内点法 第三章 椭球法 第五章 自协调函数
第六章 结论与展望
摘要：

摘要线性规划是运筹学的重要分支，无论在理论上还是实际应用中都有着非常重要的意义。其算法是运筹学中研究地最成熟的，是运筹学其他规划算法研究的基础。由于自协调理论的出现，其内点法能非常容易地推广到更为复杂的非线性优化问题上，如非线性凸规划、非线性互补、变分不等式、半-定优化以及二阶-锥优化等。而实际应用上，线性规划已渗透到社会经济生产的各行各业，成为生产制造、市场营销、银行贷款、股票行情、出租车费、统筹运输、电话资费、电脑上网等热点现实问题决策的依据。目前，线性规划的典型算法主要有单纯形法、椭球法及内点法三类。这三类算法各有优缺点。从理论上说，椭球法和内点法是多项式时间算法，优于单纯形算法，但在实...

展开>> 收起<<
线性规划典型算法的研究.pdf

共70页,预览7页

还剩页未读， 继续阅读

相关推荐

更多
立即下载
作者：陈辉 分类：高等教育资料 价格：15积分 属性：70 页 大小：767.31KB 格式：PDF 时间：2024-11-19

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务

作者详情

相关内容

更多

推荐作者

热门标签

/ 70
评分 收藏
分享
立即下载 VIP免费下载
客服
关注