线性规划模型的应用与灵敏度分析

第一章 线性规划问题

1. 线性规划及灵敏度分析简介

线性规划(Linear Programming)问题, 简称LP问题,是运筹学中最基本, 也是最重要的内容, 被广泛地应用于军事决策、企业管理、工程设计、交通运输等领域. 特别是经济领域应用更为广泛, 有资料称, 在对500家有相当效益的公司所作的评述中, 有85%的公司都曾应用了线性规划。

灵敏度分析对于决策者的重要性不言而喻，在真实世界里，周围的环境、条件是在不断变化的。

2. 线性规划模型应用的发展

线性规划及其通用解法——单纯形法是由美国G.B.Dantzig在1947年研究空军军事规划提出来的。法国数学家傅里叶和瓦莱－普森分别于1832和1911年独立地提出线性规划的想法，但未引起注意。1939年苏联数学家康托罗维奇在《生产组织与计划中的数学方法》一书中提出线性规划问题，也未引起重视[1]。

1947年美国数学家丹齐克提出线性规划的一般数学模型和求解线性规划问题的通用方法──单纯形法，为这门学科奠定了基础。1947年美国数学家诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域，扩大了它的应用范围和解题能力[2]。

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

1984年美国贝尔电话实验室的印度数学家N.卡马卡提出解线性规划问题的新的多