什么是大型规划?

[拼音]：daxing guihua

[外文]：large scale mathematical programming

包括大型线性规划和大型非线性规划。数学规划得到广泛应用的主要原因是存在求解大型问题的有效的计算机程序。求解大型问题的关键是利用问题的特殊结构。大型线性规划问题的约束矩阵一般都十分稀疏（即大多数元素是零），且非零元素按一定次序排列，例如，除少数的行和列外，均沿主对角线排列。大型非线性规划一般也是稀疏结构，且线性项的比例很高，非线性项也有特殊结构，如可分结构等。

求解大型线性规划问题的方法可分为两类：直接法和分解法。直接法是用一个现存的算法来求解一类特定的问题。大型线性规划问题多采用直接法求解，基本工具是改进单纯形法，主要计算问题是求逆程序。在特殊的矩阵结构下只需要存储一个约化矩阵。实用计算机程序能有效地求解 8000～16000行的大型线性规划问题。若模型具有广义上界结构，可用广义上界算法GUB求解规模更大的问题。

分解法又称分块法，它的主导思想是把原系统分成若干独立的子系统求解，再用适当的方法来考虑各子系统之间的影响。1970年美国数学家M.D.梅萨罗维茨提出分解－协调算法。这种算法的设计思想来自大系统的多级递阶控制结构。首先把原问题分解成若干相对独立的子问题，称为一级子问题，分别求解，然后再用适当的方法定义一个或若干个二级子问题，来协调一级子问题之间的相互影响，以得到原问题的解。60年代中期曾广泛流行过的丹齐克－沃尔夫分解算法，现在只有少量商业上的应用。其主要原因是这种算法在计算上存在不稳定性和计算机程序的复杂性。

求解大型非线性规划的方法有两类：可分规划和近似规划。可分规划的特点是任一非线性函数都是可分的，即

。

因此每个非线性函数可按格点集上的点分段线性化，从而把非线性可分规划变成线性规划。可分规划对于大部分是线性函数并具有凸可分非线性函数的问题是一种有效的算法，其实用计算机程序可求解数千行数千列的大型非线性规划问题。

近似规划是利用线性规划程序作为子程序来处理一般形式的非线性函数。设大型非线性规划问题是：

式中min表示求极小值,s.t.表示约束条件；xj为线性变量，y为非线性变量的m维向量，gi为非线性函数。所有变量均有上界和下界。给定初始基点向量y0，每个函数gi都近似地是这个点的线性化函数：

式中Δy =y-y0，而墷gi是gi的梯度向量。用此线性化函数代替每个gi，就把原问题约化为线性规划问题。规定Δy的上界和下界，即－ε≤Δy≤ε，求解此线性规划，得到Δy*，把它加到y0上得到新的基点,计算对应的梯度向量墷gi，必要时可减小ε,然后重复上述过程。现在已有近似规划的通用程序和专用程序。

利用线性规划基变量的树结构，可用单纯形法求解有数十万个节点或弧的网络问题。其解法比最有效的网络算法更快。