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


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

主問題
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の最安値が安いって事で良いのでは?

Q【至急!!】線形計画問題教えてください。

次の問題を双対シンプレックス法により解け。
minimize 15x1+7x2+12x3
sub to x1x+2x+x3≧1
3x1+x2+x3≧2
x1,x2,x3≧0

双対シンプレックス法での解き方がいまいち分かりません。
双対シンプレックス法での解き方が分かる方教えてください(>_<)

Aベストアンサー

回答の「至急!!」とありますが
問題打ち込みミス訂正の確認問合せに応答ないですね。
急ぎではないですか?

3行目が
正:sub to x1+x2+x3≧1
だとすると
x1=x2=1/2,x3=0のとき 最小値=11 となります。
シンプレックス表は参考URLを参考にご自分でお作りください。

参考URL
http://www.komazawa-u.ac.jp/~takai/kyozai/LP.doc

参考URL:http://www.bunkyo.ac.jp/~nemoto/lecture/mathpro/2002/dual2002.pdf

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

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

よろしくお願いします。

Aベストアンサー

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

Q行列の正定・半正定・負定

行列の正定・半正定・負定について自分なりに調べてみたのですが、
イマイチ良くわかりません。。。
どなたか上手く説明していただけないでしょうか?
過去の質問の回答に

>cを列ベクトル、Aを行列とする。
>(cの転置)Ac>0
>となればAは正定値といいます。
>Aの固有値が全て正であることとも同値です。

とあったのですが、このcの列ベクトルというのは
任意なのでしょうか?
また、半正定は固有値に+と-が交じっていて、
負定は固有値が-のみなのですか?

どなたかお願いしますorz

Aベストアンサー

まず、行列の正定・半正定・負定値性を考えるときは、
行列は対称行列であることを仮定しています。
なので、正確な定義は、

定義 n次正方 "対称" 行列 A が正定値行列であるとは、
『ゼロベクトルではない任意の』n次元(列)ベクトル c に対して、
(cの転置)Ac>0
となることである。

です。

対称行列Aが正定値なら、その固有値はすべて正です。
(cとして固有ベクトルをとってみればよいでしょう。)
逆に、対称行列Aの固有値がすべて正なら、Aは正定値行列です。

ただし、対称行列ではないAの固有値がすべて正だからといって、
(cの転置)Ac>0とは限りません。
例えば、
A =
[ 1 4 ]
[ 0 1 ]
とすると、Aは対称行列ではなく、固有値は1です。
しかし、
(cの転置) = [ 1, -2]
とすると、
(cの転置)Ac = -3 < 0
となってしまいます。(実際に計算して確かめてください。)
なので、行列Aが対称行列であるという条件はとても重要です。

また、半正定値の定義は、上の定義で
『ゼロベクトルではない任意の』 --> 『任意の』
と書き直したものです。
このとき、半正定値行列の固有値はすべて0以上です。(つまり0も許します。)
逆に、対称行列の固有値がすべて0以上なら、その行列は半正定値です。

さらに、負定値の定義は、『ゼロではない任意の』ベクトルcに対して
(cの転置)Ac<0
となることです。
固有値についてはもうわかりますね。

まず、行列の正定・半正定・負定値性を考えるときは、
行列は対称行列であることを仮定しています。
なので、正確な定義は、

定義 n次正方 "対称" 行列 A が正定値行列であるとは、
『ゼロベクトルではない任意の』n次元(列)ベクトル c に対して、
(cの転置)Ac>0
となることである。

です。

対称行列Aが正定値なら、その固有値はすべて正です。
(cとして固有ベクトルをとってみればよいでしょう。)
逆に、対称行列Aの固有値がすべて正なら、Aは正定値行列です。

ただし、対称行列...続きを読む

Q価格com.の値段

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

Aベストアンサー

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

Qデータが正規分布しているか判断するには???

初歩的なことですが。。急いでいます。
おわかりになる方 教えてください。
サンプリングしたデータが正規分布しているかどうかを確認するにはどうすればよろしいでしょうか。
素人でも分かるように説明したいのですが。。
定性的にはヒストグラムを作り視覚的に訴える方法があると思います。今回は定量的に判断する方法を知りたいです。宜しくお願いします。

Aベストアンサー

>機械的に処理してみるとできました。
>でも理屈を理解できていません。
 とりあえず、理屈は後で勉強するとして、有意水準5%で有意差あり(有意確率が0.05以下)であれば、正規分布ではないと結論づけてお終いでいいのではないですか。
>この検定をもっと初心者でもわかりやすく解説しているサイト等ご存じありませんか。
 私が知っている限りでは、紹介したURLのサイトが最も丁寧でわかりやすいサイトでした。
>データの区間を分けるときのルール等ありますでしょうか。
 ヒストグラムを作成する場合、区間距離、度数区分数は、正規的なグラフになるように試行錯誤で行うことが多い(区間距離や度数区分数を本来の分布に則するようにいろいろ当てはめて解釈する。データ個数の不足や、データの取り方、または見かけ上の分布によりデータのばらつきが正しく反映されて見えないことがあるため)のですが、度数区分数は、機械的に、
=ROUNDUP(1+LOG10(データ個数)/LOG10(2),0):エクセル計算式
で区分数を求める方法があります。
 また、区間距離は、=ROUND((データの最高値-最低値)/(度数区分数値-1),有効桁数)で求め、区分の左端は、
=ROUNDUP(データの最低値-区間距離/2,有効桁数)
右端は=ROUNDUP(データの最高値+区間距離/2,有効桁数)
とします。
 区間がと度数区分数が出たら、その範囲にあるデータ数を数えて、ヒストグラムができます。
 
>最小側、最大側は 最小値、最大値を含んだ値としなければならないのでしょうか。
 ヒストグラム作成の処理に関しては、上記を参考にしてください。
 その前に、データの最小値と最大値が、正しくとれたデータか検討するため、棄却検定で外れ値が存在するか否かを検定し、外れ値が存在しないと結論づけられたら、正規分布の検定を行ってみてください。もし外れ値が存在する可能性があれば、そもそも、そのデータの信頼性が失われます。サンプリング手法の再検討(データの取り方に偏りがなかったか、無作為に設定してデータを取っていたか等)をして、再度データを得る必要があります。また、そもそも検定する以前に、データ数が少ないと判断が付かなくなってしまいますので、データ数は十分揃える(少なくとも20~30個)必要もあります。

>機械的に処理してみるとできました。
>でも理屈を理解できていません。
 とりあえず、理屈は後で勉強するとして、有意水準5%で有意差あり(有意確率が0.05以下)であれば、正規分布ではないと結論づけてお終いでいいのではないですか。
>この検定をもっと初心者でもわかりやすく解説しているサイト等ご存じありませんか。
 私が知っている限りでは、紹介したURLのサイトが最も丁寧でわかりやすいサイトでした。
>データの区間を分けるときのルール等ありますでしょうか。
 ヒストグラムを作成する場合、区...続きを読む

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

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

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

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

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

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

Aベストアンサー

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

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

Q加重平均と平均の違い

加重平均と平均の違いってなんですか?
値が同じになることが多いような気がするんですけど・・・
わかりやす~い例で教えてください。

Aベストアンサー

例えば,テストをやって,A組の平均点80点,B組70点,C組60点だったとします.
全体の平均は70点!・・・これが単純な平均ですね.
クラスごとの人数が全く同じなら問題ないし,
わずかに違う程度なら誤差も少ないです.

ところが,A組100人,B組50人,C組10人だったら?
これで「平均70点」と言われたら,A組の生徒は文句を言いますよね.
そこで,クラスごとに重みをつけ,
(80×100+70×50+60×10)÷(100+50+10)=75.6
とやって求めるのが「加重平均」です.

Q価格comの星印は何?

価格comの星印は何?


価格comに付いている星印は何の印ですか?
製品に対する何かの評価である事は分かりますが、どの様な意味合いを持っているのですか?

解りづらい文章ですみません!

Aベストアンサー

ユーザーレビューについている★印のことでしょう?

であれば、その★印の欄自体をクリックしてもらえば画面が切り替わり表示されるのでわかるかと思いますが、その製品を実際に購入・使用した人が、その製品の評価として使用感を投稿する際に、それぞれの項目を5点満点のうち、それぞれ点数を入れます。

当然、複数の方々が投稿しますので、最初に表示されているのはその平均点としての評価となります。

Q「ノルム、絶対値、長さ」の違いについて

あじぽんと申します。よろしくお願いします。

ベクトルや複素数などに出てくる「ノルムと絶対値と長さ」というのは同じことを違う言葉で表現しているのでしょうか?
手元にある書籍などには全てが同じ式で求められています。
同じ式で表現されていても意味は少しづつ違っていたりするのでしょうか?

よろしくお願いします。

Aベストアンサー

どれも同じような性質を持ちますが、違いの1つとして定義される空間が違います。

「絶対値」は、実数や複素数といった「数」に対して定義されます。
定義は、一通りしかありません。
ベクトルに対して、絶対値を求めるという言い方をする場合もあるかもしれませんが、それはベクトルの長さを表す記号に絶対値の記号を利用する場合があるからであり、参考書にも文章として「ベクトルの絶対値」という言い方はあまりされていないのではないでしょうか?



「長さ」というのは、空間にある「線」に対して定義できます。
数に対しては「長さ」という言い方はあまり聞かないと思います。
例えば、「3」の長さというような言い方は耳になじまないと思います。
一方、ベクトルの場合は、「矢印」という「線」になりますので「長さ」が定義できます。



最後の「ノルム」は、線形空間に対して定義できます。(もちろん実数、複素数やベクトルも線形空間です)
ノルムの条件を満たせばノルムになるため、複数のノルムが考えられます。
そのため、「(1,1)というベクトルに対するノルムは?」
という質問に対しては、「どのノルムを使うか?」という条件が欠けているため厳密に言うと「解答はできません」。
例としてよく扱われるノルムは「ユークリッドノルム」と言われ、通常のベクトルの長さと等しくなります。

ベクトルに対するノルムでは、「最大値ノルム」というのが他の例としてよく使われます。
これは、ベクトルの各要素の最大値で定義されます。
(例:(3,1,5)というベクトルの最大値ノルムは、3つの数字の最大値である5になります)

ノルムというと、線形空間であれば定義できるため、
f(x) = 3x^2+5x
という数式に対するノルムというのも考えられます。
(数式は、定数倍したり、足し算したりできますよね)
数式に対して「絶対値」とか「長さ」と言ってもピンと来ないですよね。

しかし、まだやられていないかもしれませんが、数式に対するノルムというのは存在します。


そうすると、なんでこんなんがあるねん。って話になると思います。

ここで、ベクトルに対してある定理があったとします。

それがさっきのような数式など他の線形空間でも成り立つんだろうか?
というのを考えるときに「ノルム」の登場です。

その定理の証明で、「ベクトル」として性質を使わずに「ノルム」の性質だけを使って証明ができれば、
それは「ベクトル」に対する証明でなくて「ノルムを持つもの」に対する証明になります。
(ちょっと難しいかな?)


このようにして、定理の応用範囲を広げるために「長さ」や「絶対値」の考え方をベクトルだけでなく「線形空間」という広い考え方に適用できるようにしたのが「ノルム」になります。

どれも同じような性質を持ちますが、違いの1つとして定義される空間が違います。

「絶対値」は、実数や複素数といった「数」に対して定義されます。
定義は、一通りしかありません。
ベクトルに対して、絶対値を求めるという言い方をする場合もあるかもしれませんが、それはベクトルの長さを表す記号に絶対値の記号を利用する場合があるからであり、参考書にも文章として「ベクトルの絶対値」という言い方はあまりされていないのではないでしょうか?



「長さ」というのは、空間にある「線」に対して...続きを読む


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

人気Q&Aランキング