关于数学规划介绍

[拼音]：shuxue guihua

[外文]：mathematical programming

研究在变量尣＝(x1，x2，…，xn)受到某些条件约束之下，如何寻求一尣，使得某一个（或几个）给定的函数在尣处取极小（或极大）值的一门学科。用 D表示满足所给定的条件的x的全体，则数学规划的主要内容就是要对某函数ƒ(尣)寻求一尣∈D，使得对于所有的尣∈D，都有ƒ(尣)≤ƒ(尣)(或≥ƒ(尣))，ƒ(尣)称为问题的目标函数，D称为约束集，属于D 的尣称为问题的可行解，尣称为问题的一个最优解，也称为总体最优解。若存在尣0∈D的一个邻域U(尣0)，使得对于U(尣0)∩D中之尣，都有ƒ(尣)≤ƒ(尣0)，则称尣0为问题的一个局部最优解。若D＝Rn，即n维欧氏空间，则上述规划称为无约束规划，否则称为带约束规划。

在生产实际中，有大量的问题都可化为数学规划问题来处理。例如，关于物资运输的组织，在一定要求之下厂房建筑的最优结构、厂址的选择、水利资源的分析（诸如水力发电与农业用水之间的平衡、城区用水的分配）等等。根据问题的性质以及处理方法的不同，数学规划分成许多不同的分支：

（1）线性规划，即D可以用(x1，x2，…，xn)的一些线性(不)等式表出，ƒ(x)为(x1，x2，…，xn)的线性函数的规划。

（2）非线性规划，即在表示D 的诸函数和目标函数ƒ(尣)中出现非线性函数的规划。

（3）整数规划，即规定部分（或全体）变量只能取某些整数值的规划。

（4）组合规划，或称组合最优化，即利用组合方法在一有限的集合中寻求一元素使所给定的目标达到最优的规划。

（5）参数规划，即在表示D的诸函数或目标函数中含有某些参数的规划。

（6）随机规划，即某些变量和(或)系数是随机变量的规划。

（7）动态规划，这是从事处理多阶段决策过程的一种方法。

（8）多目标规划，即ƒ(x)是一个向量函数的规划。除上述情形外，还有几何规划，分数规划，半无限规划，模糊规划，等等。

数学规划中最简单、最基本、应用最广的一个形式是线性规划。它可以表示如下：

求在条件i=1，2，…，m，xj≥0，j=1，2，…，n之下的极小值。许许多多的实际问题皆可化成线性规划来求解。例如一大类的运输问题可以表成求在条件，之下的极小值。一大类的任务分配问题可以化成求在条件或1之下的极小值。

有些实际问题，如水源管理，要把它们形成数学规划问题，必须经过对具体情况作仔细调查和反复推敲，然后才能定出有关的变量、约束条件和目标函数。同时，由于规划问题本身所考虑的是未来的活动安排，可能有一些因素是不确定的，有些数据是通过估计得到的不一定确切，有些因素可能是未曾预料到的。这也是参数规划、随机规划引起人们注意的原因之一。

将数学方法用于生产的组织和规划的思想，在19世纪或更早的时期就已萌生。如在17世纪P.de费马提出如下问题：求一点使其到三个给定点的距离之和为最小。这可视为厂址选点问题的一个雏形。然而，首先认识到某些重要的大量存在的生产安排问题均具有某种共同的明确的数学结构，且可以用数学方法去处理，应归之于Л.Β.坎托罗维奇。他的工作出现时很少为人注意，因而没有得到发展。1947年，G.B.丹齐克作出了解决线性规划问题的单纯形法。同时，人们发现，大量的生产问题都可化成线性规划问题来解决，从而引起人们的普遍重视。由于线性规划的影响，生产实际中许多与最优决策有关的问题提了出来，其中不少问题却不能用线性规划方法来处理，因此产生了上述的各种分支。可以认为它们都是线性规划在某种意义下的推广。

国际数学规划协会于1970年成立，每三年召开一次国际性讨论会。从1982年开始，每次会上颁发两项奖金：一为富尔克森奖（组合数学），一为丹齐克奖（数学规划）。

参考书目

1. A.Bachem，ed.，MatheMatical Programming，The State of the Art，Springer-Verlag，Berlin，1983.