Python中线性规划最小化错误 - 单纯形法

Question

我正在使用scipy.optimize.linprog库来使用单纯形法计算最小化。我有两种情况出现错误: "ValueError: 单纯形法第1阶段未能找到可行解。 拟伪目标函数的值为3.1e-12，超过了将解视为足够接近零以成为基本解所需的公差1e-12。考虑将公差增加到大于3.1e-12。如果此公差不可接受，则可能问题无解。 也许有人可以找到问题所在。

Minimaze:     45x1 + 54x2 + 42x3 + 36x4

Subject to:   x1 + x2 + x3 + x4 = 1600
              30x1 + 60x2 + 70x3 + 80x4 = 100000
              30x1 + 40x2 + 0x3 + 20x4 = 30000

我编写的代码：

A = np.array([[-30, -60, -70, -80], [-30, -40, 0, -20], [-1, -1, -1, -1]])
b = np.array([-100000, -30000, -1600])
c = np.array([45, 54, 42, 36])

res = linprog(c, A_eq=A, b_eq=b, bounds=(0, None))

这是第二个例子：

Minimize:     100x1 + 50x2 + 100x3

Subject to:   x1 + x2 + x3 = 3000
              28x1 + 14x2 + 10x3 <= 42000
              10x1 + 12x2 + 6x3 <= 24000
              30x1 + 20x2 + 30x3 >= 75000
              10x1 + 10x2 + 15x3 >= 36000

这是代码：

A_ub = np.array([[28, 14, 10], [10, 12, 6], [-30, -20, -30], [-10, -10, -15]])
b_ub = np.array([42000, 24000, -75000, -36000])
A_eq = np.array([[1, 1, 1]])
b_eq = np.array([3000])
c = np.array([100, 50, 200])

res = linprog(c, A_ub, b_ub, A_eq, b_eq, bounds=(0, None))

print('Optimal value:', res.fun, '\nX:', res.x)

- Dubster

---

请在第一个示例中添加目标函数（最小化：）。它缺失了。 - kcw78

如果我移除等式约束，linprog 就能正常工作。程序告诉你没有一个有效的值集合能够满足所有的约束条件。你应该检查一下。 - Tarifazo

嗯，这两种解决方案都是可行的。@Mstaino - rockikz

Answer 1

我检查了系统并发现解决方案确实可行。在阅读这篇文章后，似乎linprog存在浮点问题，这显然是方法的问题。传递method='interior-point'可以改善算法。

这对我两种情况下都有效：

情况1：

res = linprog(c, A_eq=A, b_eq=b, method='interior-point')
print('Optimal value:', res.fun, '\nX:', res.x)
>> Optimal value: 64090.8624935836 
X: [4.90908724e+02 1.50821194e-05 3.45454303e+02 7.63635788e+02]

案例2：

res = linprog(c, A_ub, b_ub, A_eq, b_eq, bounds=(0, None), method='interior-point')
print('Optimal value:', res.fun, '\nX:', res.x)
#output:
>> Optimal value: 449999.99988966336 
X: [ 377.22836393  748.5144238  1874.25721154]

- Tarifazo

---

你检查了第一案例的状态吗？我得到了 res.status = 4（消息是 The solution does not satisfy the constraints, yet no errors were raised...Otherwise, please enable presolve）。我没有禁用 presolve。我添加了 disp=True 选项以打印收敛消息。它说 Optimization terminated successfully. 我手动检查了约束条件，它们非常接近（<0.1误差）。不确定该怎么处理。 - kcw78

Answer 2

linprog 的 simplex 方法确实存在一些问题。我已经发现了超过15个在 Matlab 中可解但无法通过 "method=simplex" 的 linprog 解决的情况。可以通过传递 "method=interior-point" 来解决它。但通常 simplex 方法更受欢迎。希望能够修复这个问题。

- Robin Pan