发布时间 : 星期一 文章线性规划模型的应用与灵敏度分析更新完毕开始阅读
中国石油大学胜利学院本科毕业设计(论文）
前 言
线性规划是运筹学的一个重要分支。1947年，当时正在美国空军担任数学顾问的Dantzig在《最优规划的科学计算》中提出“如何使规划过程机械化”问题，并着手建立数学模型。他从改造投入产出模型入手，逐步研究，形成了“单纯形法”，并于1953年提出“改进单纯形法”，以解决计算机求解过程中的舍入误差问题。之后，线性规划理论逐步趋于成熟，在实用中日益广泛和深入。
通过设计该课题，可以加深对运筹学、最优化、线性规划、非线性规划以及MATLAB的认识，提高对这些知识的综合应用水平，提高利用灵敏度分析解决各种线性规划问题的能力。本文章主要介绍了线性规划在实际生活中的应用，包括解线性方程组的各种方法，包括图解法，单纯形法，大M法，二阶段法以及对偶单纯形法，以及简要介绍了有关灵敏度分析的方法。由于线性方程组是解决各种应用问题的主要工具， 而有许多问题仅仅利用线性规划的解决方法还不足以解决问题，还用到了对偶理论，也因此引出了对偶单纯形法。
本课题当前的研究方向有：LP的内点算法，它通过非线性规划解决线性问题，其成功是对数学思想的革新；算法复杂度，评价算法好坏应从平均工作量出发；大型问题的分解算法、近似算法。线性规划的应用正在不断扩大，企业成功确实通过提高生产和有效使用资源的竞争过程来达到。
中国石油大学胜利学院本科毕业设计(论文）
线性规划模型的应用与灵敏度分析
第一章 线性规划问题
1. 线性规划及灵敏度分析简介
线性规划(Linear Programming)问题, 简称LP问题,是运筹学中最基本, 也是最重要的内容, 被广泛地应用于军事决策、企业管理、工程设计、交通运输等领域. 特别是经济领域应用更为广泛, 有资料称, 在对500家有相当效益的公司所作的评述中, 有85%的公司都曾应用了线性规划。
灵敏度分析对于决策者的重要性不言而喻，在真实世界里，周围的环境、条件是在不断变化的。
2. 线性规划模型应用的发展
线性规划及其通用解法——单纯形法是由美国G.B.Dantzig在1947年研究空军军事规划提出来的。法国数学家傅里叶和瓦莱－普森分别于1832和1911年独立地提出线性规划的想法，但未引起注意。1939年苏联数学家康托罗维奇在《生产组织与计划中的数学方法》一书中提出线性规划问题，也未引起重视[1]。
1947年美国数学家丹齐克提出线性规划的一般数学模型和求解线性规划问题的通用方法──单纯形法，为这门学科奠定了基础。1947年美国数学家诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域，扩大了它的应用范围和解题能力[2]。
1951年美国经济学家库普曼斯把线性规划应用到经济领域，为此与康托罗维奇一起获1975年诺贝尔经济学奖。50年代后对线性规划进行大量的理论研究，并涌现出一大批新的算法。例如，1954年莱姆基提出对偶单纯形法，1954年加斯和萨迪等人解决了线性规划的灵敏度分析和参数规划问题，1956年塔克提出互补松弛定理，1960年丹齐克和沃尔夫提出分解算法等。线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究[3]。
1984年美国贝尔电话实验室的印度数学家N.卡马卡提出解线性规划问题的新的多
1
中国石油大学胜利学院本科毕业设计(论文）
项式时间算法。用这种方法求解线性规划问题在变量个数为5000时只要单纯形法所用时间的1/50。现已形成线性规划多项式算法理论。50年代后线性规划的应用范围不断扩大[4]。
3. 线性规划模型研究的问题
建立线性规划模型线性规划研究的问题主要有两类:一类是当一项任务确定后，如何统筹安排，尽量做到以最少的人力、物力等资源去完成；另一类是在人力、物力等资源确定的情况下，如何安排使用这些资源，使创造的价值最多，其实质是解决稀缺资源在有竞争环境中如何进行最优分配的问题，即寻求整个问题的某个整体指标最优的问题[4]。
4. 线性规划模型的应用
4.1问题
a.目标函数最优化——单一目标，多重目标问题如何处理？
b.实现目标的多种方法，若实现目标只有一种方法不存在规划问题。 c.生产条件的约束——资源是有限的，资源无限不存在规划问题。 4.2线性规划方法的特点及局限性 特点：
a.可以使研究对象具体化、数量化。可以对所研究的技术经济问题做出明确的结论； b.线性；
c.允许出现生产要素的剩余量； d.有一套完整的运算程序； 局限性：
a. 线性规划它是以价格不变和技术不变为前提条件的，不能处理涉及到时间因素的问题。因此，线性规划只能以短期计划为基础。
b.在生产活动中，投入产出的关系不完全是线性关系，由于在一定的技术条件下，报酬递减规律起作用，所以要满足线性假定是不可能的。在线性规划解题中，常常把投入产出的非线性关系转化为线性关系来处理，以满足线性的假定性，客观上产生误差。
c.线性规划本身只是一组方程式，并不提供经济概念，它不能代替人们对现实经
2
中国石油大学胜利学院本科毕业设计(论文）
济问题的判断。
4.3线性规划模型的基本结构
(1)决策变量 ——未知数。它是通过模型计算来确定的决策因素。又分为实际变量——求解的变量和计算变量，计算变量又分松弛变量（上限）和人工变量（下限）。 (2)目标函数——经济目标的数学表达式。目标函数是求变量的线性函数的极大值和极小值这样一个极值问题。
(3)约束条件——实现经济目标的制约因素。它包括：生产资源的限制（客观约束条件）、生产数量、质量要求的限制（主观约束条件）、特定技术要求和非负限制。 4.4线性规划模型的一般形式 极大值模型
MaxZ?c1x1?c2x2?c3x3?...?cnxn
a11x1+a12x2+a13x3+????a1nxn?b1 (1-1) a21x1+a22x2+a23x3+????a2nxn?b2 (1-2) ?????? ??????
am1x1+am2x2+am3x3+????amnxn?bm (1-3)
x1,x2,x3???xn?0 其简缩形式为
MaxZ?c1x1?c2x2?c3x3?...?cnxn ?aijxj?bi
j?1n xj?0,j?1,2,3??????,n 极小值模型
MinZ?c1x1?c2x2?c3x3?...?cnxn
a11x1+a12x2+a13x3+????a1nxn?b1 (1-4)
a21x1+a22x2+a23x3+????a2nxn?b2 (1-5) ?????? ??????
3