1. 研究目的与意义
1.1研究背景
线性规划概念是在1947年的军事行动计划有关实践中产生的，与此相关问题发展至今已有近 100 年的历史了，主要用于解决资源利用、人力调配、生产安排等问题。线性规划的常用的求解方法是单纯形法和内点法。1947年，Dantzig提出单纯形法，单纯形法的基本思想是：沿着可行域边界，从一个顶点走到另一个顶点来寻找最优点。但单纯形法总是围绕着可行域的边界找点，所以随着约束和变量的增多，单纯形法的迭代次数也增多。虽然单纯形法在实际计算中时间短，但是其理论并不能保证在所有的线性规划问题中都有良好的表现。Kell文中举出反例，证明单纯形法在最坏情况下其计算复杂度是呈指数级的。
1979年，Khachian提出的椭球算法是第一个多项式时间的算法。椭球算法的提出对线性规划的发展产生了很大的影响，但椭球算法在实际计算中的表现不如单纯形法好。1984年，Kamarkar对解决线性规划问题提出了投影尺度算法，也称为Kamarkar算法或内点法。内点法使线性规划算法得到了真正的突破。内点法是从满足约束的内点出发，沿着最速下降方向逐渐靠近问题的最优解。因为内点法是从可行域内部逐渐靠近最优解，所以内点法的迭代次数并不会随着约束条件和变量数目的增加而增加。因此，对于大规模的线性规划问题，内点法的计算速度优于单纯形法。
2. 研究内容和预期目标
2.1研究内容
论文拟分为三部分：第一部分介绍文章中用到的一些基本概念和结论，介绍几种常见的内点法：势函数投影变换法、路径跟踪算法、仿射尺度算法，并通过对比各自的优缺点，选择第二部分须着重论述的方法。第二部分重点介绍其中的一类内点法，给出算法的相关理论，探究其优缺点，给出改进方案。第三部分将给出在实际计算中搜索方向、步长、初始点的选取规则，利用Python撰写算法对人工合成问题和Netlib测试集进行测试。
2.2预期目标
3. 研究的方法与步骤
3.1研究方法
通过文献综合研究法了解线性规划及内点法的发展、意义和研究现状。利用定量分析方法分别对比内点法和单纯形法的优缺点、三种内点法的优缺点。后使用实证研究法对提出的改进算法进行验证。
3.2研究步骤
4. 参考文献
[1]何立猛,龙霆,王永红.线性规划模型在企业人员配置的应用研究[J].现代商业,2022(32):67-70.
[2]丘书豪,陈鑫,刘冬怡,蒋卓玲.线性规划模型在中小零售企业的应用设计研究[J].科技创新与生产力,2022(06):48-55.
[3]刘浪.线性规划方法在金融投资问题中的应用[J].财富时代,2021(04):30-31.
5. 计划与进度安排
1. 2024年12月16日-2024年2月19日：完成毕业论文选题工作，进行网上选题，根据要求准备材料；与导师见面，第一次面授；
2.2024年2月20日-2月24日：根据教师下达的毕业论文任务书，进行论文撰写的前期准备；
3.2024年2月20日-3月3日：完成外文翻译和开题报告，指导教师修改和审定学生外文翻译及论文开题报告；
以上是毕业论文开题报告，课题毕业论文、任务书、外文翻译、程序设计、图纸设计等资料可联系客服协助查找。
