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

Question

我有一个巨大的 linprog 问题，几乎有 1k 个变量和限制。 我可以用

scipy.optimize.linprog(method='simplex')

计算解决方案，但我需要约 100 个不等式的影子价格（或机会成本）。

我可以通过在不等式右边加 1 来计算它们，然后解决该问题。然后我得到影子价格减去两个解决方案的目标函数值：

shadow_price_i = f_max_original - f_max_i

。然后重复100次。此方法有效，但速度慢得令人痛苦（1 小时）。

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

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))

Answer 2

最后一个答案需要稍微补充一下： 也就是说，假设原始问题和约束的形式为正确的对偶设置：

  max c x == min -c x

    A x <= b
    x >= 0

然后

dual_c = b
dual_b = - (-1.0 c) = c
dual_A = -1.0 * np.transpose(A)

因为对偶约束与原始 x 具有相同的符号：

 y' A >= - c' 

然后进入“双重”术语：

   - A' y <= c'
   dual_A' y  <= dual_b