python - PuLP（线性规划）LpMaximize 如何选择最优解？

Question

我在 Python 中使用 PuLP 并使用 LpMaximize 最大化决策变量。假设我有几种组合，每种组合都有特定的点。在这种情况下，决策变量是“点”，因为点是我想要最大化的。我这个练习的预期目标是找到最高点的组合。我的代码：

prob = LpProblem("Allocation",LpMaximize)

alloc_vars = LpVariable.dicts("Allocation",combinations,0,1,LpBinary)

prob += lpSum(binary.loc[i]["points"]*alloc_vars[i] for i in combinations)

for j in vendors:
prob += lpSum([alloc_vars[i]*binary.loc[i][j] for i in combinations]) == 1

#"binary" is a matrix file/dataframe that's commonly used in PuLP solver

prob.solve()
print("Status: ", LpStatus[prob.status])

var_output = []
for i in alloc_vars:
for j in vendors:
    var_output += [{
        'Vendor': j,
        'Combination': i,
        'Allocation': alloc_vars[i].varValue*binary.loc[i][j],
    }]

[i for i in var_output if i['Allocation']==1]

value(prob.objective)

selected_combinations = set([i['Combination'] for i in var_output if i['Allocation']==1])

样本输入：（这只是虚拟数据）

| Combination | Vendor 1 | Vendor 2 | Vendor 3 | Vendor 4 | Points |  A  |  B  |  C  |  D | 
|   Comb1     |     A    |          |          |          |   73   |  1  |  0  |  0  |  0 |
|   Comb2     |     B    |          |          |          |   54   |  0  |  1  |  0  |  0 |  
|   Comb3     |     C    |          |          |          |   47   |  0  |  0  |  1  |  0 |
|   Comb4     |     D    |          |          |          |   89   |  0  |  0  |  0  |  1 |
|   Comb5     |     A    |     B    |          |          |   73   |  1  |  1  |  0  |  0 |
|   Comb6     |     B    |     A    |          |          |   -43  |  1  |  1  |  0  |  0 |
|   Comb7     |     D    |     C    |   A      |          |   111  |  1  |  0  |  1  |  1 |
...
...
...

作为输出，我得到最大点的组合。我不确定这些组合是如何选择的。作为一个极端情况，我有一个输入数据框，其中所有组合都有 0 点，但在运行 PuLP 求解器后仍然得到一些组合。所以这让我想知道，纸浆如何找到哪个组合会给出最高分？

标签： pythonlinear-programmingpulp