文档库

最新最全的文档下载
当前位置:文档库 > 线性规划

线性规划

线性规划问题在经济生活中的应用

内容摘要:线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法一在经济管理、交通运输、工农业生产等经济活动中,提高经济效果是人们不可缺少的要求,而提高经济效果一般通过两种途径:一是技术方面的改进,例如改善生产工艺,使用新设备和新型原材料:二是生产组织与计划的改进,即合理安排人力物力资源。线性规划所研究的是在一定条件下,合理安排人力物力等资源,使经济效果达到最优。一般地,求线性目标函数在线性约束条件下的最大值或最小值的问题,统称为线性规划问题。文章根据线性规划问题在现实生活中的意义进行相关讨论与探究,介绍了线性规划问题产生的背景、特点和实际运用情况,以及线性规划问题在经济生活中运用的意义。

线性规划问题是数学的一个重要分支,它们所研究的问题是讨论在众多的方案中什么样的方案是最优的、以及怎么找出这些最优方案。在现实的生产活动中这类问题普遍存在,例如在生产计划安排中,选择什么样的生产方案才能提高产值、利润;在原料配给问题中,怎样确定各种成分的比例,才能使提高质量、降低成本的目标得以实现;在资源的分配问题中,怎样分配有限的资源,使得分配方案既能满足于各方面的基本要求,又能获得好的经济效益;在农田规划中,怎样安排各种农作物的合理布局,才能保持高产、稳定,以发挥地区优势;在经济管理中如何使产出率最大,即单位成本的产值最大,或者赢利率最大。诸如此类问题不胜枚举,线性规划就是为了求解这类问题并为求解这些问题提供理论基础与方法而应运而生的、实用性强的学科。

线性规划问题的发展

1947 年美国数学家G B .丹齐克提出线性规划的一般数学模型和求解线性规划问题的通用方法——单纯形法,为这门学科奠定了基础。同年美国数学家J VOIq诺伊曼提出对偶理

论,开创了线性规划的许多新的研究领域,扩大了它的应用范围和解题能力。19 5 1 年美国经济学家T .C .库普曼斯把线性规划应用到经济领域,为此与康托罗维奇一起获19 75 年诺贝尔经济学奖。

2 0 世纪5 0 年代后对线性规划进行大量的理论研究,并涌现出一大批新的算法。例如,1 9 5 4 年C 莱姆基提出对偶单纯形法,1954 年S .加斯和T 萨迪等人解决了线性规划的灵敏度分析和参数规划问题,1 956 年A 塔克提出互补松弛定理,1960年G B 丹齐克和P.沃尔夫提出分解算法等。线性规划的研成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究。由于数字电子计算机的发展,出现了许多线性规划软件,如M P SX ,O P H E IE ,U M P IR E等,可以很方便地求解几千个变量的线性规划问题。

19 79 年苏联数学家L.G .K hachian提出解线性规划问题的椭球算法,并证明它是多项式时间算法。1984 年美国贝尔电话实验室的印度数学家N 卡马卡提出解线性规划问题的新的多项式时间算法。用这种

方法求解线性规划问题在变量个数为5000时只要单纯形法所用时间的1/50 。现已形

成线性规划多项式算法理论。

20 世纪50 年代后线性规划的应用范围不断扩大。线性规划问题应用的特点及般步骤线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法。在经济管理、交通运输、工农业生产等经济活动中,提高经济效果是人们不可缺少的要求,而提高经济效果一般通过两种途径:一是技术方面的改进,例如改善生产工艺,使用新设备和新型原材料。二是生产组织与计划的改进,即合理安排人力物力资源。线性规划所研究的是在一定条件下,合理安排人力物力等资源,使经济效果达到最好。一般地,求线性目标函数在线性约束条件下的最大值或最小值的问题,统称为线性规划问题。满足线性约束条件的解叫做可行解,由所有可行解组成的集合叫做可行域。决策变量、约束条件、目标函数是线性规划的三要素。

许多实际问题抽象成数学模型后均可以归为求解线性规划问题,因此线性规划问题有很强的实用性,实际问题经过数学抽象后成数学模型,均可归结为求解线性规划问题,并且这些实际问题的解就是线性规划问题的最优解,也就是指导现实生产生活的最优方案,由此可见,线性规划问题有很强的实用·性和最优性,它们能为生产生活中的配置提供最优方案。线性规划问题数学模型建立一般步骤:第一,列出约束条件及目标函数;第二,画出约束条件所表示的可行域;第三,在可行域内求目标函数的最优解及最优值。求解线性规划问题的方法常规求解线性规划问题的方法有以下几种:

( 一) 推直线法

对于一些简单的线性规划问题可以用推直线的办法求其最优解,其做法是建立目标函数等值线方程,等值线的法向量元就是目标函数中各未知数系数组成的向量C,它也称为目标函数的梯度,指向目标函数的增长方向,因此沿方向n 移动等值线时,线上各点目标函数值均增大,而沿一n 方向移动等值线时,目标函数值减少。所以求极大值点就泞着n 方向移动等值线,直至它到达极限位置,如再移动就到达与可行域的交为空集的位置。若求目标函数的最小值,就沿一n方向移动目标数等值线直至极限位置,这种方法在处理两元问题时非常有效。

( 二) 单纯形法

单纯形方法的基本思想就是从一个基本可行解出发,求一个使目标函数值有所改善的基本可行解,通过不断改进基本可行解,力图得到最优基本可行解;单纯形法有一个弱点,那就是它们首先要找出一组基本可行解,再从这个基本可行解出发求改进的基本可行解,目前较常见的求初始基本可行解的方法有两种,一种是两阶段法;另外一种是大M 法。

( 三) K arm arkar 算法1984 年印度数学家N K arm a rka 提出了解线性规划问题的一种新算法,这就是关于线性规划的多项式时间算法,轰动了有关领域。引起了人们的极大兴趣,多项式算法就是如果用一个算法解一种问题时需要的计算时间在最坏的情况下不超过输入长度的某个多项式所确定的数值P (L ),则称这个算法是解这种问题的多项式时间算法,简称多项式算法。

( 四) 凸单纯形法

若线性分式规划问题有最优解,则必存在最优极点。凸单纯形方法的基本思想也是从一个基本可行解出发,沿着既约梯度方向,求一个使目标函数值有所改善的基本可行解,通过不断改进基本可行解,力图得到最优基本可行解。

( 五) 代换法

代换法又称C ha rne s —C o op e r方法,它是C harne s 和C o o p e r于1 96 2 年提出来的方法;这种方法的主要思路是利用代换思想将目标函数转化为线性函数,然后利用线性规划的方法去求解。

线性规划问题应用实例

线性规划问题是经济数学的一个重要分支,在实践中有着广泛的应用,不仅许多实际课题属于线性规划问题,而且运筹学中一些分支中的问题也可以转化为线性规划问题来计算,因此线性规划问题在最优化学科中占有重要的地位。建模是解决线性规划问题极为重要的环节。一个正确教学模型的建立要求建模者熟悉规划问题的具体实际内容。当面对文字长、数据多的应用题,要明确目标函数和约束条件有相当的难度。解决这个难点的关键是通过表格的形式把问题中的已知条件和各种数据进行整理分析,从而找出约束条件和目标函数,并从数学角度有条理地表述出来。单位生产成本的最大增值问题。某工厂在计划期内要生产三种A ,B ,C 产品,假定产品畅销,已知生产的固定成本为1 0000 元,即生产期内的固定资产损耗量。并且生产单位产品所需要的劳动力、设备台时、原材料、变动成本以及产值如表1 所示。厂方规定总生产成本不要超过1 3 0000元,问应如何安排生产才能使得成本产出率最大?

建立数学模型:

设工厂在计划期内生产A ,B ,C 三种产品的数量分别为x 1,x 2和x 3,显然成本产出率的表达式是:

线性规划

线性规划

且A 、B 、C 三种产品的数量受4 种资源量的限制:劳动力量的限制:15 x 1 + 2 0 x 2+3 0 x 3= 8 0 0 0 ( 2 )

设备台时的限制:2 0 x 1+ 10 x 2+2 5 x 3:1 2 0 0 0 ( 3 )

原材料的限制:3 0 x 1+4 0 x 2 + 4 5 x 3= 15 0 0 0 ( 4 )

变动成本的限制:2 6 0 x 1+ 2 8 0 x 2+3 8 5 x 3 = 1 2 0 0 0 0 ( 5 ) 此外A,B,C 三种产品的产量不能为负数,即x 1,x 2,x 3≥0。综上所述,本文的问题就是在条件( 2 ) 至(5 ) 以及未知数非负的限制条件下求使得( 1 ) 最大的解,( 1 ) 式称为目标函数。(2 ) 至(5 ) 式称为约束条件,和工业资源配置问题一样的还有农业生产计划安排问题,商业流动资金的分配问题以及食谱问题等,这些问题经数学抽象后,均可建立起线性规划模型。线性规划在经济生活中运用的意义随着经济全球化的不断发展,企业面临更加激烈的市场竞争。企业必须不断提高盈利水平,增强其获利能力,在生产、销售、新产品研发等~系列过程中只有自己的优势,提高企业效率,降低成本,形成企业的核心竞争力,才能在激烈的竞争中立于不败之地。过去很多企业在生产、运输、市场营销方面没有利用线性规划进行合理的配置,从而增加了企业的生产,使企业的利润不能达到最大化。在竞争日益激烈的今天,如果还按照过去的方式是难以生存的,所以就有必要利用线性规划的知识对战略计划、生产、销售各个环节进行优化从而降低生产成本,提高企业的效率。

在各类经济活动中,经常遇到这样的问题:在生产条件不变的情况下,如何通过统筹安排,改进生产组织或计划,合理安排人力、物力资源,组织生产过程,使总的经济效益最好。这样的问题常常可以化成或近似地化成所谓的“线性规划”问题。线性规划是应用分析、量化的方法,对经济管理系统中的人、财、物等有限资源进行统筹安排,为决策者提供有依据的最优方案,以实现有效管理。利用线性规划我们可以解决很多问题。如在不违反一定资源限制下,组织安排

生产,获得最好的经济效益(产量最多、利润最大、效用最高)。也可以在满足一定需求条件下,进行合理配置,使成本最小。同时还可以在任务或目标确定后,统筹兼顾,合理安排,用最少的资源(资金、设备、原材料、人工、时间等)去完成任务。

把线性规划的知识运用到企业中去,可以使企业适应市场激烈的竞争,及时、准确、科学的制定生产计划、投资计划、对资源进行合理配置。过去企业在制定计划,调整分配方面很困难,既要考虑生产成本,又要考虑获利水平,人工测算需要很长时间,不易做到机动灵活,运用线性规划并配合计算机进行测算非常简便易行,很快就可以得到最优案,提高企业决策的科学性和可靠性。其决策理论是建立在严格的理论基础之上,运用大量基础数据,经严格的数学运算得到的,能使企业在生产的各个环节中优化配置资源,提高了企业的效率,对企业大有益处。