- ベストアンサー
最適化の計算問題なんですが
はじめまして 最適化のレポート問題なのですが 目的 ：z = 3x1 － 5x2 → Max 制約 ：x1 + 2x2 ≤ 7 (i) －4x1 + 3x2 ≤ 5 (ii) x1, x2 ≥ 0 を考える 。 以下の各問いに答えよ 。 (1) 最適解および最適値を求めよ 。 (2) 最適基底行列およびその逆行列は何か 。 という問題で、(1)はシンプレックスタブロー法で x1=7, x2=0, x3=0, x4=33 最適値=21 と求まったのですが 最適基底行列とはなんですか？ 教えて頂きたいです。 お願いしますm(__)m
- tamutamu_240
- お礼率0% (0/1)
- 数学・算数
- 回答数1
- ありがとう数0
- みんなの回答 （1）
- 専門家の回答
質問者が選んだベストアンサー
(1) x3=7-x1-2x2 x4=5+4x1-3x2 とすると x1+2x2≦7 -4x1+3x2≦5 だから基底変数はx3,x4,zで連立方程式は x1+2x2+x3 =7……(x3行) -4x1+3x2 +x4 =5……(x4行) -3x1+5x2 +z=0……(z行) x1≧0,x2≧0,x3≧0,x4≧0 シンプレックス表で 1) z行で最も小さい負の値-3を持つ列(x1列)に対応する非基底変数x1を新たに基底に入れる変数に選ぶ。 2) z行を除く各行において(定数項の値)/(新たに基底に入れることになった変数x1の係数)を計算する。 x3行は7 x4行は-5/4 その値を増加限界と呼ぶ。 z行を除く各行の増加限界の中で非負で最小の値(7)を取った行(x3行)に対応する変数x3を追い出す変数に決める。 3) 新たに基底に加える変数x1の列と基底から追い出す変数x3の行との交点の係数1をピボットにする。 ピボット(x3行x1列)ピボットを中心に掃き出しを行う 4) 連立方程式を解く 各行からピボットの行を何倍かして引くことにより、ピボット列の数字がピボット以外0になるようにする。 x1+2x2 +x3 =7……(x3行) 11x2+4x3+x4 =33……(x4行+(x3行)*4) 11x2+3x3 +z=21……(z行+(x3行)*3) 5) zの行を見ると負の値は無い。 つまり,これ以上基底を変更してもよりよい目的関数値は得られない。 よって、現在得られている解が最適である。 x2=x3=0のとき x1=7 x4=33 z=21 (2) 最適基底はx1,x4,zだから 連立方程式から作った最初のシンプレックス表で (列はx1列,x4列,z列,行はx3行,x4行,z行の順に並べると) 最適基底行列は (1 ,0,0) (-4,1,0) (-3,0,1) その逆行列は (1,0,0) (4,1,0) (3,0,1) となる 逆行列*定数項列=解 (1,0,0)(7)=(7) (4,1,0)(5).(33) (3,0,1)(0).(21) となる
関連するQ&A
- シンプレックス法について
制約条件は以下のようになります。 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をどうやって表に入れるのかわかりませんでした。 どなたわかる方がいらっしゃいましたら、ご教授よろしくお願いします！
- ベストアンサー
- 情報工学
- 大学の問題なのですが、解けなくて困ってます…
大学の問題なのですが、解けなくて困ってます… 線形計画問題 (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 (<，>は＿がついてますが表記が？になるのであえてこれにしました) (２の方は目的関数の絶対値をとって単に計算したやつでも構いません) よろしくお願いします。
- ベストアンサー
- 数学・算数
- 制約条件のある連立多元方程式の解法２
連立多元１次方程式で制約条件がある場合について 再度質問させてください。 未知数をx1,x2,x3、その他はある定数で、 a1・x1+b1・x2+c1・x3 = A a2・x1+b2・x2+c2・x3 = B a3・x1+b3・x2+c3・x3 = C 制約条件が0<x1,x2,x3<1としたときの解法を前回伺いましたが、 ご回答で、 「まず方程式の解(x1=z1,x2=z2,x3=z3)を得たあと 制約条件を満たすもっとも近い解は、 距離の２乗＝ （z1-x1）^2 + (z2-x2)^2 + (z3-x3)^2を最小にする x1,x2,x3を求める問題に帰着されます。」 さらにシンプレックス法を使えばと言うアドバイスを頂きました。 そこでシンプレックスについていろいろ見てみましたが、目的関数がこのように２次になっている場合は良く分かりませんでした。 どうすれば良いのでしょうか？
- ベストアンサー
- 数学・算数
- シンプレックス法の問題
線形計画、数学に詳しい方に質問です 以下の目的関数zを最大にするx1,x2,x3をシンプレックス表を用いて求めよという問題が解けませんでした z=x1+2x2-x3 2x1+x2+x3≦14 4x1+2x2+3x3≦28 2x1+5x2+5x3≦30 回答をお願いします
- 締切済み
- 数学・算数
- シンプレックスの単体表の作り方がわかりません！
シンプレック法による解法で単体表を作らなければならないのですが、その単体表の作り方の手順がわからなくて困っています。問題は以下のとおりです。 次の問題をシンプレックス法で解きなさい。 目的関数 Ｚ＝４ｘ１ ＋３ｘ２ →最大 制約条件 ２ｘ１ ＋１ｘ２ ≦３０ （ａ） ３ｘ１ ＋４ｘ２ ≦６０ （ｂ） １ｘ１ ＋２ｘ２ ≦２６ （ｃ） （ｘ１ ≧０，ｘ２ ≧０）
- ベストアンサー
- 数学・算数
- 非線形計画法 主-双対問題
次のような制約付き最小化問題を考えています。 目的関数は非線形です。 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が負になった制約式はの除いてそのあともう一度問題を解きなおす。つまり２番目の問題を前問に置き換える。 っといったことをして問題を解決させようとかんがえていますが、これは理論的に正しいのでしょうか。 これはほんの例題ですが、複数個の不等式制約式を扱い、かつ偏微分可能な最適化問題を解く際に、最適解に対して全てが有効制約になるとは限りませんので、どうかうまくいくアドバイスをください。
- 締切済み
- 数学・算数
- 線形計画問題を単体法を使って解く問題です。
タブローを使ってとこうとしたのですが制約式にx_2の項がない場所があったため0で割れず行き詰まってしまいました。 解答も解説もなく行き詰まっているため、親切な方詳しい解答・解説をおねがいします。 主問題 Max 2x_1+3x_2+x_3 s.t.x_1+x_2+x_3≦1 -2x_1+x_3≧1 x_1,x_2,x_3≧0 1)単体法を用いて解き、最適解と最適値を過程を記し求めよ。 2)双対問題を記し、1)の結果と相補性定理を用いて最適解を求めよ。 3)ある非負の実数kを用いて主問題の目的関数を(2+k)x_1+3x_2+x_3と変化させた線形計画問題をP'とする（制約式は同じ） 1)で求めた最適解がP'の最適解で在り続けるためのkの範囲を求めよ。
- 締切済み
- 数学・算数
- なぜ、双対問題（双対性）を考えるのですか？
現在、線形計画法を勉強中で、よくわからないことがあります。 例えばこのような問題があるとしまして、 主問題 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 は、必ず一致することは、 シンプレックス法で実際に解いて確認できます。できました。 （参考書として読んでいる本の、標準形での証明・説明はいまいちわかりませんでした…。） ですが、 なんらかの収益を最大にしたい…という問題を定式化して解けば、 その収益を最大にしたいときの最適解・最適値を求められるなら 主問題の方だけ充分ではないのでしょうか？ 上記の式の例ですと式の規模(？)に大した違いはないですが、 問題によって、双対問題に作り直した方が計算しやすい？ といったようなメリットがあるのですか？ なぜ、双対問題を考えるのか、どなたか分かりやすく教えて頂けませんでしょうか。
- ベストアンサー
- 数学・算数
- この問題の回答、解説お願いします。数C
この問題の回答、解説お願いします。 問1,正方行列Aの逆行列を消去法で求める解法では,未知行列をXと置いて,AX=Eを満たす行列Xを求めている.XがAの逆行列であるためにはもう一つの条件,XA=Eを満たさなければならない.Xgaこの条件を満たすことを証明せよ。 問2.4次の行列式の定義を述べ,ファンデルモンデの行列式の値を求めよ. |1 x x*2 x*3 | |1 y y*2 y*3 | |1 z z*2 z*3 | |w w*2 w*3 | x*2はxのニ乗でx*3はxの三乗です。y,z,wのもおなじです。 問3,連立方程式｛ax + by =0が,x=0,y=0以外の解を持つとき, {cx + dy =0 |a b|=0が成り立つことを証明せよ。 |c d| ｛は下の｛とつながっています。 。←気にしないでください。すみません。 問4,連立方程式 {a1x + b1y + c1z = 0 {a2x + b2y + c2z = 0 が, x=0,y=0,z=0以外の解を持つとき, {a3x + b3y + c3z = 0 |a1 b1 c1 | |a2 b2 c2 |=0が成り立つことを証明せよ。 |a3 b3 c3 | {は3行つながっています。 わかりづらいと思いますが、よろしくお願いします。
- 締切済み
- 数学・算数
