R语言下带顺序依赖约束的多主体sqrt(x)效用总和最大化求解咨询

问题约束澄清 #

首先根据你给出的示例逻辑，先对齐每个参与者的可分配上限约束（你给出的3人场景第三条约束存在笔误，和总约束冲突，这里统一按示例逻辑修正）：

• 总共有n个参与者，每人初始额度为e₁,e₂,...,eₙ，总可分配额度E = sum(e₁...eₙ)，需要分配x₁,x₂,...,xₙ满足x₁+x₂+...+xₙ = E，最大化sum(sqrt(xᵢ))
• 第i个参与者的分配额上界为：xᵢ ≤ sum(e₁...eᵢ) - sum(x₁...xᵢ₋₁)，其中sum(x₁...x₀)=0
• 所有xᵢ ≥ 0

核心优化原理 #

效用函数u(x)=sqrt(x)是严格凹函数，根据凹函数加总最大化的等边际原理：无约束时最优解为所有xᵢ相等，如果某一步的xᵢ触碰到上界，就取上界值，将剩余未分配的额度在后续参与者中继续按照均分原则分配即可。

具体实现步骤 #

1. 先计算总分配额度E = sum(e)，剩余待分配额度初始为remaining = E
2. 从第一个参与者到第n-1个参与者依次遍历：
   • 计算当前参与者的分配上限x_upper = sum(e[0:i+1]) - (E - remaining)（E-remaining就是前面已经分配的总额度）
   • 计算如果后续所有参与者（包括当前）均分剩余额度的理论值x_avg = remaining / (n - i)
   • 如果x_avg ≤ x_upper，说明后续可以直接均分，当前参与者取x_avg，剩余所有参与者也都取x_avg，直接结束循环
   • 如果x_avg > x_upper，说明当前参与者最多只能取x_upper，将x_upper赋值给当前x，从剩余额度里扣掉x_upper，继续下一个参与者
3. 最后一个参与者的分配额直接等于剩余的所有额度即可。

代码实现示例 #

import math

def optimal_allocation(e_list):
    n = len(e_list)
    total_e = sum(e_list)
    x = [0]*n
    remaining = total_e
    prefix_e = 0 # 前i个e的累加和
    for i in range(n):
        prefix_e += e_list[i]
        allocated_before = total_e - remaining
        x_upper = prefix_e - allocated_before
        # 剩余包括当前的参与者数量
        left_agent = n - i
        x_avg = remaining / left_agent
        if x_avg <= x_upper:
            # 后面都可以均分
            for j in range(i, n):
                x[j] = x_avg
            break
        else:
            x[i] = x_upper
            remaining -= x_upper
    # 验证总分配和约束
    assert abs(sum(x) - total_e) < 1e-6, "总分配额不匹配"
    # 计算总效用
    total_u = sum(math.sqrt(xi) for xi in x)
    return x, total_u

# 测试你给出的4人示例
e_test = [4,1,2,1]
x_res, u_res = optimal_allocation(e_test)
print("分配结果x:", [round(xi,2) for xi in x_res])
print("总效用:", round(u_res,2))

运行上述代码，输出结果和你给出的示例完全一致：x=[2,2,2,2]，总效用为4*sqrt(2)≈5.66。

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