如何最优利用有序对达成指定元素计数要求？

问题建模 #

这是典型的二维资源匹配整数规划问题：每个企业有序对(x;y)同时占用x（1-5）和y（6-10）两类资源的配额，需从现有350组有序对中选择子集，最大化满足给定的各元素计数需求，无法完全满足时追求最优匹配。

核心定义

1. 输入数据：

   • 设count[i][j]为现有数据中类型为(i;j)的企业数量（i∈{1,2,3,4,5}，j∈{6,7,8,9,10}）
   • 需求数组demand：
     • 元素1-5需求：demand[1]=6, demand[2]=31, demand[3]=25, demand[4]=25, demand[5]=36
     • 元素6-10需求：demand[6]=34, demand[7]=53, demand[8]=27, demand[9]=24, demand[10]=35

2. 决策变量：

   • x[i][j]：选择的(i;j)类型企业数量，满足0 ≤ x[i][j] ≤ count[i][j]，且x[i][j]为非负整数

3. 目标函数：
   最大化所有元素的实际满足量总和（等价于最小化需求缺口总和）：

   Maximize sum_{i=1-5} (sum_{j=6-10} x[i][j]) + sum_{j=6-10} (sum_{i=1-5} x[i][j])
   

   注：也可改为最小化sum(|需求值-实际满足值|)，但线性规划中通常用线性形式的目标，上述最大化总和更易实现。

4. 约束条件：

   • 对于每个元素i（1-5）：所选包含i的有序对总数不超过其需求：

     sum_{j=6到10} x[i][j] ≤ demand[i]
     

   • 对于每个元素j（6-10）：所选包含j的有序对总数不超过其需求：

     sum_{i=1到5} x[i][j] ≤ demand[j]
     

   • 非负整数约束：x[i][j] ∈ ℕ, 0 ≤ x[i][j] ≤ count[i][j]

求解实现（Python Pulp库） #

以下是可直接运行的代码示例，需先安装pulp库（pip install pulp）：

import pulp

# 1. 定义需求数据
demand = {
    1: 6, 2: 31, 3: 25, 4: 25, 5: 36,
    6: 34, 7: 53, 8: 27, 9: 24, 10: 35
}

# 2. 假设现有有序对计数（需替换为你的真实数据）
# 示例：count[i][j] 表示(i;j)类型的企业数量
count = {
    (1,6): 2, (1,7): 1, (1,8): 3, (1,9): 0, (1,10):0,
    (2,6):5, (2,7):8, (2,8):7, (2,9):6, (2,10):5,
    (3,6):4, (3,7):6, (3,8):5, (3,9):5, (3,10):5,
    (4,6):6, (4,7):7, (4,8):6, (4,9):4, (4,10):2,
    (5,6):17, (5,7):31, (5,8):6, (5,9):9, (5,10):23,
}

# 3. 创建问题实例
prob = pulp.LpProblem("FirmPairOptimize", pulp.LpMaximize)

# 4. 定义决策变量
x = pulp.LpVariable.dicts("Pair", count.keys(), lowBound=0, upBound=None, cat='Integer')

# 5. 设置目标函数：最大化总满足量
total_satisfaction = pulp.lpSum([x[i,j] for i,j in count.keys()]) * 2  # 每个配对贡献x和y两个元素的满足量
prob += total_satisfaction

# 6. 添加约束条件
# 约束1：x元素（1-5）的满足量不超过需求
for i in range(1,6):
    prob += pulp.lpSum([x[i,j] for j in range(6,11) if (i,j) in count]) <= demand[i], f"Constraint_X_{i}"

# 约束2：y元素（6-10）的满足量不超过需求
for j in range(6,11):
    prob += pulp.lpSum([x[i,j] for i in range(1,6) if (i,j) in count]) <= demand[j], f"Constraint_Y_{j}"

# 约束3：每个类型的选择数量不超过现有数量
for (i,j) in count.keys():
    prob += x[i,j] <= count[(i,j)], f"Constraint_Count_{i}_{j}"

# 7. 求解问题
prob.solve(pulp.PULP_CBC_CMD(msg=0))  # msg=0关闭日志输出

# 8. 输出结果
print("最优选择方案：")
for (i,j) in count.keys():
    if pulp.value(x[i,j]) > 0:
        print(f"选择 {int(pulp.value(x[i,j]))} 个 ({i};{j}) 类型企业")

print("\n各元素实际满足量：")
for i in range(1,6):
    satisfied = sum(pulp.value(x[i,j]) for j in range(6,11) if (i,j) in count)
    print(f"元素{i}: {int(satisfied)}/{demand[i]}")
for j in range(6,11):
    satisfied = sum(pulp.value(x[i,j]) for i in range(1,6) if (i,j) in count)
    print(f"元素{j}: {int(satisfied)}/{demand[j]}")

print(f"\n总满足量：{int(pulp.value(total_satisfaction)/2)} 个企业（每个企业贡献2个元素满足）")

关键说明 #

• 替换代码中的count字典为你的真实350组有序对的统计数据（先按(i;j)类型统计数量）
• 若不需要整数约束（仅做理论最优参考），可将cat='Integer'改为cat='Continuous'，求解速度更快
• 若追求最小化最大缺口或其他目标，可调整目标函数（比如改为最小化各元素缺口的加权和）

内容的提问来源于stack exchange，提问作者timmtamsar