论文部分内容阅读
对于一种大中规模的线性规划问题,当约束条件结构具有方块角形的形式时,为了减少计算量的内存容量等,常可采用系统分解原理来进行求解。但泽格和华尔夫(1960)提出的以对偶理论为基础的分解——对偶法,以及其后班台尔(1962)的推广已广泛应用。但其算法式都比较复杂,概念亦不很直观。本文提出一种以线性规划问题约束凸集的基本特性,和耦合约束对解的影响的基本法则为出发点的另一计算分解问题的途径,即:“最小减优率法”。后者是目标函数对各子问题约束的相对增减量(偏导数值)。利用此最小减优率(Least Reduction Race)的概念,就可直接从子问题的解推求有耦合约束时的线性规划问题的最优解。其迭代求解的步骤往往较少,概念亦较为直观。从文中所附算例可以看出它与分解——对耦法的明显差别。此法还同样可解其他一些特定结构的可分解大型线性规划问题。
For a large and medium-scale linear programming problem, when the constraint structure has the form of a square, in order to reduce the amount of computational memory, etc., the system decomposition principle can often be used to solve. However, the decomposition-duality method based on duality theory proposed by Zeegg and Waldorf (1960) and the subsequent promotion of Banel (1962) have been widely used. However, the algorithm is more complex and the concept is not very intuitive. In this paper, we propose another approach to the decomposition of the problem, which is the basic characteristics of the linear programming problem constrained convex set and the influence of the coupling constraint on the solution, ie, the “minimum reduction rate method”. The latter is the relative increase/decrease (bias derivative) of the objective function for each subproblem constraint. Using the concept of Least Reduction Race, the optimal solution of the linear programming problem with coupled constraints can be derived directly from the solution of the subproblem. The iterative solution steps are often fewer and the concepts are more intuitive. From the examples attached in the article, it can be seen that it is significantly different from the decomposition-coupling method. This method can also solve other specific structures of large-scale linear programming problems.