scipy.optimize 中的 linprog - 检查解决方案
linprog in scipy.optimize - checking solution
我尝试使用 scipy.optimize
中的 linprog
求解具有约束的线性系统,但得到的答案与一些不等式相矛盾。
这是我的设置:
import numpy as np
from scipy.optimize import linprog
c = np.array([1,0,0,0,0,0,0])
A_ub = np.identity(7)*(-1)
b_ub = np.array([[-2],[-2],[-2],[-2],[-2],[-2],[-2]])
A_eq = np.array([[1,1,1,1,1,1,0],[0.3,1.3,0.9,0,0,0,-1],[0.3,0,0,0,0,0,-2/3],
[0,0.65,0,0,0,0,-1/15],[0,0,0.3,0,0,0,-1/15]])
b_eq = np.array([[100],[0],[0],[0],[0]])
res = linprog(c = c, A_ub=A_ub, b_ub=b_ub, A_eq = A_eq, b_eq = b_eq)
答案如下:
fun: -0.0
message: 'Optimization terminated successfully.'
nit: 15
slack: array([ -2., -2., -2., 94., 0., 0., -2.])
status: 0
success: True
x: array([ 0.00000000e+00, -8.88178420e-16, -1.77635684e-15,
9.60000000e+01, 2.00000000e+00, 2.00000000e+00,
-7.10542736e-15])
如你所见x_2 => 8.88178420e-16
不小于-2。
有人可以解释为什么会这样吗?
这里是 link 文档:
linprog
总的来说,scipy 的 linprog (method='simplex'
) 有点损坏,不再维护了。
消极的休闲裤如:
slack: array([ -2., -2., -2., 94., 0., 0., -2.])
永远不会产生有效的解决方案!
虽然我在 linprog 中看到了一些不好的东西(没有找到现有的可行解决方案),但这看起来非常非常糟糕(声称不可行的解决方案是正确的)!
所以三件事:
- scipy >= 1.0 有一个新的基于内点的 LP 求解器
method='interior-point'
,它更强大、更先进
- 算法方面非常不同!
- 对于像您这样的用例,唯一的区别(除了稳健性和性能之外)在于解决方案的性质:
- 不保证是基本解决方案(不支持交叉;商业求解器允许)!
- 使用边界参数而不是那些不等式来描述变量边界!
- 更专业的处理!
- 您描述了:
-x <= -2 <-> x >= 2
- 预期的正确解决方案是
x >= 2
!
您的代码上的 IPM:
con: array([ 2.77992740e-10, -1.52664548e-11, 3.69659858e-12, -5.92570437e-12,
-2.37077025e-12])
fun: 43.3333333331385
message: 'Optimization terminated successfully.'
nit: 5
slack: array([4.13333333e+01, 6.92779167e-13, 2.33333333e+00, 1.47777778e+01,
1.47777778e+01, 1.47777778e+01, 1.75000000e+01])
status: 0
success: True
x: array([43.33333333, 2. , 4.33333333, 16.77777778, 16.77777778,
16.77777778, 19.5 ])
我尝试使用 scipy.optimize
中的 linprog
求解具有约束的线性系统,但得到的答案与一些不等式相矛盾。
这是我的设置:
import numpy as np
from scipy.optimize import linprog
c = np.array([1,0,0,0,0,0,0])
A_ub = np.identity(7)*(-1)
b_ub = np.array([[-2],[-2],[-2],[-2],[-2],[-2],[-2]])
A_eq = np.array([[1,1,1,1,1,1,0],[0.3,1.3,0.9,0,0,0,-1],[0.3,0,0,0,0,0,-2/3],
[0,0.65,0,0,0,0,-1/15],[0,0,0.3,0,0,0,-1/15]])
b_eq = np.array([[100],[0],[0],[0],[0]])
res = linprog(c = c, A_ub=A_ub, b_ub=b_ub, A_eq = A_eq, b_eq = b_eq)
答案如下:
fun: -0.0
message: 'Optimization terminated successfully.'
nit: 15
slack: array([ -2., -2., -2., 94., 0., 0., -2.])
status: 0
success: True
x: array([ 0.00000000e+00, -8.88178420e-16, -1.77635684e-15,
9.60000000e+01, 2.00000000e+00, 2.00000000e+00,
-7.10542736e-15])
如你所见x_2 => 8.88178420e-16
不小于-2。
有人可以解释为什么会这样吗?
这里是 link 文档: linprog
总的来说,scipy 的 linprog (method='simplex'
) 有点损坏,不再维护了。
消极的休闲裤如:
slack: array([ -2., -2., -2., 94., 0., 0., -2.])
永远不会产生有效的解决方案!
虽然我在 linprog 中看到了一些不好的东西(没有找到现有的可行解决方案),但这看起来非常非常糟糕(声称不可行的解决方案是正确的)!
所以三件事:
- scipy >= 1.0 有一个新的基于内点的 LP 求解器
method='interior-point'
,它更强大、更先进- 算法方面非常不同!
- 对于像您这样的用例,唯一的区别(除了稳健性和性能之外)在于解决方案的性质:
- 不保证是基本解决方案(不支持交叉;商业求解器允许)!
- 使用边界参数而不是那些不等式来描述变量边界!
- 更专业的处理!
- 您描述了:
-x <= -2 <-> x >= 2
- 预期的正确解决方案是
x >= 2
!
- 预期的正确解决方案是
您的代码上的 IPM:
con: array([ 2.77992740e-10, -1.52664548e-11, 3.69659858e-12, -5.92570437e-12,
-2.37077025e-12])
fun: 43.3333333331385
message: 'Optimization terminated successfully.'
nit: 5
slack: array([4.13333333e+01, 6.92779167e-13, 2.33333333e+00, 1.47777778e+01,
1.47777778e+01, 1.47777778e+01, 1.75000000e+01])
status: 0
success: True
x: array([43.33333333, 2. , 4.33333333, 16.77777778, 16.77777778,
16.77777778, 19.5 ])