一、线性规划问题退化最优基可行解的性质（论文文献综述）
孙敏[1]（2021）在《拉格朗日乘子与单纯形乘子关系探讨》文中研究说明拉格朗日乘子法是求解含等式约束极值问题的有效方法,其核心思想是通过引入拉格朗日乘子将条件极值问题转化为无条件极值问题,而单纯形方法是求解带不等式约束的线性规划问题的经典方法,其矩阵描述中含有单纯形乘子参数,即影子价格.在线性规划的基本可行解非退化的假设下,证明了单纯形乘子就是拉格朗日乘子.通过数值实验验证了理论分析,特别地,通过实际例子说明了当最优解是退化基可行解时,拉格朗日乘子可能包含了单纯形乘子.
杨扬[2]（2020）在《电动公交车行车计划问题建模与算法研究》文中研究说明城市地面公交系统具有绿色、高效、节能等优点,对改善大城市道路交通状况具有重要作用。行车计划是公交运营规划过程的核心要素,对公交日常运营起着指导性作用,不仅决定了公交企业的资源配置效率,同时也是实时调度的基础。传统公交车的行车计划编制方法一般以线路时刻表和车次集合为基础,考虑车次衔接等约束条件,构建车次链集合。然而当采用电动公交车时,需要考虑电动公交车有限的续驶里程和充电资源等约束,加之由于技术、成本等原因导致的购置、维护成本高等因素,使得在编制行车计划时需要额外考虑车辆特点带来的约束。同时,公交行车计划编制问题是一个复杂的组合优化问题,在现有的规划模型和方法中直接添加新的约束可能导致问题求解不可行,使得电动公交车行车计划优化问题难度大,这在一定程度上也阻碍了电动公交车的大规模推广应用。因此如何精确、高效地对电动公交线路进行行车计划编制,成为摆在公交管理者和研究人员面前亟待解决的重要课题。本文通过分析电动公交车的运营过程和行车特点,对电动公交行车计划问题进行优化建模和算法设计研究,旨在帮助公交公司合理安排车辆计划,为以电动公交车为载运工具的公交运营系统提供理论支持,同时也可以为其它应用电动车的行业,在进行资源配置和运营优化管理时提供思路与方法。本论文的主要工作和创新点如下:（1）根据电动公交车不同的充电方式及对公交运营过程的影响程度,将电动公交车的运营模式划分为两类:“慢充”运营模式和“快充/换电”运营模式,并根据实际运营数据,对电动公交车运营特性进行分析;根据公交车运营特点,将电动公交行车计划转化为由场站、车次、充电站、车次运营顺序、充电机会选择等元素组成的拓扑网络表示,并将行车计划优化问题拓扑转化为网络流优化问题。（2）将基于慢速充电方式的电动公交运营转化为有里程约束的行车计划问题,并构建两类优化模型。一类是基于网络流的紧凑模型,以车队固定成本、运营成本、空驶/等待成本最小为目标函数,以车辆行驶里程限制、车次耦合条件等为约束,以车次运营先后关系为变量的混合整数规划模型;另一类是基于集合分割理论,以行车计划总成本最小为目标函数,以单个车辆计划为变量,并将其它复杂约束条件隐含的定义在车辆计划集合中,建立0-1整数规划模型。根据模型特点,分析了两类模型的求解复杂度,并基于分支定价技术,设计了求解问题集分割模型的优化算法。通过对算例和实际案例进行求解,验证所构建模型和算法的效率。（3）构建了基于快充/换电方式的电动公交运营优化模型,并设计了两种算法对模型进行求解,一种是基于变邻域搜索和禁忌搜索的混合启发示方法,用以近似求解大规模的行车计划问题;另一种是以分支定价为基础的数学规划方法,用以精确求解中小规模的行车计划问题。对示例问题的求解验证了启发示算法和精确算法的可行性、适用性与效率。（4）在推广绿色交通背景下,分析了电动公交购置成本对公交车队运营管理的影响,在考虑排放因素的条件下,将常规公交车与电动公交车混合运营,建立混合车队行车计划优化模型。以行车计划总成本最小为目标函数,综合考虑电动车的里程约束、充电选择约束、常规公交车的排放约束、车次耦合约束等,从不同的排放约束角度建立4种优化模型,分别为:考虑排放成本的混合车队公交行车计划模型、考虑车辆数量约束的混合车队公交行车计划模型、考虑CO2排放硬约束的混合车队公交行车计划模型、考虑CO2排放软约束的混合车队公交行车计划模型。同时分析了问题的求解难度和复杂度,并设计精确算法对示例问题进行求解。
代晓阳[3]（2020）在《解有限维无约束极大极小问题的光滑化-积极集两阶段算法》文中研究说明极大极小问题是一类典型的非光滑优化问题,广泛应用于交通运输,投资决策及电子线路等领域.光滑化算法是求解该问题的一类有效算法,它将极大极小问题等价转化为一系列带光滑化参数的光滑优化问题,当光滑化参数趋于无穷大时,光滑优化问题的解趋于原问题的解.但随着光滑化参数的增大,光滑优化问题越来越病态,针对这种病态问题,本文给出了一种积极集策略.对于线性极大极小问题,基于该问题的一阶最优性条件,给出了强积极指标集的定义.在积极集策略中,利用光滑化算法得到的近似解,通过求解方程组或线性规划问题得到强积极指标集,然后经过有限次迭代得到问题的最优解及对应的积极指标集.最后证明了光滑化算法及该积极集策略的两阶段算法对一般线性极大极小问题的收敛性.初步的数值实验表明了该两阶段算法的有效性.对于非线性极大极小问题,基于该问题的一阶最优性条件,给出了线性独立积极指标集的定义.在积极集策略中,利用光滑化算法得到的近似解,通过求解方程组或一系列线性规划问题得到线性独立积极指标集.基于线性独立积极指标集,得到稳定点处的等价光滑方程组,该方程组在一定条件下非病态,进而利用牛顿法对其求解.最后证明了光滑化算法及该积极集策略的两阶段算法在一定条件下的收敛性.初步的数值实验表明了对于满足一定条件的问题,该算法可得到任意精度的解,且光滑化算法的近似解可由较小的光滑化参数对应的光滑优化问题得到,因此这种两阶段算法有效地避免了光滑化算法的病态问题.
朱外明[4]（2019）在《面向多星协同观测的区域覆盖优化方法》文中研究说明在成像卫星的工程应用中,常常遇到这样的场景,在指定的时间内,需要使用多颗成像卫星协同对单个较大的区域目标进行成像观测。制定该场景下卫星合理的覆盖计划即为本文研究的面向多星协同观测的区域覆盖优化问题。给定一个待观测的大区域,和若干成像卫星,每颗卫星每次只能覆盖一个矩形条带区域（小于待观测区域）。由于卫星所携带的相机可以侧摆,不同侧摆角度下覆盖的条带区域的位置不同;卫星相机具有固定的视场角,不同侧摆角度下覆盖的条带区域的宽度不同;卫星相机的开关机时间不同,覆盖的条带区域的位置和长度也不相同。因此,不同的卫星观测动作,会覆盖不同位置、不同长度、不同宽度的条带区域。覆盖优化要求:合理地安排每个卫星每次过境机会内的观测动作,使得总体的覆盖方案对应某一个给定的目标尽可能的优。该问题是一个与计算几何高度耦合的连续空间组合优化问题,其求解具有一定的挑战性。本文对该问题进行了深入研究,提出了一系列技术方法,所取得的主要创新点如下:（1）提出了三种面向多星协同观测的区域覆盖优化问题,即覆盖资源有限情形下最大覆盖面积、覆盖资源充足情形下最小完工时间、覆盖资源充足情形下最小化覆盖成本问题,分析了各个问题的特征,并基于网格离散化技术建立了相应的整数线性规划模型。（2）针对最大覆盖面积问题,设计了多项式时间复杂度的启发式算法,并使用拉格朗日松弛技术计算对应的上界,仿真实验结果表明,在小规模情况下,该启发式算法能够求得近似最优解（最优性GAP<1%）;针对最小完工时间问题,提出了多项式时间的两阶段启发式算法,仿真实验表明,该两阶段启发式算法能够以较少的计算花费求得高质量的解;针对最小覆盖成本问题,设计了基于隐枚举算法求解子问题的branch and price算法（IE-BP）,提出并证明了可以削剪价格子问题解空间的支配原则,使得大量的列可以预先排除,大大加速了求解的速度,仿真实验表明,所提出的支配原则可以削减约68%的列,部分算例能够求得近似最优解,且计算效率优于美国着名商业优化软件Gurobi。（3）提出基于嵌套网格的逼近策略。先使用启发式、两阶段启发式、IE-BP算法在单元格尺寸较大的网格上进行求解,在求得解方案以后,进一步地,在现有网格内构造一个单元格尺寸更小的嵌套网格,并且在已有的解方案（即覆盖方案）“周围”再次进行搜索寻优,进行精度更细的求解。由于二次搜索是在一次求解的基础上进行,仅需消耗少量的计算量。重复使用这样的逼近策略可以不断提高离散化的精细程度,求得高质量的解方案。仿真实验表明,该方法稳定高效。（4）针对大规模问题,基于“分而治之”的总体思路,提出一种基于分区的求解策略:即将大区域分割成较小的分区,将覆盖资源分配给各个分区,并在各个分区内求解覆盖方案,各分区覆盖方案合并起来形成总体覆盖方案。不同的资源分配方案对应不同的分区覆盖方案,从而导致不同的总体覆盖方案。为获取高质量的总体覆盖方案,采用模拟退火亚启发式算法,对覆盖机会分配方案进行搜索,实现覆盖机会的动态分配。仿真实验表明,直接求解需要消耗极大的计算资源,甚至无法直接求解,而基于分区的求解策略能够在可接受的时间内求得高质量的解。
陈瑞[5]（2018）在《基于离散选择模型的品类与定价优化问题研究》文中进行了进一步梳理品类与定价优化问题是零售商在需求多元化的当下所面临最为复杂且重要的运营问题之一。在该问题中,零售商需要在满足运营约束的前提下,通过从给定产品集合中选择一个子集,并决定产品销售价格的方式来最大化期望收益。该问题的核心在于如何准确地刻画顾客的选择行为,并设计有效的优化算法。我们主要通过引入多种离散选择模型来捕捉相似产品之间的替代效应,并研究考虑位置效应的情形,即产品的选择概率受产品展示位置影响的情形。首先,我们研究顾客选择行为服从MNLD模型的情形,并首次将该模型引入空间约束下联合品类与定价优化问题中。对于这个NP-难问题,我们提出基于动态规划和通用近似方案的?-近似算法。此外,当所有产品空间权重相同时,我们的算法能得到对应联合优化问题的最优解。其次,我们研究顾客选择行为服从NL模型的情形,并首次研究空间约束下基于NL模型的联合品类与定价优化问题。对于这个NP-完全问题,我们首先利用二分查找和动态规划将其拆分为一系列非线性最大化子问题。之后,通过运用多重选择背包问题近似算法和构建可行解集合的方式,我们获得非线性子问题的近似解,并基于此提出联合优化问题的?-近似算法。再次,我们研究顾客选择行为服从MLNL模型的情形。MLNL模型是NL模型的自然延伸且能更好地刻画产品之间多维度的替代效应。在价格敏感系数由产品的主属性决定时,我们证明基于MLNL模型的定价优化问题可以转换为等价的单变量且单峰的最大化问题。紧接着,我们研究空间约束下基于MLNL模型的联合品类与定价优化问题并将其转换为等价的不动点问问题。随后,我们提出基于动态规划和背包问题近似算法的?-近似算法。最后,我们将之前的研究结果分别推广到相应的寡头博弈和具有灵活价格敏感系数的情形。最后,我们首次研究考虑位置效应且基于NL模型的品类优化问题。对以概率最大化为优化目标的情形,我们首先证明该优化问题为NP-完全问题。随后,我们提出基于动态规划的精确算法以及基于边际贡献最大化原则的启发式算法并比较其数值性能。对以期望收益最大化为优化目标的情形,我们提出基于线性规划和动态规划的整合算法来求得该优化问题的最优解。数值实验表明,与先进行品类优化再考虑位置效应的顺序方法相比,我们的整合算法能提升平均10.27%的期望收益。最后,我们将研究结果推广到展示位置分配已知的特殊情形和考虑位置效应下基于NL模型的联合品类与定价优化问题,并分别设计相应的求解算法。
王洋,张萍[6]（2018）在《单纯形算法的两种部分定价策略》文中认为根据Hu和Johnson的原始一对偶单纯形算法原理,提出了两种部分定价策略.给定一组原始一对偶可行解,首先,选择与原始问题简约价值系数为负且对偶松弛变量取零值相应的非基变量作为部分定价变量,再用Dantzig准则的单纯形算法求解该原始子问题.其次,针对原始退化问题,选择相应于原始问题简约价值系数小于某个适当小正数的非基变量进行部分定价,然后应用Bland准则的单纯形算法求解原始子问题,以克服退化可能引起的循环现象.最后,对来自NETLIB和MIPLIB的一些典型算例执行初步数值试验,结果表明,与经典单纯形算法相比,提出的算法具有更好的计算表现.
敖特根[7]（2014）在《线性规划的起因和发展》文中研究表明线性规划是运筹学的一个分支,线性规划的产生和发展引领了非线性规划和动态规划的发展。线性规划主要有两个方面的研究内容,一是规划。二是计算方法。这个规划的目标函数和约束函数都是线性函数,线性规划这个名称也是由此而演变形成的。线性规划研究者的主要目的在于如何制定计划,而不在于执行或实施计划。可以把这些有关学问所形成的整个领域称做“规划”,在于着重强调极大化或极小化问题时候,还可以称做最优规划。简单的说,线性规划所考虑的问题是如何按照最佳可能的（最优）方式来计划一项各种相互关联的活动的集合体。这个方法是求解线性规划问题的特殊方法,叫做单纯形法。线性规划不仅是运筹学中最早形成的分支,而且也应用非常广泛的一个分支。因此,对线性规划史的研究,具有十分重要的历史意义和现实价值。本文在查阅参考大量原始文献和有关研究文献的基础上,以曲安京教授的“为什么数学”思想为切入点,在分析研究归纳综合的基础上,对线性规划问题的历史进程进行了较为详细的研究。本文主要研究成果有：（1）讨论和分析冯·诺伊曼（J. V. Neumann）关于博弈论研究对线性规划的影响。（2）讨论和分析李昂替夫（W. W. Leontief）关于投入-产出的研究对线性规划发展的影响。（3）讨论和分析希奇柯克（F. L. Hitchcock）关于运输问题的研究和斯蒂格勒（G.J.Stigler）关于营养问题的研究对线性规划发展的影响。（4）讨论和分析了丹齐格（G. B. Dantzig）对线性规划的贡献及单纯形法的创建。（5）分析和讨论单纯形法的发展进程和我国线性规划学习发展历程。
贾堰林[8]（2014）在《带模糊数线性规划问题的算法研究》文中研究表明本文针对在应用较广和较新的课题——模糊优化研究中,提出的多样化的模糊优化模型和其相应的解法中存在的退化、参数影响和算法效率等问题,借助于现有模糊线性规划理论和算法,模糊数、模糊向量和秩函数的概念和运算,较深入地研究了模糊系数线性规划和模糊变量线性规划的退化问题,分别提出了它们对应的改进单纯形法,避免了循环情况；研究了含参数的模糊系数线性规划和含参数的模糊变量线性规划问题,获得了参数在目标函数系数和约束条件右边项连续变化时,问题最优基的变化规律,提出了相应的算法,拓展和丰富了模糊线性规划问题灵敏度分析的研究；研究了求解具有较多约束条件的模糊系数线性规划问题的有效算法,提出了一种适合模糊系数线性规划问题改进的内点法,一定程度上填补了国内外该领域研究的空白!这些新方法的数值算例表明,提出的新算法正确可行。本文主要开展了以下几方面的深入研究：1.研究了模糊系数线性规划的退化问题。针对现有单纯形法求解退化的模糊系数线性规划问题时会陷入循环情况,构建了相应的新模型,研究了它们解的关系,提出了一种改进的单纯形法,避免了循环情况。2.研究了模糊变量线性规划的退化问题。针对现有单纯形法求解退化的模糊变量线性规划问题时会陷入循环情况,构建了相应的新模型,研究了它们解的关系,提出了一种改进的单纯形法,避免了循环情况。3.研究了含参数的模糊系数线性规划问题,它是现有的模糊系数线性规划问题灵敏度分析研究的一种扩展。首先分别定义了两类含参数的模糊系数线性规划；然后研究了参数λ,在目标函数系数以及约束条件的右边项,连续变化时最优基的变化规律,即研究了参数与最优基的关系；最后归纳了求解方法和步骤。4.研究了含参数的模糊变量线性规划问题,它是现有的模糊变量线性规划问题灵敏度分析研究的一种扩展。首先分别定义了两类含参数的模糊变量线性规划；然后研究了参数λ,在目标函数系数以及约束条件的右边项,连续变化时最优基的变化规律,即研究了参数与最优基的关系；最后归纳了求解方法和步骤。5.研究了模糊系数线性规划问题的内点法。从计算复杂度的角度分析,内点法优于单纯形法,然而传统的内点法不能直接用于求解模糊系数线性规划问题,故提出了一种适合模糊系数线性规划问题的改进的内点法。以上研究成果,在一定程度上丰富了现有结合秩函数解决模糊线性规划问题的理论知识。
刘道建[9]（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定解问题找到了一条有效的新途径。
鲁法明,曾庆田,包云霞[10]（2012）在《判定工作流网S-可覆盖性的有效算法》文中研究表明为有效判定工作流网的S-可覆盖性,将工作流网的S-可覆盖性判定转化为线性规划问题,借助单纯形方法给出一个判定工作流网S-可覆盖性的有效算法。对单纯形算法进行扩展,在判定工作流网S-可覆盖性的同时可以求出一组S-不变量的极小支集。只要给定的工作流网满足S-可覆盖性,上述算法就可以求出一组覆盖所有库所的S-不变量的极小支集。结合投诉处理业务流程实例对算法进行了验证。
二、线性规划问题退化最优基可行解的性质（论文开题报告）
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
本文主要提出一款精简64位RISC处理器存储管理单元结构并详细分析其设计过程。在该MMU结构中,TLB采用叁个分离的TLB,TLB采用基于内容查找的相联存储器并行查找,支持粗粒度为64KB和细粒度为4KB两种页面大小,采用多级分层页表结构映射地址空间,并详细论述了四级页表转换过程,TLB结构组织等。该MMU结构将作为该处理器存储系统实现的一个重要组成部分。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
三、线性规划问题退化最优基可行解的性质（论文提纲范文）
（1）拉格朗日乘子与单纯形乘子关系探讨（论文提纲范文）
| 0 引言 |
| 1 拉格朗日乘子与单纯形乘子 |
| 2 拉格朗日乘子与单纯形乘子关系 |
| 3 数值实验 |
（2）电动公交车行车计划问题建模与算法研究（论文提纲范文）
| 致谢 |
| 摘要 |
| ABSTRACT |
| 1 绪论 |
| 1.1 研究背景 |
| 1.2 研究意义 |
| 1.3 国内外研究综述 |
| 1.3.1 公交行车计划问题 |
| 1.3.2 电动汽车路径规划及调度 |
| 1.3.3 考虑碳排放的车辆路径优化问题 |
| 1.3.4 新模式公交的调度问题 |
| 1.3.5 现有研究总结 |
| 1.4 论文组织结构及研究内容 |
| 1.4.1 论文组织结构 |
| 1.4.2 研究内容 |
| 2 电动公交运营特性分析 |
| 2.1 电动公交运营方式 |
| 2.1.1 电动车充电方式 |
| 2.1.2 电动公交能源消耗 |
| 2.1.3 电动公交运营方式分类 |
| 2.2 电动公交车运营特性统计分析 |
| 2.2.1 数据来源、采集与数据格式 |
| 2.2.2 运营特性统计分析 |
| 2.3 电动公交运营拓扑网络表示 |
| 2.3.1 表示方法 |
| 2.3.2 一些假设 |
| 2.4 本章小结 |
| 3 基于慢充的电动公交行车计划问题建模 |
| 3.1 基于里程约束的行车计划问题及模型 |
| 3.1.1 网络流模型 |
| 3.1.2 集分割模型 |
| 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.5 本章小结 |
| 4 基于快充/换电的电动公交行车计划问题建模 |
| 4.1 问题描述与模型 |
| 4.1.1 问题建模 |
| 4.1.2 SP模型 |
| 4.2 基于VNS/TS的混合启发示算法设计 |
| 4.2.1 元启发示算法与Local Search(LS) |
| 4.2.2 基于VNS/TS的混合启发示算法设计 |
| 4.3 精确算法设计 |
| 4.3.1 子问题求解 |
| 4.3.2 求解整数解 |
| 4.3.3 加速方法 |
| 4.3.4 算法流程及框架 |
| 4.4 算例分析 |
| 4.4.1 数据说明 |
| 4.4.2 终止条件 |
| 4.4.3 费用参数 |
| 4.4.4 运算结果 |
| 4.5 本章小结 |
| 5 电动与常规公交车混合车队行车计划问题建模 |
| 5.1 背景 |
| 5.2 碳排放与行车计划 |
| 5.2.1 碳排放相关概念 |
| 5.2.2 车辆运营与碳排放 |
| 5.2.3 碳排放限额与交易 |
| 5.3 混合车队行车计划 |
| 5.4 基于排放约束的混合车队行车计划问题 |
| 5.4.1 问题定义与描述 |
| 5.4.2 问题模型 |
| 5.5 求解算法 |
| 5.6 算例分析 |
| 5.6.1 参数设定 |
| 5.6.2 求解结果 |
| 5.7 本章小结 |
| 6 总结及展望 |
| 6.1 研究工作总结 |
| 6.2 本文创新点 |
| 6.3 研究展望 |
| 参考文献 |
| 附录A 车次集合 |
| 附录B 基于慢速充电的电动公交行车计划问题解集 |
| 附录C 基于快充/换电的电动公交行车计划问题解集 |
| 作者简历及攻读博士学位期间取得的研究成果 |
| 学位论文数据集 |
（3）解有限维无约束极大极小问题的光滑化-积极集两阶段算法（论文提纲范文）
| 中文摘要 |
| ABSTRACT |
| 1 绪论 |
| 1.1 有限维无约束极大极小问题的研究背景 |
| 1.2 凝聚函数 |
| 1.3 本文的组织结构 |
| 1.4 预备知识与符号说明 |
| 2 解线性极大极小问题的光滑化-积极集两阶段算法 |
| 2.1 解线性极大极小问题的积极集策略 |
| 2.2 线性光滑化-积极集两阶段算法及收敛性 |
| 2.3 数值实验 |
| 3 解非线性极大极小问题的光滑化-积极集两阶段算法 |
| 3.1 解非线性极大极小问题的积极集策略 |
| 3.2 非线性光滑化-积极集两阶段算法及收敛性 |
| 3.3 数值实验 |
| 4 总结 |
| 参考文献 |
| 附录 |
| 致谢 |
（4）面向多星协同观测的区域覆盖优化方法（论文提纲范文）
| 致谢 |
| 摘要 |
| abstract |
| 第一章 绪论 |
| 1.1 研究背景与研究意义 |
| 1.1.1 研究背景 |
| 1.1.2 研究意义 |
| 1.2 研究内容与技术框架 |
| 1.2.1 研究内容 |
| 1.2.3 技术框架 |
| 1.3 国内外研究现状 |
| 1.3.1 卫星任务规划问题 |
| 1.3.2 多边形几何覆盖问题 |
| 1.3.3 设施选址覆盖问题 |
| 1.3.4 二维装箱问题 |
| 1.3.5 研究现状综合分析 |
| 1.4 文章结构 |
| 第二章 相关的基础理论与方法 |
| 2.1 拉格朗日松弛技术 |
| 2.1.1 拉格朗日松弛问题 |
| 2.1.2 拉格朗日对偶问题 |
| 2.2 割平面算法 |
| 2.2.1 GF不等式 |
| 2.2.2 MIR不等式 |
| 2.2.3 GMI不等式 |
| 2.3 Branch and price算法 |
| 2.3.1 分支定界算法 |
| 2.3.2 列生成算法 |
| 2.4 本章小结 |
| 第三章 面向多星协同观测的最大覆盖面积问题 |
| 3.1 引言 |
| 3.2 问题描述与建模 |
| 3.3 最长基本覆盖模式生成算法 |
| 3.4 启发式求解算法 |
| 3.5 拉格朗日松弛上界 |
| 3.6 基于嵌套网格的逼近策略 |
| 3.7 基于分区的求解策略 |
| 3.8 仿真实验 |
| 3.8.1 启发式算法求解效率验证 |
| 3.8.2 逼近策略求解效率验证 |
| 3.8.3 分区策略求解效率验证 |
| 3.9 本章小结 |
| 第四章 面向多星协同观测的最小完工时间问题 |
| 4.1 引言 |
| 4.2 问题描述与建模 |
| 4.3 两阶段启发式求解算法 |
| 4.4 基于嵌套网格的逼近策略 |
| 4.5 基于分区的求解策略 |
| 4.6 仿真实验 |
| 4.6.1 两阶段启发式算法求解效率验证 |
| 4.6.2 逼近策略求解效率验证 |
| 4.6.3 分区策略求解效率验证 |
| 4.7 本章小结 |
| 第五章 面向多星协同观测的最小覆盖成本问题 |
| 5.1 引言 |
| 5.2 问题描述与建模 |
| 5.3 Branch and price求解算法 |
| 5.3.1 列生成求解线性松弛问题 |
| 5.3.2 分支定界策略 |
| 5.4 逼近策略与分区策略 |
| 5.5 仿真实验 |
| 5.5.1 IE-BP算法求解效率验证 |
| 5.5.2 逼近策略求解效率验证 |
| 5.5.3 分区策略求解效率验证 |
| 5.6 本章小结 |
| 第六章 总结与展望 |
| 参考文献 |
| 攻读博士学位期间的学术活动及成果情况 |
（5）基于离散选择模型的品类与定价优化问题研究（论文提纲范文）
| 摘要 |
| abstract |
| 主要符号对照表 |
| 第1章 引言 |
| 1.1 研究背景 |
| 1.2 研究内容 |
| 1.3 论文贡献 |
| 1.4 论文结构 |
| 第2章 文献综述 |
| 2.1 引言 |
| 2.2 基于MNL模型的相关文献 |
| 2.3 基于MMNL模型的相关文献 |
| 2.4 基于NL模型的相关文献 |
| 2.5 基于MLNL模型的相关文献 |
| 2.6 基于其他选择模型的相关文献 |
| 2.7 考虑位置效应的相关文献 |
| 2.8 小结 |
| 第3章 基于MNLD模型的联合品类与定价优化问题 |
| 3.1 引言 |
| 3.2 问题描述与建模 |
| 3.3 问题性质与拆分 |
| 3.3.1 基于动态规划的空间分配 |
| 3.3.2 子问题的数学性质 |
| 3.4 近似子问题 |
| 3.4.1 1/2-近似算法 |
| 3.4.2 多重选择背包问题近似算法 |
| 3.5 小结 |
| 第4章 基于NL模型的联合品类与定价优化问题 |
| 4.1 引言 |
| 4.2 问题描述与建模 |
| 4.3 问题性质与拆分 |
| 4.3.1 问题性质 |
| 4.3.2 问题拆分 |
| 4.4 近似子问题 |
| 4.4.1 问题重构 |
| 4.4.2 构建可行解集合 |
| 4.4.3 说明性算例 |
| 4.5 算法复杂度分析 |
| 4.6 巢内个数约束的特殊情形 |
| 4.6.1 求解最优解 |
| 4.6.2 说明性算例 |
| 4.7 小结 |
| 第5章 基于MLNL模型的联合品类与定价优化问题 |
| 5.1 引言 |
| 5.2 问题描述与建模 |
| 5.3 定价优化问题研究 |
| 5.3.1 期望收益函数的凹性 |
| 5.3.2 期望收益函数的单峰性 |
| 5.3.3 说明性算例 |
| 5.4 联合品类与定价优化问题研究 |
| 5.4.1 问题重构与拆分 |
| 5.4.2 子问题求解 |
| 5.5 推广与应用 |
| 5.5.1 寡头博弈 |
| 5.5.2 灵活价格敏感系数 |
| 5.6 小结 |
| 第6章 考虑位置效应的品类与定价优化问题 |
| 6.1 引言 |
| 6.2 问题描述与建模 |
| 6.3 选择概率最大化 |
| 6.3.1 动态规划算法 |
| 6.3.2 启发式算法 |
| 6.3.3 说明性算例 |
| 6.3.4 数值实验 |
| 6.4 考虑位置效应的品类优化问题 |
| 6.4.1 子问题求解 |
| 6.4.2 最优期望收益 |
| 6.4.3 数值实验 |
| 6.5 推广与应用 |
| 6.5.1 位置分配已知的特殊情形 |
| 6.5.2 联合品类与定价优化问题 |
| 6.6 小结 |
| 第7章 总结与展望 |
| 7.1 论文总结 |
| 7.2 未来研究方向展望 |
| 参考文献 |
| 致谢 |
| 个人简历、在学期间发表的学术论文与研究成果 |
（6）单纯形算法的两种部分定价策略（论文提纲范文）
| 1 引言 |
| 2 单纯形算法的部分定价策略 |
| 3 退化问题的部分定价策略 |
| 4 结束语 |
（7）线性规划的起因和发展（论文提纲范文）
| 摘要 |
| 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 线性规划的影响 |
| 参考文献 |
| 攻读博士学位期间发表的论文 |
| 攻读博士学位期间参加的学术活动 |
| 致谢 |
（8）带模糊数线性规划问题的算法研究（论文提纲范文）
| 摘要 |
| Abstract |
| 第1章 绪论 |
| 1.1 研究目的及意义 |
| 1.2 国内外研究现状 |
| 1.2.1 国内研究现状 |
| 1.2.2 国外研究现状 |
| 1.3 研究内容和研究方法 |
| 1.3.1 研究内容 |
| 1.3.2 研究方法 |
| 1.4 研究成果和特色及创新点 |
| 1.4.1 主要研究成果 |
| 1.4.2 特色和创新点 |
| 第2章 预备知识 |
| 2.1 模糊规划理论 |
| 2.1.1 模糊规划简介 |
| 2.1.2 模糊规划算法简介 |
| 2.2 模糊理论 |
| 2.2.1 模糊集与隶属函数 |
| 2.2.2 模糊数及其运算 |
| 2.2.3 模糊向量及运算 |
| 2.3 秩函数理论 |
| 2.3.1 秩函数定义 |
| 2.3.2 秩函数运算规则 |
| 第3章 模糊规划退化问题研究 |
| 3.1 模糊系数线性规划退化问题的研究 |
| 3.1.1 模型和理论 |
| 3.1.2 算法研究 |
| 3.1.3 数值算例及分析 |
| 3.2 模糊变量线性规划退化问题的研究 |
| 3.2.1 模型和理论 |
| 3.2.2 算法研究 |
| 3.2.3 数值算例及分析 |
| 第4章 含参数模糊规划问题研究 |
| 4.1 模糊系数线性规划问题的参数研究 |
| 4.1.1 目标函数系数变化 |
| 4.1.2 约束条件的右边项变化 |
| 4.2 模糊变量线性规划问题的参数研究 |
| 4.2.1 目标函数系数变化 |
| 4.2.2 约束条件的右边项变化 |
| 第5章 模糊系数线性规划问题的内点法研究 |
| 5.1 理论依据 |
| 5.1.1 改进的内点法思想 |
| 5.1.2 计算公式的推导 |
| 5.2 算法步骤 |
| 5.3 实例应用及分析 |
| 5.3.1 实例应用 |
| 5.3.2 算法分析 |
| 第6章 结论与认识 |
| 6.1 结论 |
| 6.2 认识 |
| 致谢 |
| 参考文献 |
| 攻读硕士学位期间发表的论文及科研等成果 |
（9）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. 科研项目 |
四、线性规划问题退化最优基可行解的性质（论文参考文献）
- [1]拉格朗日乘子与单纯形乘子关系探讨[J]. 孙敏. 枣庄学院学报, 2021(05)
- [2]电动公交车行车计划问题建模与算法研究[D]. 杨扬. 北京交通大学, 2020
- [3]解有限维无约束极大极小问题的光滑化-积极集两阶段算法[D]. 代晓阳. 山西师范大学, 2020(07)
- [4]面向多星协同观测的区域覆盖优化方法[D]. 朱外明. 合肥工业大学, 2019(01)
- [5]基于离散选择模型的品类与定价优化问题研究[D]. 陈瑞. 清华大学, 2018(06)
- [6]单纯形算法的两种部分定价策略[J]. 王洋,张萍. 数学的实践与认识, 2018(10)
- [7]线性规划的起因和发展[D]. 敖特根. 西北大学, 2014(01)
- [8]带模糊数线性规划问题的算法研究[D]. 贾堰林. 西南石油大学, 2014(02)
- [9]SLI的条件冗余性及LP问题的算法研究[D]. 刘道建. 西南交通大学, 2013(10)
- [10]判定工作流网S-可覆盖性的有效算法[J]. 鲁法明,曾庆田,包云霞. 计算机集成制造系统, 2012(08)