- ベストアンサー
双対問題について教えてください。
- みんなの回答 （3）
- 専門家の回答
質問者が選んだベストアンサー
双対問題は1変数になりますよ． s-125-_-さんがどういう知識をお持ちなのか書かれていないので答えにくいのですが，一般の線形計画問題について記します． まず表記について書きます． ・ベクトル・行列の転置を^Tであらわします． ・ベクトル間の不等号をつぎのように導入します． n次元のベクトルx, yについて， x ≧ y <=> x_i ≧ y_i (i=1, ..., n)． （対応する要素間に不等号の関係が成り立つということ． 例：(x y z)^T ≧ (1 2 3)^T <=> x≧1かつy≧2かつz≧3） このとき，n次元ベクトルx,c，m×n行列A，m次元ベクトルbについての線形計画問題 最小化： c^T x 制約条件：Ax ≦ b x ≧ 0 を主問題とすると， 双対問題は，m次元ベクトルyと，主問題とおなじA, b, cについての線形計画問題 最大化： y^T b 制約条件：y^T A ≧ c^T y ≧ 0 となります． ご質問の問題は，c = (3 2 1 -1 2)^T, x = (x_1 x_2 x_3 x_4 x_5)^T, A = (1 3 2 1 1), b = (3) で，双対問題は 最大化：3y 制約条件：y(1 3 2 1 1) ≧ (3 2 1 -1 2) y ≧ 0 となります．
その他の回答 (2)
- killer_7
- ベストアンサー率57% (58/101)
失礼．最小と最大を逆に書いてしまいました． すべて逆に読み替えてください．
- Mr_Holland
- ベストアンサー率56% (890/1576)
自信はないけど、次のようになるのでは？ ｃT＝（-3 -2 -1 1 -2） Ａ＝（-1 -3 -2 -1 -1） ｂ＝-3 ／ -y1 ＼ ／ -3 ＼ ｜ -3y2 ｜ ｜ -2 ｜ ｜ -2y3 ｜ ≦ ｜ -1 ｜ ｜ -y4 ｜ ｜ 1 ｜ ＼ -y5 ／ ＼ -2 ／ 行列をはずすと、y1≧3, 3y2≧2, 2y3≧1, y4≧-1, y5≧2 ここで、yi≧0, i=1,2,3,4,5だから、 制約条件： y1≧3, y2≧2/3, y3≧1/2, y4≧0, y5≧2 また、最大化はyT bだから、 最小化： 3y1+3y2+3y3+3y4+3y5 行列が見にくいかもしれないけど、等角フォントにすればなんとか見られるかも。
お礼
丁寧に教えてくださってありがとうございました。 とてもわかりやすかったです。 参考URLまで載せてくださって本当にありがとうございました。
関連するQ&A
- なぜ、双対問題（双対性）を考えるのですか？
現在、線形計画法を勉強中で、よくわからないことがあります。 例えばこのような問題があるとしまして、 主問題 max Z = 6X1 + 4X2（例えば収益を最大にしたい…） s.t. 2X1 + X2 =< 70 3X1 + 4X2 =< 180 X1,X2 => 0 双対問題 min W = 70Y1 + 180Y2（例えば費用を最小にしたい…） s.t. 2Y1 + 3Y2 => 6 Y1 + 4Y2 => 4 Y1,Y2 => 0 主問題の最適な目的関数値 Z と、 双対問題の最適な目的関数値 W は、必ず一致することは、 シンプレックス法で実際に解いて確認できます。できました。 （参考書として読んでいる本の、標準形での証明・説明はいまいちわかりませんでした…。） ですが、 なんらかの収益を最大にしたい…という問題を定式化して解けば、 その収益を最大にしたいときの最適解・最適値を求められるなら 主問題の方だけ充分ではないのでしょうか？ 上記の式の例ですと式の規模(？)に大した違いはないですが、 問題によって、双対問題に作り直した方が計算しやすい？ といったようなメリットがあるのですか？ なぜ、双対問題を考えるのか、どなたか分かりやすく教えて頂けませんでしょうか。
- ベストアンサー
- 数学・算数
- 非線形計画法 主-双対問題
次のような制約付き最小化問題を考えています。 目的関数は非線形です。 min x1^2+x2^2 s.t. -x1-x2+4<=0 x1>=0 x2>=0 この問題の場合最適解は(x1,x2)=(2,2)であり、その時の目的関数値は8となります。 次に次式のような双対問題を考えます。 g(x)=-x1-x2+4とおき 双対関数 φ(u)=inf{x1^2+x2^2+u*(-x1-x2+4) : x1>=0 , x2>=0} =inf{x1^2-u*x1 : x1>=0}+inf{x2-2-u*x2 : x2>=0}+4*u 上記においてもしu>=0であれば、x1=x2=(u/2). （なぜなら、x1^2-u*x1をx1で微分するとx1=u/2となる。） u<0であるならばx1=x2-0であることに注目しますと。 φ(u)=-(1/2)*u^2+4*u for u>=0 =4u for u<0 となります． 双対関数がu>0の場合は最大がu=4であることに注目すると、その時の目的関数は8であり、主問題と双対問題の最適な目的関数値は一緒となります。 次に主問題を次のように制約を増やした最小化問題を考えます。 min x1^2+x2^2 s.t. -x1-x2+4<=0 -2*x1-3*x2<=0 x1>=0 x2>=0 これの最適解は上記の問題と同じにならないといけないのですが、 例えば、ラグランジュ関数F(x1,x2,λ1,λ2)を次のようにおき各変数で偏微分して最適解を求めると（λ：ラグランジュ乗数）、 F(x1,x2,λ1,λ2)=x1^2+x2^2+λ1*(-x1-x2+4)+λ2*(-2*x1-3*x2) 最適解はx1=12, x2=-8であり、その時の目的関数は208となり、前問と異なった解が得られました。 この原因は明確であり、ラグランジュ関数の中の各制約式が、偏微分して解を得ることで不等式制約ではなく等式制約とみなされたためです。 偏微分して解を求めなければいいのですが、どうしても偏微分でかいを求めたいために、、前門で示した双対問題を導入しましたが、結果は双対問題のほうでも偏微分するので一緒でした。 しかし、双対問題で得られた解。つまりuは主問題のλに相当し、KKT条件より必ず正である必要があるので、双対問題を解き、uが負になった制約式はの除いてそのあともう一度問題を解きなおす。つまり２番目の問題を前問に置き換える。 っといったことをして問題を解決させようとかんがえていますが、これは理論的に正しいのでしょうか。 これはほんの例題ですが、複数個の不等式制約式を扱い、かつ偏微分可能な最適化問題を解く際に、最適解に対して全てが有効制約になるとは限りませんので、どうかうまくいくアドバイスをください。
- 締切済み
- 数学・算数
- 数理計画法の双対問題の解法について
私は現在、以下のような問題に取り組んでおります。 問題：次の線形計画問題の双対問題を解け。 minimize: z = 2x1+3x2+8x3 2x1+2x2+6x3 ≥ 6 x1+2x2+4x3 ≥ 4 x1,x2,x3 ≥ 0 私はこの双対問題のシンプレックス表を用いて解く方法が分かりません。 どなたか解答・解説をお願いします。
- 締切済み
- 数学・算数
- 線形計画問題の双対問題について疑問
線形計画問題の双対問題について疑問 主問題 minimize 2x1 + 5x2 sublect to 3x1 + x2 <=3 2x1 + x2 >=5 x1, x2>=0 の双対問題はどうなるのですか？ たとえば、 主問題 minimize 2x1 + 5x2 sublect to 3x1 + x2 >=3 2x1 + x2 >=5 x1, x2>=0 なら、 双対問題 maximaize 3y1 + 5y2 sublect to 3y1 + 2y2 <=2 y1 + y2 <=5 y1, y2>=0 となるということはわかるんですが・・・・ よろしくお願いします。
- 締切済み
- その他（学問・教育）
- 確率の問題で困っています
こんにちは。 確率と統計の問題で苦戦しています。 問題は 当たる確率がp(0<p<1)のくじをn回引いたとき、あたりの出る回数を確率変数Xとする。 Xの期待値と分散、標準偏差を求めなさい。また、分散が（ｐの関数と見たとき）最大になるｐの値を求めなさい。ただし、くじが当たる確率は互いに独立であるとする。 なお、i回目に引いたくじの結果を確率変数Xiで表すものとし、当たりであればXi=1、はずれであればXi=0とすれば、X=X1+X2+・・・+Xnである。 というものです。 毎回行き詰ってしまうので、模範解答をよろしくお願いします。
- ベストアンサー
- 数学・算数
- 最大化・最小化問題について
Max and Min x^2-2xy+2y^2 suject to x^2+y^2=1 (-∞＜x,y＜∞） 以下の設問に答えよ。 （１）最大・最小化問題をできるだけ多くの方法で解け （２）最小化問題に対する逆問題（i)、および最大化問題に対する逆問題（Ｉ）を述べて、それぞれ解け。 （３）最小化問題に対する双対問題(d)、および最大化問題に対する双対問題（Ｄ）を述べて、それぞれ解け。 上記のような問題なのですが、（１）は三角関数に置き換えて解けたのですが（２）（３）の逆問題、双対問題がよくわからず、手のつけようがありません。 また、（１）についても他に解き方があれば、教えていただけないでしょうか。（どんなマニアックな回答でも大歓迎です） どなたか宜しくお願い致します。
- 締切済み
- 数学・算数
- 【至急!!】線形計画問題教えてください。
次の問題を双対シンプレックス法により解け。 minimize 15x1+7x2+12x3 sub to x1x+2x+x3≧1 3x1+x2+x3≧2 x1,x2,x3≧0 双対シンプレックス法での解き方がいまいち分かりません。 双対シンプレックス法での解き方が分かる方教えてください(>_<)
- ベストアンサー
- 数学・算数
- 大学数学の質問です
R^4上の関数 f(X1,X2,X3,X4):=X1 X2^2 X^3 X^4 は連続なので、 R^4の有界閉集合D:={(X1,X2,X3,X4)∈R^4 | Xi≧0 (1≦i≦4), ∑(1≦i≦4) Xi≦1} において最大値を持つ。 この最大値をとる点p∈Dについて、次の問いに答えよ。 (1) 点pがDの内部 Di:={(X1,X2,X3,X4)∈R^4 | Xi＞0 (1≦i≦4), ∑(1≦i≦4) Xi＜1}に属すると仮定して、矛盾を導け (2) よってpはDの境界 δD:=D／Di 上にある。 このpを求め、fのDにおける最大値を求めよ。 という問題が分かりません 解説よろしくお願いします。
- 締切済み
- 数学・算数
お礼
基本から丁寧に教えてくださってありがとうございました。 確認してみて理解することができました。 本当に感謝です。