在 scipy linprog 中高效获取影子价格

Question

我有一个巨大的 linprog 问题，几乎有 1k 个变量和限制。我可以用 scipy.optimize.linprog(method='simplex') 计算解决方案，但我需要 ~100 个不等式的影子价格（或机会成本）。

我可以通过在不等式的右边加 1 然后求解该问题来计算它们。然后我得到影子价格减去两个解决方案的 objective 函数值：shadow_price_i = f_max_original - f_max_i。然后重复100次。此方法有效，但速度非常慢 (1h)。

我可以做些什么来更快地获得影子价格？也许我缺少一些技巧或功能...

Answer 1

解决对偶问题，只需再调用一次 linprog，即可获得所有影子价格。以下是标准 LP 问题的示例：

import scipy.optimize as opt
import numpy as np

c = np.array([400, 200, 250])     # negative of objective function
b = np.array([1000, 300, 625])    # constraint bounds
A = np.array([[3, 1, 1.5],
              [0.8, 0.2, 0.3],
              [1, 1, 1]])        # constraints
x1_bnds = (0, None)     # bounds on x1
x2_bnds = (0, None)     # bounds on x2
x3_bnds = (0, None)     # bounds on x3
result = opt.linprog(-c, A_ub=A, b_ub=b, bounds=(x1_bnds, x2_bnds, x3_bnds))

dual_c = b
dual_b = -1.0 * c
dual_A = -1.0 * np.transpose(A)
result = opt.linprog(dual_c, A_ub=dual_A, b_ub=dual_b,
                     bounds=(x1_bnds, x2_bnds, x3_bnds))

在 scipy linprog 中高效获取影子价格

Efficiently get shadow prices in scipy linprog

python

scipy

linear-programming