数学规划是现代应用数学的一个重要分支。 数学规划问题实际上都是在满足某些约束条件的情况下求函数极值的问题。一个数学规划问题通常包含以下要素:
根据目标函数和约束条件的特征,数学规划问题通常包含线性规划,二次规划,整数规划,非线性规划等类型。
线性规划问题的目标函数是线性函数,所有的约束条件又都是线性约束条件。线性规划问题可以用如下形式表达:
上式中fTx为目标函数,Ax=b为等式约束条件,Cxd为不等式约束条件,l和u分别为x的下限和上限。上下限约束条件实际上可以归到不等式约束条件里,但由于上下限约束条件比一般 的不等式约束条件较容易处理,而且非常普遍,所以我们通常将它们单独列出。当然并不是所有的线性规划问题都包含各类约束条件, 很多线性规划问题仅有等式约束条件或不等式约束条件。
二次规划问题的目标函数为二次函数,而约束条件则均为线性约束条件。二次归化问题可以用如下形式表达:
上式中Q为一对称矩阵。如果Q是一个对称半正定矩阵,则上式中的目标函数是一个凸函数。目标函数为凸函数的 二次规划问题,如果其可行域非空的话,则它的任何一个局域最优解都是全局最优解。该类问题也是二次规划中应用较为广泛的 一类。
整数规划问题要求部分或全部决策变量是整数。在大多数情况下,如果没有特别指出,整数规划指的是线性整数规划,即目标函数 是线性函数,除整数约束条件之外的其他约束条件均为线性约束条件。整数规划中的一个特例要求全部或部分决策变量为0或1。 该类问题是Karp的21类NP-complete问题之一。