具有附加约束的运输问题

Question

我正在尝试使用 PuLP 包解决运输问题。在我的例子中，它略有修改并且有额外的限制。假设有 7 个供应商 [s1、s2、s3、s4、s5、s6、s7] 和 6 个目的地 [d1、d2、d3、d4、d5、d6]。每个目的地的需求是 1。每个供应商的供应是 3。

目前执行情况：

capacity=3
suppliers,targets = cost.shape
    objective = LpProblem("Optimize_allocation",LpMinimize)
    x = LpVariable.dicts("assignment", product(range(suppliers), range(targets)), 0, 1)
    objective += lpSum(cost[i, j] * x[i, j] for i in range(suppliers) for j in range(targets))
    
    for j in range(targets):
        condition1 = lpSum( x[i, j] for i in range(suppliers)) == 1
        objective+= condition1
    for i in range(suppliers):
        condition2 = lpSum(x[i, j] for j in range(targets)) <= capacity
        objective+= condition2  
    
    objective.solve(PULP_CBC_CMD(msg=0))

我的其他限制是，目的地 (d3,d4) 将只接受来自一个供应商（可以是其中任何一个）的货物，并且该供应商应该只为他们提供服务，而不应向任何其他目的地提供服务。如果我将它们与需求 2 组合到一个目的地并平均可行的成本，但我如何确保约束的后半部分？这只是一个示例案例，但在我的实际问题中，可能有多个目的地相互组合并要求相同的约束示例：(d1,d2) 和 (d5,d6,d3)。

编辑：根据@kabdulla 的回答更新为以下工作代码，但最后一个约束已更改。

suppliers = 10
targets = ['A','B','C','D','E','F','G','H','I']
grps = [['A','B','C'],['D'],['E'],['F','G'],['H','I']] #constraint groups
groups = [[0, 1, 2], [3], [4], [5, 6], [7, 8]] #constraint group ids
capacities = [3, 1, 1, 2, 2]
capacity = 3
cost = np.random.rand(suppliers,len(targets))
objective = LpProblem("Optimize_allocation",LpMinimize)
x = LpVariable.dicts("assignment1", product(range(suppliers), range(len(targets))), 0, 1,'Integer')
y = LpVariable.dicts("assignment2", product(range(suppliers), range(len(groups))), 0, 1,'Integer')
objective += lpSum(cost[i, j] * x[i, j] for i in range(suppliers) for j in range(len(targets)))

    
for j in range(len(targets)):
    objective+= lpSum( x[i, j] for i in range(suppliers)) == 1
     
    
for i in range(suppliers):
    objective+= lpSum(x[i, j] for j in range(len(targets))) <= capacity
     

for i in range(suppliers):
    for k in range(len(groups)):
        objective += lpSum(x[i,j] for j in groups[k]) <= y[i,k]*capacities[k]
        
    
for k in range(len(groups)):
    objective += lpSum(y[i,k] for i in range(suppliers)) == 1


for i in range(suppliers):
    objective+= lpSum(y[i, j] for j in range(len(groups))) <= 1

objective.solve()

Answer 1

首先观察 - 您的 x[i, j] 变量（从供应商 i 到目标 j 的供应数量）是连续的 - 表明可以运送一小部分单位。如果这不是本意，这些 x 需要设为整数（cat='Integer' 调用 LpVariable.dicts()）。

如果我正确理解了您的附加限制条件，则存在一些目标节点的“独家供应”集 E_k。在其中一组中：

所有供应必须来自单个供应商节点
该供应商不得向集外的任何节点提供

要执行这种逻辑，您将需要一些二进制变量（如果您的 x 变量是不连续的并且限制在 [0,1] 范围内（即它们是二进制的），您可能是可以直接使用）。我假设你的 x 是连续的。

解决这个问题的一种方法是引入新的二进制变量y[i, k]，当且仅当供应商i是选择的独家供应商来设置k。

假设您还声明了属于相同排他供应集的目标节点列表列表E您可以添加所需的约束，如下所示：

for i in suppliers:
    for k in range(len(E)):
        objective += lpSum(x[i,j] for j in E[k]) <= y[i, k]*M[k]

其中 M[k] 足够大以至于当 y[i,k] 为 1 时它们不会添加额外的约束（例如，这可能只是 k 中节点的需求总和独家供应套装

然后您可以对 y[i,k] 变量强制执行所需的约束 - 即每个集合 k 必须只有一个供应商：

for k in range(len(E)):
    objective += lpSum(y[i, k] for i in suppliers) == 1

最后你需要添加一个约束，如果供应商 i 正在服务独占集 k（即 y[i,k] == 1），则不允许他们提供任何不在其中的节点那一组：

for i in suppliers:
    for k in range(len(E)):
        objective += lpSum(x[i, j] for j in targets if j not in E[k]) <= \
                       (1 - y[i,k])*N[k]

其中 N[k] 足够大以至于当 y[i,j] == 0 时它们不会添加额外的约束（例如可能是不在第 k 个独家供应中的节点的需求总和设置。

具有附加约束的运输问题

Transportation problem with additional constraints

python

optimization

pulp