囧事百科-生活百科知识大全

网站地图生活

囧事百科-生活百科知识大全

当前位置: 囧事百科 > 炒股 >

线性规划

时间:2022-04-30 09:36人气:来源: www.clzqx88.com

线性规划概述
线性规划是运筹学中研究较早、进步较快、应用广泛、办法较成熟的一个要紧分支,它是辅助大家进行科学习管理的一种数学办法.在经济管理、交通运输、工农业生产等经济活动中,提升经济成效是大家不可或缺的需要,而提升经济成效通常通过两种渠道:一是技术方面的改进,比如改变生产工艺,用新设施和新型原材料.二是生产组织与计划的改进,即合理安排人力物力资源.线性规划所研究的是:在肯定条件下,合理安排人力物力等资源,使经济成效达到最好.通常地,求线性目的函数在线性约束条件下的最大值或最小值的问题,统称为线性规划问题。满足线性约束条件的解叫做可行解,由所有可行解组成的集合叫做可行域。决策变量、约束条件、目的函数是线性规划的三要点.
线性规划的进步
法国数学家 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.由决策变量所受的限制条件确定决策变量所要满足的约束条件。
当大家得到的数学模型的目的函数为线性函数,约束条件为线性等式或不等式时称此数学模型为线性规划模型。
例:
生产安排模型:某工厂要安排生产Ⅰ、Ⅱ两种商品,已知生产单位商品所需的设施台时及A、B两种原材料的消耗,如表所示,表中右侧一列是每天设施能力及原材料提供的限量,该工厂生产一单位商品Ⅰ可获利2元,生产一单位商品Ⅱ可获利3元,问应怎么样安排生产,使其获得最多?



解:
1、确定决策变量:设x1、x2为商品Ⅰ、Ⅱ的生产数目;
2、明确目的函数:获利最大,即求2x1+3x2最大值;
3、所满足的约束条件:
设施限制:x1+2x2≤8
原材料A限制:4x1≤16
原材料B限制:4x2≤12
基本需要:x1,x2≥0
用max代替最大值,s.t.(subject to 的简写)代替约束条件,则该模型可记为:
maxz=2x1+3x2
s.t. x1+2x2≤8
4x1≤16
4x2≤12
x1,x2≥0
线性规划的解法
求解线性规划问题的基本办法是单纯形法,目前已有单纯形法的规范软件,可在电子计算机上求解约束条件和决策变量数达 10000个以上的线性规划问题。为了提升解题速度,又有改进单纯形法、对偶单纯形法、原始对偶办法、分解算法和各种多项式时间算法。对于只有两个变量的容易的线性规划问题,也可使用图形解析法求解。这种办法仅适用于只有两个变量的线性规划问题。它的特征是直观而易于理解,但实用价值不大。通过图形解析法求解可以理解线性规划的一些基本定义。
单纯形法
可按现代电子计算机标准程序求解线性规划模型的通常办法。分为代数形式的单纯形法和表格形式的单纯形法。前者提供基本算法所依据的逻辑规则,适用于在电子计算机上进行求解运算;后者将变量和数据列成表格,适用于笔算。两者在数学上是等价的。单纯形法是由美国数学家G.B.丹齐克(1914~)于1947年提出来的,它与苏联数学家Л.Β.坎托罗维奇(1912~)于1938年提出的解乘数法相类似。 依据单纯形法的原理,在线性规划问题中,决策变量(控制变量)x1,x2,…x n的值称为一个解,满足所有些约束条件的解称为可行解。使目的函数达到最大值(或最小值)的可行解称为最佳解。如此,一个最佳解能在整个由约束条件所确定的可行地区内使目的函数达到最大值(或最小值)。求解线性规划问题的目的就是要找出最佳解。
可能出现下列状况之1、①存在着一个最佳解;②存在着无穷多个最佳解;③没有最佳解,这只在两种状况下发生,即没可行解或各项约束条件不阻止目的函数的值无限增大(或向负的方向无限增大)。
要缩小对最佳解的搜索范围,就需要认识最佳解的通常性质,最佳解假如存在的话,则它势必处于可行地区的边界上。
任何一项约束条件的边界方程是用“=”号来替换该约束条件中的“≤”或“≥”号而得到的。每个边界方程确定一个超平面。因此,可行地区的边界是由那些满足一个或同时满足几个边界方程(即处在作为边界的一个或几个超平面上)的可行解所组成,而且最佳解必在其中。最佳解不止是在可行地区的边界上,而且也在这个地区的一个隅角上。一个可行解,假如不处在由另两个可行解连接起来的任何线段上,它就是一个角点可行解。假如连接两个角点可行解的线段处在可行地区的边界上,这两个角点可行解就称为相邻的角点可行解。角点可行解具备下列三个重要程度质:①假如存在着一个最佳解,那样它一定是角点可行解。假如存在有多个最佳解,那样至少有两个最佳解一定是相邻的角点可行解。②只存在有限个数的角点可行解。③假如一个角点可行解按目的函数值来衡量时比其所有些相邻角点可行解更好一些,那它就比所有其他角点可行解都更好,也就是最佳解。
上述这类性质构成单纯形法的原理基础。最后一个性质的重要程度在于它为一个角点可行解是不是是最佳解提供了一种方便的检验标准,因而毋需列举所有些可行解。单纯形法正是借助了这个性质,只须检查少数的角点可行解,并且一旦这个最佳性检验获得通过就可立即停止运算。
单纯形法的运算步骤可归结为:①起始步骤──在一个角点可行解上开始。②迭代步骤──移动至一个更好一些的相邻角点可行解(依据需要反复进行这一步骤)。③停止法则──在目前角点可行解比所有相邻角点可行解都更好些时停止。目前角点可行解就是一个最佳解。
单纯形法的优点及其成功之处在于它仅需较少的有限次数的迭代,即可找到最佳解。
线性规划的应用
在企业的各项管理活动中,比如计划、生产、运输、技术等问题,线性规划是指从各种限制条件的组合中,选择出最为适当的计算办法,打造线性规划模型从而求得最好结果.


标签: 线性规划(0)

上一篇:经济增长方法

网站首页

下一篇:没有了