[科普中国]-规划论

简介

规划论又称“数学规划”。运筹学的一个分支。研究在所给定的条件下，如何按某一衡量指标来寻求计划管理工作中的最优方案。通常称必须满足的条件为“约束条件”，衡量指标为“目标函数”。包括线性规划、非线性规划、整数规划、动态规划、组合规划、随机规划、多目标规划等。在经济管理、工程设计和过程控制等方面有广泛应用。

如今，最简单的规划论技巧即线性规划已被列入高中数学教材，其实教材当中也包括了部分非线性规划的因素，教会学生用直观的方法给出问题的最优解。这种思想在物理学里也经常用到，在那里常被称为“图解法”。这种思想重在分析，通过分析来减少运算量，较列出函数关系求极值的方法要更高明，是一种很有用的思想。

线性规划起源研究线性规划最早的是苏联的康脱洛维奇，1939年，他发表了《生产组织与计划中的数学方法》一书。主要讨论了机床、负荷、下料运输等问题。但他提出的问题在当时并未引起人们的注意。他自己也未能提出一个统一的求解方法。在第二次世界大战期间，由于军事运输的需要，提出线性问题的解法，美国的经济学家柯普曼（Koupman）也研究了运输问题。直到1947年，美国的G.B.Dantzig提出了求解线性规划的单纯形法，才使线性规划这门学科在理论上趋于成熟，并成功地运用到了工业、交通、农业、军事等各个领域内，使线性规划的理论与方法成为管理科学的重要内容。在当今电子技术高度发展的信息社会中，线性规划给人类在经济管理、生产管理、人才事务管理等方面发挥了巨大作用。现在对于成千上万个约束条件、成千上万个变量的线性规划问题在计算上已没有任何问题。据20世纪80年代末美国一个杂志对全美500家大公司的调查，线性规划的应用范围名列前茅，有85%的公司频繁使用线性规划。

基础理论线性规划问题是在一组线性约束条件的限制下，求一线性目标函数最大或最小的问题。 在解决实际问题时，把问题归结成一个线性规划数学模型是很重要的一步，但往往 也是困难的一步，模型建立得是否恰当，直接影响到求解。而选适当的决策变量，是我 们建立有效模型的关键之一。 建立数学模型的步骤：

（1）分析实际问题；（2）确定决策变量；（3）找出约束条件；（4）确定目标函数；（5）整理写出数学模型。

应用线性规划主要应用在以下几个方面：

（1）在某一企业内部，如何配合产品的销售时间，在各部门的原料，产品的存储，分配的数量等最为合理。

（2）在某一企业生产的产品数量（或产值），如何使现有的设备，人力，原料等条件限制下，合理组织生产，使经济效益最高。

（3）在某地的交通网中，如何合理组织运输，使运费最小。

（4）在市场上产品的（或原料）价格变动时，对于这些变动，企业如何做出最优决策。

（5）合理下料问题，即利用某种原料下料时，如何达到既满足要求，又使原料最少。

（6）配料问题，即生产由各种原料生产的的产品时（如混合饲料等）时，如何既满足规定的质量的标准，又使产品的成本最低。

（7）库存问题，在仓库的容量及其他条件的限制下，确定库存物资的品种，数量，期限，使库存的效益最高。

（8）在投入产出问题中，引进某一目标函数，制定最优的企业（或地区）经济计划。

非线性规划起源非线性规划是具有非线性约束条件或目标函数的数学规划，是运筹学的一个重要分支。非线性规划是20世纪50年代才开始形成的一门新兴学科。70年代又得到进一步的发展。非线性规划在工程、管理、经济、科研、军事等方面都有广泛的应用，为最优设计提供了有力的工具。非线性规划研究一个 n元实函数在一组等式或不等式的约束条件下的极值问题，且目标函数和约束条件至少有一个是未知量的非线性函数。

非线性规划是20世纪50年代才开始形成的一门新兴学科。1951年H.W.库恩和A.W.塔克发表的关于最优性条件（后来称为库恩－塔克条件）的论文是非线性规划正式诞生的一个重要标志。在50年代还得出了可分离规划和二次规划的n种解法，它们大都是以G.B.丹齐克提出的解线性规划的单纯形法为基础的。50年代末到60年代末出现了许多解非线性规划问题的有效的算法，70年代又得到进一步的发展。非线性规划在工程、管理、经济、科研、军事等方面都有广泛的应用，为最优设计提供了有力的工具。20世纪80年代以来，随着计算机技术的快速发展，非线性规划方法取得了长足进步，在信赖域法、稀疏拟牛顿法、并行计算、内点法和有限存储法等领域取得了丰硕的成果。

算法对于一个实际问题，在把它归结成非线性规划问题时，一般要注意如下几点：

（i）确定供选方案：首先要收集同问题有关的资料和数据，在全面熟悉问题的基础上，确认什么是问题的可供选择的方案，并用一组变量来表示它们。

（ii）提出追求目标：经过资料分析，根据实际需要和可能，提出要追求极小化或极大化的目标。并且，运用各种科学和技术原理，把它表示成数学关系式。

（iii）给出价值标准：在提出要追求的目标之后，要确立所考虑目标的“好”或 “坏”的价值标准，并用某种数量形式来描述它。

（iv）寻求限制条件：由于所追求的目标一般都要在一定的条件下取得极小化或极大化效果，因此还需要寻找出问题的所有限制条件，这些条件通常用变量之间的一些不等式或等式来表示。

学科发展数学规划问题是指在一定约束条件下最大化或最小化某一目标函数的问题，其变量可能是连续或离散的．研究这类问题的数学性质、求解算法和具体实现以及应用这些算法解决实际问题的学科统称为数学规划。数学规划的一个“近似”或通俗的名字是“最优化”。

数学规划问题求解“最优”的特征决定了其应用的广泛性。早在18世纪，著名数学家欧拉就曾说：宇宙万物无不与最小化或最大化的原理有关系。经济社会中，在有限的资源下求解最优的计划、路线、组合和策略等问题都可以归结为数学规划问题。数学规划的应用遍及工程、经济、金融、管理、医药和军事等领域。可以说，数学规划的原理渗入到社会发展的各个方面，甚至在我们的日常生活里也有各种各样的最优化问题。

在学科分类上，一般把数学规划看成是运筹学的一个分支，是运筹学的基础学科。在管理科学中，数学规划是最常用的建模方法和工具，与统计和模拟仿真一起组成三大基本方法和技术。由于数学规划与数学理论的天然联系，也可以把数学规划看成是应用数学的一个分支。在国际上，数学规划的研究活动分布在运筹学、管理科学、应用数学、计算机科学和电子工程等领域。在一些国际大型学术组织中，如美国运筹与管理科学学会(INFORMS)、国际运筹学会联合会(IFORS)、欧洲运筹学会(EURO)、美国工业与应用数学联盟(SIAM)和美国计算机科学学会(ACM)等，数学规划都是非常活跃的研究方向和分支1。