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

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

No.1 回答者： stomachman 回答日時： 2000/12/29 07:51

線形計画法(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法です。
という訳で、答としては：「頂点だけをたどっていくのに便利だから。」