摘要
在本文中,我们通过一个实际问题归纳出一个数学模型(正文中的模型Ⅰ),并通过新变量的引用,韩模型Ⅰ转化成一个高维0-1瓶颈规划(正文中的模型Ⅱ).对模型Ⅱ,我们建立了求模型Ⅱ最优解的动态规划算法(带有阀值Q).该算法与普通动态规划相比大大节约了运算量.最后指出了该算法对0-1瓶颈问题的求解具有一定的普遍性.
In this paper, we present the following mathematical model Ⅰ ：
max f （X）
s.t.{∑ n j=1 xij=ai（i=1,2,…,m）
xij≥0 integer（i=1,2,…,m;j=1,2,…,n）
where X ={Xij},f（X）=min1≤j≤n{∑ m i=1xijxij},aiand cij are known positive integers.
Model Ⅰ transform into the following model Ⅱ through quotation of new variables：
maxg（Y）
s.t.{∑ n j=1 yij=1（i=1,2,…,M;j=1,2,…,n）}
where Y = {yij}, g（Y）=min≤j≤n{∑ m i=1wijyij},M=∑ m i=1aiand wij are known positive
integers. Besides, the dynamic programming algorithm with a threshold Q is established for finding an optimal solution to model II. At last, we indicate the universality of this algorithm in finding higher-dimensional 0-1 bottleneck problems.
出处
《数值计算与计算机应用》
CSCD
2013年第1期38-46,共9页
Journal on Numerical Methods and Computer Applications
关键词
0-1瓶颈问题
动态规划
阀值
0-1 bottleneck problem
Dynamic Programming
Threshold
