Python linprog 最小化错误——单纯形法

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)

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&nbsp;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&nbsp;X: [ 377.22836393&nbsp; 748.5144238&nbsp; 1874.25721154]

Answer 2

使用单纯形法的linprog确实存在一些问题。我发现超过15个案件溶于Matlab的，但不能要解决linprog用。也可以通过传递来解决。但通常的单纯形方法更受欢迎。希望能修好。"method=simplex""method=interior-point"