wsuAAA线性规划

线性规划概述 线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法.在经济管理、交通运输、工农业生产等经济活动中，提高经济效果是人们不可缺少

线性规划概述 线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重 要分支,它是辅助人们进行科学管理的一种数学方法.在经济管理、交通运输、工农 业生产等经济活动中，提高经济效果是人们不可缺少的要求，而提高经济效果一般 通过两种途径：一是技术方面的改进，例如改善生产工艺，使用新设备和新型原材 料.二是生产组织与计划的改进，即合理安排人力物力资源.线性规划所研究的是： 在一定条件下，合理安排人力物力等资源，使经济效果达到最好.一般地，求线性 目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题。满足 线性约束条件的解叫做可行解，由所有可行解组成的集合叫做可行域。决策变量、 约束条件、目标函数是线性规划的三要素. 线性规划的发展 法国数学家J.-B.-J.傅里叶和C.瓦莱－普森分别于1832和1911年独立 地提出线性规划的想法，但未引起注意。 1939年苏联数学家Л.В.康托罗维奇在《生产组织与计划中的数学方法》一 书中提出线性规划问题，也未引起重视。 1947年美国数学家G.B.丹齐克提出线性规划的一般数学模型和求解线性规划 问题的通用方法──单纯形法，为这门学科奠定了基础。 1947年美国数学家J.von诺伊曼提出对偶理论,开创了线性规划的许多新的 研究领域，扩大了它的应用范围和解题能力。 1951年美国经济学家T.C.库普曼斯把线性规划应用到经济领域，为此与康托 罗维奇一起获1975年诺贝尔经济学奖。 50年代后对线性规划进行大量的理论研究，并涌现出一大批新的算法。例 如，1954年C.莱姆基提出对偶单纯形法，1954年S.加斯和T.萨迪等人解决了线