Scipy Linprog - 没有给出预期的解决方案

Question

我有一组简单的线性方程，正在使用 sciprog 求解。 Objective函数是最小化x(i)*c.

其中：

c定义如下（常量）

i 范围从 1 到 28

我也有等式约束（14 个方程），我可能需要一个解决方案。事实上，解决方案非常简单。 excel 中提到了预期的解决方案。但是当我使用 linprog 来解决这个问题时，它失败了。有什么理由要检查吗？

from scipy.optimize import linprog

A_eq = [[1211.881188118812, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0],
        [0.0, 0.0, 3599.9999999999995, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0],
        [0.0, 0.0, 0.0, 0.0, 0.0, 2006.5573770491803, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0],
        [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 2185.714285714286, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0],
        [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 2147.3684210526317, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0],
        [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 290.04739336492895, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0],
        [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 382.5, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0],
        [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 181.87221396731056, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0],
        [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 382.5, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0],
        [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 291.4285714285714, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0],
        [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 382.5, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0],
        [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0],
        [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1224.0, 0.0, 0.0],
        [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 3599.9999999999995, 0.0]
        ]

b_eq = [0, 0, 1397.8722944969109, 1215.3540665438804, 0, 1217.8280665438817,
        177.21022795303054, 1217.8280665438822, 177.21022795303054, 177.21022795303048,
        177.21022795303054, 0, 0, 0]

c = [50,27]*14

sol = linprog(c = c, A_eq = A_eq, b_eq = b_eq, bounds = (0, None))
#sol
#Out[138]: 
#     fun: 1210.4060665438813
# message: 'Optimization failed. Unable to find a feasible starting point.'
#     nit: 13
#  status: 2
# success: False
#       x: nan

最初我认为，这可能是 A14:AB14 造成的，因此将所有系数从 0 替换为 1。但结果仍然相同。有什么线索吗？

Answer 1

改为使用内点法（众所周知，单纯形求解器相当不可靠——这不是归咎于单纯形法，而是归咎于实施不当）。当然这个模型完全可以在presolve中解决：没有什么需要优化的。

sol = linprog(c = c, A_eq = A_eq, b_eq = b_eq, bounds = (0, None), method='interior-point')

这给出：

     con: array([  0.00000000e+00,   0.00000000e+00,   0.00000000e+00,
         0.00000000e+00,   0.00000000e+00,  -2.27373675e-13,
         0.00000000e+00,   0.00000000e+00,   0.00000000e+00,
         0.00000000e+00,   0.00000000e+00,   0.00000000e+00,
         0.00000000e+00,   0.00000000e+00])
     fun: 381.92688642606663
 message: 'The solution was determined in presolve as there areno non-trivial constraints.'
     nit: 0
   slack: array([], dtype=float64)
  status: 0
 success: True
       x: array([ 0.        ,  0.        ,  0.        ,  0.        ,  0.        ,
        0.69665204,  0.        ,  0.55604434,  0.        ,  0.        ,
        0.        ,  4.19872095,  0.        ,  0.46329471,  0.        ,
        6.69606445,  0.        ,  0.46329471,  0.        ,  0.60807431,
        0.        ,  0.46329471,  0.        ,  0.        ,  0.        ,
        0.        ,  0.        ,  0.        ])

Scipy Linprog - 没有给出预期的解决方案

Scipy Linprog - not giving expected solution

python

optimization

scipy

linear-programming