基于Rglpk的含连续销售约束的二进制线性优化问题求解

Hey there! Let's break down how to model that "continuous 3+ quarters of sales" constraint in Rglpk. I've worked through similar production/sales planning problems before, so let's walk through this step by step.

First, let's clarify the setup:

• We have n quarters, define binary variables x_j where x_j = 1 means we sell in quarter j, 0 otherwise.
• Our goal is to maximize total profit: sum(p_j * x_j) where p_j is the profit from selling in quarter j.
• The key constraint: If we choose to sell at all, the sales must be a continuous block of at least 3 quarters (no single-quarter or two-quarter sales runs allowed).

Step 1: Translate the constraint into linear rules #

To enforce continuous 3+ quarter sales, we need to block invalid scenarios:

1. No single-quarter sales: If x_j = 1, there must be adjacent quarters also set to 1.
2. No two-quarter sales runs: If two consecutive quarters are 1, there must be a third adjacent quarter also set to 1.

We can translate these into linear constraints without extra auxiliary variables (this keeps things simpler):

• For the first quarter: If we sell in Q1, we must sell in Q2 and Q3 → x1 ≤ x2 and x1 ≤ x3
• For middle quarters (Q2 to Qn-1): If we start selling in quarter j (meaning x_j=1 but x_{j-1}=0), we must sell in j+1 and j+2 → x_j - x_{j-1} ≤ x_{j+1} and x_j - x_{j-1} ≤ x_{j+2}
• For the last quarter: If we sell in Qn, we must sell in Qn-1 and Qn-2 → x_n ≤ x_{n-1} and x_n ≤ x_{n-2}

Step 2: Implement in Rglpk #

Let's use a concrete example with 4 quarters and sample profits to show the code:

# Load the package
library(Rglpk)

# Define parameters
n_quarters <- 4
profit_per_quarter <- c(10, 15, 20, 12) # Q1 to Q4 profits

# Build constraint list
constraints <- list()

# Constraints for Q1: must sell in Q2 and Q3 if selling in Q1
constraints[[1]] <- list(ind = c(1, 2), val = c(1, -1), dir = "<=", rhs = 0) # x1 ≤ x2
constraints[[2]] <- list(ind = c(1, 3), val = c(1, -1), dir = "<=", rhs = 0) # x1 ≤ x3

# Constraints for middle quarters (Q2 to Qn-1): start of sales requires next two quarters to sell
for(j in 2:(n_quarters - 1)) {
  # x_j - x_{j-1} ≤ x_{j+1}
  constraints[[length(constraints) + 1]] <- list(
    ind = c(j-1, j, j+1),
    val = c(-1, 1, -1),
    dir = "<=",
    rhs = 0
  )
  # x_j - x_{j-1} ≤ x_{j+2} (only if j+2 exists)
  if(j <= n_quarters - 2) {
    constraints[[length(constraints) + 1]] <- list(
      ind = c(j-1, j, j+2),
      val = c(-1, 1, -1),
      dir = "<=",
      rhs = 0
    )
  }
}

# Constraints for last quarter: must sell in Qn-1 and Qn-2 if selling in Qn
constraints[[length(constraints) + 1]] <- list(ind = c(n_quarters-1, n_quarters), val = c(-1, 1), dir = "<=", rhs = 0) # xn ≤ xn-1
constraints[[length(constraints) + 1]] <- list(ind = c(n_quarters-2, n_quarters), val = c(-1, 1), dir = "<=", rhs = 0) # xn ≤ xn-2

# Convert constraints into matrix format for Rglpk
constraint_matrix <- matrix(0, nrow = length(constraints), ncol = n_quarters)
constraint_dir <- character(length(constraints))
constraint_rhs <- numeric(length(constraints))

for(i in seq_along(constraints)) {
  constraint_matrix[i, constraints[[i]]$ind] <- constraints[[i]]$val
  constraint_dir[i] <- constraints[[i]]$dir
  constraint_rhs[i] <- constraints[[i]]$rhs
}

# Define variable types (all binary)
var_types <- rep("B", n_quarters)

# Solve the linear program
solution <- Rglpk_solve_LP(
  obj = profit_per_quarter,
  mat = constraint_matrix,
  dir = constraint_dir,
  rhs = constraint_rhs,
  types = var_types,
  max = TRUE # We want to maximize profit
)

# Print results
cat("Maximum Profit:", solution$optimum, "\n")
cat("Optimal Sales Quarters:", which(solution$solution == 1), "\n")

Step 3: Verify the solution #

In this example, the optimal solution will be selling in Q2, Q3, Q4 (total profit 15+20+12=47), which is a valid 3-quarter continuous run. Any invalid runs (like Q1+Q2 only, or Q3 only) will be blocked by the constraints.

What if you have more quarters? #

This code scales easily—just adjust n_quarters and profit_per_quarter to match your data. The loops will automatically handle the middle quarters as long as n_quarters ≥3 (if n_quarters <3, the constraint is impossible to satisfy unless you choose no sales at all).

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