词条 | 大型规划 |
释义 | daxing guihua 大型规划(卷名:自动控制与系统工程) large scale mathematical programming 包括大型线性规划和大型非线性规划。数学规划得到广泛应用的主要原因是存在求解大型问题的有效的计算机程序。求解大型问题的关键是利用问题的特殊结构。大型线性规划问题的约束矩阵一般都十分稀疏(即大多数元素是零),且非零元素按一定次序排列,例如,除少数的行和列外,均沿主对角线排列。大型非线性规划一般也是稀疏结构,且线性项的比例很高,非线性项也有特殊结构,如可分结构等。 大型线性规划 求解大型线性规划问题的方法可分为两类:直接法和分解法。直接法是用一个现存的算法来求解一类特定的问题。大型线性规划问题多采用直接法求解,基本工具是改进单纯形法,主要计算问题是求逆程序。在特殊的矩阵结构下只需要存储一个约化矩阵。实用计算机程序能有效地求解 8000~16000行的大型线性规划问题。若模型具有广义上界结构,可用广义上界算法GUB求解规模更大的问题。 分解法又称分块法,它的主导思想是把原系统分成若干独立的子系统求解,再用适当的方法来考虑各子系统之间的影响。1970年美国数学家M.D.梅萨罗维茨提出分解-协调算法。这种算法的设计思想来自大系统的多级递阶控制结构。首先把原问题分解成若干相对独立的子问题,称为一级子问题,分别求解,然后再用适当的方法定义一个或若干个二级子问题,来协调一级子问题之间的相互影响,以得到原问题的解。60年代中期曾广泛流行过的丹齐克-沃尔夫分解算法,现在只有少量商业上的应用。其主要原因是这种算法在计算上存在不稳定性和计算机程序的复杂性。 大型非线性规划 求解大型非线性规划的方法有两类:可分规划和近似规划。可分规划的特点是任一非线性函数都是可分的,即 ![]() 近似规划是利用线性规划程序作为子程序来处理一般形式的非线性函数。设大型非线性规划问题是: ![]() ![]() 大型网络流问题 利用线性规划基变量的树结构,可用单纯形法求解有数十万个节点或弧的网络问题。其解法比最有效的网络算法更快。 |
随便看 |
百科全书收录78206条中英文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。