プロが教えるわが家の防犯対策術!

私は現在、以下のような問題に取り組んでおります。

問題:次の線形計画問題の双対問題を解け。

minimize: z = 2x1+3x2+8x3

2x1+2x2+6x3 ≥ 6

x1+2x2+4x3 ≥ 4

x1,x2,x3 ≥ 0

私はこの双対問題のシンプレックス表を用いて解く方法が分かりません。
どなたか解答・解説をお願いします。

A 回答 (1件)

なにがわからないんでしょうか? 自分で書いていある通りのことをすればいいだけですよね?

    • good
    • 0

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

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

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

Qなぜ、双対問題(双対性)を考えるのですか?

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


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

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

ですが、

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

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


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

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


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

主問題
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 は、必ず一致することは、
シンプレックス法で実際に解いて確認...続きを読む

Aベストアンサー

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

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) にある」ということが言えます。つまり、とりあえず得られている解が最適解からどれくらい離れているかの評価ができます。

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

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

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 が双対変数とかラグランジュ乗数と呼ばれるもの...続きを読む

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&Aランキング