[拼音]：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，必要时可减小ε,然后重复上述过程。现在已有近似规划的通用程序和专用程序。

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

严正声明：本文由历史百科网注册或游客用户任依林自行上传发布关于» 大型规划的内容，本站只提供存储，展示，不对用户发布信息内容的原创度和真实性等负责。请读者自行斟酌。同时如内容侵犯您的版权或其他权益，请留言并加以说明。站长审查之后若情况属实会及时为您删除。同时遵循 CC 4.0 BY-SA 版权协议，尊重和保护作者的劳动成果，转载请标明出处链接和本声明内容：作者：任依林；本文链接：https://www.freedefine.cn/wenzhan/55226.html