現在、線形計画法を勉強中で、よくわからないことがあります。


例えばこのような問題があるとしまして、

主問題
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 は、必ず一致することは、
シンプレックス法で実際に解いて確認できます。できました。
(参考書として読んでいる本の、標準形での証明・説明はいまいちわかりませんでした…。)

ですが、

なんらかの収益を最大にしたい…という問題を定式化して解けば、
その収益を最大にしたいときの最適解・最適値を求められるなら
主問題の方だけ充分ではないのでしょうか?

上記の式の例ですと式の規模(?)に大した違いはないですが、
問題によって、双対問題に作り直した方が計算しやすい?
といったようなメリットがあるのですか?


なぜ、双対問題を考えるのか、どなたか分かりやすく教えて頂けませんでしょうか。

このQ&Aに関連する最新のQ&A

目的 関数」に関するQ&A: 目的関数

A 回答 (3件)

私も線形計画法で双対性を教わったとき、「だから何なんだ」でした。

しかしラグランジュ乗数法でわかって、線形計画法はその特殊な場合として納得できました。つまり少なくとも私の場合、ラグランジュ乗数法を経由しなければ双対性にどんな意味があるか、わかりませんでした。

f(x) を目的関数、g(x) = 0 を制約条件とすると、最適化問題 min_x {f(x) | g(x)=0} の解は、ラグランジュ関数 L(x,m) := f(x) + m g(x) の鞍点 dL/dx = dL/dm = 0 です。x が主変数、m が双対変数とかラグランジュ乗数と呼ばれるものです。

このとき L を見てわかるのは、最適点においては g を目的関数と思って f を制約条件と思っても x は同じだ、ということです。つまり目的関数と制約条件との役割を入れ替えても解は同じです。

これを制約条件がたくさんある場合に一般化して言うと、最適点において目的関数は制約条件の 1 つと思ってかまわない、ということです。私はこの互換性が双対性の意味だと思ってます。

じゃあ、双対問題を考えると、どんな良いことがあるか?

No.1 で指摘されたように、ラグランジュ乗数、すなわち shadow price の経済的な意味がはっきりします。

主変数がたくさんあって制約条件が少なければ、双対問題の方が変数が少なくできます。すると、主問題より楽に解ける可能性が高いです。

L の鞍点を求めるのに、x に関する最小化と m に関する最大化を交互に行う解法が取れます。(主双対解法と言うのだと思います。)そうすると計算の途中でも「目的関数の最適値における値は、この値とあの値の間 (duality gap) にある」ということが言えます。つまり、とりあえず得られている解が最適解からどれくらい離れているかの評価ができます。

とは言え、最大の利点は先に述べた、目的関数と制約条件とを分けて考える必要がなくなるという、概念の単純化だと思います。「効用の最大化は費用の最小化」だけでも感動的ではないですか?
    • good
    • 0

(´・ω・`)ノこんばんわ


数学者ではありませんが、双対性の問題は電気回路でも出てくるし
どこの分野でもあると思う。
まず双対性の議論をする前に双対性の定義を簡単に

Aという集合があってBという集合がある
Aの中のある性質a,bをa→b b→aに入れ替えたときに
Aで成り立つことがらがBという場所でも成立する場合

AとBに関して a,bに関して双対性があるという風に言うのは
数学の群論だったかな?ではいいます。

人生論なんかでいくとあなたがある場所である経験をしたとします。
別の場所にいったら、今までの経験と対応したものがありそれが成立
していたとしたら、結構いいですよね?また今までの経験で有用だったものが別の場所でも有用であるということになります。

双対問題は今までの経験を新しい状況に対応させるまさに人生そのもの
の理論ではないかと思います。

何か趣旨をはずれていたらすいません。
    • good
    • 2
この回答へのお礼

回答ありがとうございます。

いろいろ考えてみましたが、欲しい答えではない感じです…。

>今までの経験で有用だったものが別の場所でも有用であるということになります。
今までの経験で有用だったもの…主問題の最適値?
別の場所でも有用である…双対問題の最適値?
つまり、主問題の最適値=双対問題の最適値ということでしょうか。
そういうことは一応わかっているつもりです…。

>双対問題は今までの経験を新しい状況に対応させるまさに人生そのものの理論
うーん。。。新しい状況に対応・・・。
最適な目的関数値は一致しますが、
主問題の変数 X と双対問題の変数 Y は表すものが違うんですよね。。。

やはり、抽象的な回答でよくわかりません。ごめんなさい。

お礼日時:2009/12/15 11:31

双対の最適解から潜在価格 (shadow price) がわかるので, 感度分析に使えますね.

この回答への補足

回答ありがとうございます。

潜在価格…。これもよくわからないので質問しようかと思っていました。

>双対の最適解から潜在価格 (shadow price) がわかるので, 感度分析に使えますね.
この潜在価格とは主問題の潜在価格でしょうか?
感度分析についてちょっと調べてみましたが、
感度分析に使えるとどんなメリット等あるのでしょうか?

潜在価格と感度分析についても教えて頂けませんでしょうか。

補足日時:2009/12/15 16:27
    • good
    • 0

このQ&Aに関連する人気のQ&A

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人はこんなQ&Aも見ています

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Q価格COMのサイトより現実に安い商品はあるの!?

価格COMのサイトより現実に安い商品はあるの!?
市販の電気店で電気製品を買う時いくら値切ってもさすがに価格COMの最低金額はとんでもなく値切る事の出来ない市販の電気店!価格COM本当に最低金額?価格COMでの店にあるその気に入った商品を買うのは底値の底値で本当に正解ですか?

Aベストアンサー

一般的に実店舗の店が、人件費や店舗代等のコストカット出来ているネット通販に価格で勝てる事は殆どありません。
例外的に特価品などでネット通販より安く販売している場合もありますが・・・

交渉すれば価格.comの値段まで下げられる、なんてのは、余程でなければ出来ませんから。

ただ、価格.comの底値に関しては、店によっては客寄せ用で、実際に買おうとすると、到着までに時間がかかって、周りの平均額がその値段まで下がった頃にようやく発送、なんて所もありますので十分に注意が必要です。

とは言え、カメラだと、価格.comの最安値よりカメラのキタムラの実店舗の方が安い場合もありますけどね。
目当ての商品があるなら、価格.comでその商品のクチコミみてると、最安値より安く売ってた、なんて情報も稀に入ってきます。

後、価格.comの最安値と実店舗比べる場合は、送料込みの価格で比較しないと駄目ですよ。
送料考えたら実店舗と変わらなかった、なんて場合もある訳ですから。

まぁ、概ね価格.comの最安値が安いって事で良いのでは?

Qx1=(1,1,1),x2=(1,1,-1),x3=(1,-1,-1)をC^3の基底,{y1,y2,y3}がその双対基底でx=(0,1,0)の時,y1(x),y

[問] ベクトルx1=(1,1,1),x2=(1,1,-1),x3=(1,-1,-1)をC^3の基底とする。
{y1,y2,y3}がその双対基底でx=(0,1,0)の時、
y1(x),y2(x),y3(x)を求めよ。

という問題の解き方をお教え下さい。

双対基底とは
{f;fはF線形空間VからFへの線形写像}
という集合(これをV*と置く)において、
V(dimV=nとする)の一組基底を{v1,v2,…,vn}とすると
fi(vj)=δij(:クロネッカーのデルタ)で定めるV*の部分集合
{f1,f2,…,fn}はV*の基底となる。これを{v1,v2,…,vn}の双対基底と呼ぶ。

まず、
C^3の次元は6(C^3の基底は(1,0,0),(0,1,0),(0,0,1),(i,0,0),(0,i,0),(0,0,i))
だと思うので上記のx1,x2,x3は基底として不足してると思うのです(もう3ベクトル必要?)。

うーん、どのようにしたらいいのでしょうか?

Aベストアンサー

>C^3の次元は6(

これが間違え.
「x1=(1,1,1),x2=(1,1,-1),x3=(1,-1,-1)をC^3の基底」
といってるんだから,係数体はRではなく,C.

あとは定義にしたがって,
dualな基底を書き下せばいいだけ.
y1(x1)=1,y1(x2)=y1(x3)=0であって
v=ax1+bx2+cx2と表わせるわけだし,
v=(v1,v2,v3)とすれば,a,b,cはv1,v2,v3で表現できる
#単なる基底変換の問題.

Q価格COMのキャッシュバックについて

1年前、価格COMのキャッシュバックキャンペーンにて、So-netと契約しました。
このキャッシュバックは、価格COMとSo-netで別々にあるのでしょうか?
一年前に契約したのですが、このキャッシュバックに関する資料を紛失したのかありません。
最近、So-netからは1年経過したのでキャッシュバックすると連絡がありました。
当時の資料がないため、これで全てか、または価格Comからもあるのかがわかりません。
もし、価格COMのキャッシュバックがあるのであれば、どのような方法であるのでしょうか?ユーザである私から連絡を取る必要があるのでしょうか?

よろしくお願いします。

Aベストアンサー

自分は価格.COMからniftyを申し込みましたが、キャッシュバックのお金は銀行振り込みでした。事前にniftyからメールが来て振込み先の確認をしてから指定日に銀行振り込みでした。So-netも法人でしょうから銀行振り込みだと思いますが。

Qx*y=log(e^x+e^y)と定義すると、(x*y)+z=(x+z)*(y+z)

x、y∈Rに対して
x*y=log(e^x+e^y)
と定義すると、
(x*y)+z=(x+z)*(y+z)
が成り立ちます。
分配法則の*と+を逆にしたような感じですが、この*から何かしらの代数的な事実が従うのでしょうか?
この*の意味は何なのでしょうか?

x*x=aのとき、x=√aと定めと、
√(a*b)≧(a+b)/2
といった相加相乗平均の関係の類似は成り立つようですが。

Aベストアンサー

e^x=X, e^y=Y, e^z=Z と置いて考えましょう。
e^(x*y)=e^x+e^y → Z=X+Y
e^(x+y)=e^x*e^y → Z=X*Y
つまり、正の数の加算と乗算になります。

>分配法則の*と+を逆にしたような感じですが

まさにその通りです。入れ替えて見てください。

>√(a*b)≧(a+b)/2

通常の相加相乗平均とは逆ですね。

Q価格com.の値段

エアコンを買おうと思っています。価格com.で売れ筋と値段を調べたら、かなり安いのがあって近所の量販店に行ってみましたが、そんな値段で売ってるところはありません。
価格com.の値段はどのようなものなのでしょうか?どのように参考にしたらよいのでしょうか。

Aベストアンサー

そりゃそうですよ。
価格コムなどネット通販のお店は、基本的に店頭販売していないです。店舗を持たない分安いのです。
ですがエアコンは買ったら終わりではなく、設置が必要です。個人での設置は難しいですよね? 家電量販店だと、大抵は設置料込の値段表示になっていますが、ネット通販はエアコン本体の価格のみで、設置費用は入っていません。
本体だけ安く買っても、設置だけを電気屋に依頼すると、工賃が高くなります。
トータルでどちらがよいか、よく考えてみてください。

Q線形です (1)を x+3y-2z=0 x-2y+4z=0 x^2+y^2+z^2=1をもちいて 答

線形です
(1)を
x+3y-2z=0
x-2y+4z=0
x^2+y^2+z^2=1をもちいて
答えが+-の答えになりました
(2)では外せきが8,-6,-5となり
おおきさの5ルート5で割ると
+-の答えにはなりませんでした
どちらが正しいのでしょうか?

Aベストアンサー

外積からでてきた単位べクトルは、外積の定義から、ベクトルa、bに垂直ですよね。
だからそれと正反対のベクトルも、ベクトルa、bに垂直な単位ベクトルだから、これも答えに入れれば
よいのです。つまり外積から出した単位ベクトルの各成分に(-1)をかけた成分のベクトルも答えに
なります。そしてこうして出した2つのベクトルは、先に内積で出した2つのベクトルと一致します。

Q価格comでのプロバイダー選び

引越しのため新しくネットの接続の契約をしようと思っています

現在は、ケーブルネットを利用しています。
今までに、ビビックとYAHOO.BBを利用した事があります。

今回、NTTのフレッツ光にしようと思っていますが、色々なキャンベーンを総合して
実質月額使用料で考えると、価格com経由が圧倒的に安い
しかも、ほとんどオプションなしで相応のキャッシュバックがついています。
他の窓口は、光電話やひかりTVなどなど色々なオプションを付けないと、大きなキャッシュバックになりません。

価格COMの説明に、プロバイダーからの利益を還元しているための様な事を書いてありまが
その通りに受け取っていいのでしょうか?

NTTのホームページから申し込むより、価格COM経由で申し込んだほうが、格段に安いのかが納得できません。

Aベストアンサー

私も価格コム経由で契約しました。
結構なキャッシュバックがありましたので満足です。

あまり気にせずに申し込めば良いと思いますよ。
プロバイダが独自にキャンペーンやるより価格コムの方が圧倒的にユーザーが多いので、キャッシュバックも多いのだろうと思います。
(価格コムも掲載料くらいしか取ってないのでは?)
まあ実際にお金はもらえるし、プロバイダもキチンとしているし問題無いでしょう。

Qx+y+z=3 x^2+y^2+z^2=9のとき、4xyの最大値 最

x+y+z=3 x^2+y^2+z^2=9のとき、4xyの最大値 最小値はいくらになりますか x、y、zは実数

Aベストアンサー

言いたくはないけど、何でもかんでも微分と言うのはやめようよ。

いずれにしても、zは不要になる。

x+y=a、xy=bとすると、実数条件から a^2-4b≧0 ‥‥(1)
とすると、条件は a+z=3 x^2+y^2+z^2=(x+y)^2-2xy+z^2=a^2-2b+z^2=9 からzを消すと b=a^2-3a ‥‥(2)
(1)と(2)から、0≦a≦4 ‥‥(3) 4xy=4b=4(a^2-3a)=4(a-3/2)^2-9 これはaの2次関数だから (3)の範囲で考えると -9≦4xy≦16。
但し、最大値と最小値を与えるxとyの値は?

Qソフトバンク携帯を価格COMで購入すると安いでしょうか?

ドコモを現在使用しています。
評判や電波状況が悪いのは承知しての質問です。

価格COMで0円携帯を見かけました。
現在販売奨励金はないはず。どうして0円なのでしょうか?
ソフトバンク携帯を購入する場合はどこで購入しても同じなのでしょうか?それとも、価格COMが安いでしょうか?

今日、店に見に行く予定です。
早急に回答下さい。

Aベストアンサー

スーパーボーナスに加入することを条件として機種代金が毎月の支払いが実質0円になる機種のことです。
注意が必要なのは26ヶ月契約の縛りがあるので途中解約するとスーパーボーナスの特典がない通常の機種料金残高を支払う必要が出てくることと
0円携帯は少し古い機種になってしまうということです。
最新機種で0円というのはありませんし、価格comだろうがどこで購入しても同じです。
(店によってはSDカードが無料で貰えるなんてのはあるでしょうが)

Q3x^2+7xy+2y^2-5x-5y+2=(x+2y-1)(3x+y-2)について

3x^2+7xy+2y^2-5x-5y+2を因数分解せよという問題で、xについて整理し、3x^2+(7y-5)x+(y-2)(2y-1)という方針で解いていくやり方と、
yについて整理し、2y^2+(7x-5)y+(x-1)(3x-2)という方針で解いていくとき方の2通りありますが、どちらで解く習慣を身につけておいた方がよろしいでしょうか?

Aベストアンサー

xやyのどちらの文字で整理するかで決めるのでなく、
次数の低い方、
その文字の現れる項数が少ない方
両方とも同じなら最高次の係数が小さい方
の文字に着目して整理して解くのが基本かと思います。

例題の場合はx,yについて共に2次、項数も共に3項で同じ、最高次の係数も3と2で素数の小さな数ですから、あまり差はありません。後は好みだけの問題でしょう。同じならxと決めて置いても

他の方法としてxとyの両方に着目し2次の項の因数分解
3x^2+7xy+2y^2=(x+2y)(3x+y)
をしてから、一時項を含めた因数分解に進めます。
左辺=(x+2y+a)(3x+y+b)
定数項ab=2に着目してa,bの候補を絞れば良いですね。


このQ&Aを見た人がよく見るQ&A

人気Q&Aランキング

おすすめ情報