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

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

作者：笔触狂放9 | 2024-05-20 09:54:54

赞

踩

mathorcupd题2024

问题1

针对问题1建立一个适合该问题的QUBO模型，可以考虑以下因素：
1、医院的位置：可以将医院的位置抽象为一个n维向量，其中每个维度代表一个医院，取值为0或1，表示该医院是否被选中。
2、医疗设备的类型和数量：可以将医疗设备的类型和数量抽象为一个n维向量，其中每个维度代表一个医院，取值为0或1，表示该医院是否拥有该类型的医疗设备。
3、医生的专业和工作量：可以将医生的专业和工作量抽象为一个n维向量，其中每个维度代表一个医院，取值为0或1，表示该医院是否拥有该类型的医生。
4、医疗服务的效率和成本：可以将医疗服务的效率和成本抽象为一个n维向量，其中每个维度代表一个医院，取值为该医院的效率和成本。
5、约束条件：可以将医院的位置、医疗设备的类型和数量、医生的专业和工作量等因素设定为约束条件，通过限制医院的选择变量的取值来满足约束条件。

目标函数:
m i n ∑ i = 1 n ∑ j = 1 m x i j ⋅ ( c 1 ⋅ e i + c 2 ⋅ d i j + c 3 ⋅ p i j ) min \sum_{i=1}^{n} \sum_{j=1}^{m} x_{ij} \cdot (c_1 \cdot e_i + c_2 \cdot d_{ij} + c_3 \cdot p_{ij}) mini=1∑n​j=1∑m​xij​⋅(c1​⋅ei​+c2​⋅dij​+c3​⋅pij​)
其中，n为医院的数量，m为医疗设备的类型数量， x i j x_{ij} xij​为0-1变量，表示医院i是否选择医疗设备j； e i e_i ei​为医院i的效率； d i j d_{ij} dij​为医疗设备j在医院i的距离； p i j p_{ij} pij​为医疗设备j的价格； c 1 c_1 c1​、 c 2 c_2 c2​、 c 3 c_3 c3​为相应的权重系数，用于调节不同因素的重要性。

约束条件:
∑ j = 1 m x i j ≤ 1 , ∀ i ∈ [ 1 , n ] \sum_{j=1}^{m} x_{ij} \leq 1, \forall i \in [1,n] j=1∑m​xij​≤1,∀i∈[1,n]
每个医院最多选择一种医疗设备。

∑ i = 1 n x i j ≥ 1 , ∀ j ∈ [ 1 , m ] \sum_{i=1}^{n} x_{ij} \geq 1, \forall j \in [1,m] i=1∑n​xij​≥1,∀j∈[1,m]
每种医疗设备至少被选择一次。

x i j ≤ x k j , ∀ i , k ∈ [ 1 , n ] , j ∈ [ 1 , m ] x_{ij} \leq x_{kj}, \forall i,k \in [1,n], j \in [1,m] xij​≤xkj​,∀i,k∈[1,n],j∈[1,m]
医院i选择了某种医疗设备j，则其他相同类型的医疗设备只能被选择一次。

∑ j = 1 m x i j ⋅ d i j ≤ D i , ∀ i ∈ [ 1 , n ] \sum_{j=1}^{m} x_{ij} \cdot d_{ij} \leq D_i, \forall i \in [1,n] j=1∑m​xij​⋅dij​≤Di​,∀i∈[1,n]
医院i的距离和超过了其能力范围 D i D_i Di​。

∑ j = 1 m x i j ⋅ p i j ≤ P i , ∀ i ∈ [ 1 , n ] \sum_{j=1}^{m} x_{ij} \cdot p_{ij} \leq P_i, \forall i \in [1,n] j=1∑m​xij​⋅pij​≤Pi​,∀i∈[1,n]
医院i的费用超过了其能力范围 P i P_i Pi​。

∑ i = 1 n x i j ⋅ y i = 1 , ∀ j ∈ [ 1 , m ] \sum_{i=1}^{n} x_{ij} \cdot y_i = 1, \forall j \in [1,m] i=1∑n​xij​⋅yi​=1,∀j∈[1,m]
每种医疗设备都有且只有一种医院选择。

y i ∈ [ 0 , 1 ] , ∀ i ∈ [ 1 , n ] y_i \in [0,1], \forall i \in [1,n] yi​∈[0,1],∀i∈[1,n]
y i y_i yi​为1表示医院i被选择，为0表示医院i未被选择。

∑ i = 1 n y i ≥ 3 \sum_{i=1}^{n} y_i \geq 3 i=1∑n​yi​≥3
至少选择3家医院。

∑ i = 1 n y i ⋅ z i ≤ M \sum_{i=1}^{n} y_i \cdot z_i \leq M i=1∑n​yi​⋅zi​≤M
z i ∈ [ 0 , 1 ] , ∀ i ∈ [ 1 , n ] z_i \in [0,1], \forall i \in [1,n] zi​∈[0,1],∀i∈[1,n]
z i z_i zi​为1表示医院i选择了大型医疗设备，为0表示未选择。

其中，M为一个较大的常数，用于限制大型医疗设备的数量。

python示例代码如下：

import numpy as np
import dimod

# 定义目标函数及约束条件中的参数
# 医院位置
hospital_location = ['A', 'B', 'C'] 
# 医疗设备类型
medical_equipment = ['X', 'Y', 'Z']
# 医生专业
doctor_major = ['a', 'b', 'c']
# 医生工作量
doctor_workload = [10, 20, 30]
# 医院每天可接待病人数量
hospital_capacity = [50, 100, 150]
# 医疗设备的成本
equipment_cost = {'X': 100, 'Y': 200, 'Z': 300}
# 医生的工资
doctor_salary = {'a': 5000, 'b': 6000, 'c': 7000}
# 医院的租金
hospital_rent = {'A': 10000, 'B': 15000, 'C': 20000}
# 医生的工作小时数
doctor_hour = {'a': 8, 'b': 10, 'c': 12}
# 医疗设备的使用时间
equipment_hour = {'X': 10, 'Y': 20, 'Z': 30}
# 医院每天的运营成本
hospital_cost = {'A': 5000, 'B': 6000, 'C': 7000}

# 定义QUBO模型中的变量
# 医院选择变量
hospital_choice = {'A': 0, 'B': 1, 'C': 2}
# 医生选择变量
doctor_choice = {'a': 0, 'b': 1, 'c': 2}
# 医疗设备选择变量
equipment_choice = {'X': 0, 'Y': 1, 'Z': 2}

# 定义目标函数及约束条件
# 目标函数
def objective(h, d, e):
    cost = 0
    for i in range(len(h)):
        cost += hospital_choice[h[i]] * hospital_rent[h[i]] + doctor_choice[d[i]] * doctor_salary[d[i]] * doctor_hour[d[i]] + equipment_choice[e[i]] * equipment_cost[e[i]] * equipment_hour[e[i]] + hospital_choice[h[i]] * hospital_cost[h[i]]
    return cost

# 约束条件
# 医院每天可接待病人数量
def hospital_capacity_constraint(h):
    capacity = 0
    for i in range(len(h)):
        capacity += hospital_choice[h[i]] * hospital_capacity[h[i]]
    return (capacity - 100)**2

# 医生工作量约束
def doctor_workload_constraint(d):
    workload = 0
    for i in range(len(d)):
        workload += doctor_choice[d[i]] * doctor_workload[d[i]]
    return (workload - 50)**2

# 医生和医疗设备匹配约束
def doctor_equipment_constraint(h, d, e):
    constraint = 0
    for i in range(len(h)):
        constraint += hospital_choice[h[i]] * (doctor_choice[d[i]] + equipment_choice[e[i]])
    return (constraint - 2)**2

# 构建QUBO模型
def build_qubo():
    # 构建QUBO模型的系数矩阵
    Q = {}
    # 目标函数
    for i in range(len(hospital_location)):
        for j in range(len(doctor_major)):
            for k in range(len(medical_equipment)):
                Q[(hospital_location[i], doctor_major[j], medical_equipment[k])] = objective(hospital_location[i], doctor_major[j], medical_equipment[k])
    # 约束条件
    for i in range(len(hospital_location)):
        for j in range(len(doctor_major)):
            for k in range(len(medical_equipment)):
                Q[(hospital_location[i], doctor_major[j], medical_equipment[k])] += hospital_capacity_constraint(hospital_location[i]) + doctor_workload_constraint(doctor_major[j]) + doctor_equipment

  • 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

问题2

第二个问题是如何根据上述因素建立QUBO模型，规划需要采购的挖掘机型号和数量，并给出挖掘机和矿车之间的匹配关系，使得5年内的总利润最大化。
和数学表达式。

首先，我们需要确定本问题的目标函数。根据题目要求，我们需要最大化5年内的总利润，即
m a x ∑ i = 1 5 ∑ j = 1 n ( p i j − c i j ) max \sum_{i=1}^{5} \sum_{j=1}^{n} (p_{ij} - c_{ij}) maxi=1∑5​j=1∑n​(pij​−cij​)
其中， p i j p_{ij} pij​为第i年第j种设备的收益， c i j c_{ij} cij​为第i年第j种设备的总成本。

其次，我们需要确定决策变量。根据题目给出的数据，我们需要决策的变量包括挖掘机的型号和数量，以及挖掘机和矿车的匹配关系。假设挖掘机的型号共有m种，数量分别为 x 1 , x 2 , . . . , x m x_1, x_2, ..., x_m x1​,x2​,...,xm​，对应的收益为 p 1 , p 2 , . . . , p m p_1, p_2, ..., p_m p1​,p2​,...,pm​，总成本为 c 1 , c 2 , . . . , c m c_1, c_2, ..., c_m c1​,c2​,...,cm​。矿车的型号共有k种，数量分别为 y 1 , y 2 , . . . , y k y_1, y_2, ..., y_k y1​,y2​,...,yk​，对应的收益为 q 1 , q 2 , . . . , q k q_1, q_2, ..., q_k q1​,q2​,...,qk​，总成本为 d 1 , d 2 , . . . , d k d_1, d_2, ..., d_k d1​,d2​,...,dk​。匹配关系可以用一个 m × k m \times k m×k的二进制矩阵 A A A来表示，其中 A i j A_{ij} Aij​为1表示第i种挖掘机和第j种矿车匹配，0表示不匹配。

为了简化模型，我们假设在整个5年内，挖掘机和矿车的匹配关系是固定的，即匹配关系矩阵 A A A是一个常数。因此，我们的决策变量可以简化为挖掘机的数量和矿车的数量。挖掘机的总数量为 ∑ i = 1 m x i \sum_{i=1}^{m} x_i ∑i=1m​xi​，矿车的总数量为 ∑ j = 1 k y j \sum_{j=1}^{k} y_j ∑j=1k​yj​。

接下来，我们需要考虑约束条件。根据题目给出的约束条件，我们可以列出如下约束条件：

  1. 每种挖掘机的数量不能小于0，即 x i ≥ 0 , i = 1 , 2 , . . . , m x_i \geq 0, i = 1, 2, ..., m xi​≥0,i=1,2,...,m。
  2. 每种矿车的数量不能小于0，即 y j ≥ 0 , j = 1 , 2 , . . . , k y_j \geq 0, j = 1, 2, ..., k yj​≥0,j=1,2,...,k。
  3. 挖掘机和矿车的匹配关系矩阵 A A A是一个常数。
  4. 每种挖掘机至少需要匹配一辆矿车，即 ∑ j = 1 k A i j ≥ 1 , i = 1 , 2 , . . . , m \sum_{j=1}^{k} A_{ij} \geq 1, i = 1, 2, ..., m ∑j=1k​Aij​≥1,i=1,2,...,m。
  5. 每种矿车的总数量不能超过已购买的数量，即 ∑ i = 1 m A i j ≤ z j , j = 1 , 2 , . . . , k \sum_{i=1}^{m} A_{ij} \leq z_j, j = 1, 2, ..., k ∑i=1m​Aij​≤zj​,j=1,2,...,k，其中 z j z_j zj​为第j种矿车已购买的数量。
  6. 挖掘机和矿车的匹配关系必须满足表3中的约束条件，即 A i j ≤ b i j , i = 1 , 2 , . . . , m , j = 1 , 2 , . . . , k A_{ij} \leq b_{ij}, i = 1, 2, ..., m, j = 1, 2, ..., k Aij​≤bij​,i=1,2,...,m,j=1,2,...,k，其中 b i j b_{ij} bij​为表3中对应的数值。
  7. 挖掘机和矿车的匹配关系必须满足整体包含的挖掘机型号不能少于3种的约束，即 ∑ i = 1 m ∑ j = 1 k A i j ≥ 3 \sum_{i=1}^{m} \sum_{j=1}^{k} A_{ij} \geq 3 ∑i=1m​∑j=1k​Aij​≥3。

最后，我们需要确定每种挖掘机和矿车的收益和总成本。根据题目给出的数据，我们可以得到如下表达式：

挖掘机的收益： p i = ∑ j = 1 k A i j p i j p_i = \sum_{j=1}^{k} A_{ij}p_{ij} pi​=∑j=1k​Aij​pij​
挖掘机的总成本： c i = ∑ j = 1 k A i j c i j c_i = \sum_{j=1}^{k} A_{ij}c_{ij} ci​=∑j=1k​Aij​cij​
矿车的收益： q j = ∑ i = 1 m A i j q i j q_j = \sum_{i=1}^{m} A_{ij}q_{ij} qj​=∑i=1m​Aij​qij​
矿车的总成本： d j = ∑ i = 1 m A i j d i j d_j = \sum_{i=1}^{m} A_{ij}d_{ij} dj​=∑i=1m​Aij​dij​

综合以上分析，我们可以得到如下QUBO模型：

m i n ∑ i = 1 m ∑ j = 1 k ( x i + y j ) ( ∑ t = 1 5 ( p i j − c i j ) + ∑ t = 1 5 ( q i j − d i j ) ) + α ∑ i = 1 m ( ∑ j = 1 k A i j − 1 ) 2 min \sum_{i=1}^{m} \sum_{j=1}^{k} (x_i + y_j)(\sum_{t=1}^{5} (p_{ij} - c_{ij}) + \sum_{t=1}^{5} (q_{ij} - d_{ij})) + \alpha \sum_{i=1}^{m} (\sum_{j=1}^{k} A_{ij} - 1)^2 mini=1∑m​j=1∑k​(xi​+yj​)(t=1∑5​(pij​−cij​)+t=1∑5​(qij​−dij​))+αi=1∑m​(j=1∑k​Aij​−1)2

其中， α \alpha α为一个较大的正数，用于惩罚匹配关系不满足约束条件的情况。
，实现QUBO模型的构建，求解和结果可视化。

python代码实现：

import numpy as np
from pyqubo import Array, Binary, Constraint, Placeholder, solve_qubo

# 定义变量
x = Array.create('x', shape=4, vartype='BINARY') # 每种挖掘机的数量
y = Array.create('y', shape=3, vartype='BINARY') # 每种矿车的数量
z = Array.create('z', shape=(4,3), vartype='BINARY') # 每种挖掘机分配给每种矿车的数量

# 定义目标函数
H_cost = Placeholder('cost') # 成本
H_revenue = Placeholder('revenue') # 收益
H_efficiency = Placeholder('efficiency') # 效率
H_profit = Placeholder('profit') # 利润
H = H_revenue * H_efficiency * 5 - H_cost - H_profit

# 挖掘机和矿车的匹配关系
c1 = [z[0,0] + z[0,1] >= 2,
	z[1,0] + z[1,1] >= 2,
	z[2,0] + z[2,1] + z[2,2] >= 2,
	z[3,0] + z[3,1] + z[3,2] >= 2]
# 每种挖掘机分配给的矿车数量不超过该挖掘机的最大匹配数量
c2 = [z[0,0] <= 7,
	z[0,1] <= 7,
	z[1,0] <= 7,
	z[1,1] <= 7,
	z[2,0] <= 7,
	z[2,1] <= 7,
	z[2,2] <= 3,
	z[3,0] <= 3,
	z[3,1] <= 3,
	z[3,2] <= 3]
# 每种挖掘机和矿车的总数量不超过已购买的数量
c3 = [x[0] + x[1] + x[2] + x[3] <= 3,
	y[0] + y[1] + y[2] <= 10]
# 每种挖掘机和矿车的总数量不能小于0
c4 = [x[i] >= 0 for i in range(4)]
c5 = [y[j] >= 0 for j in range(3)]
# 每种挖掘机和矿车的匹配关系满足实际情况
c6 = [z[0,1] + z[0,2] == 0,
	z[1,2] + z[1,3] == 0,
	z[2,
实现。

# 导入Kaiwu SDK
from qboson import Qboson
# 导入模拟退火求解器和CIM模拟器
from qboson import Annealer, Cim

# 定义问题2中的参数
bucket_capacity = [5, 8, 10, 12] # 挖掘机斗容
excavator_efficiency = [3, 5, 7, 10] # 挖掘机作业效率
truck_capacity = [10, 15, 20] # 矿车装载量
fuel_consumption = [2, 3, 4, 5] # 油耗
price_excavator = [300, 400, 500, 600] # 挖掘机价格
price_truck = [250, 350, 450] # 矿车价格
labor_cost = [1000, 1500, 2000, 2500] # 人工成本
maintenance_cost = [500, 750, 1000, 1250] # 维护成本
start_capital = 4000 # 启动资金
working_days = 20 # 每月工作天数
working_hours = 8 # 每天工作小时数
fuel_price = 7 # 油价
ore_price = 20 # 矿石价格
# 定义匹配关系
matching = [[2, 1, 0], [2, 2, 1], [3, 2, 1], [3, 3, 2]] # 匹配关系表格，如表7所示
# 定义QUBO模型
Q = {}
# 定义目标函数，即最大化总利润
def f(x):
    # 计算挖掘机和矿车的数量
    excavator_num = sum(x[:4])
    truck_num = sum(x[4:])
    # 计算每种挖掘机和矿车的利润
    excavator_profit = [price_excavator[i] * excavator_num - (excavator_efficiency[i] * working_days * working_hours * fuel_price * fuel_consumption[i]) for i in range(4)]
    truck_profit = [price_truck[i] * truck_num - (bucket_capacity[i] * working_days * working_hours * ore_price) for i in range(3)]
    # 计算总利润
    total_profit = sum(excavator_profit) + sum(truck_profit) - (labor_cost[excavator_num - 1] + maintenance_cost[excavator_num -1] + labor_cost[truck_num - 1] + maintenance_cost[truck_num -1])
    # 将总利润作为目标函数的值
    return total_profit
# 定义约束函数
def g(x):
    # 计算挖掘机和矿车的数量
    excavator_num = sum(x[:4])
    truck_num = sum(x[4:])
    # 定义约束条件，即挖掘机和矿车的匹配关系
    constraint = 0
    for i in range(4):
        constraint += x[i] * matching[i][0] # 计算挖掘机和矿车的匹配关系
    # 返回约束条件
    return constraint
# 定义QUBO模型的构建函数
def build_qubo():
    # 遍历所有可能的解
    for i in range(2 ** 7):
        # 将解转换为二进制数
        binary = bin(i)[2:].zfill(7)
        # 将二进制数转换为列表
        x = [int(j) for j in binary]
        # 计算目标函数的值
        target = f(x)
        # 计算约束函数的值
        constraint = g(x)
        # 将目标函数和约束函数的值作为QUBO模型的系数
        Q[(tuple(x), tuple(x))] = target - constraint
    # 返回QUBO模型
    return Q
# 构建QUBO模型
Q = build_qubo()
# 使用模拟退火求解器求解QUBO模型
result_annealer = Annealer(Q, 100, 100) # 100为迭代次数，100为退火次数
# 使用CIM模拟器求解QUBO模型
result_cim = Cim(Q, 100) # 100为迭代次数
# 输出结果
print("模拟退火求解器: ", result_annealer)
print("CIM模拟器: ", result_cim)


  • 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
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115

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

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

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

  

闽ICP备14008679号