使用R lpSolve包开发自动排班工具遇最优解问题求助

Hey there, let's troubleshoot why your scheduling tool isn't meeting the demand requirements. I see a couple of key issues with your current code that are causing those supply-demand gaps, and I'll walk you through fixing them step by step.

Key Issues in Your Current Code #

1. Incorrect Objective Direction & Function
   You're using lp("max", obj.fun, ...) with an objective function of all 1s. This tells the solver to maximize the total number of shifts, which is the opposite of your goal to minimize the gap between supply and demand. Instead, you want to minimize either the total number of shifts or the total supply hours (whichever aligns better with your "minimize total supply-demand difference" goal).

2. Backwards Constraint Directions
   Your constraint direction is set to <=, which limits hourly supply to not exceed the demand. That's exactly why you're seeing supply fall short—you're forcing the solver to cap supply below what's needed! You need two sets of constraints:

   • Hourly supply must meet or exceed the demand (>= direction)
   • Hourly supply must not exceed the maximum cap of 46 (<= direction)

Corrected Code #

Let's adjust the code to fix these issues. First, we'll define the correct constraints, then set the right objective:

library(lpSolve)

# Objective function: Minimize total number of shifts
# If you want to minimize total supply hours instead, use the shift_durations vector below
# shift_durations <- c(8,14,2,12,3,10,2,8,5) # Count of hours each shift covers
obj.fun <- c(1,1,1,1,1,1,1,1,1)

# Original constraint matrix (each row = hour, each column = shift, 1 = shift covers this hour)
constr <- matrix(c(
  1, 0, 0, 0, 0, 0, 0, 0, 0,
  1, 0, 0, 0, 0, 0, 0, 0, 0,
  1, 0, 0, 0, 0, 0, 0, 0, 0,
  1, 0, 0, 1, 0, 0, 0, 0, 0,
  1, 0, 0, 1, 0, 1, 0, 0, 0,
  1, 0, 0, 1, 0, 1, 0, 1, 0,
  1, 0, 0, 1, 0, 1, 0, 1, 0,
  1, 0, 0, 1, 0, 1, 0, 0, 1,
  0, 1, 0, 1, 0, 1, 0, 1, 0,
  0, 1, 0, 1, 0, 1, 0, 1, 0,
  0, 1, 0, 1, 0, 1, 0, 1, 0,
  0, 1, 0, 0, 1, 1, 0, 1, 0,
  0, 1, 0, 0, 1, 0, 1, 1, 0,
  0, 1, 0, 0, 1, 0, 1, 0, 1,
  0, 1, 0, 1, 0, 1, 0, 1, 0,
  0, 1, 0, 1, 0, 1, 0, 0, 1,
  0, 1, 0, 1, 0, 1, 0, 1, 0,
  0, 1, 0, 1, 0, 1, 0, 1, 0,
  0, 1, 0, 1, 0, 1, 0, 1, 0,
  0, 1, 0, 0, 0, 1, 0, 1, 0,
  0, 1, 0, 0, 0, 0, 0, 1, 0,
  0, 1, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 1, 0, 0, 0, 0, 0, 0,
  0, 0, 1, 0, 0, 0, 0, 0, 0
), nrow = 24, byrow = TRUE)

# Combine two sets of constraints: supply >= demand, supply <= 46
constr_combined <- rbind(constr, constr)
constr.dir <- c(rep(">=", 24), rep("<=", 24))
constr.val <- c(c(24, 20, 21, 22, 26, 34, 40, 44, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 41, 27), rep(46, 24))

# Solve for minimum number of shifts (use "min" instead of "max")
day.shift <- lp("min", obj.fun, constr_combined, constr.dir, constr.val, compute.sens = TRUE)

# Get the optimal shift counts
day.shift$solution

# Calculate hourly supply to verify
hourly_supply <- constr %*% day.shift$solution
hourly_supply

What This Fixes #

• Constraint Logic: Now we ensure every hour's supply meets or exceeds the demand, while also capping supply at 46 as required.
• Objective Alignment: By minimizing the total number of shifts, we naturally minimize the gap between total supply and total demand (since we're using the fewest shifts possible to meet requirements).

Optional: Refine the Objective #

If your top priority is minimizing the hourly supply-demand gaps (not just total shifts), you could adjust the objective to minimize the sum of excess supply. This would require introducing slack variables for each hour's excess, but that adds complexity. For most scheduling cases, minimizing total shifts is a practical starting point that aligns with your goal.

After running this corrected code, check the hourly_supply vector—you should see that every hour meets or exceeds the demand, without exceeding the 46 cap.

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