线性规划大学毕业论文.doc

《线性规划大学毕业论文.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、线性规划大学毕业论文目录摘要ABSTRACT第1章绪论1.1线性规划的基本概念1.1.1线性规划简介1.1.2线性规划由来的时间简史1.2线性规划的研究目的及意义第2章线性规划问题的数学模型2.1线性规划模型的建立2.2线性规划模型的求解方法2.2.1图解法2.2.2单纯形法第3章线性规划在实际问题中的应用3.1线性规划在企业管理中的应用3.1.1线性规划在企业管理中的应用范围3.1.2如何实现线性规划在企业管理中的应用3.2线性规划在企业生产计划中的应用3.3线性规划在运输问题中的应用结论参考

2、文献佳木斯大学教务处第18页第1章绪论1.1线性规划的基本概念1.1.1线性规划简介线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法.在经济管理、交通运输、工农业生产等经济活动中，提高经济效果是人们不可缺少的要求，而提高经济效果一般通过两种途径：一是技术方面的改进，例如改善生产工艺，使用新设备和新型原材料.二是生产组织与计划的改进，即合理安排人力物力资源.线性规划所研究的是：在一定条件下，合理安排人力物力等资源，使经济效果达到最好.

3、一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题.满足线性约束条件的解叫做可行解，由所有可行解组成的集合叫做可行域.决策变量、约束条件、目标函数是线性规划的三要素.1.1.2线性规划由来的时间简史法国数学家J.-B.-J.傅里叶和C.瓦莱－普森分别于1832和1911年独立地提出线性规划的想法，但未引起注意.1939年苏联数学家Л.В.康托罗维奇在《生产组织与计划中的数学方法》一书中提出线性规划问题，也未引起重视.1947年美国数学家G.B.Dantzing提出求

4、解线性规划的单纯型法，为这门学科奠定了基础.佳木斯大学教务处第18页1947年美国数学家J.von诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域，扩大了它的应用范围和解题能力.1951年美国经济学家T.C.库普曼斯把线性规划应用到经济领域，为此与康托罗维奇一起获1975年诺贝尔经济学奖.50年代后对线性规划进行大量的理论研究，并涌现出一大批新的算法.例如，1954年C.莱姆基提出对偶单纯形法，1954年S.加斯和T.萨迪等人解决了线性规划的灵敏度分析和参数规划问题，1956年A.塔克提出互

5、补松弛定理，1960年G.B.丹齐克和P.沃尔夫提出分解算法等.线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究.由于数字电子计算机的发展，出现了许多线性规划软件，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解几千个变量的线性规划问题.1979年苏联数学家L.G.Khachian提出解线性规划问题的椭球算法，并证明它是多项式时间算法.1984年美国贝尔电话实验室的印度数学家N.卡马卡提出解线性规划问题的新的多项式时间算法.用这种方法求解线性规

6、划问题在变量个数为5000时只要单纯形法所用时间的1/50.现已形成线性规划多项式算法理论.50年代后线性规划的应用范围不断扩大.建立线性规划模型的方法佳木斯大学教务处第18页第2章线性规划问题的数学模型2.1线性规划模型的建立线性规划是合理利用、调配资源的一种应用数学的方法.它的基本思路是在满足一定的约束条件下，使预定的目标达到最优.它的研究内容可归纳为两个方面：一是系统的任务资源数量已定，精细安排，用最少的资源去实现这个任务；二是资源数量已定，如何合理利用、调配，使任务完成的最多.前者是求极

7、小，后者是求极大.线性规划的一般定义如下：对于求取一组变量Xj（j=1,2,…,n)，使之既满足线性约束条件，又使具有线性特征的目标函数取得极值的一类最优化问题称为线性规划问题.线性规划模型建立需具备以下条件：一是最优目标.问题所要达到的目标能用线性函数来描述，且能够使用极值（最大或最小）来表示.二是约束条件.达到目标的条件是有一定限制的，这些限制可以用决策变量的线性等式或线性不等式来表示.三是选择条件，有多种方案可以供选择，以便从中找出最优方案.线性规划问题的一般数学模型如下：(1)s.t.(

8、2)称为决策变量佳木斯大学教务处第18页称为目标函数系数()称为约束右端系数称为约束系数其中式（1）为目标函数，式（2）称为约束条件.由于目标函数和约束条件内容和形式上的差别，线性规划问题有多种表达式，为了便于讨论和制定统一的算法，规定标准形式如下：（1）标准形式(2)Σ记号简写式（3）矩阵形式式中,佳木斯大学教务处第18页（4）向量形式式中C,X,b,0的含义与矩阵的表达式相同，而即A=（）将非标准形式化为标准形式的情况（3种基本情况）（1）目标函数为求极小值minZ=CX,则作Z’=-CX,