词条 | 线性规划 |
释义 | xianxing guihua 线性规划(卷名:数学) linear programming 是数学规划中理论成熟,方法有效,应用最广泛的一个分支。它研究线性的目标函数的极值,而自变量必须满足一组线性等式与不等式组成的约束条件。 线性规划最早的工作始于20世纪30年代。1939年苏联数学家Л.Β.坎托罗维奇发表的名为《生产组织与计划中的数学方法》的小册子,是有关线性规划的最早文献。在这以后,美国也开始研究这个问题,早期最有影响的是F.L.希契科克研究的运输问题及其解。但是,他们的工作都没有受到注意。由于战争的需要,军事中有关规划、计划、侦察、后勤、生产等各方面的问题都陆续被提出来,系统的研究线性规划的解法与应用便被提到日程上来了。1947年,G.B.丹齐克提出了一般的线性规划模型和理论(线性规划的名称也是他首先提出的),以及著名的单纯形方法,从而奠定了数学规划作为一门学科的基石。直到现在,单纯形方法仍然是这门学科中的有力工具。 从50年代起,线性规划的应用逐渐从军事扩大到其它领域。例如,1951年T.C.库普曼斯结合W.列昂季耶夫投入产出模型将线性规划应用于生产问题;J.冯·诺伊曼研究矩阵对策与线性规划的关系,将它应用于经济平衡问题。大型电子计算机的出现对线性规划的理论以及应用的发展起着决定性的作用。在经济领域中广泛地应用线性规划方法,并且利用电子计算机已能解决变量个数达数百万之多的具有特殊结构的大型线性规划问题。 线性规划的基本概念 可以用一个简单的例子来说明,一个工厂生产甲、乙两种产品,假设产品甲受某种所需原料的限制,每周最多只能生产8个单位,又假设甲、乙同时需要的另一种原料每周供应60公斤,而生产每单位产品甲需原料5公斤,乙需要2公斤。此外,生产甲、乙需要同一台机器,且单位产品加工时间甲需2小时,乙需4小时,每周机械最多工作80小时。如果甲的单价为15元,乙为10元,若以生产总值最大为目标,且令甲、乙的产量分别为x1,x2,那么,问题是要确定x1与x2的值,使满足约束条件:x1≤8,5x1+2x2≤60,2x1+4x2≤80,x1≥0,x2≥0=且使目标函数ƒ(x)=15x1+10x2取最大值。下面借助附图来说明这个简单线性规划问题的解的基本性质。 满足约束条件的每一个点称为可行解。可行解的全体组成的集合称为可行解集。在所有可行解中求出一个使目标函数取最大值的可行解,这个可行解称为最优解。 上述问题的可行解集形成图中多边形ABCDE围成的区域,它有5个顶点A,B,C,D,E。如果赋于目标函数一个给定的值d,则称ƒ(x)=d为目标函数的等值线,如图 ![]() 上例说明,线性规划的最优解可以在可行解集的某一个顶点上达到。这对于未知变量多于两个和可行解集不是有界的情形也是正确的,是线性规划解的一个基本性质。根据这一性质,为了求最优解,只须比较目标函数在有限个顶点上的值。然而,对于变量和约束条件很多的情形,顶点数目很大,必须采用有效方法和借助于电子计算机来求解,单纯形方法就是基于此性质而建立的计算方法。 单纯形方法 1947年由丹齐克建立的解决线性规划问题的有效方法。它解决如下的标准型线性规划问题: ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() 线性规划的对偶理论 每个线性规划问题都有一个被称为它的对偶问题的线性规划问题与之对应。如线性规划问题(4)~(6)的对偶问题为 ![]() 对偶定理 若原问题与对偶问题之一有有限最优解,则另一问题亦有有限最优解,且两者的目标函数值相等,即mincTx=maxbTu。若其中之一无有限最优值,则另一问题无可行解。 基于对偶理论,与单纯形法有密切联系的,有对偶单纯形法,原始对偶单纯形法等;由于计算数学、特别是数值代数的发展,单纯形法的具体实现已经有了很大发展,并且形成了许多能够有效解决大型线性规划问题的计算机软件包,但是从理论上讲,单纯形法不是多项式算法(见组合最优化),苏联数学家Л.Γ.哈奇扬于1979年提出了著名的线性规划多项式算法,或称椭球体算法,从理论上证明了线性规划问题属于p问题,解决了十多年来悬而未决的问题。但只是理论结果,这一方法距离实际应用还很远。1984年,印度数学家N.卡马卡提出一个新的多项式算法──投影算法,在理论上优于椭球体算法,在实际计算效果上,也显示了高速度,引起了运筹学界的重视。 运输问题 是一类特殊的线性规划问题,它是由Л.Β.坎托罗维奇与F.L.希契科克分别提出的。其基本提法如下: 设某种产品的产地为A1,A2,…,Am;Ai的产量为αi,若欲将产品从产地运往销地B1,B2,…,Bn;Bj的销量为bj,且 ![]() 设xij为从Ai运到Bj的产品数量,则上述问题的数学模型为 ![]() ![]() 对于解决运输问题,较有效的解法是网络流方法和表上作业法。如果将产地和销地及其间的距离在图上表示,且要求的是吨公里数最小,则可以用图上作业法求解。这个方法是50年代初中国粮食部门的同志的经验总结,中国科学院的运筹学工作者从数学上严格论证了它的最优性。图上作业法的要点是:①没有对流,即在任何一段运输路线上没有相对往返的运输;②没有迂回,在一条封闭成圈的回路上,从一点到另一点的运输要走小半圈,若走大半圈就是迂回。 上述方法简单易懂,只需在图上进行计算和调整,便可得到吨公里最小的方案。 参考书目 中国科学院数学研究所运筹室编:《运筹学》,科学出版社,北京,1973。 G.B.Dantzig,Lineαr Progrαmming, PrincetonUniv.Press, Princeton, 1963. |
随便看 |
百科全书收录78206条中英文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。