質問: 経営科学の線形計画法、教えてください 線形計画法のシンプレックス法で、問題を解くために不等式であらわされた制約条件式を、わざわざ余裕変数を用いて等式条件にするのはどうしてですか?
回答: 線形計画法(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と呼ばれる変数xn+jを追加して、未知数のベクトル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法です。 という訳で、答としては:「頂点だけをたどっていくのに便利だから。」