English

运筹学学报

• 运筹学 • 上一篇    下一篇

圆形区域分散布局问题研究

余善恩1,*  徐文洋2   刘光宇1   

  1. 1. 杭州电子科技大学自动化学院, 杭州 310018; 2. 杭州电子科技大学理学院, 杭州 310018
  • 收稿日期:2015-09-14 出版日期:2018-09-15 发布日期:2018-09-15
  • 通讯作者: 余善恩 E-mail: nwcd@163.com
  • 基金资助:

    国家自然科学基金(No. 11201121), 河南省科技厅基础前沿基金(No.162300410221)

Researching of the scattered layout problem in circular zone

YU Shanen1,*   XU Wenyang2  LIU Guangyu1   

  1. 1. School of Automation, Hangzhou Dianzi University,  Hangzhou 310018, China; 2. School of Science, Hangzhou Dianzi University,  Hangzhou 310018, China  
  • Received:2015-09-14 Online:2018-09-15 Published:2018-09-15

PDF

160

摘要：

针对圆形区域分散布局问题, 文中给出了一个带约束的非线性规划模型. 当布局点数量较少时, 通过将模型转化为无约束优化问题, 利用梯度方法进行求解; 对于布局点数量较多的情况, 提出了一个界为1/2的多项式时间的近似算法, 并进行了相应的算例分析, 进一步来验证算法解的合理性. 研究的结论及方法一定程度上丰富和完善了圆形区域的分散布局理论.

关键词: 圆形区域, 分散布局, 规划模型, 近似算法

Abstract:

In this paper, we studied the scattered layout problem in a circular zone by establishing a non-linear mathematical programming model, which can be solved by gradient method after transformed into the maximum value search for a no-constrained optimization problem when the number of layout points is less. However, the gradient method will become extremely inefficient or even can not work if the layout points are many. In order to solve this problem we proposed an approximation algorithm with the bound of 1/2 for fast solution, And several cases are given to verify the rationality and performance of the approximate algorithm at last. In a sense, the conclusions and approximation algorithm of this article enrich and improve the theories of the scattered layout problem.

Key words: circular zone, scattered layout, programming model, approximate algorithm