Python linprog 最小化错误 - 单纯形法
Python linprog minimization error - simplex method
我正在使用 scipy.optimize.linprog 库来计算使用单纯形法的最小化。我有两种情况出现错误:
"ValueError: 单纯形法的第 1 阶段未能找到可行的解决方案。伪 objective 函数的计算结果为 3.1e-12,超出了 1e-12 的要求公差对于要考虑 'close enough' 为零的解决方案是基本解决方案。考虑将公差增加到大于 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)
查了系统,确实可行。看了this post,好像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]
linprog 与 simplex 方法确实存在一些问题。我发现超过 15 个案例可以在 Matlab 中解决,但无法通过 linprog 和 "method=simplex"
解决。也可以通过"method=interior-point"
来解决。但通常单纯形法更受欢迎。希望修复。
我正在使用 scipy.optimize.linprog 库来计算使用单纯形法的最小化。我有两种情况出现错误:
"ValueError: 单纯形法的第 1 阶段未能找到可行的解决方案。伪 objective 函数的计算结果为 3.1e-12,超出了 1e-12 的要求公差对于要考虑 'close enough' 为零的解决方案是基本解决方案。考虑将公差增加到大于 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)
查了系统,确实可行。看了this post,好像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]
linprog 与 simplex 方法确实存在一些问题。我发现超过 15 个案例可以在 Matlab 中解决,但无法通过 linprog 和 "method=simplex"
解决。也可以通过"method=interior-point"
来解决。但通常单纯形法更受欢迎。希望修复。