基于Pulp构建线性规划：多公司成本单元分配方案咨询

Great question! Since you already have a working two-company binary linear programming model, extending it to handle N companies is straightforward once you adjust a few key parts of your setup. Let’s break this down step by step, building on your existing implementation.

1. Redefine Your Variables #

In your two-company model, you used variables like x1, x2 where each pair represented a single cost unit assigned to either Company A or B. For multiple companies, we’ll switch to a 2-dimensional binary variable to make scaling easier:

• Let x[i][j] = 1 if cost unit i is assigned to company j, and 0 otherwise.
• This way, for M cost units and N companies, you’ll have M*N binary variables (instead of 2*M for two companies).

2. Update the Objective Function #

Your original objective function summed the cost of each binary variable. For multiple companies, you’ll just extend this sum to cover all cost unit-company pairs. For example:

• If cost unit i costs c_ij when assigned to company j, your objective becomes:

  Minimize sum(c_ij * x[i][j] for all i, j)
  

  This directly maps to your original model—you’re just adding more terms for each additional company.

3. Adjust Constraints #

The critical constraint from your two-company model was that each cost unit is assigned to exactly one company. For N companies, this constraint generalizes to:

• For every cost unit i, the sum of x[i][j] across all companies j must equal 1.

  sum(x[i][j] for j in companies) = 1  for each cost unit i
  

  This ensures no cost unit is unassigned or split between multiple companies.

You can also add optional constraints if needed, like:

• Minimum/maximum number of cost units per company (e.g., "each company must handle at least 2 units")
• Budget limits per company (e.g., "total cost for Company A can’t exceed $500")

4. Example Code Implementation #

Here’s how to adapt your existing PuLP code to support 3 companies, using your original cost values as a starting point:

from pulp import LpProblem, LpMinimize, LpVariable, lpSum, value

# Define your companies and cost units
companies = ["A", "B", "C"]
cost_units = ["Unit1", "Unit2", "Unit3"]

# Cost matrix: cost_units -> company -> cost (matches your original values)
cost_matrix = {
    "Unit1": {"A": 20, "B": 30, "C": 25},  # Added a cost for Company C
    "Unit2": {"A": 100, "B": 20, "C": 30}, # Added a cost for Company C
    "Unit3": {"A": 40, "B": 30, "C": 20}   # Added a cost for Company C
}

# Initialize the problem
prob = LpProblem("Multi_Company_Cost_Allocation", LpMinimize)

# Create binary variables: x[unit][company]
allocation_vars = LpVariable.dicts(
    "Allocation",
    (cost_units, companies),
    cat="Binary"
)

# Set objective function: minimize total cost
prob += lpSum(
    cost_matrix[unit][comp] * allocation_vars[unit][comp]
    for unit in cost_units
    for comp in companies
)

# Add core constraint: each unit is assigned to exactly one company
for unit in cost_units:
    prob += lpSum(
        allocation_vars[unit][comp] for comp in companies
    ) == 1, f"Must_Assign_Unit_{unit}"

# Optional: Add constraints like minimum units per company
# for comp in companies:
#     prob += lpSum(allocation_vars[unit][comp] for unit in cost_units) >= 1, f"Min_Units_For_{comp}"

# Solve the problem
prob.solve()

# Print results
print("Optimal Allocation:")
for unit in cost_units:
    for comp in companies:
        if value(allocation_vars[unit][comp]) == 1:
            print(f"Cost Unit {unit} → Company {comp} (Cost: ${cost_matrix[unit][comp]})")

print(f"\nTotal Cost: ${value(prob.objective):.2f}")

Key Takeaways #

• The core logic of your original model stays intact—we’re just scaling the variable space and constraints to accommodate more companies.
• Using a 2-dimensional variable structure makes it easy to add/remove companies without rewriting large parts of your code.
• You can extend this further with custom constraints (like budget caps or workload limits) by adding additional linear equations to the problem.

内容的提问来源于stack exchange，提问作者Valberto Enoc Rodrigues