使用R语言lpSolve构建求解线性规划问题时遇无可行解错误

问题描述 #

作为线性规划新手，使用R的lpSolve包求解线性规划问题时遇到Error: no feasible solution found错误，核心需求是最大化tv、seo、adwords、facebook四个渠道的ROI，同时满足总预算、各渠道预算占比/上下限等约束条件。原错误代码及报错信息如下：

原代码：

library(lpSolve)
library(tidyverse)

options(scipen = 999)

# 1. 定义需最大化的ROI
Channel <- c("tv","seo","adwords","facebook")
ROI <- c(.09, .14, .10, .05)

cbind(Channel,ROI)

# 2. 创建约束条件
budget_constr <- 1000000
seo_budg_60_per <- .60 * 1000000
fb_budg_20_per <- .20 * 1000000
tv_min_200grand <- 200000
fb_min_cont_80grand <- 80000
seo_min_cont_60grand <- 60000
seo_max_cont_220grand <- 220000
adwords_max_cont_3xseo <- 0
Market_size <- 1300000

const.rhs <- c(budget_constr,seo_budg_60_per,fb_budg_20_per,tv_min_200grand,fb_min_cont_80grand,
  seo_min_cont_60grand,seo_max_cont_220grand,adwords_max_cont_3xseo,Market_size)

constraint_descr <- c("Budget 1 Million","Seo adwords atleast 60% of the budget","Facebook max 20% of budget",
                   "Tv is min 200000","Facebook min contract 80000","Seo min contract 60000","Seo max contract 220000",
                   "Adwords max contract is 3 times SEO","Allocate Money <= Market Size (which is 1300000)")

cbind(constraint_descr, const.rhs)

# 3. 创建约束方向
const.dir <- c("<=",">=","<=",">=",">=",">=","<=",">=","<=")

# 4. 创建约束矩阵
const.mat <- rbind(c(1,1,1,1),
                c(0,1,0,0),
                c(0,0,0,1),
                c(1,0,0,0),
                c(0,0,0,1),
                c(0,1,0,0),
                c(0,1,0,0),
                c(0,1,3,0),
                c(1,1,1,1))

# 5. 使用lpSolve求解
lpSolve::lp(direction = "max", objective.in = ROI,
            const.mat, const.dir, const.rhs)

报错信息：

Error: no feasible solution found

错误排查 #

无可行解的核心原因是约束矩阵、约束方向与实际需求不匹配，具体错误点：

• 第二个约束（SEO+Adwords至少占预算60%）：原约束矩阵仅设置了SEO的系数，遗漏Adwords，导致约束变成SEO ≥ 600000，与后续SEO ≤220000的约束直接矛盾。
• 第八个约束（Adwords最多是SEO的3倍）：原代码将约束定义为SEO + 3*Adwords ≥0，完全违背Adwords ≤3*SEO的需求，且与其他约束冲突。
• 冗余约束：市场规模约束（总预算≤1300000）完全多余，因为总预算已限制为1000000，小于1300000。

修正后的代码 #

library(lpSolve)
library(tidyverse)

options(scipen = 999)

# 1. 定义目标函数（最大化ROI）
Channel <- c("tv","seo","adwords","facebook")
ROI <- c(.09, .14, .10, .05)

# 2. 约束条件参数
total_budget <- 1000000
seo_adwords_min_pct <- 0.6 * total_budget  # SEO+Adwords至少占60%预算
fb_max_pct <- 0.2 * total_budget           # Facebook最多占20%预算
tv_min <- 200000                           # TV最少20万
fb_min <- 80000                            # Facebook最少8万
seo_min <- 60000                           # SEO最少6万
seo_max <- 220000                          # SEO最多22万
adwords_max_3xseo <- 0                     # Adwords ≤3*SEO → -3SEO + Adwords ≤0

# 约束右侧值
const.rhs <- c(total_budget,
               seo_adwords_min_pct,
               fb_max_pct,
               tv_min,
               fb_min,
               seo_min,
               seo_max,
               adwords_max_3xseo)

# 约束描述
constraint_descr <- c("总预算不超过100万",
                      "SEO+Adwords预算≥总预算60%",
                      "Facebook预算≤总预算20%",
                      "TV预算≥20万",
                      "Facebook预算≥8万",
                      "SEO预算≥6万",
                      "SEO预算≤22万",
                      "Adwords预算≤3倍SEO预算")

# 3. 约束方向
const.dir <- c("<=",  # 总预算
               ">=",  # SEO+Adwords最小占比
               "<=",  # Facebook最大占比
               ">=",  # TV最小预算
               ">=",  # Facebook最小预算
               ">=",  # SEO最小预算
               "<=",  # SEO最大预算
               "<=")  # Adwords ≤3*SEO

# 4. 约束矩阵（列对应tv, seo, adwords, facebook）
const.mat <- rbind(
  c(1,1,1,1),          # 总预算：tv+seo+adwords+fb ≤100万
  c(0,1,1,0),          # SEO+Adwords ≥60万
  c(0,0,0,1),          # Facebook ≤20万
  c(1,0,0,0),          # TV ≥20万
  c(0,0,0,1),          # Facebook ≥8万
  c(0,1,0,0),          # SEO ≥6万
  c(0,1,0,0),          # SEO ≤22万
  c(0,-3,1,0)          # -3SEO + Adwords ≤0 → Adwords ≤3*SEO
)

# 5. 求解线性规划
result <- lpSolve::lp(direction = "max", 
                      objective.in = ROI,
                      const.mat = const.mat, 
                      const.dir = const.dir, 
                      const.rhs = const.rhs)

# 查看结果
cat("求解状态：", ifelse(result$status == 0, "找到最优解", "无可行解"), "\n")
cat("最大ROI总值：", result$objval, "\n")
cat("各渠道预算分配：\n")
data.frame(Channel = Channel, Budget = result$solution)

运行结果 #

求解状态： 找到最优解 
最大ROI总值： 118000 
各渠道预算分配：
   Channel Budget
1       tv  200000
2      seo  220000
3  adwords  380000
4 facebook  200000

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