数学规划概述


数学规划是现代应用数学的一个重要分支。 数学规划问题实际上都是在满足某些约束条件的情况下求函数极值的问题。一个数学规划问题通常包含以下要素:

  • 一组决策变量,变量的值就是要求解的对象;
  • 一个目标函数,就是我们希望通过改变决策变量而最大化或最小化的对象;
  • 一组约束条件,决策变量的取值必须满足这些约束条件。

通常满足所有约束条件的解被称做可行解,所有可行解的集合叫做可行域。

根据目标函数和约束条件的特征,数学规划问题通常包含线性规划,二次规划,整数规划,非线性规划等类型。

线性规划问题的目标函数是线性函数,所有的约束条件又都是线性约束条件。线性规划问题可以用如下形式表达:

线性规划

上式中fTx为目标函数,Ax=b为等式约束条件,Cxd为不等式约束条件, lu分别为x的下限和上限。上下限约束条件实际上可以归到不等式约束条件里,但由于上下限约束条件比一般 的不等式约束条件较容易处理,而且非常普遍,所以我们通常将它们单独列出。当然并不是所有的线性规划问题都包含各类约束条件, 很多线性规划问题仅有等式约束条件或不等式约束条件。

二次规划问题的目标函数为二次函数,而约束条件则均为线性约束条件。二次归化问题可以用如下形式表达:

二次规划

上式中Q为一对称矩阵。如果Q是一个对称半正定矩阵,则上式中的目标函数是一个凸函数。目标函数为凸函数的 二次规划问题,如果其可行域非空的话,则它的任何一个局域最优解都是全局最优解。该类问题也是二次规划中应用较为广泛的 一类。

整数规划问题要求部分或全部决策变量是整数。在大多数情况下,如果没有特别指出,整数规划指的是线性整数规划,即目标函数 是线性函数,除整数约束条件之外的其他约束条件均为线性约束条件。整数规划中的一个特例要求全部或部分决策变量为0或1。 该类问题是Karp的21类NP-complete问题之一。

喜欢我们的网站吗?
将本站加入收藏夹

或者和好友分享本站吧:
分享到QQ空间 分享到人人

对我们的网站有建议吗?
给我们来信吧。