- 締切済み
- すぐに回答を!
経営科学の線形計画法、教えてください
線形計画法のシンプレックス法で、問題を解くために不等式であらわされた制約条件式を、わざわざ余裕変数を用いて等式条件にするのはどうしてですか?
- mikkey
- お礼率0% (0/1)
- 回答数1
- 閲覧数407
- ありがとう数7
みんなの回答
- 回答No.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 を最大化せよ。
- ベストアンサー
- 数学・算数
- 線形計画法の問題で、悩んでます。
線形計画法の問題ですが。 たとえの問題です。 2種類の餌料「X」と「Y」を牛に与える1日に必要な、 ビタミン量を確保したままで、できるだけ価格を安くしたい。 X=50円/kg Y=100円/Kg ビタミン量X Y ------------ A 4 1 B 2 1 C 7 10 D 1 3 ------------ 餌(kg) ビタミン(mg) ビタミン必要量 ------------ A 12 B 10 C 70 D 15 ------------ ヒントは:目的は安くすること、制約条件は必要量。 どうとくのか、式だけでも教えていただけないでしょうか? どう、手をつけたらいいのかわかりません。
- 締切済み
- 物理学
- 線形計画法の問題
ダム建設用のコンクリート作成に必要な砂、および砂利の調達を担当することになりました。ダムで利用する骨材は、不要な成分である細砂を5%以下に抑え、砂を60%含み、砂利を35%以上含むものにしなければなりません。利用可能な採掘場は4つあり、それぞれの運搬などの単位量あたり費用、構成比(砂、砂利、細砂)は以下の表のようになっています。これらを混ぜ合わせてコンクリート用の骨材を用意します。 採掘場1 採掘場2 採掘場3 採掘場4 指定混合比 単位量あたり費用 1 4 13 15 ― 砂 0.25 0.7 0.85 0.1 60% 砂利 0.65 0.2 0.1 0.9 35%以上 細砂 0.1 0.1 0.05 0 5%以下 それぞれの採掘場から調達する比率をXi (i=1,2,3,4) として、費用を最小化する目的変数および制約条件を求めたいのです。砂利と細砂の指定混合比の合計が40%になるように基底変数を立てていけばいいと思っているのですが、そこからが良くわからないのです。線形計画法について熟知されている方ならどなたでも、教えていただきますようよろしくお願いします。
- ベストアンサー
- 数学・算数
- 線形計画法のシンプレックス法(単体法)について分からないところがある.....
シンプレックス法の1段階単体法が分かるけど いつどうやって2段階単体法を使う事はまったく理解できません 誰か説明していただきませんか? 人工変数も分からない 教えてください
- 締切済み
- 数学・算数