- 締切済み
シンプレックス法について
- みんなの回答 （2）
- 専門家の回答
みんなの回答
- jcpmutura
- ベストアンサー率84% (311/366)
z=x1+2x2+x3 2x1+x2+x3≦14 4x1+2x2+3x3≦28 2x1+5x2+5x3≦30 x1≦5の時 x2≦6-2x1/5-x3 だから z=x1+2x2+x3≦x1+12-4x1/5-2x3+x3=12+x1/5-x3≦13-x3<13 x1>5の時 5<x1≦7-x2/2-x3/2 x2/2+x3/2<2 x2+x3<4 だから z=x1+2x2+x3<7-x2/2-x3/2+2x2+x3=7+3x2/2+x3/2<7+3(x2+x3)/2<13 ∴ z=x1+2x2+x3<13…(1) x1=5-5/n x2=4 x3=2/n とすると 2x1+x2+x3=10-10/n+4+2/n=14-8n<14 4x1+2x2+3x3=20-20/n+8+6/n=28-14/n<28 2x1+5x2+5x3=10-10/n+20+10/n=30 z=x1+2x2+x3=13-3/n lim_{n→∞}z=13…(2) x1=5 x2=4 x3=0 の時 目的関数zは最大値z=13をとるが x3=0となってx3>0という条件を満たさない (1)z<13 と (2)lim_{n→∞}z=13 から 目的関数zを最大にするx1,x2,x3>0は存在しない
- info222_
- ベストアンサー率61% (1053/1707)
大学の課題のようですね。 丸投げしないで自身でできるところは自分でやるようにして、わからない箇所だけ具体的に質問してください。 シンプレックス法は複数の連立不等式や表をいくつか作らないと解答を書けません。 ここで表や連立不等式を沢山作って掲載することは難しいので、下記のサイトを参考にして、自身でやってみてください。
関連するQ&A
- シンプレックス法の問題
線形計画、数学に詳しい方に質問です 以下の目的関数zを最大にするx1,x2,x3をシンプレックス表を用いて求めよという問題が解けませんでした z=x1+2x2-x3 2x1+x2+x3≦14 4x1+2x2+3x3≦28 2x1+5x2+5x3≦30 回答をお願いします
- 締切済み
- 数学・算数
- シンプレックスの単体表の作り方がわかりません！
シンプレック法による解法で単体表を作らなければならないのですが、その単体表の作り方の手順がわからなくて困っています。問題は以下のとおりです。 次の問題をシンプレックス法で解きなさい。 目的関数 Ｚ＝４ｘ１ ＋３ｘ２ →最大 制約条件 ２ｘ１ ＋１ｘ２ ≦３０ （ａ） ３ｘ１ ＋４ｘ２ ≦６０ （ｂ） １ｘ１ ＋２ｘ２ ≦２６ （ｃ） （ｘ１ ≧０，ｘ２ ≧０）
- ベストアンサー
- 数学・算数
- シンプレックス法について
シンプレックス法は、以下のサイトで紹介されているように目的関数を最大もしくは最小化するときに使用されます。 http://www.bunkyo.ac.jp/~nemoto/lecture/or/97/simplex/index.htm しかし、シンプレックス法のアルゴリズムでは、 目的関数を「最大化」する場合、目的関数が、 Object＝a・x＋b・y a>0、b>0 となっており、 目的関数を「最小化」する場合、目的関数が、 Object＝－a・x－b・y a>0、b>0 となっている必要があると思います。 （ピボット列の選択のとき、目的関数を最大化する場合には、目的関数 を増やすために、係数a、bはプラスでなくてはならない。 目的関数を最小化する場合には、目的関数を減らすために係数a、bはマイナス でなくてはならない） ここで疑問なのは、目的関数を「最小化」する場合、 目的関数が、 Object＝a・x＋b・y a>0、b>0 となっている場合、シンプレックス法では解けないのでしょうか？ 対象とする問題によっては、このようなことが起きうると思うのですが、何か方法があるのでしょうか？ 回答よろしくお願いします。
- 締切済み
- 数学・算数
- 線形計画法を2段階シンプレックス法を用いて解く
次の問いを2段階法を用いて解けというものなのですが (1) x0 = 4x1 - 2x2 + x3 → 最大化 2x1 + x2 + x3 ≦ 6 4x1 - 2x2 + x3 ≦ -4 x1, x2, x3 ≧ 0 (2) x0 = 3x1 + 2x2 → 最大化 x1 + 2x2 ≦ 20 7x1 + 6x2 ≧ 84 x1 - x2 ≦ 8 x1, x2 ≧0 (1)に関しては人為変数が不要なのでそもそも2段階法で解けるのでしょうか？ (2)は x1 + 2x2 +x3 = 20 7x1 + 6x2 - x4 = 84 x1 - x2 +x5 = 8 とした後に人為変数x6を用いて x1 + 2x2 +x3 = 20 7x1 + 6x2 - x4 +x6 = 84 x1 - x2 +x5 = 8 として解いていったのですがシンプレックス表で解いている途中で詰まってしまいます。 (1), (2)ともにある程度の途中計算を交えて教えてくださると助かります。 よろしくお願いします。
- 締切済み
- 数学・算数
- シンプレックス法について
制約条件は以下のようになります。 max z=3x+2y subject to 2x+3y<=24 3x+y>=15 x+y=7 x,y>=0 最適解をシンプレックス法によって求めよという問題です。 グラフ法だったらものすごく簡単にもとまりますが、シンプレックス法でどうやって解くのかわからないのです。 私はタブローを使うシンプレックス法で解こうとしましたが、表を作ってみましたが、x+y=7という等式 をどう扱うか困りました。 2x+3y+λ1=24 -3x-y+λ2=15 z-3x-2y=0 x+y=7 x,y>=0 基底 x y λ1 λ2 右辺 λ1 2 3 1 0 24 λ2 -3 -1 0 1 15 z -3 -2 0 0 0 になりますが、x+y=7をどうやって表に入れるのかわかりませんでした。 どなたわかる方がいらっしゃいましたら、ご教授よろしくお願いします！
- ベストアンサー
- 情報工学
- シンプレックス法の質問です。
シンプレックス法でｆはx1,x2,x3,x4の関数であり、それを最小化したいとします。その途中で式を正準系に直し、fの変数の中で負で最も係数の大きいものを次の基底変数に選びます。では次の「非基底変数」にはどういうものをを選べばいいのでしょう？
- ベストアンサー
- 数学・算数
- 線形計画法の問題です。
問題は以下のURLの一番下（第2問-問題3）です。 http://www.gsm.kyoto-u.ac.jp/images/education/kakomon/24sugaku.pdf 得られる利益をz、製品Aをx1トン、製品Bをx2トン生産するとし、スラック変数x3、x4を導入すると、 -3x1 - 2x2 + z=0 x1 + x2 = 7 -(1) 2x1 + 3x2 + x3 = 24 3x1 + x2 - x4 =15 x1～x4≧0 ここで(1)式より、x2 = 7 - x1なので、他の式からx2を消去すると、 -x1 + z = 14 -x1 + x3 = 3 2x1 - x4 = 8 これを掃き出し法で解こうとすると、以下の写真のようになったのですが、 この掃き出し法によって分かるのは「z = 18 + x4/2」でx4の係数が正なので、「x4 = 0のときにzが最大値18をとる」とは言えませんよね？ 図形的に考えると、おそらくz=18（x1=4、x2=3）になると思うのですが、私の計算がどこかで間違っているのでしょうか？ それともこの掃き出し法の結果から、zが最大値18をとると言えるのでしょうか？ どなたかご教授ください。どうぞよろしくお願いします。
- ベストアンサー
- 数学・算数
- シンプレックス法の問題について質問です
今、線形計画問題について学習中で以下の問題で行き詰りました。 どなたかわかる方がいましたら解法を教えてほしいです。 よろしくお願いします。 maximize z=-x+2y+ z subject to: 3x+ y-4z<=4 x- y- z<=10 x-2y+6z<=9 上記の問題についてz>100を満たす可能解を示せ、
- 締切済み
- 数学・算数
- 非線形計画法 主-双対問題
次のような制約付き最小化問題を考えています。 目的関数は非線形です。 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が負になった制約式はの除いてそのあともう一度問題を解きなおす。つまり２番目の問題を前問に置き換える。 っといったことをして問題を解決させようとかんがえていますが、これは理論的に正しいのでしょうか。 これはほんの例題ですが、複数個の不等式制約式を扱い、かつ偏微分可能な最適化問題を解く際に、最適解に対して全てが有効制約になるとは限りませんので、どうかうまくいくアドバイスをください。
- 締切済み
- 数学・算数
- なぜ、双対問題（双対性）を考えるのですか？
現在、線形計画法を勉強中で、よくわからないことがあります。 例えばこのような問題があるとしまして、 主問題 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 は、必ず一致することは、 シンプレックス法で実際に解いて確認できます。できました。 （参考書として読んでいる本の、標準形での証明・説明はいまいちわかりませんでした…。） ですが、 なんらかの収益を最大にしたい…という問題を定式化して解けば、 その収益を最大にしたいときの最適解・最適値を求められるなら 主問題の方だけ充分ではないのでしょうか？ 上記の式の例ですと式の規模(？)に大した違いはないですが、 問題によって、双対問題に作り直した方が計算しやすい？ といったようなメリットがあるのですか？ なぜ、双対問題を考えるのか、どなたか分かりやすく教えて頂けませんでしょうか。
- ベストアンサー
- 数学・算数
