《《参数线性规划的算法研究》-公开DOC·毕业论文》由会员分享，可在线阅读，更多相关《《参数线性规划的算法研究》-公开DOC·毕业论文（35页珍藏版）》请在金锄头文库上搜索。
1、l 毕业论文 I 摘要 参数线性规划是约束条件和目标函数中的价值系数 工艺系数 资源限量中含有 一个或多个参数的优化模型 是线性规划理论的重要组成部分 线性规划是运筹学的 一个重要分支 从解决技术问题的最优化设计 到工业 农业 商业 交通运输 军 事 经济等 在许多领域中都有着重要的应用 在生产过程中 由于工艺条件 资源 限量 市场需求 市场价格等因素都在不断的变化 因此 最优解也就带有一定程度 的不确定性 为了及时根据市场动态及数据资料的变化调整决策方案 运用参数线性 规划这一工具 建立参数线性规划模型 可以更好地指导实际工作 适应市场的变化 达到增加收益 降低成本的目的 1947 年 Da
2、ntzig 针对线性规划提出了单纯形法 为线性规划发展奠定了基础 1954 年 C 莱姆基提出了对偶单纯形法 1954 年 S 加斯和 T 萨迪等人在对偶单纯形 法的基础上解决了线性规划的灵敏度分析和参数规划问题 近年来 参数线性规划模型在单纯形法和对偶单纯形法的基础上 又产生了搜索 法 分块矩阵法 建立神经网络模型法等方法 随着计算机软件的发展 通过建立仿 真模型用计算机解决参数线性规划问题也成为一种重要的途径 本文针对价格系数和右端资源数据中同时含有两个参数的复杂情形 对实际问题 建立了参数线性规划模型 并分析了最优解不变的情况下 参数的变化区间 找到了 最优目标函数的变化规律 并用 Ma
3、tlab 绘出了三维仿真图 为求解大型参数线性规划 问题提供了基础 关键词 参数线性规划 最优解 区间 对偶 决策变量 II Abstract Parametric linear programming is one kind of optimal modle with some constraint conditions which there exist one or more parametrics in the objective function technology factors or limited resourses It is widly applicated to man
4、y fields from technical problems to optimization design such as industrial agricalfural transportation military economic and so on In the producing process the solution of the parametric linear programming often will be some uncertainties due to the change of technology conditions resources market d
5、emands material prices and other factons So in order to adjust decision schem and meet with the market needs data must be changed timely and immdiatly Parametric linear programming has play a important role in dealing with such problems It has been a very useful tool for us to obtain decision plan a
6、nd to increase value and reduce costs In 1947 Dantzig proposed a important method simplex method laying the foundation for solving linear programming in 1954 C Lemke proposed dual simplex method in 1954 S Gaston and T Saadi and others solved the parametric programming based on studing dual simplex m
7、ethod to the problem of the linear programming In recent years many new methods the parameters of linear programming model with the basis of simplex method and the dual simplex method produced the search method sub block matrix method the establishment of neural network models and other methods With
8、 the development of computer software linear programming problem with parameters can be solved by computer through the establishment of simulation computer model In this paper a mathematical model is created in accordance with the practical problem which has two parameters one is in the price coeffi
9、cients anothisin the right resource data The interval is obtained in the condition of analysis the optimal solution unchanged to provide the fundation to solve complicated parametric linear programming By solving optimal solution we have obtained the fuction with two parametrics At last the simulati
10、ons have been given by MATLAB Keywords Parametric linear programming the optimal solution interval dual decision variation III 目录 第一章第一章 绪论绪论 1 1 1 参数线性规划的研究背景 1 1 1 1 什么是线性规划 1 1 1 2 参数线性规划的内容 1 1 2 参数线性规划的研究现状 2 1 3 参数线性规划研究的意义 3 第二章第二章 参数线性规划的理论参数线性规划的理论 4 2 1 参数线性规划研究的常用方法 4 2 1 1 目标函数的系数含有参数的线性
11、规划问题 4 2 1 2 约束条件右端的常数项含有参数的线性规划问题 5 2 2 线性规划灵敏度分析 7 2 2 1 什么是线性规划的灵敏度 7 2 2 2 价值系数的灵敏度分析 7 2 2 3 资源限量的灵敏度分析 10 第三章第三章 参数线性规划的数学建模参数线性规划的数学建模 14 3 1 实际问题的提出 14 3 2 实际问题的分析与解决 14 3 2 1 获利最大的生产计划模型 14 3 2 2 A 产品的利润变化区间的确定方法 16 3 2 3 关于开发新产品的决策研究 16 3 2 4 购入原材料进行扩大再生产的必要性的理论分析 17 3 2 5 影子价格的含义及分析 18 第四
12、章第四章 两参数线性规划问题的解法两参数线性规划问题的解法 20 4 1 两参数线性规划的定义 20 4 2 两参数线性规划问题的求解方法 20 4 3 两参数线性规划问题的分析与求解 22 第五章第五章 结论结论 27 参考文献参考文献 28 IV 谢辞谢辞 29 附录一 1 附录二 6 1 参数线性规划的算法研究参数线性规划的算法研究 第一章第一章 绪论绪论 1 1 参数线性规划的研究背景参数线性规划的研究背景 1 1 1 什么是线性规划什么是线性规划 线性规划是运筹学的一个基本的 也是成熟的分支 为了解决二次世界大战中的 后勤供应问题 早在 20 世纪 30 年代末期康托洛维奇和希奇柯克
13、等在生产的组织和运 输问题等方面就开始研究应用这一数学方法 10 多年后 Dantzig 等人提出的单纯形方 法给线性规划这一数学方法的成熟与发展奠定了坚实的理论基础 随着时间的推移 能用线性规划解决问题的类型在大量的增加 现在几乎所有的工业领域 商业领域 军事领域及科学技术的研究领域都在不同程度地运用这一方法 正是由于它的应用 全球每年各个领域节省了上亿万美元的资金 而各个生产部门也创造了大量的经济效 益 我国在建国初期就开始应用线性规划这一数学方法 线性规划方法是一种重要的数学方法 线性规划方法是企业进行总产量计划时常 用的一种定量方法 线性规划是运筹学的一个最重要的分支 理论上最完善 实
14、际应 用得最广泛 主要用于研究有限资源的最佳分配问题 即如何对有限的资源作出最佳 方式地调配和最有利地使用 以便最充分地发挥资源的效能去获取最佳的经济效益 由于有成熟的计算机应用软件的支持 采用线性规划模型安排生产计划 并不是一件 困难的事情 在总体计划中 用线性规划模型解决问题的思路是 在有限的生产资源 和市场需求条件约束下 求利润最大的总产量计划 该方法的最大优点是可以处理多 品种问题 可解决如运输问题 生产的组织与计划问题 合理下料问题 配料问题 布局问题 分派问题等 1 1 2 参数线性规划的内容参数线性规划的内容 在线性规划的实际应用中 由于某种原因 有时线性规划问题的目标函数的系数
15、 c 和约束条件的常数项 b 的数据不是固定的常数 而有所波动 例如在制订生产计划时 一个工厂生产的各种产品的价格 由于原材料的供应价格有所波动 因而也有所波动 这样 代表总利润的目标函数中的价格系数 c 便会随某个参数 即原材料的价格升降 百分数 而改变 又例如 在同样的问题中 由于供应原材料的单位的生产发生改变 原材料的限制量产生波动时 那么约束条件右端的常数项 b 也将随某个参数 即原材 2 料生产增长的百分数 而有所改变 再比如 该工厂的工艺技术条件发生变化 那么 原线性规划问题约束条件的系数矩阵的系数就随之改变 这样的一些线性规划问题 便是所谓的 参数线性规划 对于这种线性规划 我们
16、所关心的时在参数的可能范围 内 求出问题的最优解 即可以用原来数学模型按实际出现的目标函数的系数或约束 条件右端的常数项来决策最优方案 2 在实际的生产或经济活动中 应用线性规划方法解决实际问题时 仅仅求出最优 解或最佳决策是不够的 还必须掌握参数变化对最优解或最佳决策的影响 即要做灵 敏性分析 依据变化了的情况 采取相应的措施 做好相应预案 争取更好的经济利 益 否则 如果事先对这方面的情况没有充分的了解和准确的估计 难免导致决策失 误 造成经济上的损失 当线性规划中的工艺系数 价值系数 资源限量中一个量或多个量变成确 ij a j c i b 定或不确定区间里的一个参数时 这时线性规划模型就变成一个参数线性规划的模型 当对参数线性规划模型模型里的参数赋予具体的值的时候 这时又变成了线性规划模 型 线性规划模型是研究参数线性规划的依据 所有的参数线性规划模型的建立于解 决都是建立在线性规划模型的基础上 但现实中市场瞬息万变 变化是绝对的 工艺 系数 新产品的加入 市场价格 资源需求等因素都在改变 原生产计划建立的线性 规划模型也就不适用于实际生产中去了 这时候就需要建立参数线性规划模
