切割库存优化：在R语言中查找全部可行切割组合的技术咨询

Absolutely! For your specific cutting stock problem (stock length 100, cut sizes 14, 31, 36, 45), you can generate all 37 feasible patterns using a straightforward brute-force approach (perfect for small problem sizes) or more optimized methods for larger cases. Here's how to do it step-by-step:

Brute-force Approach (Ideal for Small Instances) #

The core task is to find all non-negative integer solutions to this inequality:

14x₁ + 31x₂ + 36x₃ + 45x₄ ≤ 100
where x₁, x₂, x₃, x₄ represent the number of each cut size in a pattern, and we exclude the trivial all-zero pattern (since it doesn't use any stock).

Step-by-Step Code #

# Define your problem parameters
cut_sizes <- c(14, 31, 36, 45)
stock_length <- 100

# Calculate maximum possible counts for each cut size (floor division)
max_counts <- floor(stock_length / cut_sizes)

# Generate every possible combination of cut counts
all_combinations <- expand.grid(
  x1 = 0:max_counts[1],
  x2 = 0:max_counts[2],
  x3 = 0:max_counts[3],
  x4 = 0:max_counts[4]
)

# Compute total length used for each combination
all_combinations$total_used <- with(all_combinations, 
  x1*cut_sizes[1] + x2*cut_sizes[2] + x3*cut_sizes[3] + x4*cut_sizes[4]
)

# Filter valid patterns (non-zero usage, total length ≤ stock length)
valid_patterns <- all_combinations[all_combinations$total_used > 0 & all_combinations$total_used <= stock_length, ]

# Extract just the count columns (optional, for clean output)
pattern_matrix <- as.matrix(valid_patterns[, 1:4])

# Verify the number of valid patterns
nrow(pattern_matrix) # Should return 37, matching your reference

Explanation #

• We first calculate the maximum number of each cut size that could fit in the stock (e.g., 7 pieces of 14-length, since 7*14=98 ≤100).
• expand.grid generates every possible combination of these counts, ensuring we don't miss any potential pattern.
• We filter out invalid combinations: those that use no stock (all zeros) or exceed the stock length.
• The final result includes all 37 feasible patterns, like your examples [1,0,1,1] (14+36+45=95) and [0,0,0,2] (45*2=90).

For Larger Problems #

If you're working with bigger stock lengths or more cut sizes, brute-force becomes inefficient due to exponential growth in combinations. For these cases, you can use integer programming libraries like lpSolve or ROI to generate feasible solutions iteratively, or combinatorial optimization packages to prune invalid combinations early. However, for your specific problem, the brute-force method is simple and efficient enough.

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