| 一种新的椭球算法 |
| |
| 作者姓名： | 杨德庄 张敏洪 张利华 |
| |
| 作者单位： | 1. 中国科学技术大学研究生院 北京 100039;
2. 中国科学院自然科学史研究所 北京 100010 |
| |
| 摘 要： | 基于更动约束的思想与方法,提出了求解线性规划问题的新椭球算法.它与L.G.Khachian的椭球算法不同,在新算法的椭球迭代过程中,不仅用约束不等式割掉不含约束集的半个椭球 (椭球中心不在约束集内时 ),称之为约束割 ;而且在椭球中心落在约束集内时,它用目标不等式割掉含约束集的半个椭球,称之为目标割.新算法的不等式系统是由原规划 (或对偶规划 )的约束不等式与目标不等式组成的 (规模小 ),而不是由原椭球算法的K K T条件组成的不等式系统 (规模大 ).这种新椭球算法即有多项式计算复杂性的特性,又在迭代过程中得到一系列单调趋向最优解的可行解 (在解存在时 ).如果认为已得满意解,可随时停机.对于实际问题,大多数是变量有界的,初始椭球不大,因此新算法更为实际,有效.
|
| 关 键 词： | 椭球算法 约束割 目标割 |
| 收稿时间： | 2000-11-20 |
A New Ellipsoid Method |
| |
| Authors: | Yang Dezhuang Zhang Minhong Zhang Lihua |
| |
| Institution: | 1. Graduate School, University of Science and Technology of China, Beijing 100039;
2. Institute for the History of Natural Science, Chinese Academy of Sciences, Beijing 100010 |
| |
| Abstract: | Base on the mathematical idea and method to alter const raints of a problem, a new a-l gorithm for linear prog ramming to solve has been given. This method is different from the primary e-l lipsoid method by L. G. Khachian. The step-by-step procedure in the new method is not only cut t ing dow n the hal-f ellipsoid, that does not contain the const raint set by the constraint inequalit ies named the constraint funct ion cut, w hen the center of ellipsoid is not in the const raint set ; but also cut t ing dow n the hal-f ellipsoid that contain the constraint set by the object ive inequalit ies named the object ive funct ion cut w hen the center of this ellipsoid fall in the constraint set. The inequality set of this new algorithms consist of the const raint inequalit ies of primary prog ram ( or dual prog ram) and object ive inequality, w hich is small in scale, and does not resemble to consist of K-K-T opt imality conditions for the primary ellipsoid method inequalit ies set w hich is large in scale. T his new ellipsoid algorithm not only has characterist ic of poly nomial complex ity, but also can get a series of monotone feasible solut ions to approach the optimal solut ion if this solut ion exist. If we think to g et a sat isfied solut ion, w e can terminate the iterative scheme at any t ime. So the new method is more practical and effect ive than the primary method. Because the variables and bounded, and the initial ellipsoid is not big in the vast majority of pract ical problems, the new algorithms is more feasible. |
| |
| Keywords: | ellipsoid method const raint function cut object ive funct ion cut |
|
| 点击此处可从《》浏览原始摘要信息 |
| 点击此处可从《》下载免费的PDF全文 |
|
