线性规划在企业决策中的应用

《线性规划在企业决策中的应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、页眉线性规划在企业决策中的应用第一章线性规划理论1.线性规划简介线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法.在经济管理、交通运输、工农业生产等经济活动中，提高经济效果是人们不可缺少的要求，而提高经济效果一般通过两种途径：一是技术方面的改进，例如改善生产工艺，使用新设备和新型原材料.二是生产组织与计划的改进，即合理安排人力物力资源.线性规划所研究的是：在一定条件下，合理安排人力物力等资源，使经济效果达到最好.一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题[1]。满足线性约束条件的解

2、叫做可行解，由所有可行解组成的集合叫做可行域[2]。决策变量、约束条件、目标函数是线性规划的三要素。2.线性规划的发展历程法国数学家J.-B.-J.傅里叶和C.瓦莱－普森分别于1832和1911年独立地提出线性规划的想法，但未引起注意。　　1939年苏联数学家Л.В.康托罗维奇在《生产组织与计划中的数学方法》一书中提出线性规划问题，也未引起重视。　　1947年美国数学家G.B.丹齐克提出线性规划的一般数学模型和求解线性规划问题的通用方法──单纯形法，为这门学科奠定了基础。　　1947年美国数学家J.von诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域，扩大了它的应用范围和解题

3、能力。　　1951年美国经济学家T.C.库普曼斯把线性规划应用到经济领域，为此与康托罗维奇一起获1975年诺贝尔经济学奖。　　50年代后对线性规划进行大量的理论研究，并涌现出一大批新的算法。例如，195428页眉年C.莱姆基提出对偶单纯形法，1954年S.加斯和T.萨迪等人解决了线性规划的灵敏度分析和参数规划问题，1956年A.塔克提出互补松弛定理，1960年G.B.丹齐克和P.沃尔夫提出分解算法等。　　线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究。由于数字电子计算机的发展，出现了许多线性规划软件，如MPSX，OPHEIE，UMPIRE

4、等，可以很方便地求解几千个变量的线性规划问题[3]。　　1979年苏联数学家L.G.Khachian提出解线性规划问题的椭球算法，并证明它是多项式时间算法。　　1984年美国贝尔电话实验室的印度数学家N.卡马卡提出解线性规划问题的新的多项式时间算法。用这种方法求解线性规划问题在变量个数为5000时只要单纯形法所用时间的1/50。现已形成线性规划多项式算法理论。50年代后线性规划的应用范围不断扩大。建立线性规划模型的方法。3.线性规划的数学模型及其标准形式3.1线性规划问题的提出在生产管理和经营活动中经常提出一类问题，即如何合理地利用有限的人力、物力、财力等资源，以便得到最好的经济效

5、果。线性规划主要解决两类问题：（1）资源有限，要求生产的产品（或利润）最多。（2）任务（或产品）一定，要求消耗的资源（或成本）最少。3.2线性规划问题的特征（1）每一个问题都用一组决策变量表示某一方案；这组决策变量的值就有代表一过具体方案。（2）一般这些变量取值是非负的。（3）存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。（4）都有一个要求达到的目标，它可用决策变量的线性函数（称为目标函数）来表示。按问题的不同，要求目标函数实现最大化或最小化。满足以上四个条件的数学模型称为线性规划的数学模型。3.3从实际问题中建立数学模型的步骤；28页眉（1）根据影响所要达

6、到目的的因素找到决策变量；（2）由决策变量和所在达到目的之间的函数关系确定目标函数；（3）由决策变量所受的限制条件确定决策变量所要满足的约束条件。3.4所建立的线性规划模型的特点；（1）每个模型都有若干个决策变量，其中为决策变量个数。决策变量的一组值表示一种方案，同时决策变量一般是非负的。（2）目标函数是决策变量的线性函数，根据具体问题可以是最大化或最小化，二者统称为最优化[3]。（3）约束条件也是决策变量的线性函数。3.5线性规划模型的一般形式目标函数：(1-1)约束条件：(1-2)在线性规划的数学模型中，方程（3-1）称为目标函数；（3-2）称为约束条件。3.6线性规划模型的标

7、准形式(1-3)(1-4)其中.简写形式为：(1-5)28页眉(1-6)向量和矩阵表示：(1-7)(1-8)其中，4.线性规划的解法求解线性规划问题的基本方法有图解法和单纯形法，但实际运用的主要是是单纯形法，现在已有单纯形法的标准软件，可在电子计算机上求解约束条件和决策变量数达10000个以上的线性规划问题。为了提高解题速度，又有改进单纯形法、对偶单纯形法、原始对偶方法、分解算法和各种多项式时间算法。对于只有两个变量的简单的线性规划问题，也可采用图解法求解。这种方法仅