大系统分解线性规划的最小减优率法

对于一种大中规模的线性规划问题,当约束条件结构具有方块角形的形式时,为了减少计算量的内存容量等,常可采用系统分解原理来进行求解。但泽格和华尔夫(1960)提出的以对偶理论为基础的分解——对偶法,以及其后班台尔(1962)的推广已广泛应用。但其算法式都比较复杂,概念亦不很直观。本文提出一种以线性规划问题约束凸集的基本特性,和耦合约束对解的影响的基本法则为出发点的另一计算分解问题的途径,即:“最小减优率法”。后者是目标函数对各子问题约束的相对增减量(偏导数值)。利用此最小减优率(Least Reduction Race)的概念,就可直接从子问题的解推求有耦合约束时的线性规划问题的最优解。其迭代求解的步骤往往较少,概念亦较为直观。从文中所附算例可以看出它与分解——对耦法的明显差别。此法还同样可解其他一些特定结构的可分解大型线性规划问题。