- 締切済み
経営科学の線形計画法、教えてください
線形計画法のシンプレックス法で、問題を解くために不等式であらわされた制約条件式を、わざわざ余裕変数を用いて等式条件にするのはどうしてですか?
- mikkey
- お礼率0% (0/1)
- その他(学問・教育)
- 回答数1
- ありがとう数7
- みんなの回答 (1)
- 専門家の回答
みんなの回答
- stomachman
- ベストアンサー率57% (1014/1775)
線形計画法(linear programming) (1)「A[i,1]x[1] + .... + A[i,N] x[N] ≦b[i] (i=1,2,...,M)という条件下で 目的関数c' x (=Σ(c[j] xj]))を最大化する」 という問題を、slack またはstubと呼ばれる変数x[N+j](j=1,2,...,M)を追加して、未知数のベクトルxの次元を上げ、 (2)「A[i,1]x[1] + .... + A[i,N] x[N] + x[N+i] = b[i] (i=1,2,...,M)という条件下で c' x を最大化する」に変換するのは、なんでか?という質問ですね。 (1)の条件式で不等号を等号に置き換えたひとつの方程式 A[i,1]x[1] + .... + A[i,N] x[N] =b[i] の解(一つには決まりません)の集合はN次元空間の一つの超平面を作ります。従って、この超平面上では、(2)の等式のslack変数x[N+i] は0になります。 この問題の解は(存在するなら)、それは必ず各条件式によって決まるM個の超平面で囲まれた超多面体の頂点のどれかです。(どのjについても < だとすれば、c' xを必ずもっと大きくできる。)そして頂点に於いては、N個の変数がゼロになり、残りが正になる。 つまり、slack変数を導入すれば、(1)の問題は、「(2)においてx[i] (i=1,2,....,N+M)のうちのどのN個を0にすれば良いか?」という問題に変換される。そして、まずどれか一つの頂点を選び(つまりx[i]のうちのN個を0にしてみて)、その頂点と辺で繋がっている頂点を調べて、目的関数がより大きくなるように、いわば移動していく。これがsimplex法です。 という訳で、答としては:「頂点だけをたどっていくのに便利だから。」
関連するQ&A
- 線形計画法の解法について!
線形計画法の解き方が判らなくて困っています。 判らないこと 1.制約条件の式と計算値 2.目的関数の式と目的値 線形計画法は変数と制約条件と目的関数が与えられます。 制約条件を満足し、目的関数が最大(最小)となる変数を求めます。 線形計画法の例 変数 x y 制約条件 (A) 10x + 4y ≦ 360 (B) 4x + 5y ≦ 200 (C) 2x + 10y ≦ 300 (D) x ≧ 0 (E) y ≧ 0 目的関数 M = 7x+12y A,B,C,D,Eの条件を満足し目的関数(M)が最大となる変数x,yを求めます。
- ベストアンサー
- 数学・算数
- 線形計画法の解について!
線形計画法の解、シャドウ価格の求め方がわからなくて、困っています。 問題は、以下のとおりです。 (線形計画法とシャドウ価格) 次の線形計画法の解、各制約のシャドウ価格を求めなさい。 制約条件 2x+y≦7, x+3y≦6, x≧0,y≧0 のもとで、目的関数 Z=x+y を最大化せよ。
- ベストアンサー
- 数学・算数
- 非線形計画法について
非線形計画法を現在勉強しています。 1. どういうときに線形でどういうときに非線形となるのか良く分かりません。 例えば、ある従属変数yを線形関数f=Σcx で表したいときにパラメータcの絶対値の和が定数bより小さくなるという制約のもとで、yとfの二乗誤差を最小化するパラメータcを求める問題を考えます。 この場合、制約条件はcについて線形ですが、最小化したいのは、yとfの二乗誤差なのでこの場合は非線形ということになるのでしょうか?それとも関数fはcに関して線形関数なので、線形計画法で解くことになるのでしょうか? 2. 以下のサイトで勉強しているのですが、このサイトにある楕円型の等高線はおそらく、従属変数yと目的関数fの誤差を表しているのだと思うのですが、なぜ「楕円」になるのですか?二乗誤差を考えるのならば、「円」になるのではと疑問で仕方ありません。 http://www.sist.ac.jp/~suganuma/kougi/other_lecture/SE/opt/nonlinear/nonlinear.htm#2.2 疑問が晴れずにもやもやしています。 回答もしくはアドバイス、よろしくお願いします。
- 締切済み
- 数学・算数
- 非線形最小二乗法とシンプレックス法
非線形最小二乗法をシンプレックス法を使って解く方法がわかりません。Gauss-Newton法で解いてもいいのですが、この方法は適当な初期値の範囲が狭いという欠点があるようです。 シンプレックス法ならばいいらしいのですが、いろいろ調べてもシンプレックス法は線形問題で扱う場合がほとんどのようで、非線形問題にはでてきません。 シンプレックス法で非線形問題を扱うには、どうすればよいでしょうか? そもそも非線形問題でシンプレックス法は扱えるのでしょうか?
- ベストアンサー
- 数学・算数
- 線形計画問題
最近線形計画法について独学で勉強を始めたのですが いくつかの書籍を調べてもどうしても分からない点が あったのでこの場を利用させて頂きます。 頭を悩めていますのは制約条件が特殊なためです。 問題を簡略すると以下のようになっています。 min : x(1)/2 + 5x(2)/2 suject to: 1/x(1)+1/4x(2) ≦ 8 x(1) ≧ 0, x(2) ≧ 0 御覧頂けますように制約条件において決定変数が 分母にきているのです。目的関数で分母に変数を 持つものは分数計画問題といるのを拝見した事が あるのですが上記のような例は探し方が悪いのか 見つける事ができていません。 実行可能領域は非有界ですが最小化問題のため 上記の例であると2変数なのでグラフにプロットする 事でおよそですが解は見つかりました。 しかし実際の問題は10変数以上の問題となっています ので解が求められません。 その後も実行可能領域を多面体で近似すれば良いのか 等の考察を繰り返しましたが問題が複雑になりお手上げ の状態です。 ちゃんとした解法があるのならお教え頂けるか書籍の 案内をして頂きたいです。宜しくお願いします。
- ベストアンサー
- 数学・算数