时间戳

首页 > 解决方案 > 从 Pulp 和 Linprog 获得不同的结果

python - 从 Pulp 和 Linprog 获得不同的结果

问题描述

我是线性编程的新手，我尝试了 Pulp 和 (SciPy) Linprog。每个给我不同的结果。

我认为这可能是因为 Linprog 使用的是内点法，而 Pulp 可能使用的是单纯形法？如果是这样，有没有办法让 Pulp 产生与 Linprog 相同的结果？

import pulp
from pulp import *
from scipy.optimize import linprog

# Pulp

# Upper bounds
r = {1: 11, 2: 11, 3: 7, 4: 11, 5: 7}

# Create the model
model = LpProblem(name="small-problem", sense=LpMaximize)

# Define the decision variables
x = {i: LpVariable(name=f"x{i}", lowBound=0, upBound=r[i]) for i in range(1, 6)}

# Add constraints
model += (lpSum(x.values()) <= 35, "headroom")

# Set the objective
model += lpSum([7 * x[1], 7 * x[2], 11 * x[3], 7 * x[4], 11 * x[5]])

# Solve the optimization problem
status = model.solve()

# Get the results
print(f"status: {model.status}, {LpStatus[model.status]}")
print(f"objective: {model.objective.value()}")

for var in x.values():
    print(f"{var.name}: {var.value()}")

for name, constraint in model.constraints.items():
    print(f"{name}: {constraint.value()}")

# linprog

c = [-7, -7, -11, -7, -11]
bounds = [(0, 11), (0, 11), (0, 7), (0, 11), (0, 7)]
A_ub = [[1, 1, 1, 1, 1]]
B_ub = [[35]]
res = linprog(c, A_ub=A_ub, b_ub=B_ub, bounds=bounds)
print(res)

上面代码的输出：

status: 1, Optimal
objective: 301.0
x1: 10.0
x2: 0.0
x3: 7.0
x4: 11.0
x5: 7.0
headroom: 0.0
     con: array([], dtype=float64)
     fun: -300.9999999581466
 message: 'Optimization terminated successfully.'
     nit: 4
   slack: array([4.60956784e-09])
  status: 0
 success: True
       x: array([7., 7., 7., 7., 7.])

额外的问题：在给定一些约束的情况下，我将如何制定一个我想最大化 x[i] 值的问题？上面我试图最大化 x[i] 的总和，但想知道是否有更好的方法。

标签： pythonscipylinear-programmingpulp

解决方案

正如@Erwin Kalvelagen 在评论中已经指出的那样，并非所有 LP 都有独特的解决方案。在您的情况下，您有两组变量{x1, x2, x4}，并且{x3, x5}在所有情况下都具有相同的系数。

在您的情况下，最好使用最大可能值，x3, x5并且在您的约束中仍然可用的 35 是x1, x2, x4任意分布的（因为它对目标没有影响）。

请注意，您的纸浆解决方案是基本解决方案，而您的 scipy 解决方案不是。是的，这可能是因为两者使用不同的算法来解决问题。

推荐阅读