線形計画法の相補性定理

質問

線形計画法の相補性定理

線形計画法の相補性定理が分かりません。
意味も良く分かりませんし、なので証明も分かりません。
相補性定理とはどういう意味のものかと、意義、その証明を分かりやすく教えてくだされば幸いです。

回答No.2

Tacosan · ベストアンサー

えっと, 双対問題の変数のことを双対変数といいます. で, 工場での生産計画を LP に書くと主問題の制約は資源に対応し, 従って双対変数も資源に対応します. 双対変数は「その資源を増やすとどのくらい利益が増加するのか」を表す値で shadow price とも呼ばれます.
でここまでわかると「主問題の制約と双対変数との間の相補性」は簡単に理屈がつきます. つまり, 最適解において
・余っている資源は (増やしても利益は増加しないので) shadow price は 0
・shadow price が正の資源は (余っていると利益が増加し, 従って最適であることに反するので) ぴったり使いきっている
ということを意味しています.

お礼

返事が非常に遅くなってしまい申し訳ありません！
本をちゃんと読み直すことにより、相補性定理の代数的な証明自体はすぐ理解できました。
意味がやはり良くわからなかったのですが、shadow priceについて教えて頂き、意味自体も理解することもできました。
お陰で相補性の意味自体も理解できました。
ありがとうございます。

回答No.1

Tacosan

双対変数の意味がわからないと相補性定理も理解できないんじゃないかなぁ.... 逆に, 双対変数の意味が分かれば相補性定理も納得できると思う.
「工場でどのように製品を作るか」を線形計画法で考えましょうって話 (参考にあげた URL の [例1.1] みたいなやつ) は導入のところでよくやるんだけど, 聞いたことはありますか?

参考URL：

http://www.sist.ac.jp/~suganuma/kougi/other_lecture/SE/opt/linear/linear.htm

お礼

ありがとうございます。
URLのような問題は聞いたことが有ります。
どの本を読んでも工場計画問題は最初に触れられていたと思います。
双対変数は初めて聞きました。
双対問題の変数ベクトルyのことでしょうか？