约束系数随决策变量变化的向量优化（R语言求解）

现有当前分数向量：

current_score <- c(60, 59, 78, 79, 76)

可选择将指定索引的分数提升至95，每个选择对应成本：

decision <- rep(1, times=length(current_score))
cost <- c(2792, 5207, 1814, 642, 1037)

要求加权分数（分数与成本加权和除以总成本）不低于目标值：

goal <- 70

需找到最优二进制决策向量（元素为0或1），最小化总选择成本。

尝试用optim做非线性优化但结果异常；尝试用lpSolve构建线性规划，但不知道如何处理随决策变量变化的约束。已知Excel遗传算法可实现该需求，希望在R中完成求解。

1. optim实现尝试 #

定义目标函数：

fn <- function(decision, current_score, cost, goal)
{
    # 若decision为TRUE，对应分数设为95
    current_score[which(decision == TRUE)] <- 95

    # 计算决策后的加权分数
    wt_score <- sum(current_score*cost)/sum(cost)   
    
    # 若未达到目标分数，赋值极大值以排除该决策
    if(wt_score < goal)
    {
        decision_cost <- .Machine$double.xmax
    } else
    {
        decision_cost <- sum(decision * cost)
    } 
    
    return(decision_cost)
}

调用代码：

upper <- rep(1, times=length(decision))
lower <- rep(0, times=length(decision))

result <- optim(par=decision, fn=fn, upper=upper, lower=lower, method=c("L-BFGS-B"), current_score = current_score, cost = cost, goal=goal)

示例：当decision = c(1,0,0,0,0)时，wt_score = 73.39，decision_cost = 2792，属于较优解。

2. lpSolve实现尝试框架 #

# 根据决策变量修改分数向量
constraint_vector <- function(score, x)
{
  score <- score[x==TRUE] <- 95
}

lp_min <- function(score, cost, crvs, goal)
{
  # 目标函数系数为成本向量
  f.obj <- cost
  # 约束系数随决策变量x变化，此处未正确实现
  f.con <- constraint_vector(score,x)
  f.dir <- c(">=")
  f.rhs <- goal
  
  solution <- lp("min", f.obj, f.con, f.dir, f.rhs, all.bin=TRUE)
}

核心思路：约束线性化 #

原始约束依赖决策变量，无法直接用于线性规划，但可以通过代数变形将其转化为线性形式：
原始约束：sum( (current_score_i + (95 - current_score_i)*x_i ) * cost_i ) / sum(cost_i) >= goal
两边乘以正数sum(cost_i)，整理后得到：
sum( (95 - current_score_i)*cost_i * x_i ) >= goal * sum(cost_i) - sum(current_score_i * cost_i)
此时约束变为关于二进制变量x_i的线性表达式，可直接用lpSolve求解。

具体实现代码 #

library(lpSolve)

# 定义参数
current_score <- c(60, 59, 78, 79, 76)
cost <- c(2792, 5207, 1814, 642, 1037)
goal <- 70

# 计算约束所需的常量值
original_sum <- sum(current_score * cost)
total_cost <- sum(cost)
required_increase <- goal * total_cost - original_sum

# 约束系数：每个x_i对应的系数为(95 - current_score_i)*cost_i
con_coeffs <- (95 - current_score) * cost

# 构建线性规划
f.obj <- cost  # 目标：最小化总成本
f.con <- matrix(con_coeffs, nrow=1)  # 约束矩阵
f.dir <- c(">=")
f.rhs <- c(required_increase)

# 求解二进制整数规划
solution <- lp("min", f.obj, f.con, f.dir, f.rhs, all.bin=TRUE)

# 输出结果
cat("最优决策向量：", solution$solution, "\n")
cat("最小总成本：", solution$objval, "\n")

# 验证加权分数
adjusted_score <- current_score + (95 - current_score)*solution$solution
final_wt_score <- sum(adjusted_score * cost)/total_cost
cat("最终加权分数：", round(final_wt_score, 2), "\n")

结果说明 #

运行代码后会得到满足加权分数≥70的最小成本决策向量。以给定参数为例，最优解为c(1,0,0,0,0)，总成本2792，加权分数73.39，符合要求。

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