线性规划大学毕业论文

1、 毕业论文（设计）毕业论文（设计）课题名称课题名称 线性规划模型的求解及应用线性规划模型的求解及应用 学学 院院 理理 学学 院院 专专 业业 数学与应用数学数学与应用数学 （S S） 班班 级级 20102010 级级 数学数学 2 2 班班 指导教师指导教师 学生姓名学生姓名 佳佳 木木 斯斯 大大 学学 教教 务务 处处毕业论文 （设计）用纸佳木斯大学教务处佳木斯大学教务处 线性规划模型的求解及应用线性规划模型的求解及应用吴烈东吴烈东佳木斯大学理学院数学系佳木斯大学理学院数学系20142014 年年 6 6 月月毕业论文 （设计）用纸佳木斯大学教务处佳木斯大学教务处 第第 1 页页摘摘

2、要要线性规划是运筹学的一个重要分支，它辅助人们进行科学管理，是国际应用数学、经济、计算机科学界所关注的重要研究领域.线性规划主要研究有限资源最佳分配问题，即如何对有限的资源进行最佳地调配和最有利地使用，以便最充分发挥资源的效能来获取最佳的经济效益.线性规划运用数学语言描述某些经济活动的过程，形成数学模型，以一定的算法对模型进行计算，为制定最优计划方案提供依据.其解决问题的关键是建立符合实际情况的数学模型，即线性规划模型.在各种经济活动中，常采用线性规划模型进行科学、定量分析，安排生产组织与计划，实现人力物力资源的最优配置，获得最佳的经济效益.目前，线性规划模型被广泛应用与经济管理、交通运输、工

3、农业生产等领域.本文主要介绍线性规划的两种基本解法即图解法和单纯形法，并讨论了这两种方法的优缺点和在一些实际问题中的应用.关键词关键词: : 线性规划；图解法；单纯形法；数学模型；应用毕业论文 （设计）用纸佳木斯大学教务处佳木斯大学教务处 第第 2 页页AbstractLinear programming is an important branch of operations research, which assist people to scientific management is an important area of research internationally appli

4、ed mathematics, economics, computer science communitys concerns. The main study of linear programming optimal allocation of limited resources, namely how to limited resources optimally deploy and most advantageously used in order to most fully effective resources to get the best value for money.Line

5、ar programming using mathematical language to describe the process of certain economic activities, the formation of mathematical models to a certain algorithm to calculate the model to provide a basis for the formulation of the optimal plan for. The key to solve the problem is to create a mathematic

6、al model in line with the actual situation, namely linear programming model. In various economic activities, often using linear programming model for scientific, quantitative analysis, organization and planning for production to achieve the optimal allocation of human and material resources, to get

7、the best value for money. At present, the linear programming model is widely used in economic management, transportation, industrial and agricultural production and other fields.This paper describes two basic solution that graphical method for linear programming and the simplex method, and discuss t

8、he advantages and disadvantages of both methods and applications in a number of practical problems.Key words: Linear Programming；Graphic method; simplex method; mathematical model; Application毕业论文 （设计）用纸佳木斯大学教务处佳木斯大学教务处 第第 3 页页目目 录录摘摘 要要.AbstractAbstract.第第 1 1 章章 绪论绪论.1.1 线性规划的基本概念.1.1.1 线性规划简介.1.1

9、.2 线性规划由来的时间简史.1.2 线性规划的研究目的及意义.第第 2 2 章章 线性规划问题的数学模型线性规划问题的数学模型.2.1 线性规划模型的建立.2.2 线性规划模型的求解方法.2.2.1 图解法.2.2.2 单纯形法.第第 3 3 章章 线性规划在实际问题中的应用线性规划在实际问题中的应用.3.1 线性规划在企业管理中的应用.3.1.1 线性规划在企业管理中的应用范围.3.1.2 如何实现线性规划在企业管理中的应用.3.2 线性规划在企业生产计划中的应用.3.3 线性规划在运输问题中的应用.结论结论.参考文献参考文献.毕业论文 （设计）用纸佳木斯大学教务处佳木斯大学教务处 第第

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

11、最小值的问题，统称为线性规划问题.满足线性约束条件的解叫做可行解，由所有可行解组成的集合叫做可行域.决策变量、约束条件、目标函数是线性规划的三要素.1.1.21.1.2 线性规划由来的时间简史线性规划由来的时间简史 法国数学家 J.- B.- J.傅里叶和 C.瓦莱普森分别于 1832 和 1911 年独立地提出线性规划的想法，但未引起注意.1939 年苏联数学家 .康托罗维奇在生产组织与计划中的数学方法一书中提出线性规划问题，也未引起重视.1947 年美国数学家 G.B.Dantzing 提出求解线性规划的单纯型法，为这门学科奠定了基础.毕业论文 （设计）用纸佳木斯大学教务处佳木斯大学教务处

12、 第第 5 页页1947 年美国数学家 J.von 诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域，扩大了它的应用范围和解题能力.1951 年美国经济学家 T.C.库普曼斯把线性规划应用到经济领域，为此与康托罗维奇一起获 1975 年诺贝尔经济学奖.50 年代后对线性规划进行大量的理论研究，并涌现出一大批新的算法.例如，1954年 C.莱姆基提出对偶单纯形法，1954 年 S.加斯和 T.萨迪等人解决了线性规划的灵敏度分析和参数规划问题，1956 年 A.塔克提出互补松弛定理，1960 年 G.B.丹齐克和 P.沃尔夫提出分解算法等.线性规划的研究成果还直接推动了其他数学规划问题包括整数

13、规划、随机规划和非线性规划的算法研究.由于数字电子计算机的发展，出现了许多线性规划软件，如MPSX，OPHEIE，UMPIRE 等，可以很方便地求解几千个变量的线性规划问题.1979 年苏联数学家 L. G. Khachian 提出解线性规划问题的椭球算法，并证明它是多项式时间算法.1984 年美国贝尔电话实验室的印度数学家 N.卡马卡提出解线性规划问题的新的多项式时间算法.用这种方法求解线性规划问题在变量个数为 5000 时只要单纯形法所用时间的 1/50.现已形成线性规划多项式算法理论.50 年代后线性规划的应用范围不断扩大. 建立线性规划模型的方法毕业论文 （设计）用纸佳木斯大学教务处佳

14、木斯大学教务处 第第 6 页页第第 2 2 章章 线性规划问题的数学模型线性规划问题的数学模型2.12.1 线性规划模型的建立线性规划模型的建立线性规划是合理利用、调配资源的一种应用数学的方法.它的基本思路是在满足一定的约束条件下，使预定的目标达到最优.它的研究内容可归纳为两个方面：一是系统的任务资源数量已定，精细安排，用最少的资源去实现这个任务；二是资源数量已定，如何合理利用、调配，使任务完成的最多.前者是求极小，后者是求极大.线性规划的一般定义如下： 对于求取一组变量 Xj（j=1,2,n)，使之既满足线性约束条件，又使具有线性特征的目标函数取得极值的一类最优化问题称为线性规划问题.线性规

15、划模型建立需具备以下条件：一是最优目标.问题所要达到的目标能用线性函数来描述，且能够使用极值 （最大或最小） 来表示.二是约束条件.达到目标的条件是有一定限制的，这些限制可以用决策变量的线性等式或线性不等式来表示.三是选择条件，有多种方案可以供选择，以便从中找出最优方案.线性规划问题的一般数学模型如下： (1)max (或) = 11+ 22 + a11x1+ a12x2+ + a1nxn ( = , ) 1 a21x1+ a22x2+ + a2nxn ( = , ) 2 s.t. (2) am1x1+ a2x2+ + anxn ( = , ) 1x2 0( 0) 称为决策变量 j(j = 1

16、,2,) 称为目标函数系数 j(j = 1,2,)毕业论文 （设计）用纸佳木斯大学教务处佳木斯大学教务处 第第 7 页页 () 称为约束右端系数 j = 1,2, 称为约束系数j( = 1,2, = 1,2,)其中式（1）为目标函数，式（2）称为约束条件 . 由于目标函数和约束条件内容和形式上的差别，线性规划问题有多种表达式，为了便于讨论和制定统一的算法，规定标准形式如下：（1）标准形式 ), 1(0max221122222121112121112211njxbxaxaxabxaxaxabxaxaxaxcxcxczjmnmnmmnnnnnn(2) 记号简写式 ),.,2 , 1(0),.,2

17、, 1(max11njxmibxaxczjnjijijnjjj（3）矩阵形式 0maxXbAXCXz式中, =（1,） =（1,） 0.000 ,.,.321212222111211bbbbaaaaaaaaaAmnmmnn（4）向量形式毕业论文 （设计）用纸佳木斯大学教务处佳木斯大学教务处 第第 8 页页 0max1XbxpCXznjjj式中 C,X,b,0 的含义与矩阵的表达式相同，而 =,2,( = 1,2,)即 A=（）1,2, 将非标准形式化为标准形式的情况（3 种基本情况）（1）目标函数为求极小值minZ=CX, 则作 Z=-CX, 即 maxZ=-CX(2)右端项小于 0 只需要将

18、两端同乘（-1） ，不等号改变方向，然后再将 不等式改为等式（3）约束条件为不等式 若约束条件为“”则在不等式左侧增加一个非负松驰变量，使其转化为“” ；若约束条件为“” ，则在不等式左侧减去一个非负剩余变量（也称松驰变量） ，使其转化为“”.2.22.2 线性规划模型的求解方法线性规划模型的求解方法 2.2.12.2.1 图解法图解法线性规划可以在一定条件下合理安排人力、 物力等资源 ,使经济效果达到最好.一般来说 ,求线性目标函数在线性约束条件下的最大值或最小值的问题 ,统称为线性规划问题.满足线性约束条件的解叫做可行解 ,由所有可行解组成的集合叫做可行域.决策变量、 约束条件、 目标函数

19、是线性规划的三要素.然而图解法不适合解大规模的线性规划的问题，局限性比较大.但对于只有两个或者三个变量的线性规划问题 ,可以用图解法求最优解 ,也就是作出约束条件的可行域 ,利用图解的方法求出最优解 ,其特点是过程简洁、 图形清晰，简单易懂.下面仅做只有两个变量的线性规划问题. 只含两个变量的线性规划问题，可以通过在平面上作图的方法求解，步骤如下：（1）以变量 x1为横坐标轴，x2为纵坐标轴，适当选取单位坐标长度建立平面坐标直角坐标系.由变量的非负性约束性可知，满足该约束条件的解均在第一象限内.（2）图示约束条件，找出可行域（所有约束条件共同构成的图形）.毕业论文 （设计）用纸佳木斯大学教务处

20、佳木斯大学教务处 第第 9 页页（3）画出目标函数等值线，并确定函数增大（或减小）的方向.（4）可行域中使目标函数达到最优的点即为最优解.下面举出一个实例来说明：例 1某木器厂生产圆桌和衣柜两种产品，现有两种木料，第一种有 72，第二种有 563m，假设生产每种产品都需要用两种木料，生产一张圆桌和一个衣柜分别所需木3m料如下表所示.每生产一张圆桌可获利 60 元,生产一个衣柜可获利 100 元.木器厂在现有木料条件下,圆桌和衣柜各生产多少,才使获得利润最多?木料(单位)3m产 品第 一 种第 二 种圆 桌0.180.08衣 柜0.090.28解：设生产圆桌张,生产衣柜个,利润总额为元,则由已知

21、条件得到的线性规划模xyz型为： ,max = 60 + 100 72,. 0.18 + 0.009 . 0, 0,5628. 008. 0yxyx 图 2-1毕业论文 （设计）用纸佳木斯大学教务处佳木斯大学教务处 第第 10 页页这是二维线性规划，可用图解法解，先在 xy 坐标平面上作出满足约束条件的平面区域,即可行域 S，如上图所示.再作直线,即,把直线 平移至010060:yxl053: yxll的位置时,直线经过可行域上点,且与原点距离最远,此时取最大值，为1lMyxz10060 了得到 M 点坐标解方程组,得;5628. 008. 07209. 018. 0yxyx于是知点坐标为(3

22、50,100)，从而得到使利润总额最大的生产计划，即生产圆桌M350 张,生产衣柜 100 个,能使利润总额达到最大值 31000 元.这表明，当资源数量已知,经过合理制定生产计划,可使效益最好,这就是用图解法解线性规划来解决生产计划安排的问题之一. 2.2.22.2.2 单纯形法单纯形法单纯形是美国数学家 G.B.丹齐克于 1947 年首先提出来的.它的理论根据是：线性规划问题的可行域是 n 维向量空间 Rn 中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到.顶点所对应的可行解称为基本可行解.单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法

23、则转换到另一改进的基本可行解，再鉴别；若仍不是，则再转换，按此重复进行.因基本可行解的个数有限，故经有限次转换必能得出问题的最优解.如果问题无最优解也可用此法判别.1953 年美国数学家 G.B.丹齐克为了改进单纯形法每次迭代中积累起来的进位误差，提出改进单纯形法.其基本步骤和单纯形法大致相同，主要区别是在逐次迭代中不再以高斯消去法为基础，而是由旧基阵的逆去直接计算新基阵的逆，再由此确定检验数.这样做可以减少迭代中的累积误差，提高计算精度，同时也减少了在计算机上的存储量.1954 年美国数学家 C.莱姆基提出对偶单纯形法.单纯形法是从原始问题的一个可行解通过迭代转到另一个可行解，直到检验数满足

24、最优性条件为止.对偶单纯形法则是从满足对偶可行性条件出发通过迭代逐步搜索原始问题的最优解.在迭代过程中始终保持基解的对毕业论文 （设计）用纸佳木斯大学教务处佳木斯大学教务处 第第 11 页页偶可行性，而使不可行性逐步消失.本节内容只对一般单形法的进行探讨.下面举出一个实际例子来做介绍例：求下列线性规划问题的最优解 004155160203025max211212121xxxxxxxxxz解：化为标准形式 （1）04155160203000025max515142132154321xxxxxxxxxxxxxxz第一步：确定一个初始基可行解；基可行解就是满足非负条件的基本解，因此要在约束矩阵 A

25、中找出一个可逆的基矩阵. （2）10001010150012030A这里 m=3，3 阶可逆方阵，可以看出 x3,x4,x5的系数列向量是线性独立的，这些向量构成一个基)，对应的基变量为x3,x4,x5，x1,x2为非基变量.543)0(,(100010001pppB将基变量用非基变量表示，由(2)得：x3=160-30 x1-20 x2x4=15-5x1-x2 （3）x5=4-x1毕业论文 （设计）用纸佳木斯大学教务处佳木斯大学教务处 第第 12 页页将(3)代入目标函数得 Z=5x1+2x2+0令非基变量 x1=x2=0,代入(3),得到一个基可行解 X(0)X(0)=(0,0,160,1

26、5,4)第二步：从当前基可行解转换为更好的基可行解；从数学角度看，x1,x2的增加将会增加目标函数值，从目标函数值中 x1,x2前的系数看，x1前的系数大于 x2前的系数，所以让 x1从非基变量转为基变量，称为进基变量，怎样确定离基变量：因为 x2仍为非基变量，故 x2=0则(3)式变为x3=160-30 x1 160/30=16/3x4=15-5x1 15/5=3x5=4-x1 4/1=4min=3，所以当 x1=3 时，x4第一个减少到 0，所以 x4出基,则X(1)=(3,0,70,0,1),(531)1(pppBZ(1)=15此时非基变量为 x2,x4,用非基变量表示基变量，代入(3)

27、x3=70-14x2+6x4x1=3-1/5x2-1/5x4 （4）x5=1+1/5x2+1/5x4将(4)代入目标函数得 Z=15+x2-x4第三步：继续迭代x2进基，x4仍为非基变量，令 x4=0，则(4)式表示为x3=70-14x2 70/145x1=3-1/5x2 3/(1/5)15x5=1+1/5x2毕业论文 （设计）用纸佳木斯大学教务处佳木斯大学教务处 第第 13 页页min=5，所以当 x2=5 时，x3首先减少到 0，所以 x3出基则 X(2)=(2,5, 0,0,2),(521)2(pppBZ(2)=20此时非基变量为 x3,x4,用非基变量表示基变量，代入(4)x2=5-1

28、/14x3+3/7x4x1=2+1/70 x3-2/7x4 （5）x5=2-1/70 x3+2/7x4将(5)代入目标函数得 Z=20-1/14x3-4/7x4此时若非基变量 x3,x4的值增加，只能使 Z 值下降所以 X(2)为最优解，Z*=20, X*=(2,5, 0,0,2)第三章第三章 线性规划模型在实际问题中的应用线性规划模型在实际问题中的应用3.13.1 线性规划在企业管理中的应用线性规划在企业管理中的应用 3.1.13.1.1 线性规划在企业管理中的应用范围线性规划在企业管理中的应用范围 毕业论文 （设计）用纸佳木斯大学教务处佳木斯大学教务处 第第 14 页页线性规划在企业管理中

29、的应用广泛，主要有以下八种形式：1.产品生产计划：合理利用人力、物力、财力等，是获利最大.2.劳动力安排 ：用最少的劳动力来满足工作的需要.3.运输问题 ：如何制定运输方案，使总运费最少.4.合理利用线材问题 ：如何下料，使用料最少.5.配料问题 ：在原料供应的限制下如何获得最大利润.6.投资问题 ：从投资项目中选取方案，是投资回报最大.7.库存问题 ：在市场需求和生产实际之间，如何控制库存量从而获得更高利益.8.最有经济计划问题 ：在投资和生产计划中如何是风险最小.3.1.23.1.2 如何实现线性规划在企业管理中的应用如何实现线性规划在企业管理中的应用在线性规划应用前要建立经济与金融体系的

30、评价标准及企业的计量体系，摸清企业的资源.首先通过建网、建库、查询、数据采集、文件转换等，把整个系统的各有关部分的特征进行量化，建立数学模型，即把组成系统的有关因素与系统目标的关系，用数学关系和逻辑关系描述出来，然后白较好的数学模型编制成计算机语言，输入数据，进行计算，不同参数获取的不同结果与实际进行分析对比，进行定量，定性分析，最终作出决策.3.23.2 线性规划在企业生产计划中的应用线性规划在企业生产计划中的应用 一：应用线性规划来进行生产计划问题分析，首先需要弄清楚以下几点：1.必须明确目标函数.生产计划的经济分析是一种定量分析方法，它以企业利润作为评价目标值，所寻求的目标是使企业利润最

31、大化的生产计划决策，因此，企业利润最大化应是生产计划决策分析的目标函数.2.必须明确约束条件.企业的生产能力，原材料，设备使用，市场需求状况等诸多制约因素与生产计划分析密切相关，称为生产计划分析中目标函数的约束条件.约束条件对生产计划分析的影响较大，在不同条件下，决策分析的结论则会不同.比如，就市场需求和企业生产能力之间的关系而言，企业所处状态可有三种类型:能力不足状态，即市场对产品的需求超过了企业的生产能力;能力过剩状态，即企业生产能力超过了市场需要:中间状态，即供求平衡的状态，或者有时处于不足状态，有时又处于过剩状态.3.必须明确单件利润.单件利润不仅牵扯到产品的单件收入，还要牵扯到生产所

32、耗费的各项成本及费用.毕业论文 （设计）用纸佳木斯大学教务处佳木斯大学教务处 第第 15 页页 二、建立生产计划决策分析的线性规划模型生产计划决策分析的基本方法是以利润最大化作为优化目标，明确未知变量，确定约束条件，建立线性规划模型，最终实现企业效益最大化的生产计划.其一般模式: 目标函数为利润 P P=销售收入 R R-(成本+费用)C C.在各种约束条件下，使目标函数达到最大值.分析企业实际生产过程中的日产量情况，设模型的未知变量为企业生产的产品种类日产量建立生产计划决策分析线性规划模型的过程如下:（ = 1,2,）( 1 )目标函数企业进行生产计划决策的目标值是企业利润最大化.现假设生产

33、各种产品所获得的销售收入 R;与所耗费的产品成本和费用 C;均已知，则可以得出生产计划问题的目标函数为: =(1 1)1+(2 2)2+ + ( )( 2 )原材料约束无论是生产何种产品都需要消耗一定的原材料，在企业实际中若需耗用多种原材料则可根据原材料的种类，增添相应约束条件即可，建立约束不等式: 111+ 122+ 1 1上式中，分别为生产第 1,2，n 种产品的单件原材料消耗，11，12，1为企业每可用的原材料总量.1（3）生产能力约束. 此约束具体表现为企业的可用工作时间或可用设备，而企业在一定时期内的可用工作是有限的，所以可建立如下的约束不等式： 211+ 222+ + 2 2上式中

34、，分别为生产第 1,2，种产品的单件消耗工时，为企21，22，2，2业的日可用的工时、料总量.（4）市场需求约束 为了说明问题的方便，假设企业生产的产品市场都有需求，即, 1+ 2+ + 0无上限约束.若第 j 种产品市场需求有限，最大需求为,则可增加约束. （5）非负约束因为生产实际中最多即为不生产产品，所以所有变量 0（ = 1,2,）综上所述，建立生产计划决策分析的线性规划模型如下：毕业论文 （设计）用纸佳木斯大学教务处佳木斯大学教务处 第第 16 页页 =(1- 1)1+(2- 2)2+ + (- ) 111+ 122+ 1 1 211+ 222+ + 2 2 s. t 11+ 22+

35、 0（ = 1,2,）3.33.3 线性规划在运输问题中的应用线性规划在运输问题中的应用运输是物流活动的核心环节，线性规划是运输问题的常用数学模型，利用数学知识可以得到优化的运输方案.运输问题的提出源于如何物流活动中的运输路线或配送方案是最经济或最低成本的.运输问题解决的是已知产地的供应量，销地的需求量及运输单价，如何寻找总配送成本最低的方案；运输问题包含产销平衡运输问题和产销不平衡运输问题；通常将产销不平衡问题转化为产销平衡问题来处理；运输问题的条件包括需求假设和成本假设.需求假设指每一个产地都有一个固定的供应量所有的供应量都必须配送到目的地.与之类似，每一个目的地都有一个固定的需求量，整个

36、需求量都必须有出发地满足；成本假设指从任何一个产地到任何一个销地的配送成本和所配送的数量的线性比例关系.产销平衡运输问题的一般提法是：假设某物资有 m 个产地;各地产量分别为物资从产1，2，1，2，地运往销地的单位运价为,满足：.其数学模型为：njjmiiba11Min Z=minjijijxc11 产地约束njijx1( = 1,2, ,)毕业论文 （设计）用纸佳木斯大学教务处佳木斯大学教务处 第第 17 页页s.t 销地约束 （a）miijx1( = 1,2,) (非负约束 0 = 1,2, ,; = 1,2,)1：产销不平衡运输问题分两种情况：（1）总产量大于总销量，既满足，此时其数学模

37、型与表达式(a)基本相同，njjmiiba11只需将表达式（a）中的产地约束条件 改为 .njijx1njijx1（2）总产量小于总销量，既满足，此时其数学模型与表达式(a)也基本相同，njjmiiba11只需将表达式（a）中的产地约束条件 改为 .njijx1njijx12.运输问题的解决策略 现实生产的情况往往比较复杂，许多实际问题不一定完全符合运输问题的假设，可能一些特征近似但其中的一个或者几个特征却并不符合运输问题条件.一般来说，如果一个问题中涉及两大类对象之间的联系或往来，且该问题能提供运输问题所需要的三类数据:供应量、需求量、单位运价，那么这个问题(不管其中是否涉及运输)经适当约束条件的处理后，基木都可以应用运输问题模型来解决.例如:（1）追求的目标是效益最大而非成木最低，此时仅将表达式(a)中目标函数中的“Min Z”改为“Max Z”即可.（2）部分(或全部)