• 締切済み
  • すぐに回答を！

経営科学の線形計画法、教えてください

線形計画法のシンプレックス法で、問題を解くために不等式であらわされた制約条件式を、わざわざ余裕変数を用いて等式条件にするのはどうしてですか？

  1. カテゴリ
  2. 学問・教育
  3. その他（学問・教育）

共感・応援の気持ちを伝えよう！

  • 回答数1
  • 閲覧数407
  • ありがとう数7

みんなの回答

  • 回答No.1

線形計画法(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 を最大化せよ。

  • 線形計画

    線形計画問題の質問です。 制約が３本の不等式からなっていて、なおかつ変数が２個の 線形計画問題で、無限の解ができるような具体例について なかなか例が浮かびません。

  • 線形計画法の問題で、悩んでます。

    線形計画法の問題ですが。 たとえの問題です。 ２種類の餌料「Ｘ」と「Ｙ」を牛に与える１日に必要な、 ビタミン量を確保したままで、できるだけ価格を安くしたい。 Ｘ＝５０円/ｋｇ　Ｙ＝１００円/Ｋｇ ビタミン量Ｘ　　　Ｙ －－－－－－－－－－－－ Ａ　　　　４　　　１ Ｂ　　　　２　　　１ Ｃ　　　　７　　１０ Ｄ　　　　１　　　３ －－－－－－－－－－－－ 餌（ｋｇ)　ビタミン（ｍｇ） ビタミン必要量　　 －－－－－－－－－－－－ Ａ　　　１２ Ｂ　　　１０ Ｃ　　　７０ Ｄ　　　１５ －－－－－－－－－－－－　 ヒントは：目的は安くすること、制約条件は必要量。 どうとくのか、式だけでも教えていただけないでしょうか？ どう、手をつけたらいいのかわかりません。

  • 線形計画問題

    変数の数が２個、制約が３本の不等式からなる線形計画問題で、無限解を生成する例にはどんなものがあるのでしょうか？

  • 線形計画法とは？

    タイトル通りです。線形計画法とは、どんなものですか？ また、今の社会現象でどういうところで使われますか？？ 今の社会現象と、からみ合わせて、詳しく教えてほしいです。 よろしくお願いします。

  • 線形計画問題

    線形計画問題をシンプレックス法で解きたいのですが、よくわかりません。シンプレックス表を作成して解こうとしているのですが、流れがよく分からず解けないのです…。問題をそのまま載せてしまいますが、自分では色々資料を見て考えたつもりです。 分かる方いらっしゃいましたら、どうかよろしくお願いします。 w=x+2y+5z→min s.t. 3x+4y+z≧8 x+2y+4z≧9 x≧0,y≧0,z≧0

  • 線形計画法について

    線形計画問題で、 制約条件: x1+4x2+x3≦2 x2+x2+2x3≦3 x1,x2,x3≧0 目的関数: max(5x1+8x2+6x3) という問題がでたのですが、 ご覧の通り3変数の問題なのですが図式解法を用いて解けという指定なのです。 2変数ならすんなりできたのですが、3変数となると上手くいきません。 どなたかわかる方いたら是非ご教授願います。

  • 線形計画法の問題

    　ダム建設用のコンクリート作成に必要な砂、および砂利の調達を担当することになりました。ダムで利用する骨材は、不要な成分である細砂を５％以下に抑え、砂を６０％含み、砂利を３５％以上含むものにしなければなりません。利用可能な採掘場は４つあり、それぞれの運搬などの単位量あたり費用、構成比（砂、砂利、細砂）は以下の表のようになっています。これらを混ぜ合わせてコンクリート用の骨材を用意します。 　　　　　　　　　　　　採掘場１　採掘場２　採掘場３　採掘場４　指定混合比 単位量あたり費用　　　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%になるように基底変数を立てていけばいいと思っているのですが、そこからが良くわからないのです。線形計画法について熟知されている方ならどなたでも、教えていただきますようよろしくお願いします。

  • 線形計画法のシンプレックス法（単体法）について分からないところがある．．．．．

    シンプレックス法の１段階単体法が分かるけど いつどうやって2段階単体法を使う事はまったく理解できません 誰か説明していただきませんか？ 人工変数も分からない 教えてください

カテゴリ

専門家に質問してみよう

職業から探して質問する