ゲーム理論NEXT 線形計画問題第2回 -双対問題と双対定理-
みなさんこんにちは、こんばんは。S.Kと申します。
こちらは動画を紹介しつつ、プログラミングも見せていきます。
今回は双対問題になります。「コアの存在条件に出てくる最適化問題の双対問題を考えていく」という目的のため、その前提となる双対問題の作成の仕方を説明しています。あと、かなり重要な双対定理の紹介ですね（証明は次回以降）
では、まずは動画/スライドをご覧ください。
動画とスライド
ニコニコ動画
Youtube
スライドシェア
Pythonで実装（コード例とおまけの可視化）
前回の続きです。ほとんど解説してないですけど、大丈夫かな・・・。
これ、主問題から自動的に双対問題作れれば良いのですが。
ひとまず自分で作成した双対問題をPuLPで解きます。
動画・スライドにあった問題と回答：
コード例：
#Dual problem
problem_1=LpProblem('Dual problem', LpMinimize)
y = LpVariable.dicts('y', ([0,1]), None, None,'Continuous') #変数名prefix, リスト, 最小値, 最大値, 連続
problem_1 += 18*y[0]+52*y[1]
problem_1 += 3*y[0]+2*y[1]>=10000
problem_1 += 2*y[0]+8*y[1]>=20000
problem_1 += y[0]>=0
problem_1 += y[1]>=0
print(problem_1)
status = problem_1.solve()
print(Fraction(y[0].value()).limit_denominator(10))
print(Fraction(y[1].value()).limit_denominator(10))
print(value(problem_1.objective))結果：
Dual problem:
MINIMIZE
18*y_0 + 52*y_1 + 0
SUBJECT TO
_C1: 3 y_0 + 2 y_1 >= 10000
_C2: 2 y_0 + 8 y_1 >= 20000
_C3: y_0 >= 0
_C4: y_1 >= 0
VARIABLES
y_0 free Continuous
y_1 free Continuous
2000
2000
140000.0前回の主問題と同じ最適値140000になっています。これが双対定理で保証されてるわけです。
手計算と同じ結果です（間違えてなくてよかった…）。
おまけ：図で見る
お気づきかと思いますが、この記事のヘッダー画像です。
交点の座標を出すように修正しました。
参考文献
いいなと思ったら応援しよう！
