1、4800汉字，2700单词，1.6万字符 2013 届 毕 业 生 外 文 文 献 翻 译 学 院 理学院 专 业 信息与计算科学 姓 名 李存正
2、; 学 号 200901120224 指导教师 卢福良 线性规划在企业决策中的应用 第一章 线性规划 理论 1. 线性规划简介 线性规划是 运筹学 中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支 ,它是辅助人们进行科学管理的一种数学方法 .在经济
3、管理、交通运输、工农业生产等经济活动中，提高经济效果是人们不可缺少的要求，而提高经济效果一般通过两种途径：一是技术方面的改进，例如改善生产工艺，使用新设备和新型原材料 .二是 生产组织 与计划的改进，即合理安排人力物力资源 .线性规划所研究的 是：在一定条件下，合理安排人力物力等资源，使经济效果达到最好 .一般地，求线性目标函数在线性 约束条件 下的最大值或最小值的问题，统称为线性规划问题 1。满足线性约束条件的解叫做 可行解 ，由所有可行解组成的集合叫做可行域 2。 决策变量 、约束条件、目标函数是线性规划的三要素。 2. 线性规划的发展历程 法国数学
4、家 J.- B.- J.傅里叶和 C.瓦莱普森分别于 1832 和 1911 年独立地提出线性规划的想法，但未引起注意。 1939 年苏联数学家 .康托罗维奇在生产组织与计划中的数学方法一书中提出线性规划问题，也未引起重视。 1947 年美国数学家 G.B.丹齐克提出线性规划的一般数学模型和求解线性 规划问题的通用方法 单纯形法，为这门学科奠定了基础。 1947 年美国数学家 J.von 诺伊曼提出对偶理论 ,开创了线性规划的许多新的研究领域，扩大了它的应用范围和解题能力。
5、 1951 年美国经济学家 T.C.库普曼斯把线性规划应用到经济领域，为此与康托罗维奇一起获 1975 年诺贝尔经济学奖。 50 年代后对线性规划进行大量的理论研究，并涌现出一大批新的算法。例如， 1954 年 C.莱姆基提出对偶单纯形法， 1954 年 S.加斯和 T.萨迪等人解决了线性规划的灵敏度分析和参数规划问题， 1956 年 A.塔克提出互补 松弛定理， 1960年 G.B.丹齐克和 P.沃尔夫提出分解算法等。 线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究。由于数字电子
6、计算机的发展，出现了许多线性规划软件，如 MPSX， OPHEIE， UMPIRE 等，可以很方便地求解几千个变量的线性规划问题 3。 1979 年苏联数学家 L. G. Khachian 提出解线性规划问题的椭球算法，并证明它是多项式时间算法。 1984 年美国贝尔电话实验室的 印度 数学家 N.卡马卡提出解线性规划问题的新的多项式时间算法。用这种方法求解线性规划问题在变量个数为 5000 时只要单纯形法所用时间的 1/50。现已形成线性规划多项式算法理论。 50 年代后线性规划的应用范围不断扩大。建立线性规划模型的方法。 3
7、. 线性规划的数学模型及其标准形式 3.1 线性规划问题的提出 在生产管理和经营活动中经常提出一类问题，即如何合理地利用有限的人力、物力、财力等资源，以便得到最好的经济效果。 线性规划主要解决两类问题： （ 1）资源有限，要求生产的产品（或利润）最多。 （ 2）任务（或产品）一定，要求消耗的资源（或成本）最少。 3.2 线性规划问题的特征 （ 1）每一个问题都用一组决策变量1 2 n (x ,x .x )表示某一方案；这组决策变量的值就有代表一过具体方案。 （ 2） 一般这些变量取值是非负的。 （ 3）存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。 （ 4）都有一个要求达到的目标，它可用决策变量的线性函数（称为目标函数）来表示。按问题的不同，要求目标函数实现最 大化或最小化。 满足以上四个条件的数学模型称为线性规划的数学模型。
