線形計画問題を Python + Google OR-Tools で解いて潜在価格を調べる

線形計画問題(Linear Programming: LP)を勉強すると必ずついてくる「潜在価格」の話がありますが，Google OR-Toolsの線形計画ソルバー(Glop)ではこれをさくっと取り出すことができます。
潜在価格は，双対価格とかShadow Priceとか言われることもあります。

たとえば，制約式のオブジェクトconstraint1に対して

pi1 = constraint1.DualValue()

とすると潜在価格が取得できます。

OR-Tools公式のサンプルをほぼそのまま写して，そのうしろに，3つある制約式それぞれの潜在価格を書き出してみます。潜在価格の変数にはよく$\pi$を使うのでそんな雰囲気でprintしてみます。

from ortools.linear_solver import pywraplp

def main():
    """線形計画問題のサンプル"""
    # ソルバーのインスタンスを生成
    solver = pywraplp.Solver('LP1', pywraplp.Solver.GLOP_LINEAR_PROGRAMMING)

    # LPの変数を宣言
    x = solver.NumVar(0, solver.infinity(), 'x')  # コピペ元と違うけど
    y = solver.NumVar(0, solver.infinity(), 'y')  # なんとなく非負制約を付けたくなる…

    # 制約 0: x + 2y <= 14.
    constraint0 = solver.Constraint(-solver.infinity(), 14)
    constraint0.SetCoefficient(x, 1)
    constraint0.SetCoefficient(y, 2)

    # 制約 1: 3x - y >= 0.
    constraint1 = solver.Constraint(0, solver.infinity())
    constraint1.SetCoefficient(x, 3)
    constraint1.SetCoefficient(y, -1)

    # 制約 2: x - y <= 2.
    constraint2 = solver.Constraint(-solver.infinity(), 2)
    constraint2.SetCoefficient(x, 1)
    constraint2.SetCoefficient(y, -1)

    # 目的関数: maximize 3x + 4y.
    objective = solver.Objective()
    objective.SetCoefficient(x, 3)
    objective.SetCoefficient(y, 4)
    objective.SetMaximization()

    # 求解開始
    solver.Solve()

    print('変数の個数 =', solver.NumVariables())
    print('制約の個数 =', solver.NumConstraints())

    # 最適解を取得
    print('最適解:')
    print('目的関数値 =', solver.Objective().Value()) # 目的関数値はこれでも取れる
    print('x = ', x.solution_value())
    print('y = ', y.solution_value())

    # 各制約式の潜在価格を取得
    print('潜在価格:')
    print('Pi_0 =', constraint0.DualValue())
    print('Pi_1 =', constraint1.DualValue())
    print('Pi_2 =', constraint2.DualValue())


if __name__ == "__main__":
    main()

実行結果です。

変数の個数 = 2
制約の個数 = 3
最適解:
目的関数値 = 33.99999999999999
x =  5.999999999999998
y =  3.9999999999999996
潜在価格
Pi_0 2.333333333333333
Pi_1 -0.0
Pi_2 0.6666666666666661