一、寻找第一个对偶可行基的方法(论文文献综述)
金秋霞[1](2020)在《基于社交网络分析的混合整数规划问题求解难度预估与应用研究》文中认为作为运筹学重要内容之一的混合整数规划问题,在制造业、农业、航空运输业和金融业等领域具有广泛应用。线性规划问题发展至今,已提出和发展了多种多样的用于解决不同类型问题的算法和先进求解器。而针对不同类型和难度的问题,应当选择最合适的算法或者求解器进行求解,从而能降低计算成本,同时提高解的质量。因此,通过对问题的求解难度进行预估,有助于判断应采用何种算法或如何设置求解器参数进行求解。本文利用社交网络分析方法,将其创新性地应用于数学领域。用网络图表达混合整数规划问题,并从不同社交网络分析指标,对不同求解难度的混合整数规划问题进行统计分析,筛选出能反映求解难度的关键特征并由此建立难度预测模型,此外还基于关键特征提出了优化混合整数规划问题求解效率的改进算法。最后以实际印刷电路板装配线平衡问题以及大学课程时间表安排问题为研究案例,将基于社交网络分析的混合整数规划问题的特征分析方法、求解难度预估模型以及求解优化方法应用于其中,发现所提出的模型与方法具有良好的理论意义和实用价值。本文研究工作和主要成果如下:(1)分析了混合整数规划问题的研究现状以及MIPLIB(The Mixed Integer Programming Library)所提供的带有求解难度标签的混合整数规划问题集特征,采用交邻图对混合整数规划问题样本集进行可视化表达,并按照类别标签进行分类。应用社交网络分析方法,选取了能良好反映网络凝聚性、中心性、传递性以及最短路径等的社交网络指标,对交邻图进行特征提取,并将数据按类别标签进行区分。(2)针对含有交邻图社交网络特征的数据,在进行数据预处理后,对每一分析指标下的数据按类别标签分类,并以箱型图、小提琴图和抖动图相结合的方式展示数据分布情况,给出了描述性统计分析结果。应用Shapiro-Wilk正态性检验方法检验得到数据并不符合正态分布,因此采用非参数检验方法进行后续显着性检验。利用Kruskal-Wallis显着性检验方法,检验每一分析指标下不同类别的数据是否具有显着性差异。再利用其事后检验方法,Dunn检验方法就两两类别之间做显着性差异检验。(3)基于在Kruskal-Wallis检验和Dunn检验的双重检验下,保留在不同类别间具有显着性差异的分析指标作为关键特征。采用Bootstrap重采样方法,估计不同类别的数据在每一关键特征下的中位数和均值,以呈现具有不同类别标签的混合整数规划问题在各个关键指标下的平均水平。(4)对关键特征进行了Spearman相关性分析,以相关性矩阵图的形式阐释了关键特征之间具有较高的相关性,即具有多重共线性。应用主成分分析消除了数据之间的多重共线性,避免了多重共线性对线性分类模型分类效果的影响。并采用累计方差比例和Kaiser-Guttman规则,选择了保留了80%以上原始数据信息的主成分,完成了数据降维。在降维数据的基础上,采用逻辑回归、线性判别分析以及随机森林构建了预测模型。对带有类别标签的降维数据分为了训练集和测试集,对每一个分类模型都进行了10次10折交叉验证,并采用SMOTE采样技术解决数据不平衡问题。从预测结果准确率、Kappa值、AUC以及运行时间等角度,对三类预测模型进行了性能比较,最终得到三者表现性能相当且分类准确率可达86%左右,其中线性判别分析分类模型相对最好。(5)基于关键特征提出两种了优化混合整数规划问题求解效率的优化算法,一种是基于混合整数规划问题结构特性,即变量数量和约束条件数量,提出从分支定界法的线性松弛规划算法角度,针对不同的变量与约束条件数量之比,提出优化算法;另一种是基于混合整数规划问题对偶交邻图的社交网络特性,度中心性和中介中心性,对混合整数规划问题模型做出优化。两种优化算法经算例验证,具有可靠性和有效性。(6)开展了实例分析,其中实际应用案例包括印刷电路板装配线平衡问题和基于课程设置的课程时间表问题。通过构建实际应用案例的混合整数规划数学模型,生成交邻图,再结合上述的分析方法和构建的预测模型,对相应的混合整数规划问题进行特征分析和求解难度预测。对应不同类型的问题,采用不同优化算法进行求解,并比较了不同的优化算法的求解性能,验证了预测模型和算法的可行性和有效性。
王奇[2](2019)在《考虑货运的航班应急调度问题》文中进行了进一步梳理目前,随着综合国力的日益提高以及智能化技术的迅猛发展,航空货运领域的运输规模逐年增长,航空快递日益繁忙。目前航空货运的人工调度已经开始阻碍当前航空货运的迅猛发展。无论是传统的客机腹仓的运输模式,还是目前逐渐成熟的全货机运输,都面临着许多机遇和挑战,亟需进一步的解决。航空货运航班的排班和应急调度问题都可以划分为一般性的调度问题,这两者在航空运输企业的日常运营中都占有重要地位。降低航空运输企业的运营成本,缩短航空配送时间,提高航空服务的品质构成了目前航空运输企业的核心竞争力。然而,目前在航空货运领域的研究主要集中在可达性分析,收益分析,缺乏关于航空货运航班的应急调度研究,本文拓展了航空货运在应急调度方面的研究。本文首个将航空货运中的客机腹仓和货机运输两种常见运输模式同时考虑,研究这两种类型航班的同时考虑应急调度问题,以达到应急调度中的综合最优。文章首先对航班调度问题的相关研究进行了详尽的整理和分析,主要介绍了国内外航空领域排班和应急调度的研究现状,并对航班排班和应急调度中的经典算法进行了归纳和总结,为之后航空货运输的应急调度算法做了铺垫。本文通过对客机腹仓和货机运输两种航班的分析,分别建立了基于时空网络的多商品流模型以及集覆盖模型。基于时空网络的多商品流模型可以在小规模下达到最优解,但一旦涉及大规模问题时,多商品流模型由于其决策变量会随着问题规模的扩大急剧上升,因此将多商品流模型作为小规模的标杆。而集覆盖模型,我们可以利用列生成的方式把问题分解成主问题和子问题。在案例分析部分,我们首先在小规模案例,以多商品流模型为标杆验证了列生成算法的有效性。之后,基于实际数据设计了货物航班应急调度的大规模案例,案例的求解结果验证了算法的求解质量与效率。
黄启文[3](2019)在《规模化风电接入的电力系统经济调度并行算法研究》文中指出风能是一种最具规模化应用前景的可再生能源,风力发电近年来得到了大力开发与应用。但这些具有随机特性的风电并网接入现有电力系统后,其动态经济调度问题的建模和求解均面临巨大挑战。目前,采用Monte Carlo抽样方法模拟风电随机特性,将随机动态经济调度问题转化为场景模型或样本均值近似模型,是最基本的建模方法,也是评价其它随机调度模型精确度的基准方法。但场景模型和样本均值近似模型均为大规模的线性或二次规划模型,对其直接求解,将面临维数灾难题。本文重点研究规模化风电接入的电力系统随机动态经济调度场景模型和样本均值近似模型的并行求解方法。首先,采用Monte Carlo抽样方法建立了规模化风电接入的电力系统随机动态经济调度问题的场景模型。该模型以最小化发电成本为目标,通过引入场景转移约束,将随机优化问题转化为确定性优化问题。采用Dantzig-Wolfe分解算法对该模型实施场景解耦,可以将具有数千万个变量与约束的大规模问题分解为一系列仅含数万个变量与约束的子问题,以及一个规模更小的主问题。在迭代计算过程中,利用改进次梯度法改善算法的收敛性,并运用GAMS平台的网格计算工具构建了快速求解各个场景子问题的并行计算框架。该方法既降低了对计算机内存的要求从而成功解决原来无法计算的问题,又提高了高维问题的求解效率,因而具备工程应用价值。以IEEE 39节点系统和某省级实际电力系统为例,验证了 Dantzig-Wolfe分解算法并行策略的有效性。其次,采用Monte Carlo抽样方法建立了规模化风电接入的电力系统随机动态经济调度问题的样本均值近似模型。该模型以购电费用最小为目标,在第一个时段存在非预测性约束。针对约束系数矩阵的块对角加单边结构及具有稀疏性的特点,设计了并行单纯形法。通过对规模巨大的基矩阵进行线性变换,实现关键计算步骤的分块运算,有效改善单纯形法的计算性能,算法具有可拓展性。运用Matlab软件的并行计算工具箱和并行计算服务对内存开销大且高计算耗时的步骤实现并行计算,有效降低对计算机内存的需求并减少计算时间。最后,通过对IEEE 39节点系统和某省级实际电力系统进行计算分析,验证了并行单纯形法的有效性。
刘雁灵,李菲[4](2018)在《线性规划中关于避免人工变量的一个注记》文中研究表明讨论了线性规划问题中避免人工变量的一种方法.一方面在寻找初始解时不要求右项的非负性,另一方面也突破了传统的单纯形法中用主列非负元素除右项的想法,推广并改进了单纯形法的计算.
高培旺[5](2017)在《目标超平面上的一种原始-对偶单纯形算法》文中研究说明对于目标最优值已知的情形,提出一次迭代到目标超平面上获得相应的对偶可行基,然后应用Samaras等的原始-对偶算法在目标超平面上进行对偶迭代.在确定枢轴列时,采用无比值检验方法,节省了计算工作量.为防止Samaras等的原始-对偶算法在原始可行点退化情形下可能发生的循环现象,加快迭代进程,引入MBU对偶单纯形算法进行迭代,直到对偶间隙严格缩少.中大规模数值试验结果表明,与经典单纯形算法相比,该算法在大部分算例上使用更少的迭代次数和执行时间,具有更高的计算效率.
敖特根[6](2014)在《线性规划的起因和发展》文中研究指明线性规划是运筹学的一个分支,线性规划的产生和发展引领了非线性规划和动态规划的发展。线性规划主要有两个方面的研究内容,一是规划。二是计算方法。这个规划的目标函数和约束函数都是线性函数,线性规划这个名称也是由此而演变形成的。线性规划研究者的主要目的在于如何制定计划,而不在于执行或实施计划。可以把这些有关学问所形成的整个领域称做“规划”,在于着重强调极大化或极小化问题时候,还可以称做最优规划。简单的说,线性规划所考虑的问题是如何按照最佳可能的(最优)方式来计划一项各种相互关联的活动的集合体。这个方法是求解线性规划问题的特殊方法,叫做单纯形法。线性规划不仅是运筹学中最早形成的分支,而且也应用非常广泛的一个分支。因此,对线性规划史的研究,具有十分重要的历史意义和现实价值。本文在查阅参考大量原始文献和有关研究文献的基础上,以曲安京教授的“为什么数学”思想为切入点,在分析研究归纳综合的基础上,对线性规划问题的历史进程进行了较为详细的研究。本文主要研究成果有:(1)讨论和分析冯·诺伊曼(J. V. Neumann)关于博弈论研究对线性规划的影响。(2)讨论和分析李昂替夫(W. W. Leontief)关于投入-产出的研究对线性规划发展的影响。(3)讨论和分析希奇柯克(F. L. Hitchcock)关于运输问题的研究和斯蒂格勒(G.J.Stigler)关于营养问题的研究对线性规划发展的影响。(4)讨论和分析了丹齐格(G. B. Dantzig)对线性规划的贡献及单纯形法的创建。(5)分析和讨论单纯形法的发展进程和我国线性规划学习发展历程。
于祖国[7](2014)在《运筹学在测绘工作中的应用》文中提出随着经济的发展和现代科学技术水平的提高,测绘工作所涉及的内容越来越复杂。无论是在工程测量、摄影测量、GPS测量或是地理信息系统方面,无论是针对测绘生产管理,还是针对控制网的优化设计,都有很多问题可以通过运筹学的方法解决。本文介绍了运筹学的各个理论分支,并在参考前人研究的基础上,分析了运筹学在测绘生产管理、数据处理、数字图像处理以及地理信息系统建设中的各种应用。具体研究了在测绘生产管理中,线性规划、目标规划、整数规划等运筹学理论的应用。通过一个实例说明了应用线性规划方法进行测绘生产计划安排的具体方法。同时具体分析了当问题的各种参数条件发生变化时,如何应用灵敏度分析、目标规划、整数规划等方法进行求解。另一方面研究了在水准网优化设计中线性规划方法的应用。推导出相应的计算公式,并给出了具体的解算方法。同时编写了相应的计算程序以辅助计算。在同一水准网中,根据需要达到的精度和施测仪器精度不同,模拟了的六个方案,通过对不同方案的解算以及结果的比较,做出了相应的结论。这些结论与通常的认知是相符合的,因此它们也可以验证这种水准网优化方法的正确性。
刘道建[8](2013)在《SLI的条件冗余性及LP问题的算法研究》文中研究说明自从前苏联数学家Konterovitch和美国学者Koopmans先后提出LP问题及其数学模型以来,1947年,美国学者G. B. Dantzig (丹捷格)提出单纯形法被认为是线性规划理论研究的一次重大突破,该算法的出现为线性规划开辟了无限广阔的应用空间与前景。迄今,线性规划研究已取得巨大而辉煌的成就,在LP算法研究方面更是硕果累累。目前,LP算法构成了三大主流派系,它们是,以美国学者G. B. Dantzig所提出的单纯形法为代表的主元算法体系、以前苏联学者Khachiyan L.G所提出的椭球法为代表的割区域算法体系和以美国学者N. Karmarkar所提出的Karmarkar投影法为代表的内点迭代算法体系,其中,当属内点法派系的研究成果最为丰硕。实际上,线性规划同时具备两个最显着特性——线性及几何平面特性,当前,三大算法体系均未能综合利用好这两大特性。单纯形法类方法均属非多项式时间算法,主要针对线性特性而提出,没能体现及利用好几何平面这一特性,它们的迭代运算极易受基退化现象的干扰与影响;椭球法类方法和内点法类方法尽管理论上是多项式时间算法,但均属非线性类方法,而且都是从非线性规划算法移植而来,更无法体现及利用好几何平面这一特性,它们的非线性化处理方式导致了迭代计算十分繁杂,严重影响了搜索效率,在实际应用中,搜索效果甚至还比不上单纯形方法!本文针对当前LP算法的研究现状,充分考虑到线性规划的两面性特点,运用解析几何、线性空间理论、线性流形理论、线性规划的灵敏度分析理论及凸规划理论等,提出了有别于当前三大算法体系的LP问题新求解方案——基点定向转移搜索方案与消冗降阶方案,并围绕这两大新求解方案,重点探讨了如下几个方面的问题——条件约束冗余性问题,SLI的定解问题,l-正流形锥的可分离性问题,可行域代数、几何刻画问题以及退化基点的非退化转移问题。在此基础上,提出了多种LP问题的新求解方法及SLI的新定解方法。本文研究成果主要表现在如下几个方面:1.构建了单纯形基点的转移模型——基点转移矩阵及其运算法则,为算法研究解决了运算平台这一关键性问题,以此提出了一种LP问题的新求解方案——基点定向转移搜索方案,将LP问题的求解过程变成了矩阵的初等列变换过程,并提出了包括VSEDT迭代法在内的几种LP问题的基点定向转移搜索算法;2.为充分利用非退化基点的优良转移性能、彻底消除退化现象对基点迭代转移的不利影响,提出了单纯形平移扩张原理及局部正则化方法,确保基点迭代转移始终在非退化状况下进行,不仅解决了退化基点的可转移性问题,也较好地解决了单纯形算法中存在的基循环难题;3.基于条件约束冗余的几何特征,对其进行了代数刻画与描述,将条件约束几何冗余性判别问题变为SLI的定解问题,并将之应用到LP问题的解算研究中,提出了消冗降阶原理及LP问题的新求解方案——消冗降阶方案,进而提出了逐次消冗降阶算法及非负约束降阶预估—校正算法等LP新求解方法;4.针对SLI的定解问题,在引进l-正流形锥这一特殊代数结构及提出l-正流形锥可分离性等数学概念的基础上,对l-正流形锥的可分离性机理进行了较深入探讨,以l-正流形锥可分离性公理假设为基础,给出了关于l-正流形锥可分离性的一系列等价及判别定理,并提出了矩阵求逆的SLI新定解方法,为解决SLI定解问题找到了一条有效的新途径。
刘德龙[9](2012)在《浅谈线性规划相关理论在经济管理中的应用》文中提出采用矩阵模式介绍线性规划标准型和线性规划的核心技术单纯形法。提供了用矩阵初等行变换直接获得初始可行基的方法。通过典型实例较详细地展示了单纯形技术在标准模型、对偶模型、灵敏度分析诸方面的灵活应用,以期为使用者在不同信息环境下进行移植提供方便。
周学松,赵恒[10](2011)在《线性规划中一个避免人工变元的方法的改进》文中研究说明有许多文献讨论了线性规划问题中单纯形方法的改进(如文献[1~5]等)。我们在文献[1]的基础上,突破了传统方法中要求单纯形表中的基变量始终非负的想法,给出了求解线性规划问题中一个新的避免人工变量的方法,使其计算量得到减少。
二、寻找第一个对偶可行基的方法(论文开题报告)
(1)论文研究背景及目的
此处内容要求:
首先简单简介论文所研究问题的基本概念和背景,再而简单明了地指出论文所要研究解决的具体问题,并提出你的论文准备的观点或解决方法。
写法范例:
本文主要提出一款精简64位RISC处理器存储管理单元结构并详细分析其设计过程。在该MMU结构中,TLB采用叁个分离的TLB,TLB采用基于内容查找的相联存储器并行查找,支持粗粒度为64KB和细粒度为4KB两种页面大小,采用多级分层页表结构映射地址空间,并详细论述了四级页表转换过程,TLB结构组织等。该MMU结构将作为该处理器存储系统实现的一个重要组成部分。
(2)本文研究方法
调查法:该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法:用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法:通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法:通过调查文献来获得资料,从而全面的、正确的了解掌握研究方法。
实证研究法:依据现有的科学理论和实践的需要提出设计。
定性分析法:对研究对象进行“质”的方面的研究,这个方法需要计算的数据较少。
定量分析法:通过具体的数字,使人们对研究对象的认识进一步精确化。
跨学科研究法:运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法:这是社会科学用来分析社会现象的一种方法,从某一功能出发研究多个方面的影响。
模拟法:通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
三、寻找第一个对偶可行基的方法(论文提纲范文)
(1)基于社交网络分析的混合整数规划问题求解难度预估与应用研究(论文提纲范文)
摘要 |
ABSTRACT |
第一章 绪论 |
1.1 课题研究背景、目的与意义 |
1.1.1 课题研究背景 |
1.1.2 课题研究目的与意义 |
1.2 课题国内外研究现状 |
1.2.1 混合整数规划问题的研究现状 |
1.2.2 交邻图的研究现状 |
1.2.3 社交网络分析的研究现状 |
1.3 课题主要研究内容和技术路线 |
1.3.1 课题研究内容 |
1.3.2 课题技术路线 |
第二章 课题研究理论、数据与工具 |
2.1 课题研究理论定义 |
2.1.1 混合整数规划问题定义 |
2.1.2 交邻图与对偶交邻图定义 |
2.1.3 社交网络分析及其指标定义 |
2.2 课题研究数据来源 |
2.3 实验数据集样本选择 |
2.4 课题研究分析工具 |
2.5 本章小结 |
第三章 交邻图的特征分析与特征选择 |
3.1 MIP交邻图特征分析 |
3.2 MIP交邻图关键特征选择 |
3.2.1 关键特征选择方法流程设计 |
3.2.2 关键特征选择方法基本理论 |
3.3 关键特征选择结果分析 |
3.3.1 正态性检验结果 |
3.3.2 显着性检验结果 |
3.4 关键特征参数估计 |
3.4.1 Bootstrap参数估计方法 |
3.4.2 Bootstrap参数估计结果 |
3.5 本章小结 |
第四章 混合整数规划问题难度预测模型构建 |
4.1 关键特征相关性分析 |
4.1.1 Spearman秩相关系数 |
4.1.2 相关性分析结果 |
4.2 主成分分析 |
4.2.1 主成分分析方法 |
4.2.2 主成分分析结果 |
4.3 预测模型构建与评估 |
4.3.1 预测模型构建 |
4.3.2 预测模型评估 |
4.4 本章小结 |
第五章 基于关键特征的MIP求解优化算法 |
5.1 基于MIP问题结构特征的算法优化 |
5.1.1 MIP线性规划算法优化方法 |
5.1.2 算例验证 |
5.2 基于MIP交邻图特征的数学模型优化 |
5.2.1 MIP数学模型优化算法 |
5.2.2 算例验证 |
5.3 本章小结 |
第六章 应用案例分析 |
6.1 印刷电路板装配线平衡问题案例分析 |
6.1.1 问题定义 |
6.1.2 数学模型 |
6.1.3 PCB装配线实例描述 |
6.1.4 案例求解结果与分析 |
6.2 基于课程设置的课程时间表问题案例分析 |
6.2.1 问题定义 |
6.2.2 数学模型 |
6.2.3 CBCT实例描述 |
6.2.4 案例求解结果与分析 |
6.3 本章小结 |
第七章 结论与展望 |
7.1 结论 |
7.2 创新点 |
7.3 展望 |
参考文献 |
附录 |
致谢 |
作者简介 |
1 作者简历 |
2 攻读硕士学位期间发表的学术论文 |
3 参与的科研项目及获奖情况 |
4 软件着作权 |
学位论文数据集 |
(2)考虑货运的航班应急调度问题(论文提纲范文)
摘要 |
Abstract |
1 引言 |
1.1 研究背景及意义 |
1.2 国内外相关研究现状 |
1.2.1 航班应急调度问题国内外研究现状 |
1.2.2 航空货运相关问题国内外研究现状 |
1.3 研究的主要内容及技术路线 |
1.4 本章小结 |
2 相关理论及概念综述 |
2.1 航空货运简介 |
2.1.1 运输货物的分类 |
2.1.2 运输方式分类 |
2.1.3 航空货运的发展 |
2.2 货运航班应急调度问题的简介 |
2.2.1 问题的定义和特点 |
2.2.2 破坏场景 |
2.2.3 应急调度方式 |
2.2.4 成本构成及分析 |
2.3 货运航班的网络表述以及常见模型 |
2.3.1 网络表述 |
2.3.2 建模方式 |
2.4 航班应急调度算法分类 |
2.4.1 一般性算法 |
2.4.2 列生成算法 |
2.5 本章小结 |
3 问题分析和模型建立 |
3.1 问题分析 |
3.1.1 传统民航航班应急调度问题分析 |
3.1.2 非正常情况下航空货运的问题分析 |
3.2 基于时空网络的多商品流数学模型 |
3.2.1 时空网络模型 |
3.2.2 模型参数 |
3.2.3 决策变量 |
3.2.4 数学模型 |
3.3 列生成的数学模型 |
3.3.1 主问题的参数 |
3.3.2 主问题的决策变量 |
3.3.3 主问题的模型 |
3.3.4 客机腹仓和货机子问题 |
3.4 本章小结 |
4 算法设计 |
4.1 算法概述 |
4.2 基于时空网络的商品流模型大规模邻域算法 |
4.2.1 算法框架 |
4.2.2 弧的生成 |
4.3 列生成算法 |
4.3.1 破坏航班的预处理 |
4.3.2 简单延误的动态规划 |
4.3.3 考虑提前决策的子问题 |
4.3.4 考虑起飞、降落的子问题 |
4.3.5 考虑停机的子问题 |
4.4 本章小结 |
5 案例分析与结果展示 |
5.1 案例背景 |
5.2 问题描述 |
5.3 数据展示 |
5.4 结果分析 |
5.5 本章小结 |
6 总结与展望 |
6.1 总结 |
6.2 展望 |
参考文献 |
致谢 |
作者简历及攻读硕士学位期间的科研成果 |
(3)规模化风电接入的电力系统经济调度并行算法研究(论文提纲范文)
摘要 |
ABSTRACT |
第一章 绪论 |
1.1 选题背景与意义 |
1.2 国内外研究现状 |
1.2.1 含风电接入的电力系统优化调度方法 |
1.2.2 求解大规模优化调度问题的主要算法 |
1.3 本文主要工作 |
第二章 随机规划问题的建模及并行计算方法 |
2.1 随机规划问题的场景模型 |
2.2 随机规划问题的样本均值近似模型 |
2.3 DANTZIG-WOLFE分解方法 |
2.3.1 Dantzig-Wolfe分解法的基本原理 |
2.3.2 算法最优性分析 |
2.3.3 计算步骤 |
2.3.4 并行计算 |
2.4 并行单纯形法 |
2.4.1 单纯形法的基本原理 |
2.4.2 基矩阵的数学变换 |
2.4.3 算法设计与并行实现 |
2.5 本章小结 |
第三章 随机动态经济调度的场景模型及DANTZIG-WOLFE分解算法 |
3.1 随机动态经济调度问题的场景模型 |
3.1.1 优化目标 |
3.1.2 预测场景下的约束条件 |
3.1.3 误差场景下的约束条件 |
3.1.4 场景模型的紧凑形式 |
3.2 场景模型的DANTZIG-WOLFE分解及并行求解 |
3.2.1 场景模型的Dantzig-Wolfe分解 |
3.2.2 乘子修正策略 |
3.2.3 并行计算步骤 |
3.3 算例分析 |
3.3.1 小型测试系统 |
3.3.2 某省级系统 |
3.4 本章小结 |
第四章 随机动态经济调度的样本均值近似模型及并行单纯形算法 |
4.1 随机动态经济调度问题的样本均值近似模型 |
4.1.1 目标函数 |
4.1.2 各个场景的运行约束 |
4.1.3 样本均值近似模型的紧凑形式 |
4.2 并行单纯形法求解样本均值近似模型 |
4.2.1 模型的数学变换与并行计算 |
4.2.2 计算步骤 |
4.3 算例分析 |
4.3.1 小型测试系统 |
4.3.2 某省级系统 |
4.4 本章小结 |
结论 |
参考文献 |
攻读硕士学位期间取得的研究成果 |
致谢 |
附表 |
(4)线性规划中关于避免人工变量的一个注记(论文提纲范文)
1 避免人工变量的新算法 |
2 举例 |
3 结束语 |
(5)目标超平面上的一种原始-对偶单纯形算法(论文提纲范文)
1 算法描述 |
2 数值计算研究 |
3 结语 |
(6)线性规划的起因和发展(论文提纲范文)
摘要 |
Abstract |
第一章 前言 |
1.1 问题的提出 |
1.2 有关研究文献综述 |
1.2.1 线性不等式系统的理论建立和发展 |
1.2.2 博弈论的诞生 |
1.2.3 投入-产出模型的建立 |
1.2.4 运输问题和营养问题的研究 |
1.2.5 线性规划模型的建立和单纯形法的创建 |
1.2.6. 线性规划问题对偶模型的建立 |
1.2.7. 线性规划历史与相关历史研究文献 |
1.3 本文的研究方法与研究思路 |
1.4 研究内容和意义 |
1.4.1 研究内容 |
1.4.2 研究意义 |
1.5 研究的重点、难点和创新 |
1.5.1 研究重点 |
1.5.2 研究难点 |
1.5.3 研究的创新点 |
1.6 本文的结构安排 |
第二章 线性规划的起因 |
2.1. 冯·诺伊曼的工作 |
2.1.1 冯·诺伊曼简介 |
2.1.2 冯·诺伊曼对博弈论的贡献 |
2.1.3 冯·诺伊曼对经济均衡理论的贡献 |
2.1.4 关于线性不等式的贡献 |
2.1.5 结论 |
2.2 李昂铁夫的工作 |
2.2.1 李昂铁夫简介 |
2.2.2 李昂铁夫关于投入产出的贡献 |
2.2.3 结论 |
2.3 希奇柯克和斯蒂格勒的工作 |
2.3.1 希奇柯克的生平简介 |
2.3.2 希奇柯克的工作 |
2.3.3 斯蒂格勒生平简介 |
2.3.4 斯蒂格勒的工作 |
2.3.5 结论 |
第三章 丹齐格及相关人员工作 |
3.1 乔治·伯纳德·丹齐格 |
3.2 丹齐格的工作 |
3.2. 1 线性规划模型的建立 |
3.2.2 构造解 |
3.2.3 单纯形法在运输问题中的应用 |
3.3 单纯形法在博弈论的应用 |
3.3.1. 游戏的简化形式 |
3.3.2 对特殊游戏的应用 |
3.3.3 最小化玩家 |
3.4 线性规划和博弈论 |
3.4.1 符号和基本引理 |
3.4.2 线性规划问题 |
3.4.3 对偶问题 |
3.4.4 存在性 |
3.4.5 线性规划和博弈论 |
第四章 单纯形法的发展 |
4.1. 单纯形法发展 |
4.1.1. 二阶段法 |
4.1.2 扰动法、Bland法 |
4.1.3 改进的单纯形法 |
4.2 对偶单纯形法 |
4.2.1 对偶线性规划问题 |
4.2.2 对偶单纯形法 |
4.2.3 用Lagrange乘子解决线性规划问题 |
4.2.4 原始—对偶单纯形法 |
4.3 单纯形法在国内研究状况 |
4.4 结论 |
第五章 结论 |
5.1 博弈论研究是线性规划的一个起因 |
5.2 投入-产出问题研究是建立线性规划模型的雏形 |
5.3 运输问题是建立线性规划问题的典型例子 |
5.4 营养问题是第一个动态模型 |
5.5 线性规划的形成 |
5.6 线性规划的影响 |
参考文献 |
攻读博士学位期间发表的论文 |
攻读博士学位期间参加的学术活动 |
致谢 |
(7)运筹学在测绘工作中的应用(论文提纲范文)
摘要 |
Abstract |
第一章 绪论 |
1.1 运筹学的应用与发展 |
1.2 本文的研究背景、现状及意义 |
1.2.1 研究背景 |
1.2.2 研究现状 |
1.2.3 研究的目的和意义 |
1.3 本文研究的主要内容 |
1.4 本章小结 |
第二章 运筹学的基本理论 |
2.1 线性规划 |
2.1.1 线性规划的数学模型 |
2.1.2 线性规划的求解方法 |
2.2 对偶理论和灵敏度分析 |
2.2.1 对偶理论 |
2.2.2 灵敏度分析 |
2.2.3 参数线性规划 |
2.3 目标规划 |
2.4 整数规划 |
2.4.1 整数线性规划 |
2.4.2 整数规划的求解方法 |
2.5 动态规划 |
2.5.1 动态规划的基本概念 |
2.5.2 动态规划的基本解法 |
2.6 非线性规划 |
2.6.1 无约束极值问题 |
2.6.2 约束极值问题 |
2.7 图论 |
2.8 其他运筹学理论 |
2.8.1 决策论 |
2.8.2 排队论 |
2.8.3 存储论 |
2.9 本章小结 |
第三章 运筹学在测绘中的应用及模型建立的原则 |
3.1 在测绘生产管理中的应用 |
3.2 在测量数据处理中的应用 |
3.3 在数字图像处理中的应用 |
3.4 在地理信息系统建设中的应用 |
3.5 模型建立的原则 |
3.6 本章小结 |
第四章 数学规划在测绘生产管理中的运用 |
4.1 问题的提出 |
4.2 数学模型的建立 |
4.3 求解方法及步骤 |
4.3.1 单纯形法 |
4.3.2 人工变量法 |
4.4 实例计算 |
4.4.1 案例一 |
4.4.2 案例二 |
4.5 分析讨论 |
4.5.1 参数变化时求解最优解 |
4.5.2 最优解不变情况下求解参数变化范围 |
4.5.3 扩大生产问题 |
4.5.4 存在多目标情况下的求解 |
4.5.5 最优解要求为整数的情况 |
4.6 本章小结 |
第五章 线性规划在水准网优化中的应用 |
5.1 问题的提出 |
5.2 技术路线及求解方法 |
5.3 解算手段 |
5.4 算例分析 |
5.4.1 方案一 |
5.4.2 方案二 |
5.4.3 方案三 |
5.4.4 方案四 |
5.4.5 方案五 |
5.4.6 方案六 |
5.4.7 结论 |
5.5 本章小结 |
第六章 总结与展望 |
6.1 总结 |
6.2 展望 |
致谢 |
参考文献 |
附录A 攻读学位其间发表论文目录 |
附录B 水准网优化计算程序代码 |
(8)SLI的条件冗余性及LP问题的算法研究(论文提纲范文)
摘要 |
Abstract |
第1章 绪论 |
1.1 研究背景与选题意义 |
1.1.1 SLI条件多余性研究背景及意义 |
1.1.2 LP问题算法的研究背景及意义 |
1.2 当前主要LP问题算法综述 |
1.2.1 单纯形法概述 |
1.2.2 椭圆法概述 |
1.2.3 Karmarkar投影法概述 |
1.2.4 亏基单纯形法与基线算法概述 |
1.2.5 本节小结 |
1.3 本论文的主要研究内容 |
上篇 平移扩张原理与LP问题的基点定向转移搜索算法 |
内容提要 |
研究背景与任务 |
1 当前LP问题算法的功能状况 |
2 摄动原理及摄动单纯形法 |
3 主要任务 |
第2章 有关LP问题的基础性研究与探讨 |
前言 |
2.1 几个空间概念及相关性质 |
2.1.1 点、直线与平面 |
2.1.2 距离的定义 |
2.1.3 向量的数性积与矢性积 |
2.2 单纯形的相关描述 |
2.2.1 约束的冗余性 |
2.2.2 基点退化现象 |
2.3 本章小结 |
第3章 平移扩张原理与单纯形的局部正则化 |
前言 |
3.1 单纯形基点的一种点向式转移模型 |
3.1.1 单纯形基点转移特征的刻画与描述 |
3.1.2 模型的优点及存在的功能性缺陷 |
3.2 平移扩张原理 |
3.2.1 有关单纯形的概念及性质 |
3.2.2 退化现象的几何解释 |
3.2.3 单纯形的平移扩张及相关性质 |
3.3 非正则单纯形的局部正则化 |
3.4 章节小结 |
第4章 一种求解LP问题的VSEDT迭代算法 |
前言 |
4.1 构建LP问题的新算法平台—基点定向转移矩阵及其运算 |
4.2 小量正参数ε-正则化 |
4.2.1 顶点退化的起因分析 |
4.2.2 小量正参数ε-正则化方法 |
4.2.3 小量正参数ε-正则化阶段性终止条件 |
4.3 最优性判别定理 |
4.4 VSEDT迭代算法介绍 |
4.4.1 基本思路 |
4.4.2 基本操作 |
4.4.3 基本步骤 |
4.5 实例分析 |
4.6 VSEDT迭代法的改进—优势控制群迭代算法 |
4.6.1 相关问题分析 |
4.6.2 相关概念及性质 |
4.6.3 优势控制群迭代算法 |
4.6.4 例题对照 |
4.7 章节小结 |
第5章 一种求解LP问题的强迫性VSEDT迭代算法 |
前言 |
5.1 构建LP问题新算法平台—强迫性基点定向转移矩阵 |
5.2 几个最优性判别定理 |
5.3 强迫性VSEDT迭代算法介绍 |
5.3.1 基本思路与构想 |
5.3.2 主要操作 |
5.3.3 基本步骤 |
5.4 实例分析 |
5.5 强迫性VSEDT迭代法的改进方法—割区域搜索算法 |
前言 |
5.5.1 基本思路与构想 |
5.5.2 基本步骤 |
5.5.3 实例展示 |
5.6 强迫性VSEDT迭代算法的改进措施 |
5.7 章节小结 |
篇后语 |
下篇 LP问题的消冗降阶算法与SLI的条件冗余性 |
内容提要 |
研究背景与任务 |
1 当前LP算法研究的实际状况 |
2 研究目标与任务 |
第6章 消冗降阶原理及其应用与展望 |
前言 |
6.1 消冗、降阶定理及相关概念 |
6.2 逐次消冗降阶法 |
6.2.1 基本思想 |
6.2.2 算法基本构件 |
6.2.3 基本步骤 |
6.2.4 实例展示 |
6.3 非负约束降阶预估—校正算法 |
6.3.1 问题分析 |
6.3.2 相关概念与定理 |
6.3.3 非负约束降阶预估—校正算法 |
6.3.4 实例展示 |
6.4 影响原理应用的障碍及其展望 |
6.5 章节小结 |
第7章 一种SLI的矩阵变换定解方法 |
前言 |
7.1 一个新的SLI定解平台及其性质 |
7.1.1 强迫性基点转移矩阵及其运算 |
7.1.2 退化极点的转移问题与可行域的局部ε-正则化 |
7.2 线性不等式组的矩阵列变换定解方法 |
7.2.1 基本操作 |
7.2.2 基本步骤 |
7.3 实例展示 |
7.4 章节小结 |
第8章 l-正流形锥及其可分离性研究与应用 |
前言 |
8.1 l-正流形锥及可分离性定义及相关性质 |
8.2 l-正流形锥的可分离性公理及相关判别定理 |
8.3 l-正流形锥的可分离性在SLI定解问题中的应用 |
8.4 l-正流形锥分离性判法改进 |
8.4.1 基本构想 |
8.4.2 基本步骤与实施细则 |
8.4.3 实例展示 |
8.5 本章小结 |
篇后语 |
结论 |
1. 主要结论 |
2. 后续工作的展望 |
寄语 |
致谢 |
参考文献 |
攻读博士学位期间发表的论文及科研情况 |
1. 论文情况 |
2. 科研项目 |
(9)浅谈线性规划相关理论在经济管理中的应用(论文提纲范文)
一、线性规划相关理论简介 |
1.相关概念 |
2.线性规划的相关理论结果 |
(1) 相关定理 |
(2) 用矩阵解线性规划问题的单纯形简介 |
3.单纯形法求解的计算步骤 |
4.初始可行基的求法 |
二、线性规划理论在经济管理上的应用展示 |
1.资源利用问题 |
(1) 具体问题 |
(2) 建立模型 |
(3) 用单纯形法求解 |
2.环境污染治理费用问题 |
(1) 具体问题 |
(2) 建立模型 |
(3) 求解 |
3.生产中合理下料问题 |
(1) 具体问题 |
(2) 建立模型 |
(3) 求解 |
4.对偶问题及经济管理意义 |
(1) 具体问题 |
(2) 建立模型 |
(3) 求对偶问题的解 |
(4) 对偶问题的经济解释——影子价格 |
5.灵敏度分析在经济管理中的应用 |
(1) 若有一种新产品, 分析投产它是否有利 |
(2) 生产的产品工艺结构发生改变后的分析 |
(3) 增加一道工序对最优值的影响 |
三、结束语 |
(10)线性规划中一个避免人工变元的方法的改进(论文提纲范文)
0 引言 |
1 文献[1]中方法的进一步改进 |
2 几个例子 |
3 结束语 |
四、寻找第一个对偶可行基的方法(论文参考文献)
- [1]基于社交网络分析的混合整数规划问题求解难度预估与应用研究[D]. 金秋霞. 浙江工业大学, 2020(02)
- [2]考虑货运的航班应急调度问题[D]. 王奇. 大连海事大学, 2019(06)
- [3]规模化风电接入的电力系统经济调度并行算法研究[D]. 黄启文. 华南理工大学, 2019(01)
- [4]线性规划中关于避免人工变量的一个注记[J]. 刘雁灵,李菲. 赤峰学院学报(自然科学版), 2018(05)
- [5]目标超平面上的一种原始-对偶单纯形算法[J]. 高培旺. 徐州工程学院学报(自然科学版), 2017(04)
- [6]线性规划的起因和发展[D]. 敖特根. 西北大学, 2014(01)
- [7]运筹学在测绘工作中的应用[D]. 于祖国. 昆明理工大学, 2014(01)
- [8]SLI的条件冗余性及LP问题的算法研究[D]. 刘道建. 西南交通大学, 2013(10)
- [9]浅谈线性规划相关理论在经济管理中的应用[J]. 刘德龙. 中外企业家, 2012(04)
- [10]线性规划中一个避免人工变元的方法的改进[J]. 周学松,赵恒. 运筹与管理, 2011(05)