線形計画問題についての解法を教えてください
- 線形計画問題についての解法として、問題1の双対問題を書き、その双対問題を解く方法があります。
- 問題1の双対問題を書き、その双対問題を解くことで、線形計画問題を解くことができます。
- 問題1は、X(1) + 2X(2) + X(3) ≧ minという条件のもとで、制約条件を満たす最小の値を求める問題です。
- ベストアンサー
線形計画問題について教えてください。
学校の講義で線形計画問題を習いまして、宿題を出されたのですが、授業をしっかりと聞いておらず、後でレジュメを見て理解しようとしましたが、できませんでした。配られたレジュメを見ても、理解できませんでした。「標準形」の説明のところで記号がたくさん出てくるのでどうしてもわからないのです。 かような泣き言を書き、課題をほぼそのまま書いてしまいましたが、できれば解き方を教えていただきたいです。 問題 1 X(1) + 2X(2) + X(3) ≧ min 条件 X(1) + 5X(2) + 2X(3) ≧ 8 3X(1) + 2X(2) + 2X(3) ≧ 7 X(1)≧0 , X(2)≧0 , X(3)≧0 <1>問題1の双対問題を書いて下さい。 <2>その双対問題を解いて下さい。 <3>問題1を解いて下さい。 ※ ()の中の数字は化学でよく使う数字の右下 に付く小さな数字表しています。
- Hermet
- お礼率79% (90/113)
- 数学・算数
- 回答数1
- ありがとう数1
- みんなの回答 （1）
- 専門家の回答
質問者が選んだベストアンサー
授業は聞きましょう できれば友達に聞くなりネットで「線形計画問題」などで検索して理解することをおすすめします 答えは X1＝1.46 X＝1.31 Z=-4.08 になりました これは２段階法を使うので少し難しいですね レジュメに「２段解法」って載ってますか？ あわせて調べてみてください 下のサイトはアドバイスではなく答えに近くなるので 自分で調べるようにしてください
関連する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 となるということはわかるんですが・・・・ よろしくお願いします。
- 締切済み
- その他（学問・教育）
- 線形計画法の問題です
Ｐ：最大化ｃ＾Ｔｘ（ｃ＾Ｔはｃの転置） 条件Ａｘ＜＝ｂ ｘ＞＝０ ただし、Ａはｍ＊ｎ行列、ｂはｍ次元ベクトル、ｃはｎ次元ベクトル、ｘはｎ次元 変数ベクトルである。ベクトルはすべて列ベクトルとし、ｃ＾Ｔはｃの転置を表す。 問題Ｐは最適解を持つと仮定し、目的関数の最大値をｆと表す。また、問題Ｐ に関連して、ｍ次元ベクトルｕをパラメータとする次の線形計画問題を考える。 Ｐ（ｕ）：最大化ｃ＾Ｔｘ－ｕ＾Ｔ（Ａｘ－ｂ） 条件ｘ＞＝０ 問題Ｐ（ｕ）の目的関数の最大値ｇ（ｕ）と表す。ただし、問題Ｐ（ｕ）が有界でない 場合はｇ（ｕ）＝無限大と定義する。以下の問いに答えなさい。 １）問題Ｐの双対問題を書きなさい ２）任意のｕ＞＝０に対して、ｇ（ｕ）＞＝ｆが成り立つことを示しなさい ３）ｍｉｎ｛ｇ（ｕ）｜ｕ＞＝０｝＝ｆが成り立つことを示しなさい。ただし、線形計画問題 に対する強双対定理を用いて良い。 以上の問題をお願いします。
- 締切済み
- 数学・算数
- 非線形計画法 主-双対問題
次のような制約付き最小化問題を考えています。 目的関数は非線形です。 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: z = 2x1+3x2+8x3 2x1+2x2+6x3 ≥ 6 x1+2x2+4x3 ≥ 4 x1,x2,x3 ≥ 0 私はこの双対問題のシンプレックス表を用いて解く方法が分かりません。 どなたか解答・解説をお願いします。
- 締切済み
- 数学・算数
- 線形計画問題を単体法を使って解く問題です。
タブローを使ってとこうとしたのですが制約式に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の範囲を求めよ。
- 締切済み
- 数学・算数
- 線形計画問題
最近線形計画法について独学で勉強を始めたのですが いくつかの書籍を調べてもどうしても分からない点が あったのでこの場を利用させて頂きます。 頭を悩めていますのは制約条件が特殊なためです。 問題を簡略すると以下のようになっています。 min : x(1)/2 + 5x(2)/2 suject to: 1/x(1)+1/4x(2) ≦ 8 x(1) ≧ 0, x(2) ≧ 0 御覧頂けますように制約条件において決定変数が 分母にきているのです。目的関数で分母に変数を 持つものは分数計画問題といるのを拝見した事が あるのですが上記のような例は探し方が悪いのか 見つける事ができていません。 実行可能領域は非有界ですが最小化問題のため 上記の例であると2変数なのでグラフにプロットする 事でおよそですが解は見つかりました。 しかし実際の問題は10変数以上の問題となっています ので解が求められません。 その後も実行可能領域を多面体で近似すれば良いのか 等の考察を繰り返しましたが問題が複雑になりお手上げ の状態です。 ちゃんとした解法があるのならお教え頂けるか書籍の 案内をして頂きたいです。宜しくお願いします。
- ベストアンサー
- 数学・算数
- 線形計画問題の標準形
現在大学で線形計画法を学んでいるのですが，実際に数字を用いて問題を解く事にはなれてきたのですが，証明問題などになるとどの様に回答を行えば良いか回答に繋がるプロセス分かりません． どの様なプロセスで回答をすれば良いかなにかアドバイスがございましたらよろしくお願いします．以下が現在回答に困っている問題ですのでよろしくお願いします． 線形計画法の標準形 目的関数：c^T x →最小 制約条件：Ax =b x≧0 m<nとなる自然数．x ∈ R^n, c ∈ R^n, b ∈ R^mであり，Aはm*n実行列で，rankA = m とし b ≠ 0 とする． 問題１．線形計画問題の制約条件を満たすxのなす集合を実行可能領域Fで表し，Fが空集合でないときFが凸集合であることを示しなさい． Fが凸集合とは x,x' ∈ F ⇒tx + (1 - t)x' ∈ F (∀t ∈ [0,1]) が成立するときをいう． 問題２．Au = b を満たすベクトル u ≠ 0 が存在する事を示せ． 問題３．Ax = 0 を満たすxのなす R^n の線形部分空間はAの核と呼ばれkerAと表す．Ax = bを満たすxのなす R^n の部分集合を J で表すとき J = { x ∈ R^n | x = u + v, v ∈ kerA} となる事を示せ．ただしuは問題２で存在を示したベクトルである．
- 締切済み
- 数学・算数
お礼
すばやい回答ありがとうございます。 参考URLを見させていただきましたが、 計算結果のどれが答えなのかわからなかったです。 せっかく探していただいたのに申し訳ないです。