五山湖杯数学建模大赛官方网站
设为首页
 
首 页 | 五山湖 | 数学建模 | 自然现象 | 思想源泉 | 木棉芒果 | 礼品收藏 | 珊瑚礁 | 百步梯 | 联系咨询
  当前位置:首页 > 博文精选 

线性规划的发展
发布日期:2011-5-3 20:31:18
 点击:5907

线性规划的发展

      线性规划是合理利用、调配资源的一种应用数学方法。它的基本思路就是在满足一定的约束条件下,使预定的目标达到最优。它的研究内容可归纳为两个方面:一是系统的任务已定,如何合理筹划,精细安排,用最少的资源(人力、物力和财力)去实现这个任务;二是资源的数量已定,如何合理利用、调配,使任务完成的最多。前者是求极小,后者是求极大。线性规划是在满足企业内、外部的条件下,实现管理目标和极值(极小值和极大值)问题,就是要以尽少的资源输入来实现更多的社会需要的产品的产出。因此,线性规划是辅助企业“转轨”、“变型”的十分有利的工具,它在辅助企业经营决策、计划优化等方面具有重要的作用。
         线性规划是运筹学规划论的一个分支。它发展较早,理论上比较成熟,应用较广。20世纪30年代,线性规划从运输问题的研究开始,在二次大战中得到发展。现在已广泛地应用于国民经济的综合平衡、生产力的合理布局、最优计划与合理调度等问题,并取得了比较显著的经济效益。线性规划的广泛应用,除了它本身具有实用的特点之外,还由于线性规划模型的结构简单,比较容易被一般未具备高深数学基础,但熟悉业务的经营管理人员所掌握。它的解题方法,简单的可用手算,复杂的可借助于电子计算机的专用软件包,输入数据就能算出结果。
         线性规划的研究与应用工作,我国开始于20世纪50年代初期,中国科学院数学所筹建了运筹室,最早应用在物资调运筹方面,在实践中取得了成果,在理论上提出了论证。目前,国内高等学校已将其列为运筹学中必选的课程内容之一,在实际应用方面也已列入重点企业试点和研究项目之一。


线性规划的模型的结构
        企业是一个复杂的系统,要研究它必须将其抽象出来形成模型。如果将系统内部因素的相互关系和它们活动的规律用数学的形式描述出来,就称之为数学模型。线性规划的模型决定于它的定义,线性规划的定义是:求一组变量的值,在满足一组约束条件下,求得目标函数的最优解。
         根据这个定义,就可以确定线性规划模型的基本结构。
       (1)变量   变量又叫未知数,它是实际系统的未知因素,也是决策系统中的可控因素,一般称为决策变量,常引用英文字母加下标来表示,如Xl,X2,X3,Xmn等。
       (2)目标函数   将实际系统的目标,用数学形式表现出来,就称为目标函数,线性规划的目标函数是求系统目标的数值,即极大值,如产值极大值、利润极大值或者极小值,如成本极小值、费用极小值、损耗极小值等等。
       (3)约束条件   约束条件是指实现系统目标的限制因素。它涉及到企业内部条件和外部环境的各个方面,如原材料供应、设备能力、计划指标、产品质量要求和市场销售状态等等,这些因素都对模型的变量起约束作用,故称其为约束条件。
         约束条件的数学表示形式为三种,即≥、=、≤。线性规划的变量应为正值,因为变量在实际问题中所代表的均为实物,所以不能为负。在经济管理中,线性规划使用较多的是下述几个方面的问题:
         (1) 投资问题—确定有限投资额的最优分配,使得收益最大或者见效快。
         (2) 计划安排问题—确定生产的品种和数量,使得产值或利润最大,如资源配制问题。
        (3) 任务分配问题—分配不同的工作给各个对象(劳动力或机床),使产量最多、效率最高,如生产安排问题。
        (4) 下料问题—如何下料,使得边角料损失最小。
        (5) 运输问题—在物资调运过程中,确定最经济的调运方案。
        (6) 库存问题—如何确定最佳库存量,做到即保证生产又节约资金等等。
        应用线性规划建立数学模型的三步骤:
        (1) 明确问题,确定问题,列出约束条件。
        (2) 收集资料,建立模型。
        (3) 模型求解(最优解),进行优化后分析。
         其中,最困难的是建立模型,而建立模型的关键是明确问题、确定目标,在建立模型过程中花时间、花精力最大的是收集资料。


线性规划在工业生产中的应用
       线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法.在经济管理、交通运输、工农业生产等经济活动中,提高经济效果是人们不可缺少的要求,而提高经济效果一般通过两种途径:一是技术方面的改进,例如改善生产工艺,使用新设备和新型原材料.二是生产组织与计划的改进,即合理安排人力物力资源.线性规划所研究的是:在一定条件下,合理安排人力物力等资源,使经济效果达到最好.一般地,求线性目标函数在线性约束条件下的最大值或最小值的问题,统称为线性规划问题。满足线性约束条件的解叫做可行解,由所有可行解组成的**叫做可行域。决策变量、约束条件、目标函数是线性规划的三要素。我们根据他在现实生活中的意义进行相关讨论与探究。
                       活动过程
线性规划的发展
     法国数学家 J.- B.- J.傅里叶和 C.瓦莱-普森分别于1832和1911年独立地提出线性规划的想法,但未引起注意。
     1939年苏联数学家Л.В.康托罗维奇在《生产组织与计划中的数学方法》一书中提出线性规划问题,也未引起重视。
     1947年美国数学家G.B.丹齐克提出线性规划的一般数学模型和求解线性规划问题的通用方法——单纯形法,为这门学科奠定了基础。
     1947年美国数学家J.von诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域,扩大了它的应用范围和解题能力。
     1951年美国经济学家T.C.库普曼斯把线性规划应用到经济领域,为此与康托罗维奇一起获1975年诺贝尔经济学奖。
     50年代后对线性规划进行大量的理论研究,并涌现出一大批新的算法。例如,1954年C.莱姆基提出对偶单纯形法,1954年S.加斯和T.萨迪等人解决了线性规划的灵敏度分析和参数规划问题,1956年A.塔克提出互补松弛定理,1960年G.B.丹齐克和P.沃尔夫提出分解算法等。
   线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究。由于数字电子计算机的发展,出现了许多线性规划软件,如MPSX,OPHEIE,UMPIRE等,可以很方便地求解几千个变量的线性规划问题。
   1979年苏联数学家L. G. Khachian提出解线性规划问题的椭球算法,并证明它是多项式时间算法。
1984年美国贝尔电话实验室的印度数学家N.卡马卡提出解线性规划问题的新的多项式时间算法。用这种方法求解线性规划问题在变量个数为5000时只要单纯形法所用时间的1/50。现已形成线性规划多项式算法理论。50年代后线性规划的应用范围不断扩大。 建立线性规划模型的方法。
线性规划的模型建立
   从实际问题中建立数学模型一般有以下三个步骤;
1.根据影响所要达到目的的因素找到决策变量;
2.由决策变量和所在达到目的之间的函数关系确定目标函数;
3.由决策变量所受的限制条件确定决策变量所要满足的约束条件。
所建立的数学模型具有以下特点:
1、每个模型都有若干个决策变量(x1,x2,x3……,xn),其中n为决策变量个数。决策变量的一组值表示一种方案,同时决策变量一般式非负的。
2、目标函数是决策变量的线性函数,根据具体问题可以是最大化(max)或最小化(min),二者统称为最优化(opt)。
3、约束条件也是决策变量的线性函数。
我们得到的数学模型的目标函数为线性函数,约束条件为线性等式或不等式时称此数学模型为线性规划模型。
线性规划的应用
     企业的各项管理活动中,例如计划、生产、运输、技术等问题,线性规划是指从各种限制条件的组合中,选择出最为合理的计算方法,建立线性规划模型从而求得最佳结果。
     我们原来所谓的认识与理解都是肤浅的,对线性规划问题只是有一个模糊的理解,对深层次没有什么理解,也不能很好的把握。但经过几个月的搜集资料和认真研究,我们终于对线性规划有了深一点的发现与感受。

 
收 藏 推 荐 打 印 关 闭


最新录入  
 · 第一届“百农杯”数学建模竞赛...
 · A Microcircuit...
 · Burst firing t...
 · 第二届全国神经动力学会议回执
 · 第二届全国神经动力学会议论文...
 · 第二届全国神经动力学会议征文通知
 · 第二届全国神经动力学会议学术...
 · 第二届全国神经动力学会议(第...
 · 第二届全国神经动力学会议
 · 第二届全国神经动力学会议
相关内容   更多>>
 · 脊椎和脑的神经连接
 · 皮层中间神经元
 · 数学建模的力量
 · 蒲慕明给实验室学生讲的话
 · 遗传算法:内存中的进化
 · 线性规划的发展
 · 谁发现了时间?
 · 你能听到鼓的体积吗?
 · 为什么数学家将数学弄的这么复杂
 · 年龄大的表现
 
声明 | 报名须知 | 联系方式 | 五山湖 技术支持:郑州建网站 Copyright (c) 2011 All Rights Reserved.