- ベストアンサー
線形計画法の相補性定理
- みんなの回答 （2）
- 専門家の回答
質問者が選んだベストアンサー
えっと, 双対問題の変数のことを双対変数といいます. で, 工場での生産計画を LP に書くと主問題の制約は資源に対応し, 従って双対変数も資源に対応します. 双対変数は「その資源を増やすとどのくらい利益が増加するのか」を表す値で shadow price とも呼ばれます. でここまでわかると「主問題の制約と双対変数との間の相補性」は簡単に理屈がつきます. つまり, 最適解において ・余っている資源は (増やしても利益は増加しないので) shadow price は 0 ・shadow price が正の資源は (余っていると利益が増加し, 従って最適であることに反するので) ぴったり使いきっている ということを意味しています.
その他の回答 (1)
- Tacosan
- ベストアンサー率23% (3656/15482)
双対変数の意味がわからないと相補性定理も理解できないんじゃないかなぁ.... 逆に, 双対変数の意味が分かれば相補性定理も納得できると思う. 「工場でどのように製品を作るか」を線形計画法で考えましょうって話 (参考にあげた URL の [例1.1] みたいなやつ) は導入のところでよくやるんだけど, 聞いたことはありますか?
お礼
ありがとうございます。 URLのような問題は聞いたことが有ります。 どの本を読んでも工場計画問題は最初に触れられていたと思います。 双対変数は初めて聞きました。 双対問題の変数ベクトルyのことでしょうか？
関連するQ&A
- 線形計画法の解について！
線形計画法の解、シャドウ価格の求め方がわからなくて、困っています。 問題は、以下のとおりです。 （線形計画法とシャドウ価格） 次の線形計画法の解、各制約のシャドウ価格を求めなさい。 制約条件 2x＋y≦7, x＋3y≦6, x≧0,y≧0 のもとで、目的関数 Z＝x＋y を最大化せよ。
- ベストアンサー
- 数学・算数
- 非線形計画法について
非線形計画法を現在勉強しています。 １． どういうときに線形でどういうときに非線形となるのか良く分かりません。 例えば、ある従属変数ｙを線形関数ｆ＝Σcx で表したいときにパラメータｃの絶対値の和が定数ｂより小さくなるという制約のもとで、ｙとｆの二乗誤差を最小化するパラメータｃを求める問題を考えます。 この場合、制約条件はｃについて線形ですが、最小化したいのは、ｙとｆの二乗誤差なのでこの場合は非線形ということになるのでしょうか？それとも関数ｆはｃに関して線形関数なので、線形計画法で解くことになるのでしょうか？ ２． 以下のサイトで勉強しているのですが、このサイトにある楕円型の等高線はおそらく、従属変数ｙと目的関数ｆの誤差を表しているのだと思うのですが、なぜ「楕円」になるのですか？二乗誤差を考えるのならば、「円」になるのではと疑問で仕方ありません。 http://www.sist.ac.jp/~suganuma/kougi/other_lecture/SE/opt/nonlinear/nonlinear.htm#2.2 疑問が晴れずにもやもやしています。 回答もしくはアドバイス、よろしくお願いします。
- 締切済み
- 数学・算数
- 「線型代数学の基本定理」はどうして「基本」？
「線型代数学の基本定理」という定理がありますが、どうしてこの定理が「基本」を名乗れるような立場なのか教えてください。 https://ja.wikipedia.org/wiki/線型代数学の基本定理 私自身はデータアナリストで、行列演算等で線形代数は仕事でもよく使うのですが、この「基本定理」とやらに直接助けられた記憶はありません。 人類への貢献という観点では、例えば方程式や最適化の求解といった面で、世界を支えている定理が他にもたくさんあると思うのですが。。。 ・「線型代数学の基本定理」がなぜ「基本」と呼ばれるようになったのか、由来をご存知であれば教えてください。 ・「線型代数学の基本定理」の特にすごい応用（キラーアプリケーション）をご存知であれば教えてください。工学的な応用でも、「こんなすごい定理を証明できる」という数学的な応用でも構いません。 よろしくお願いします。
- ベストアンサー
- 数学・算数
- 線形計画問題を単体法を使って解く問題です。
タブローを使ってとこうとしたのですが制約式にx_2の項がない場所があったため0で割れず行き詰まってしまいました。 解答も解説もなく行き詰まっているため、親切な方詳しい解答・解説をおねがいします。 主問題 Max 2x_1+3x_2+x_3 s.t.x_1+x_2+x_3≦1 -2x_1+x_3≧1 x_1,x_2,x_3≧0 1)単体法を用いて解き、最適解と最適値を過程を記し求めよ。 2)双対問題を記し、1)の結果と相補性定理を用いて最適解を求めよ。 3)ある非負の実数kを用いて主問題の目的関数を(2+k)x_1+3x_2+x_3と変化させた線形計画問題をP'とする（制約式は同じ） 1)で求めた最適解がP'の最適解で在り続けるためのkの範囲を求めよ。
- 締切済み
- 数学・算数
- 線形計画法の解法について！
線形計画法の解き方が判らなくて困っています。 判らないこと 1.制約条件の式と計算値 2.目的関数の式と目的値 線形計画法は変数と制約条件と目的関数が与えられます。 制約条件を満足し、目的関数が最大（最小）となる変数を求めます。 線形計画法の例 変数 x y 制約条件 (A) 10x + 4y ≦ 360 (B) 4x + 5y ≦ 200 (C) 2x + 10y ≦ 300 (D) x ≧ 0 (E) y ≧ 0 目的関数 M = 7x+12y A,B,C,D,Eの条件を満足し目的関数(M)が最大となる変数x,yを求めます。
- ベストアンサー
- 数学・算数
- 経営科学の線形計画法、教えてください
線形計画法のシンプレックス法で、問題を解くために不等式であらわされた制約条件式を、わざわざ余裕変数を用いて等式条件にするのはどうしてですか？
- 締切済み
- その他（学問・教育）
- 線型計画法問題
線型計画法、についての質問なんですが。 海外の大学に通ってるので問題は英語です。 Write linear programming formulation for the shortest path problem. 誰か知ってる人がいればお願いします。できれば少し説明も添付されればありがたいです。
- 締切済み
- その他（プログラミング・開発）
お礼
返事が非常に遅くなってしまい申し訳ありません！ 本をちゃんと読み直すことにより、相補性定理の代数的な証明自体はすぐ理解できました。 意味がやはり良くわからなかったのですが、shadow priceについて教えて頂き、意味自体も理解することもできました。 お陰で相補性の意味自体も理解できました。 ありがとうございます。