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

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

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

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

  • 回答数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 を最大化せよ。

  • 線形計画

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

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

    線形計画法の問題ですが。 たとえの問題です。 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 ------------  ヒントは:目的は安くすること、制約条件は必要量。 どうとくのか、式だけでも教えていただけないでしょうか? どう、手をつけたらいいのかわかりません。

  • 線形計画問題

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

  • 線形計画法とは?

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

  • 線形計画問題

    線形計画問題をシンプレックス法で解きたいのですが、よくわかりません。シンプレックス表を作成して解こうとしているのですが、流れがよく分からず解けないのです…。問題をそのまま載せてしまいますが、自分では色々資料を見て考えたつもりです。 分かる方いらっしゃいましたら、どうかよろしくお願いします。 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変数となると上手くいきません。 どなたかわかる方いたら是非ご教授願います。

  • 線形計画法の問題

     ダム建設用のコンクリート作成に必要な砂、および砂利の調達を担当することになりました。ダムで利用する骨材は、不要な成分である細砂を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段階単体法を使う事はまったく理解できません 誰か説明していただきませんか? 人工変数も分からない 教えてください