devbox
繁依Fanyi0
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

2024年MathorCup高校数学建模挑战赛（A题）深度剖析_建模完整过程+详细思路+代码全解析_2024mathorcup高校数学建模竞赛题目

作者：繁依Fanyi0 | 2024-05-22 04:26:58

赞

踩

2024mathorcup高校数学建模竞赛题目

问题1

问题1的建模思路如下：

首先，给出问题的数学表达式为：

m i n ∑ i = 1 n ∑ j = 1 n ( a i j + b i j + c i j ) min \sum_{i=1}^{n}\sum_{j=1}^{n}(a_{ij}+b_{ij}+c_{ij}) mini=1∑n​j=1∑n​(aij​+bij​+cij​)

其中，n为小区的个数， a i j a_{ij} aij​、 b i j b_{ij} bij​和 c i j c_{ij} cij​分别表示小区i和j之间的冲突MR数、混淆MR数和模3干扰MR数。

然后，根据题目中给出的数据，可以得到冲突矩阵A、混淆矩阵B和干扰矩阵C。

接下来，需要对PCI进行重新分配，即确定每个小区的PCI值。令 X i X_i Xi​表示小区i分配的PCI值， X = ( X 1 , X 2 , . . . , X n ) X=(X_1,X_2,...,X_n) X=(X1​,X2​,...,Xn​)为PCI值的向量。

根据题目的要求，每个小区的PCI值必须在0到1007之间，因此，可以建立如下约束条件：

0 ≤ X i ≤ 1007 , i = 1 , 2 , . . . , n 0 \leq X_i \leq 1007, i=1,2,...,n 0≤Xi​≤1007,i=1,2,...,n

另外，为了避免PCI冲突，还需要添加如下约束条件：

X i ≠ X j , ( i , j ) ∈ Ω X_i \neq X_j, (i,j) \in \Omega Xi​=Xj​,(i,j)∈Ω

其中， Ω \Omega Ω表示同频邻区的集合。

综上所述，可以得到问题1的数学表达式为：

m i n ∑ i = 1 n ∑ j = 1 n ( a i j + b i j + c i j ) min \sum_{i=1}^{n}\sum_{j=1}^{n}(a_{ij}+b_{ij}+c_{ij}) mini=1∑n​j=1∑n​(aij​+bij​+cij​)

s . t . { 0 ≤ X i ≤ 1007 , i = 1 , 2 , . . . , n X i ≠ X j , ( i , j ) ∈ Ω s.t.\left\{

0≤Xi≤1007,i=1,2,...,nXi≠Xj,(i,j)∈Ω
\right. s.t.{0≤Xi​≤1007,i=1,2,...,nXi​=Xj​,(i,j)∈Ω​

其中， X = ( X 1 , X 2 , . . . , X n ) X=(X_1,X_2,...,X_n) X=(X1​,X2​,...,Xn​)为PCI值的向量，n为小区的个数， a i j a_{ij} aij​、 b i j b_{ij} bij​和 c i j c_{ij} cij​分别表示小区i和j之间的冲突MR数、混淆MR数和模3干扰MR数， Ω \Omega Ω表示同频邻区的集合。

根据约束条件，可以将问题转换为一个整数规划问题。但是，由于问题规模较大，求解整数规划问题的时间复杂度很高，因此可以采用启发式算法来求解。

启发式算法的基本思想是通过迭代的方式，每次找到一个可行解，并根据一定的策略进行优化，直到找到最优解为止。具体来说，可以采用贪心算法来求解。贪心算法的基本步骤如下：

  1. 初始化：随机给每个小区分配一个PCI编号；
  2. 计算目标函数(4)的值，作为当前解的目标函数值；
  3. 针对每个小区i，依次尝试将其PCI编号改为其他可选的编号，计算目标函数的值，如果新的值小于当前的值，则更新当前解，并继续下一步骤；
  4. 如果当前解的目标函数值没有改变，则停止迭代，当前解即为求解的最优解。

通过以上的贪心算法，可以得到一个近似最优解。

python代码实现：

# 导入相关库
import numpy as np
import pandas as pd
from scipy.optimize import minimize

# 读取数据
df = pd.read_csv('data.csv')

# 将数据转换为矩阵
A = df.pivot(index='主控小区', columns='邻区', values='冲突MR数量').fillna(0).values
B = df.pivot(index='主控小区', columns='邻区', values='混淆MR数量').fillna(0).values
C = df.pivot(index='主控小区', columns='邻区', values='干扰MR数量').fillna(0).values

# 定义目标函数
def objective(x):
    # 将向量x转换为矩阵
    X = x.reshape((len(x)//1008, 1008))
    # 计算目标函数值
    return np.sum(A*X) + np.sum(B*X) + np.sum(C*X)

# 定义约束条件
def constraint1(x):
    # 将向量x转换为矩阵
    X = x.reshape((len(x)//1008, 1008))
    # 每个小区只能分配一个PCI值
    return [np.sum(X, axis=1) - 1]

def constraint2(x):
    # 将向量x转换为矩阵
    X = x.reshape((len(x)//1008, 1008))
    # 每个PCI值只能分配给一个小区
    return [np.sum(X, axis=0) - 1]

def constraint3(x):
    # 将向量x转换为矩阵
    X = x.reshape((len(x)//1008, 1008))
    # 每个小区的PCI值必须在0到1007之间
    return [np.sum(X, axis=1) - 1007]

# 定义初始解
x0 = np.random.randint(0, 1008, size=1008*2067)

# 定义约束条件
cons = [{'type': 'eq', 'fun': constraint1},
        {'type': 'eq', 'fun': constraint2},
        {'type': 'eq', 'fun': constraint3}]

# 求解问题
result = minimize(objective, x0, constraints=cons)

# 输出结果
print('最小目标函数值：', result.fun)
print('分配结果：', result.x.reshape((len(result.x)//1008, 1008)))

# 将结果保存为csv文件
df_result = pd.DataFrame(result.x.reshape((len(result.x)//1008, 1008)))
df_result.to_csv('result.csv', index=False)

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57

问题2

问题2的建模思路如下：
首先，我们可以将问题转化为一个图论问题。将2067个小区看作图中的顶点，冲突、混淆和模3干扰分别看作三种边，构建一个三部图。其中，冲突和混淆的边的权重为1，模3干扰的边的权重为2。我们的目标是在保证每个顶点的度不超过1的情况下，使得所有边的权重之和最小。

然后，我们可以将问题转化为一个最小权匹配问题。根据匈牙利算法，我们可以求出一个最大匹配，它的权重就是所有边的权重之和的最小值。由于我们希望将所有边的权重之和最小化，所以我们可以将模3干扰的边的权重乘以一个较大的系数k，然后再求最大匹配。当k越大，模3干扰的边的权重就会越大，从而优先匹配冲突和混淆的边。当k为无穷大时，我们就可以保证冲突的边和混淆的边都被完全匹配，同时模3干扰的边尽量少。因此，我们可以通过调整k的值，来达到不同优先级的要求。

最后，我们可以使用二分法来确定最优的k值。具体步骤如下：

  1. 初始化k的上下限，记为k_min和k_max。
  2. 求解当前k值下的最大匹配，记为matching，以及所有匹配边的权重之和，记为sum。
  3. 如果sum等于所需最小值，停止二分法，输出最终解。
  4. 如果sum小于所需最小值，说明当前k值偏小，更新k_min为当前k值，重复步骤2。
  5. 如果sum大于所需最小值，说明当前k值偏大，更新k_max为当前k值，重复步骤2。

最终，我们可以得到最优的k值，从而得到最优的PCI分配方案。

假设PCI的分配结果为一个长度为2067的向量 x = ( x 1 , x 2 , . . . , x 2067 ) {x}=(x_1,x_2,...,x_{2067}) x=(x1​,x2​,...,x2067​)，其中 x i x_i xi​表示第i个小区分配的PCI值。冲突、混淆和干扰的MR数可以用以下公式表示：
冲突MR数：
a ( x ) = ∑ i = 1 2067 ∑ j = 1 2067 a i j x i x j a(x)=\sum_{i=1}^{2067}\sum_{j=1}^{2067}a_{ij}x_ix_j a(x)=i=1∑2067​j=1∑2067​aij​xi​xj​
混淆MR数：
b ( x ) = ∑ i = 1 2067 ∑ j = 1 2067 b i j x i x j b(x)=\sum_{i=1}^{2067}\sum_{j=1}^{2067}b_{ij}x_ix_j b(x)=i=1∑2067​j=1∑2067​bij​xi​xj​
模3干扰MR数：
c ( x ) = ∑ i = 1 2067 ∑ j = 1 2067 c i j x i x j c(x)=\sum_{i=1}^{2067}\sum_{j=1}^{2067}c_{ij}x_ix_j c(x)=i=1∑2067​j=1∑2067​cij​xi​xj​
其中， a i j 、 b i j 、 c i j a_{ij}、b_{ij}、c_{ij} aij​、bij​、cij​分别表示第i个小区与第j个小区之间的冲突、混淆和干扰MR数量。为了保证冲突的MR数降到最低，在优化目标中引入一个惩罚因子 α \alpha α，使得优化目标为：
min ⁡ x a ( x ) + α b ( x ) + α c ( x ) \min_{x}a(x)+\alpha b(x)+\alpha c(x) xmin​a(x)+αb(x)+αc(x)
其中， α \alpha α为一个大于1的常数，用于提高混淆和干扰的惩罚力度。同时，为了保证混淆的MR数降到最低，在优化目标中引入另一个惩罚因子 β \beta β，使得优化目标为：
min ⁡ x a ( x ) + α b ( x ) + β c ( x ) \min_{x}a(x)+\alpha b(x)+\beta c(x) xmin​a(x)+αb(x)+βc(x)
其中， β \beta β为一个大于 α \alpha α的常数，用于进一步提高干扰的惩罚力度。最后，为了尽量降低模3干扰的MR数，在优化目标中引入第三个惩罚因子 γ \gamma γ，使得优化目标为：
min ⁡ x a ( x ) + α b ( x ) + β c ( x ) + γ d ( x ) \min_{x}a(x)+\alpha b(x)+\beta c(x)+\gamma d(x) xmin​a(x)+αb(x)+βc(x)+γd(x)
其中， γ \gamma γ为一个大于 β \beta β的常数，用于进一步提高模3干扰的惩罚力度。综上所述，第二个问题的建模思路为，在优化目标中引入惩罚因子，通过调整不同惩罚因子的大小，来实现对冲突、混淆和模3干扰的不同优先级处理。

以下是基于python的代码：

# 定义函数，根据冲突、混淆和模3干扰的数量对小区进行排序
def sort_cells(cells):
    sorted_cells = sorted(cells, key=lambda x: (x["conflict"], x["confusion"], x["mod3"]))
    return sorted_cells

# 定义函数，为每个小区分配PCI值
def assign_pci(cells):
    assigned_cells = []
    pci = 0 # 初始PCI值
    for cell in cells:
        cell["pci"] = pci # 为小区分配PCI值
        assigned_cells.append(cell)
        pci += 1 # PCI值自增1
    return assigned_cells

# 定义函数，检查当前分配的PCI值是否会导致冲突、混淆和模3干扰的数量增加
def check_pci(assigned_cells, cell):
    for assigned_cell in assigned_cells:
        if cell["pci"] == assigned_cell["pci"]: # 如果小区分配的PCI值和已分配的小区的PCI值相同
            cell["conflict"] += assigned_cell["conflict"] # 冲突数量增加
            cell["confusion"] += assigned_cell["confusion"] # 混淆数量增加
            cell["mod3"] += assigned_cell["mod3"] # 模3干扰数量增加
    return cell

# 定义函数，为小区重新分配PCI值，并保证冲突、混淆和模3干扰的数量最少
def rearrange_pci(cells):
    cells = sort_cells(cells) # 对小区进行排序
    assigned_cells = assign_pci(cells) # 为每个小区分配PCI值
    for cell in assigned_cells:
        cell = check_pci(assigned_cells, cell) # 检查是否会增加冲突、混淆和模3干扰数量
        while cell["conflict"] > 0 or cell["confusion"] > 0 or cell["mod3"] > 0: # 如果增加了冲突、混淆和模3干扰数量
            cell["pci"] += 1 # 将小区的PCI值自增1
            cell = check_pci(assigned_cells, cell) # 检查是否还会增加冲突、混淆和模3干扰数量
    return assigned_cells

# 定义函数，计算冲突、混淆和模3干扰的数量总和
def calculate_total_conflict(cells):
    total_conflict = 0
    for cell in cells:
        total_conflict += cell["conflict"] # 冲突数量总和
    return total_conflict

def calculate_total_confusion(cells):
    total_confusion = 0
    for cell in cells:
        total_confusion += cell["confusion"] # 混淆数量总和
    return total_confusion

def calculate_total_mod3(cells):
    total_mod3 = 0
    for cell in cells:
        total_mod3 += cell["mod3"] # 模3干扰数量总和
    return total_mod3

# 定义函数，计算冲突、混淆和模3干扰的不同优先级的数量总和
def calculate_total_priority_conflict(cells):
    total_priority_conflict = 0
    for cell in cells:
        total_priority_conflict += cell["priority_conflict"] # 冲突优先级数量总和
    return total_priority_conflict

def calculate_total_priority_confusion(cells):
    total_priority_confusion = 0
    for cell in cells:
        total_priority_confusion += cell["priority_confusion"] # 混淆优先级数量总和
    return total_priority_confusion

def calculate_total_priority_mod3(cells):
    total_priority_mod3 = 0
    for cell in cells:
        total_priority_mod3 += cell["priority_mod3"] # 模3干扰优先级数量总和
    return total_priority_mod3

# 定义函数，为小区重新分配PCI值，并保证冲突、混淆和模3干扰的不同优先级的数量最少
def rearrange_priority_pci(cells):
    cells = sort_cells(cells) # 对小区进行排序
    assigned_cells = assign_pci(cells) # 为每个小区分配PCI值
    for cell in assigned_cells:
        cell = check_pci(assigned_cells, cell) # 检查是否会增加冲突、混淆和模3干扰数量
        while cell["priority_conflict"] > 0: # 如果增加了冲突优先级数量
            cell["pci"] += 1 # 将小区的PCI值自增1
            cell = check_pci(assigned_cells, cell) # 检查是否还会增加冲突、混淆和模3干扰数量
        while cell["priority_confusion"] > 0: # 如果增加了混淆优先级数量
            cell["pci"] += 1 # 将小区的PCI值自增1
            cell = check_pci(assigned_cells, cell) # 检查是否还会增加冲突、混淆和模3干扰数量
        while cell["priority_mod3"] > 0: # 如果增加了模3干扰优先级数量
            cell["pci"] += 1 # 将小区的PCI值自增1
            cell = check_pci(assigned_cells, cell) # 检查是否还会增加冲突、混淆和模3干扰数量
    return assigned_cells


def rearrange_all_pci(cells):
    cells = sort_cells(cells) # 对小区进行排序
    assigned_cells = assign_pci(cells) # 为每个小区分配PCI值
    for cell in assigned_cells:
        cell = check_pci(assigned_cells, cell) # 检查是否会增加冲突、混淆和模3干扰数量
        while cell["conflict"] > 0 or cell["confusion"] > 0 or cell["mod3"] > 0: # 如果增加了冲突、混淆和模3干扰数量
            cell["pci"] += 1 # 将小区的PCI值自增1
            cell = check_pci(assigned_cells, cell) # 检查是否还会增加冲突、混淆和模3干扰数量
    return assigned_cells


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101

问题3

问题3的建模思路如下：
首先，根据附件提供的数据，可以得到冲突矩阵A、混淆矩阵B和模3干扰矩阵C。为了方便后续的计算，可以将这些矩阵转换为N×N的对称矩阵，即A、B和C的对称矩阵分别记为A’、B’和C’。

其次，根据题目要求，需要对这2067个小区进行PCI重新分配，使得所有可能被影响到的小区间的冲突MR数、混淆MR数和模3干扰MR数的总和最小。因此，可以建立一个目标函数，表示这三种影响的总和，记为F，即：

F = ∑ i = 1 N ∑ j = 1 N ( a i j + b i j + c i j ) F = \sum_{i=1}^{N}\sum_{j=1}^{N}(a_{ij}+b_{ij}+c_{ij}) F=i=1∑N​j=1∑N​(aij​+bij​+cij​)

其中，a、b和c分别表示冲突、混淆和模3干扰的影响数目。

然后，为了避免PCI冲突，需要保证每个小区的PCI值都不相同。可以设置一个变量x表示小区的PCI值，x的取值范围为0到1007。因此，可以建立约束条件，保证每个小区的PCI值都不相同，即：

x i ≠ x j i ≠ j i , j = 1 , 2 , ⋯   , N x_i \neq x_j \quad i \neq j \quad i,j = 1,2,\cdots,N xi​=xj​i=ji,j=1,2,⋯,N

最后，为了保证所有小区都能被分配到PCI值，还需要增加一个约束条件，即：

x i ∈ [ 1 , 1007 ] i = 1 , 2 , ⋯   , N x_i \in [1,1007] \quad i=1,2,\cdots,N xi​∈[1,1007]i=1,2,⋯,N

综上所述，可以将问题3转换为一个整数规划问题，即：

m i n F min \quad F minF

s . t . x i ≠ x j i ≠ j i , j = 1 , 2 , ⋯   , N s.t.\quad x_i \neq x_j \quad i \neq j \quad i,j = 1,2,\cdots,N s.t.xi​=xj​i=ji,j=1,2,⋯,N

x i ∈ [ 1 , 1007 ] i = 1 , 2 , ⋯   , N x_i \in [1,1007] \quad i=1,2,\cdots,N xi​∈[1,1007]i=1,2,⋯,N

求解这个整数规划问题，即可得到2067个小区的最优PCI分配方案，使得所有可能被影响到的小区间的冲突MR数、混淆MR数和模3干扰MR数的总和最小。

# 导入numpy库
import numpy as np

# 定义函数，计算冲突MR数、混淆MR数和模3干扰MR数的总和
def calc_total_conflict(a, b, c):
    total = 0
    for i in range(len(a)):
        for j in range(len(a)):
            if a[i][j] != 0:
                total += a[i][j]
            if b[i][j] != 0:
                total += b[i][j]
            if c[i][j] != 0:
                total += c[i][j]
    return total

# 定义函数，计算冲突MR数、混淆MR数和模3干扰MR数的总和
def calc_total_conflict_priority(a, b, c):
    total = 0
    # 首先保证冲突的MR数降到最低
    for i in range(len(a)):
        for j in range(len(a)):
            if a[i][j] != 0:
                total += a[i][j]
    # 在此基础上保证混淆的MR数降到最低
    for i in range(len(b)):
        for j in range(len(b)):
            if b[i][j] != 0:
                total += b[i][j]
    # 最后尽量降低模3干扰的MR数
    for i in range(len(c)):
        for j in range(len(c)):
            if c[i][j] != 0:
                total += c[i][j]
    return total

# 定义函数，给小区重新分配PCI
def assign_pci(n, a, b, c):
    # 初始化PCI为0
    pci = [0] * n
    # 遍历每个小区
    for i in range(n):
        # 将小区i的PCI赋值为i+1
        pci[i] = i + 1
        # 遍历小区i的邻区
        for j in range(n):
            # 如果小区i和j同频，且PCI相同，则该邻区需要重新分配PCI
            if a[i][j] != 0 and pci[i] == pci[j]:
                # 遍历所有PCI
                for k in range(n):
                    # 如果该PCI没有被其他邻区使用，则将该PCI赋值给邻区j
                    if k + 1 not in pci:
                        pci[j] = k + 1
                        break
    # 重新计算冲突MR数、混淆MR数和模3干扰MR数的总和
    total = 0
    for i in range(n):
        for j in range(n):
            if a[i][j] != 0 and pci[i] == pci[j]:
                total += a[i][j]
            if b[i][j] != 0 and pci[i] == pci[j]:
                total += b[i][j]
            if c[i][j] != 0 and pci[i] == pci[j]:
                total += c[i][j]
    # 返回新的PCI分配方案和总和
    return pci, total

# 读取冲突矩阵、混淆矩阵和干扰矩阵
a = np.loadtxt('冲突矩阵.txt')
b = np.loadtxt('混淆矩阵.txt')
c = np.loadtxt('干扰矩阵.txt')

# 调用函数，计算总和
total = calc_total_conflict(a, b, c)

# 初始化最小总和和最优PCI分配方案
min_total = total
best_pci = []

# 遍历所有可能的PCI分配方案
for i in range(1, len(a)+1):
    pci, total = assign_pci(i, a, b, c)
    # 如果总和更小，则更新最小总和和最优PCI分配方案
    if total < min_total:
        min_total = total
        best_pci = pci

# 打印最优PCI分配方案和最小总和
print("最优PCI分配方案为：", best_pci)
print("最小总和为：", min_total)

# 随机生成一个小区，计算该小区的PCI
random_zone = np.random.randint(1, len(a)+1)
print("小区", random_zone, "的PCI为：", best_pci[random_zone-1])

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94

查看完整思路详见：
【腾讯文档】2024年MathorCup高校数学建模挑战赛全题目深度解析（详细思路+建模过程+代码实现+论文指导）
https://docs.qq.com/doc/DSFZYb1FsQ3hqbHNs

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/606255
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号