- ベストアンサー
【至急!!】線形計画問題教えてください。
- みんなの回答 （2）
- 専門家の回答
質問者が選んだベストアンサー
回答の「至急!!」とありますが 問題打ち込みミス訂正の確認問合せに応答ないですね。 急ぎではないですか？ 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
その他の回答 (1)
- info22_
- ベストアンサー率67% (2650/3922)
3行目の式 > sub to x1x+2x+x3≧1 不等式の左辺おかしくありませんか？ 正しい式に訂正願います。
関連するQ&A
- 線形計画問題の双対問題について疑問
線形計画問題の双対問題について疑問 主問題 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 となるということはわかるんですが・・・・ よろしくお願いします。
- 締切済み
- その他（学問・教育）
- 数理計画法の双対問題の解法について
私は現在、以下のような問題に取り組んでおります。 問題：次の線形計画問題の双対問題を解け。 minimize: z = 2x1+3x2+8x3 2x1+2x2+6x3 ≥ 6 x1+2x2+4x3 ≥ 4 x1,x2,x3 ≥ 0 私はこの双対問題のシンプレックス表を用いて解く方法が分かりません。 どなたか解答・解説をお願いします。
- 締切済み
- 数学・算数
- 至急お願いします！線形計画問題についてです。
maximize 7x1 + 4x2 + 2x3 subject to 3x1 + 3x2 + x3 ≦ 36 .................. 2x1 + x2 + x3 = 18 .................. x1,x2,x3≦0 この問題を2段階法により解けという問題なのですが、x1,x2,x3と3変数も出てきているのに、制約関数が2式のみって、解くことができないですよね？3変数であれば最低でも3式は必要だと思います。 問題のミスでしょうか？ どなたか教えてください。
- ベストアンサー
- 数学・算数
- 非線形計画法 主-双対問題
次のような制約付き最小化問題を考えています。 目的関数は非線形です。 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 f(x1,x2)=(x1-1)^2+x2^2 subject to x1+x2≧5 (1) 2x1+x2≧7 x1≧0 x2≧0 (1)の右辺の値がδだけ増加した時の目的関数の変化量と、この変化量に 対して乗数λ1,λ2はどのような意味を持つか述べよ という問題です。 最適値は(x1,x2)=(3,2)で乗数は(λ1,λ2)=(4,0) というところまで求めました。 変化量はδ^2/2かなとは思いますが、乗数の意味がわかりません。
- 締切済み
- 数学・算数
- 【至急】線形計画問題について、ヒントをください！
maximize 7x1 + 4x2 + 2x3 subject to 3x1 + 3x2 + x3 ≦ 36 .................. 2x1 + x2 + x3 = 18 .................. x1,x2,x3≦0 . この問題の最適解と最適値を求めたいのですが、、まず標準形の線形計画問題に変形する段階で、 2x1 + x2 + x3 = 18 と、 = がでできてしまい、 subject to 3x1 + 3x2 + x3 + x4 = 36 ................... 2x1 + x2 + x3 + x5 = 18 ................... x1,x2,x3,x4,x5≦0 としていいのか、 subject to 3x1 + 3x2 + x3 + x4 = 36 ................... 2x1 + x2 + x3 = 18 ................... x1,x2,x3,x4≦0 としていいのかが分かりません。 ≦ や ≧ ではなく、= が制約関数に含まれていると、標準形ではどの様に変形すれば宜しいのでしょうか？ どなたか教えてください。また、理由もお聞かせ頂けると幸いです。
- 締切済み
- 数学・算数
- なぜ、双対問題（双対性）を考えるのですか？
現在、線形計画法を勉強中で、よくわからないことがあります。 例えばこのような問題があるとしまして、 主問題 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 は、必ず一致することは、 シンプレックス法で実際に解いて確認できます。できました。 （参考書として読んでいる本の、標準形での証明・説明はいまいちわかりませんでした…。） ですが、 なんらかの収益を最大にしたい…という問題を定式化して解けば、 その収益を最大にしたいときの最適解・最適値を求められるなら 主問題の方だけ充分ではないのでしょうか？ 上記の式の例ですと式の規模(？)に大した違いはないですが、 問題によって、双対問題に作り直した方が計算しやすい？ といったようなメリットがあるのですか？ なぜ、双対問題を考えるのか、どなたか分かりやすく教えて頂けませんでしょうか。
- ベストアンサー
- 数学・算数
- 大学の問題なのですが、解けなくて困ってます…
大学の問題なのですが、解けなくて困ってます… 線形計画問題 (1) Z=2X1-X2+X3-X4:最小化 X1+X2+2X3+X4=2 -X1+2X2-3X3+X4=1 X1,X2,X3,X4>0 1)実行可能基底解をすべて求めよ 2)X1,X2を基底変数とするシンプレックス表から出発して単体法で最適解を求めよ 3)この問題の双対問題を書け (2)線形計画問題に変形し単体法を用いて解け | X1-X2 |:最小化 2X1-X2+X3<2 3X2-X3<5 X1+X2+2X3>6 X1,X2,X3>0 (<，>は＿がついてますが表記が？になるのであえてこれにしました) (２の方は目的関数の絶対値をとって単に計算したやつでも構いません) よろしくお願いします。
- ベストアンサー
- 数学・算数
