线性规划模型的求解及应用毕业论文.doc

《线性规划模型的求解及应用毕业论文.doc》由会员分享，可在线阅读，更多相关《线性规划模型的求解及应用毕业论文.doc（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、毕业论文（设计）课题名称 线性规划模型的求解及应用 学 院 理 学 院 专 业 数学与应用数学 （S） 班 级 2010 级 数学2班 指导教师 学生姓名 佳木斯大学教务处线性规划模型的求解及应用 佳木斯大学理学院数学系2014年6月佳木斯大学教务处 摘 要线性规划是运筹学的一个重要分支，它辅助人们进行科学管理，是国际应用数学、经济、计算机科学界所关注的重要研究领域.线性规划主要研究有限资源最佳分配问题，即如何对有限的资源进行最佳地调配和最有利地使用，以便最充分发挥资源的效能来获取最佳的经济效益.线性规划运用数学语言描述某些经济活动的过程，形成数学模型，以一定的算法对模型进行计算，为制定最优计

2、划方案提供依据.其解决问题的关键是建立符合实际情况的数学模型，即线性规划模型.在各种经济活动中，常采用线性规划模型进行科学、定量分析，安排生产组织与计划，实现人力物力资源的最优配置，获得最佳的经济效益.目前，线性规划模型被广泛应用与经济管理、交通运输、工农业生产等领域.本文主要介绍线性规划的两种基本解法即图解法和单纯形法，并讨论了这两种方法的优缺点和在一些实际问题中的应用.关键词: 线性规划；图解法；单纯形法；数学模型；应用AbstractLinear programming is an important branch of operations research, which assist

3、 people to scientific management is an important area of research internationally applied 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 advantageous

4、ly used in order to most fully effective resources to get the best value for money.Linear 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 form

5、ulation of the optimal plan for. The key to solve the problem is to create a mathematical 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 fo

6、r production to achieve the optimal allocation of human and material resources, to get 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 solu

7、tion that graphical method for linear programming and the simplex method, and discuss the 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目 录摘 要ABSTRACT第1章 绪论1

8、.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线性规划在运输问题中的应用结论参考文献第1章 绪论 1.1 线性规划的基本概念 1.1.1 线性规划简介线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重

9、要分支,它是辅助人们进行科学管理的一种数学方法.在经济管理、交通运输、工农业生产等经济活动中，提高经济效果是人们不可缺少的要求，而提高经济效果一般通过两种途径：一是技术方面的改进，例如改善生产工艺，使用新设备和新型原材料.二是生产组织与计划的改进，即合理安排人力物力资源.线性规划所研究的是：在一定条件下，合理安排人力物力等资源，使经济效果达到最好.一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题.满足线性约束条件的解叫做可行解，由所有可行解组成的集合叫做可行域.决策变量、约束条件、目标函数是线性规划的三要素.1.1.2 线性规划由来的时间简史 法国数学家J.-

10、B.- J.傅里叶和C.瓦莱普森分别于1832和1911年独立地提出线性规划的想法，但未引起注意.1939年苏联数学家.康托罗维奇在生产组织与计划中的数学方法一书中提出线性规划问题，也未引起重视.1947年美国数学家G.B.Dantzing提出求解线性规划的单纯型法，为这门学科奠定了基础.1947年美国数学家J.von诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域，扩大了它的应用范围和解题能力.1951年美国经济学家T.C.库普曼斯把线性规划应用到经济领域，为此与康托罗维奇一起获1975年诺贝尔经济学奖.50年代后对线性规划进行大量的理论研究，并涌现出一大批新的算法.例如，1954年C.

11、莱姆基提出对偶单纯形法，1954年S.加斯和T.萨迪等人解决了线性规划的灵敏度分析和参数规划问题，1956年A.塔克提出互补松弛定理，1960年G.B.丹齐克和P.沃尔夫提出分解算法等.线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究.由于数字电子计算机的发展，出现了许多线性规划软件，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解几千个变量的线性规划问题.1979年苏联数学家L. G. Khachian提出解线性规划问题的椭球算法，并证明它是多项式时间算法.1984年美国贝尔电话实验室的印度数学家N.卡马卡提出解线性规划问题的新的多项式时间

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

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

14、形式上的差别，线性规划问题有多种表达式，为了便于讨论和制定统一的算法，规定标准形式如下：（1）标准形式 (2) 记号简写式 （3）矩阵形式 式中, （4）向量形式 式中C,X,b,0的含义与矩阵的表达式相同，而 即A=（） 将非标准形式化为标准形式的情况（3种基本情况）（1）目标函数为求极小值minZ=CX, 则作Z=-CX, 即maxZ=-CX(2)右端项小于0 只需要将两端同乘（-1），不等号改变方向，然后再将 不等式改为等式（3）约束条件为不等式 若约束条件为“”则在不等式左侧增加一个非负松驰变量，使其转化为“”；若约束条件为“”，则在不等式左侧减去一个非负剩余变量（也称松驰变量），使其

15、转化为“”.2.2 线性规划模型的求解方法 2.2.1图解法线性规划可以在一定条件下合理安排人力、 物力等资源 ,使经济效果达到最好.一般来说 ,求线性目标函数在线性约束条件下的最大值或最小值的问题 ,统称为线性规划问题.满足线性约束条件的解叫做可行解 ,由所有可行解组成的集合叫做可行域.决策变量、 约束条件、 目标函数是线性规划的三要素.然而图解法不适合解大规模的线性规划的问题，局限性比较大.但对于只有两个或者三个变量的线性规划问题 ,可以用图解法求最优解 ,也就是作出约束条件的可行域 ,利用图解的方法求出最优解 ,其特点是过程简洁、 图形清晰，简单易懂.下面仅做只有两个变量的线性规划问题.

16、 只含两个变量的线性规划问题，可以通过在平面上作图的方法求解，步骤如下：（1）以变量x1为横坐标轴，x2为纵坐标轴，适当选取单位坐标长度建立平面坐标直角坐标系.由变量的非负性约束性可知，满足该约束条件的解均在第一象限内.（2）图示约束条件，找出可行域（所有约束条件共同构成的图形）.（3）画出目标函数等值线，并确定函数增大（或减小）的方向.（4）可行域中使目标函数达到最优的点即为最优解.下面举出一个实例来说明：例1某木器厂生产圆桌和衣柜两种产品，现有两种木料，第一种有72，第二种有56，假设生产每种产品都需要用两种木料，生产一张圆桌和一个衣柜分别所需木料如下表所示.每生产一张圆桌可获利60元,生

17、产一个衣柜可获利100元.木器厂在现有木料条件下,圆桌和衣柜各生产多少,才使获得利润最多?产 品木料(单位)第 一 种第 二 种圆 桌0.180.08衣 柜0.090.28解：设生产圆桌张,生产衣柜个,利润总额为元,则由已知条件得到的线性规划模型为： , 72, 图2-1这是二维线性规划，可用图解法解，先在xy坐标平面上作出满足约束条件的平面区域,即可行域S，如上图所示.再作直线,即,把直线平移至的位置时,直线经过可行域上点,且与原点距离最远,此时取最大值，为了得到M点坐标解方程组,得;于是知点坐标为(350,100)，从而得到使利润总额最大的生产计划，即生产圆桌350张,生产衣柜100个,能

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

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

20、逐步消失.本节内容只对一般单形法的进行探讨.下面举出一个实际例子来做介绍例：求下列线性规划问题的最优解 解：化为标准形式 （1）第一步：确定一个初始基可行解；基可行解就是满足非负条件的基本解，因此要在约束矩阵A中找出一个可逆的基矩阵. （2）这里m=3，3阶可逆方阵，可以看出x3,x4,x5的系数列向量是线性独立的，这些向量构成一个基)，对应的基变量为x3,x4,x5，x1,x2为非基变量.将基变量用非基变量表示，由(2)得：x3=160-30x1-20x2x4=15-5x1-x2 （3）x5=4-x1将(3)代入目标函数得Z=5x1+2x2+0令非基变量x1=x2=0,代入(3),得到一个基

21、可行解X(0)X(0)=(0,0,160,15,4)第二步：从当前基可行解转换为更好的基可行解；从数学角度看，x1,x2的增加将会增加目标函数值，从目标函数值中x1,x2前的系数看，x1前的系数大于x2前的系数，所以让x1从非基变量转为基变量，称为进基变量，怎样确定离基变量：因为x2仍为非基变量，故x2=0则(3)式变为x3=160-30x1 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)Z(1)=15此时非基变量为x2,x4,用非基变量表示基变量，代入(3)x

22、3=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/5x2min=5，所以当x2=5时，x3首先减少到0，所以x3出基则X(2)=(2,5, 0,0,2)Z(2)=20此时非基变量为x3,x4,用非基变量表示基变量，代入(4)x2=5-1/14x3+3/7x4x1=2+1/70x3-2/7x4 （5）x5=2-1/70x3+2/7x4将(5)代入目标

23、函数得Z=20-1/14x3-4/7x4此时若非基变量x3,x4的值增加，只能使Z值下降所以X(2)为最优解，Z*=20, X*=(2,5, 0,0,2)第三章 线性规划模型在实际问题中的应用3.1 线性规划在企业管理中的应用 3.1.1 线性规划在企业管理中的应用范围 线性规划在企业管理中的应用广泛，主要有以下八种形式：1.产品生产计划：合理利用人力、物力、财力等，是获利最大.2.劳动力安排 ：用最少的劳动力来满足工作的需要.3.运输问题 ：如何制定运输方案，使总运费最少.4.合理利用线材问题 ：如何下料，使用料最少.5.配料问题 ：在原料供应的限制下如何获得最大利润.6.投资问题 ：从投资

24、项目中选取方案，是投资回报最大.7.库存问题 ：在市场需求和生产实际之间，如何控制库存量从而获得更高利益.8.最有经济计划问题 ：在投资和生产计划中如何是风险最小.3.1.2如何实现线性规划在企业管理中的应用在线性规划应用前要建立经济与金融体系的评价标准及企业的计量体系，摸清企业的资源.首先通过建网、建库、查询、数据采集、文件转换等，把整个系统的各有关部分的特征进行量化，建立数学模型，即把组成系统的有关因素与系统目标的关系，用数学关系和逻辑关系描述出来，然后白较好的数学模型编制成计算机语言，输入数据，进行计算，不同参数获取的不同结果与实际进行分析对比，进行定量，定性分析，最终作出决策.3.2线

25、性规划在企业生产计划中的应用 一：应用线性规划来进行生产计划问题分析，首先需要弄清楚以下几点：1.必须明确目标函数.生产计划的经济分析是一种定量分析方法，它以企业利润作为评价目标值，所寻求的目标是使企业利润最大化的生产计划决策，因此，企业利润最大化应是生产计划决策分析的目标函数.2.必须明确约束条件.企业的生产能力，原材料，设备使用，市场需求状况等诸多制约因素与生产计划分析密切相关，称为生产计划分析中目标函数的约束条件.约束条件对生产计划分析的影响较大，在不同条件下，决策分析的结论则会不同.比如，就市场需求和企业生产能力之间的关系而言，企业所处状态可有三种类型:能力不足状态，即市场对产品的需求

26、超过了企业的生产能力;能力过剩状态，即企业生产能力超过了市场需要:中间状态，即供求平衡的状态，或者有时处于不足状态，有时又处于过剩状态.3.必须明确单件利润.单件利润不仅牵扯到产品的单件收入，还要牵扯到生产所耗费的各项成本及费用. 二、建立生产计划决策分析的线性规划模型生产计划决策分析的基本方法是以利润最大化作为优化目标，明确未知变量，确定约束条件，建立线性规划模型，最终实现企业效益最大化的生产计划.其一般模式: 目标函数为利润P=销售收入R-(成本+费用)C.在各种约束条件下，使目标函数达到最大值.分析企业实际生产过程中的日产量情况，设模型的未知变量为企业生产的产品种类日产量建立生产计划决策

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

28、，种产品的单件消耗工时，为企业的日可用的工时、料总量.（4）市场需求约束 为了说明问题的方便，假设企业生产的产品市场都有需求，即,无上限约束.若第j种产品市场需求有限，最大需求为,则可增加约束.（5）非负约束因为生产实际中最多即为不生产产品，所以所有变量综上所述，建立生产计划决策分析的线性规划模型如下： s. t 3.3 线性规划在运输问题中的应用运输是物流活动的核心环节，线性规划是运输问题的常用数学模型，利用数学知识可以得到优化的运输方案.运输问题的提出源于如何物流活动中的运输路线或配送方案是最经济或最低成本的.运输问题解决的是已知产地的供应量，销地的需求量及运输单价，如何寻找总配送成本最低

29、的方案；运输问题包含产销平衡运输问题和产销不平衡运输问题；通常将产销不平衡问题转化为产销平衡问题来处理；运输问题的条件包括需求假设和成本假设.需求假设指每一个产地都有一个固定的供应量所有的供应量都必须配送到目的地.与之类似，每一个目的地都有一个固定的需求量，整个需求量都必须有出发地满足；成本假设指从任何一个产地到任何一个销地的配送成本和所配送的数量的线性比例关系.产销平衡运输问题的一般提法是：假设某物资有m个产地;各地产量分别为物资从产地运往销地的单位运价为,满足：.其数学模型为：Min Z= 产地约束s.t 销地约束 （a） (非负约束1：产销不平衡运输问题分两种情况：（1）总产量大于总销量

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

31、目标是效益最大而非成木最低，此时仅将表达式(a)中目标函数中的“Min Z”改为“Max Z”即可.（2）部分(或全部)的供应量(产量)代表的是从产地提供的最大数量(而不是一个固定的数值)，此时只需将表达式(a)中的产地约束中部分(或全部)的“ ”改成“ ”即可.(3)部分(或全部)的需求量(销量)代表的是销地接收的最大数量(而不是一个固定的数值)，此时只需将表达式(a)中的销地约束条件中的“”部分(或全部)改成“”即可.(4)某些目的地的同时存在最大需求和最小需求，此时的解决办法是将表达式(a)中的相应的销地约束中的“”一个式子分解成最大需求和最小需求的两个式子即可. 结 论如今，线性规划的

32、求解方法有很多，许多学者都对原先的求解方法进行了不断的改进，计算机时代的发展也加快了解决复杂线性规划问题的速度。这就使得线性规划在实际生活中的应用更加的广泛。目前，中国经济正在快速的发展过程中，其发展的速度已经超过了发达国家在相同的时期发展速度。随着中国进入了WTO，中国经济正在熔入世界经济的大的市场并不断的适应和改进自己的各个方面的制度，与此同时世界各国都在不断的发展自己 。所以线性规划在经济领域的应用显得非常重要。参考文献 1 宁宣熙，运筹学实用教程M . 北京：科学出版社，2003. 2 胡运权，运筹学基础及应用M.北京：清华大学出版社，2004. 3 姜启源. 数学模型（第二版）M.

33、高等教育出版社, 1993 4 夏少刚， 刘心. 线性规划求基可行解的一种方法J. 运筹学学报，2008. 5 胡运权.运筹学基础及应用M.哈尔滨：哈尔滨工业大学出版社，1998.2：105-109 6 现代应用数学手册运筹学与最优化理论卷M.北京：清华大学出版社，1998：68-89 7 姜启源,谢金星,叶俊. 数学模型M. 北京:高等教育出版社，2003.8 8 刘来福, 增文艺. 数学模型与数学建模M. 北京师范大学出版社, 2006 9 管梅谷，郑汉鼎.线性规划.济南:山东科学技术出版社,1983.10 SCHERER C， WEILAND S. Linear matrix inequalities inontril D . delft University of Tdchnology,2005.4 BOYD S, CHAOUI L El,FERON E. etal. Linear mattrix inequalities in systems and control theory M . Philadlphia:SIAM Books1994 11ACKLEY D H. A connectionist machine for genetic hillclimbingM.Boston, USA:Kluwer Academic; Publisshers,1987.