良性隐式枚举与近隐式枚举

聂义勇, 宋翔, 苏丽杰, 于军, 苑明哲

聂义勇, 宋翔, 苏丽杰, 于军, 苑明哲. 良性隐式枚举与近隐式枚举[J]. 信息与控制, 2005, 34(3): 296-302.
引用本文: 聂义勇, 宋翔, 苏丽杰, 于军, 苑明哲. 良性隐式枚举与近隐式枚举[J]. 信息与控制, 2005, 34(3): 296-302.
NIE Yi-yong, SONG Xiang, SU Li-jie, YU Jun, YUAN Ming-zhe. Well-implied and Near-implicit Enumerations[J]. INFORMATION AND CONTROL, 2005, 34(3): 296-302.
Citation: NIE Yi-yong, SONG Xiang, SU Li-jie, YU Jun, YUAN Ming-zhe. Well-implied and Near-implicit Enumerations[J]. INFORMATION AND CONTROL, 2005, 34(3): 296-302.

良性隐式枚举与近隐式枚举

详细信息
    作者简介:

    聂义勇(1939- ),男,研究员,博士生导师.研究领域为应用数学及计算机辅助工程.
    宋翔(1976- ),女,博士.研究领域为应用数学及计算机辅助工程.
    苏丽杰(1974- ),女,博士研究生.研究领域为应用数学及计算机辅助工程.

  • 中图分类号: TP301

Well-implied and Near-implicit Enumerations

  • 摘要: 对数学规划中的枚举法进行了有效的分类:良性隐式枚举与病态隐式枚举.考察这两类隐式枚举的本质差别.给出良性隐式枚举的判别条件.根据不完全枚举的概率收敛性,提出近隐式枚举的概念.例举了几种典型的良性隐式枚举法和近隐式枚举法.文末指出良性隐式枚举及近隐式枚举的发展方向.
    Abstract: In this paper, the implicit enumeration methods for mathematical programming are effectively classified: well-implied and ill-imp lied enumerations. Essential difference between the two kinds of implicit enumeration methods is investigated. The judgment on well-implied enumeration method is given. According to probabilistic convergence of incomplete enumeration, the concept of near-implicit enumeration is proposed. Several typical well-implied enumeration methods and near-implicit enumeration methods are illustrated. In the end, the trend of developing well-implied and near-implicit enumerations is concluded.
  • [1] 卢开澄.组合数学(第2版)[M].北京:清华大学出版社,1999.
    [2] 聂义勇,贵刚,宋翔.整数规划基础[M].沈阳:东北大学出版社,2001.
    [3] 马仲蕃.线性整数规划的数学基础[M].北京:科学出版社,1998
    [4] Smale S. On the average number of step of the simplex method of linear programming [J]. Mathematical Programming, 1983,27(3):241~262.
    [5] Karmarkar N. A new polynomial-time algorithm for linear programming [J]. Combinatorics, 1984,4: 373~395.
    [6] 马仲蕃.线性规划最新进展[M].北京:科学出版社,1994.
    [7] Nie Y Y, Xu S R. An isometric plane method for linear programming [J]. Journal of Computational Mathematics, 1991,9 (3):262~272.
    [8] Nie Y Y, Su L J, Li C. An isometric surface method for integer linear programming [J]. International Journal of Computer Mathematics, 2003,80(7):835~844.
    [9] Chvatal V. Edmonds polytopes and weakly Hamilton graphs [J].Mathematical Programming, 1973,5 (1):29~40.
    [10] Dantzig G B, Fulkerson R, Johnson S M. Solution for a largescale traveling salesman problem [J]. Operations Research,1954,2: 393~410.
    [11] 张文修,梁怡.遗传算法的数学基础(第2版)[M].西安:西安交通大学出版社,2003.
    [12] 宋翔,聂义勇,储诚斌.无限制背包问题的爬山算法[J].小型微型计算机系统,2004,25(7):1352~1355.
    [13] Balas E, Zemel E. An algorithm for large zero-one knapsack problems [J]. Operations Research, 1980,28 (3): 1130~1154.
    [14] Chvatal V. Hard knapsack problems [J]. Operations Research,1980, 28(6):1402~1411.
    [15] Nie Y Y, Song X, Gui G. Incompletely enumerative solution for 1 D cutting-stock problem [J]. Far East Journal of Mathematical Sciences (FJMS), 2002, 5 (1):25~46.
    [16] Nie Y Y, Yu J, Song X. Incompletely enumerative solution for 1D cutting-stock problem Ⅱ [J]. Far East Journal of Mathematical Sciences (FJMS), 2004, 12(1):53~64.
计量
  • 文章访问数:  1393
  • HTML全文浏览量:  0
  • PDF下载量:  171
  • 被引次数: 0
出版历程
  • 收稿日期:  2005-03-29
  • 发布日期:  2005-06-19

目录

    /

    返回文章
    返回
    x