2024年第五届“华数杯”全国大学生数学建模竞赛B赛题解析

见贤思齐

本次华数杯B题第一问是根据附件1提供的信息，设计一个与电路单元连线接口坐标相关的线长评估模型，使估计线长尽可能与对应的RSMT线长相近，并可应用于评估附件1中的总连接线长。假设附件1中的每条连线接口都有两个端点，电路单元的长和宽分别为和W这样计算出来的线长与RSMT线长差值就比较小，也比较容易计算。第二个问题：根据问题1构建的线长评估模型，结合附件1和附件2提供的信息，建立数学模型，目标为最小化总连接线长，并满足单元密度约束。请仅仅回答第二个问题，并提供详细LaTeX数学公式：根据题目的要求，应该在设计的时候同时满足两个目标，即最小化总连接线长和满足单元密度约束。因此，我们可以通过加入一个惩罚项来实现对单元密度的约束。根据题目中给出的信息，我们可以知道，单元密度的计算公式为：importnumpyasnpimportmatplotlib.pyplotasplt#导入数据data1=np.loadtxt("附件1.txt",dtype=str,delimiter=",",skiprows=1)data2=np.loadtxt("附件2.txt",dtype=int,delimiter=",",skiprows=1)#将数据转换为字典形式dic1={}dic2={}foriinrange(len(data1)):   dic1[data1[i,0]]=[int(data1[i,2]),int(data1[i,3])]foriinrange(len(data2)):   dic2[data2[i,0]]=[data2[i,1],data2[i,2],data2[i,3],data2[i,4],data2[i,5],data2[i,6]]#计算连线长度defcal_length(dic2):   length=0   forkeyindic2:       foriinrange(1,5):           ifdic2[key][i]==1:               length+=abs(dic1[key][0]-dic1[key][2*i-1])+abs(dic1[key][1]-dic1[key][2*i])   returnlength#计算单元密度defcal_density(dic1,dic2,size,grid,threshold):   num=0   foriinrange(0,size[0],grid):       forjinrange(0,size[1],grid):           forkeyindic1:               ifdic1[key][0]>=ianddic1[key][0]=janddic1[key][1]=ianddic1[key][0]=janddic1[key][1]max_density:               max_density=num   returnmax_density/(grid**2)#修正模型defrevised_model(dic1,dic2,size,grid,threshold):   #初始化温度和迭代次数   T=100   max_iter=100   #随机生成初始布局   forkeyindic1:       dic1[key][0]=np.random.randint(grid,size[0]-grid)       dic1[key][1]=np.random.randint(grid,size[1]-grid)   #计算初始布局下的总连线长度   old_length=cal_length(dic2)   #开始迭代   forkinrange(max_iter):       #随机选择一个电路单元       key=np.random.choice(list(dic1.keys()))       #随机选择一个方向       direction=np.random.choice([-1,1,-grid,grid])       #计算新布局下的总连线长度       dic1[key][0]+=direction       new_length=cal_length(dic2)       #计算温度       T=0.99*T       #判断是否接受新布局       ifnp.exp((old_length-new_length)/T)>np.random.rand():           old_length=new_length       else:           dic1[key][0]-=direction   #计算最终布局下的总连线长度   new_length=cal_length(dic2)   returndic1,new_length#计算平均布线密度defcal_avg_density(dic1,dic2,size,grid):   num=0   foriinrange(0,size[0],grid):       forjinrange(0,size[1],grid):           forkeyindic1:               ifdic1[key][0]>=ianddic1[key][0]=janddic1[key][1]np.random.rand()andnew_max_density=iandnew_dic1[key][0]=jandnew_dic1[key][1]=ianddic1[key][0]=janddic1[key][1]=ianddic1[key][0]=janddic1[key][1]max_density:               max_density=num   returnmax_density/(grid**2)#修正模型defrevised_model(dic1,dic2,size,grid,threshold):   #初始化温度和迭代次数   T=100   max_iter=100   #随机生成初始布局   forkeyindic1:       dic1[key][0]=np.random.randint(grid,size[0]-grid)       dic1[key][1]=np.random.randint(grid,size[1]-grid)   #计算初始布局下的总连线长度   old_length=cal_length(dic2)   #开始迭代   forkinrange(max_iter):       #随机选择一个电路单元       key=np.random.choice(list(dic1.keys()))       #随机选择一个方向       direction=np.random.choice([-1,1,-grid,grid])       #计算新布局下的总连线长度       dic1[key][0]+=direction       new_length=cal_length(dic2)       #计算温度       T=0.99*T       #判断是否接受新布局       ifnp.exp((old_length-new_length)/T)>np.random.rand():           old_length=new_length       else:           dic1[key][0]-=direction   #计算最终布局下的总连线长度   new_length=cal_length(dic2)   returndic1,new_length#计算平均布线密度defcal_avg_density(dic1,dic2,size,grid):   num=0   foriinrange(0,size[0],grid):       forjinrange(0,size[1],grid):           forkeyindic1:               ifdic1[key][0]>=ianddic1[key][0]=janddic1[key][1]np.random.rand()andnew_max_density=iandnew_dic1[key][0]=jandnew_dic1[key][1]