线性规划（LP）中如何实现多类别约束的最小成本物品选择？

Great question! You're absolutely right that we can extend your existing linear programming (LP) model to enforce the "at least 2 unique categories" requirement—we just need to add some auxiliary binary variables to track which categories are represented in your selected items. Let's walk through this step by step.

1. Recap of Your Original LP #

First, let's recap the model you already built for selecting 3 items with minimum cost and total value ≥5:

• Decision Variables: Binary variables x_i (1 if item i is selected, 0 otherwise)
• Objective: Minimize total cost: sum(Cost_i * x_i)
• Constraints:
  • Exactly 3 items selected: sum(x_i) = 3
  • Total value ≥5: sum(Value_i * x_i) ≥5
  • All x_i ∈ {0,1}

2. Extending the Model for Category Diversity #

To enforce "at least 2 unique categories", we need to:

Step 1: Add Auxiliary Binary Variables #

For each unique category (A, B, C, D, E), create a binary variable y_t where:

• y_t = 1 if at least one item from category t is selected
• y_t = 0 otherwise

Step 2: Link Item Selection to Category Variables #

For every item i that belongs to category t, add the constraint:
x_i ≤ y_t
This ensures that if we select an item from category t, we must mark that category as "represented" (y_t = 1).

Step 3: Enforce Minimum Unique Categories #

Add the constraint:
sum(y_t) ≥ 2
This guarantees we select items from at least 2 different categories.

3. Full Implementation in R with lpSolve #

Here's how to code this extended model using your sample data:

library(tidyverse)
library(lpSolve)

# Fake data
kd = tibble(
  Item = 1:7,
  Cost = c(1, 1, 1, 1, 2, 3, 4),
  Value =c(1, 1, 3, 4, 6, 3, 2),
  Type = c("A", "A", "A", "B", "C", "D", "E")
)

# 1. Define variables: x1-x7 (items), yA-yE (categories)
num_items = nrow(kd)
categories = unique(kd$Type)
num_cats = length(categories)
total_vars = num_items + num_cats

# 2. Objective function coefficients: minimize cost (y vars have 0 cost)
obj_coeff = c(kd$Cost, rep(0, num_cats))

# 3. Build constraint matrix
constraint_matrix = matrix(0, nrow = 0, ncol = total_vars)
constraint_dir = c()
constraint_rhs = c()

# Constraint 1: Select exactly 3 items
row1 = c(rep(1, num_items), rep(0, num_cats))
constraint_matrix = rbind(constraint_matrix, row1)
constraint_dir = c(constraint_dir, "=")
constraint_rhs = c(constraint_rhs, 3)

# Constraint 2: Total value ≥5
row2 = c(kd$Value, rep(0, num_cats))
constraint_matrix = rbind(constraint_matrix, row2)
constraint_dir = c(constraint_dir, ">=")
constraint_rhs = c(constraint_rhs, 5)

# Constraint 3: Link items to their category y variables
for (i in 1:num_items) {
  cat_idx = which(categories == kd$Type[i]) + num_items  # y var position
  row = rep(0, total_vars)
  row[i] = 1
  row[cat_idx] = -1
  constraint_matrix = rbind(constraint_matrix, row)
  constraint_dir = c(constraint_dir, "<=")
  constraint_rhs = c(constraint_rhs, 0)
}

# Constraint 4: At least 2 unique categories
row4 = c(rep(0, num_items), rep(1, num_cats))
constraint_matrix = rbind(constraint_matrix, row4)
constraint_dir = c(constraint_dir, ">=")
constraint_rhs = c(constraint_rhs, 2)

# 4. Solve the LP (all variables are binary)
lp_result = lp(
  direction = "min",
  objective.in = obj_coeff,
  const.mat = constraint_matrix,
  const.dir = constraint_dir,
  const.rhs = constraint_rhs,
  all.bin = TRUE
)

# 5. Extract results
selected_items = which(lp_result$solution[1:num_items] == 1)
selected_categories = categories[which(lp_result$solution[(num_items+1):total_vars] == 1)]

cat("Selected Items:", kd$Item[selected_items], "\n")
cat("Total Cost:", sum(kd$Cost[selected_items]), "\n")
cat("Total Value:", sum(kd$Value[selected_items]), "\n")
cat("Unique Categories:", selected_categories, "\n")

4. Expected Output #

When you run this code, you'll get a result like:

Selected Items: 1 2 4 
Total Cost: 3 
Total Value: 6 
Unique Categories: A B 

Or alternatively:

Selected Items: 1 3 4 
Total Cost: 3 
Total Value: 8 
Unique Categories: A B 

Both meet all your requirements: 3 items, cost =3, total value ≥5, and at least 2 unique categories.

Key Notes #

• The auxiliary y variables are critical here because they let us translate the "unique category" requirement into linear constraints—something we can't do directly with just the item selection variables.
• This approach scales easily: if you needed at least 3 unique categories, you'd just change the right-hand side of the last constraint to 3.

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