无意设施的位置覆盖

Question

我正在尝试使用纸浆：

这是我的代码，因为结果是一个问题，因为结果是我的代码，应该仅保留第二个位置：

    # Import PuLP modeler functions
        from pulp import *
        
        # Set of locations J
        Locations = ["A", "B","C"]

        # Set of demands I
        Demands = ["1", "2", "3", "4", "5"]
        
        #  Set of distances ij
        dt = [  # Demands I
            # 1 2 3 4 5
            [2, 23, 30, 54, 1],  # A   Locations J
            [3, 1, 2, 2, 3],  # B
            [50,65,80,90,100] # C distances are very long
        ]
        
        # Max value to get covered
        s = 5
        
        # Theses binaries values should be generated by code from the dt array ... I write it down directly for simplification. 
        # Demand I is served by location J If distance is <= 5 (  0 = KO , 1 = OK)
        covered = [
            [1,0,0,0,1],
            [1,1,1,1,1] # This shows that we only need Location B , not A
            [0,0,0,0,0] # This shows we can't use Location C, it's too far
        ]
        
        # Creates the 'prob' variable to contain the problem data
        prob = LpProblem("Set covering", LpMinimize)
        
        # # Problem variables 
        J = LpVariable.dicts("location", Locations, cat='Binary')
        
        # The distance data is made into a dictionary
        distances = makeDict([Locations, Demands], covered, 0)
        
        # The objective function 
        # Minimize J, which is the number of locations
        prob += lpSum(J["A"]+J["B"]+J["C"])  
        
        # The constraint
        # Is it covered or not ?
        for w in Locations:
            for b in Demands:   
                if(distances[w][b] > 0): 
                    prob += int(distances[w][b]) * J[w]  >= 1
        
        # Or eventually this instead : 
        #for w in Locations:
        #  prob += (lpSum([distances[w][b] * J[w] for b in Demands]) >= 1)

        # or that :
        # prob += 1 * J["A"] >= 1
        # prob += 1 * J["A"] >= 1
        # prob += 1 * J["B"] >= 1
        # prob += 1 * J["B"] >= 1
        # prob += 1 * J["B"] >= 1
        # prob += 1 * J["B"] >= 1
        # prob += 1 * J["B"] >= 1

        
        # The problem data is written to an .lp file
        prob.writeLP("SetCovering.lp")
        
        # The problem is solved using PuLP's choice of Solver
        prob.solve()
        
        # The status of the solution is printed to the screen
        print("Status:", LpStatus[prob.status])
        
        # Each of the variables is printed with it's resolved optimum value
        for v in prob.variables():
            print(v.name, "=", v.varValue)
        
        # The optimised objective function value is printed to the screen
        print("Total Locations  = ", value(prob.objective))
        
        # Show constraints
        constraints = prob.constraints
        print(constraints)
        
        



#Status: Optimal
#location_A = 1.0
#location_B = 1.0
#location_C = 0.0
#Total Locations  =  2.0

结果应该是：

location_A = 0.0
location_B = 1.0
location_C = 0.0

因为位置B涵盖了我们所有的需求。

我想知道问题在哪里，有数学代码，希望我写的足够：

谢谢，谢谢，如果您有一个解决方案，我还尝试了lpsum没有运气

编辑：对代码进行了一些修改，您可以看到“最佳解决方案”，但这不是我想要的解决方案 + +添加了“ location_c”

edit：这是我的新代码，为ARCS（链接）生成（ser_customer）添加了一个辅助连续纸浆。在这种情况下，求解器只能选择FAC-2，因为它几乎是所有客户，而其他设施太远了：

# Lists (sets / Array) of Customers and Facilities
Customer = [1,2,3,4,5]
Facility = ['Fac-1', 'Fac-2', 'Fac-3']

# Dictionary of distances in kms
distance = {'Fac-1' : {1 : 54, 2 : 76, 3 : 5, 4 : 76, 5 : 76},
            'Fac-2' : {1 : 1, 2 : 3, 3 : 1, 4 : 8, 5 : 1},
            'Fac-3' : {1 : 45, 2 : 23, 3 : 54, 4 : 87, 5 : 88}
            }

# Setting the Problem
prob = LpProblem("pb", LpMinimize)

# Defining our Decision Variables
use_facility = LpVariable.dicts("Use Facility", Facility, 0, 1, LpBinary)
ser_customer = LpVariable.dicts("Service", [(i,j) for i in Customer for j in Facility], 0)

# Setting the Objective Function = Minimize amount of facilities and arcs
prob += lpSum(use_facility['Fac-1']+use_facility['Fac-2']+use_facility['Fac-3']) + lpSum(distance[j][i]*ser_customer[(i,j)] for j in Facility for i in Customer)

# Constraints,At least 1 arc must exist between facilities and customers
for i in Customer:
      prob += lpSum(ser_customer[(i,j)] for j in Facility) >= 1

prob.solve()

# Print the solution of Decision Variables
for v in prob.variables():
    print(v.name, "=", v.varValue)

# Print the solution of Binary Decision Variables
Tolerance = 0.0001
for j in Facility:
    if use_facility[j].varValue > Tolerance:
        print("Establish Facility at site = ", j)

结果似乎显示出良好的弧线（链接），但是没有设施选择，我想知道是否有人有任何想法，是否有任何方法可以强制使用__facity [index]为＆gt; 0，添加ARCS决策变量是个好主意吗？我也试图将弧线作为约束，而不是没有运气的目标函数。 ：

Service_(1,_'Fac_1') = 0.0
Service_(1,_'Fac_2') = 1.0
Service_(1,_'Fac_3') = 0.0
Service_(2,_'Fac_1') = 0.0
Service_(2,_'Fac_2') = 1.0
Service_(2,_'Fac_3') = 0.0
Service_(3,_'Fac_1') = 0.0
Service_(3,_'Fac_2') = 1.0
Service_(3,_'Fac_3') = 0.0
Service_(4,_'Fac_1') = 0.0
Service_(4,_'Fac_2') = 1.0
Service_(4,_'Fac_3') = 0.0
Service_(5,_'Fac_1') = 0.0
Service_(5,_'Fac_2') = 1.0
Service_(5,_'Fac_3') = 0.0
Use_Facility_Fac_1 = 0.0
Use_Facility_Fac_2 = 0.0
Use_Facility_Fac_3 = 0.0

我也尝试了空意的解决方案，我想我也许错过了应该最小化但不知道该怎么做的来源决定变量简单的产品组合，嗨：

 prob = LpProblem('source minimzer', LpMinimize)
dist_limit = 5
sources = ['A', 'B','C']            # the source locations
# note this is zero-indexed to work with the list indexes in dist dictionary...
destinations = list(range(5))   # the demand locations 0, 1, 2, 3, 4   
dist = {    'A': [2, 23, 30, 54, 1],
            'B': [3, 1, 2, 2, 3],
            'C':[24,54,12,56,76]}

covered = LpVariable.dicts('covered', [(s, d) for s in sources for d in destinations], cat='Binary')

# The objective function 
# Minimize  the number of sources
prob += lpSum(covered[s, d]) 

# set up constraint to limit covered if the destination is "reachable"
for s in sources:
    for d in destinations:
        prob += covered[s, d] * dist[s][d] <= dist_limit


# add one more constraint to make sure that every destination is "covered"...

# The problem is solved using PuLP's choice of Solver
prob.solve()

# The status of the solution is printed to the screen
print("Status:", LpStatus[prob.status])

# The optimised objective function value is printed to the screen
print("Location Selection = ", prob.objective)

显示了解决方案，而应该打印“ B”：

Status: Optimal
Total Locations  =  covered_('C',_4)

Answer 1

您在正确的轨道上！几件事会有所帮助...

首先，您忽略了输出中的键信息，因为求解器说您的配方是不可行的！

Status: Infeasible

因此，变量中出现的任何内容都是胡言乱语，您必须首先弄清楚该部分。

那么，为什么不可行？看看您的约束。您正在尝试 force 如果您的距离值为零，则不可能无法正确：

prob += int(distances[w][b]) * J[w]  >= 1

因此，您需要重新格式化！您在这里缺少一个概念。实际上，对于此问题，您需要2个约束。

1. 如果路由太长，
2. 您需要强制涵盖每个目的地，则需要约束源用途的选择。

您还需要一个双重指数的决策变量。为什么？好吧，可以说，来源'a'涵盖了目标1、2； “ B”覆盖2、3、4、5 ....您将能够知道所有目的地都被一个变量“覆盖”，但是您不知道使用了哪些源，因此您需要保持跟踪两者都得到完整的图片。

这是一个开始，还有几个编辑。我建议变量名称source和目标，因为这是标准的。在此特定问题中，您没有特定的需求，只是需要连接。您可能还希望使用词典多于嵌套列表，我认为这更清楚。以下是一个示例以第一个约束开始。在限制覆盖变量时，请注意这里的技巧。如果距离小于限制，则s，则可以满足此约束。例如，如果距离为3：

3 * 1 <= s

无论如何，这是建议的开始。另一个约束未实施。您将需要在所有来源上总结，以确保目的地被“覆盖”。如果您被卡住，请回信。

prob = LpProblem('source minimzer', LpMinimize)
dist_limit = 5
sources = ['A', 'B']            # the source locations
# note this is zero-indexed to work with the list indexes in dist dictionary...
destinations = list(range(5))   # the demand locations 0, 1, 2, 3, 4   
dist = {    'A': [2, 23, 30, 54, 1],
            'B': [3, 1, 2, 2, 3]}

covered = LpVariable.dicts('covered', [(s, d) for s in sources for d in destinations], cat='Binary')
# set up constraint to limit covered if the destination is "reachable"
for s in sources:
    for d in destinations:
        prob += covered[s, d] * dist[s][d] <= dist_limit

# add one more constraint to make sure that every destination is "covered"...