Help us understand the problem. What is going on with this article?

線形計画問題を 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
Why do not you register as a user and use Qiita more conveniently?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away