線形計画法

「線形の等式条件

a_{i1}x_{1} + a_{i2}x_{2} + ⋯ + a_{in}x_{n} = b_{i} (i = 1, 2, …, ℓ)

および不等式条件

a_{j1}x_{1} + a_{j2}x_{2} + ⋯ + a_{jn}x_{n} ≤ b_{j} (j = ℓ + 1, ℓ + 2, …, m)

を満たす x_{1}, x_{2}, …, x_{n} で線形関数（目的関数）

c_{1}x_{1} + c_{2}x_{2} + ⋯ + c_{n}x_{n}

を最小（または、最大）にする x_{1}, x_{2}, …, x_{n} を計算せよ」という問題を線形計画問題と呼ぶ。生産、販売、通信、輸送等から生ずるさまざまな問題が線形計画問題に定式化される。この問題への定式化、理論的な側面、計算手法を含めて線形計画法（Linear Program）と呼ぶ。

各不等式条件にスラック変数s_{j} ≥ 0 を導入すると、

a_{j1}x_{1} + a_{j2}x_{2} + ⋯ + a_{jn}x_{n} + s_{j} = b_{j}, s_{j} ≥ 0

と変換される。また、各変数 x_{k} は２つの非負な変数の差で

x_{k} = u_{k1} − u_{k2}, u_{k1} ≥ 0, u_{k2} ≥ 0

と表すことが出来る。このような変換により、すべての線形計画問題は線形計画問題の標準形

目的： c_{1}x_{1} + c_{2}x_{2} + ⋯ + c_{n}x_{n} → 最小化
条件： a_{i1}x_{1} + a_{i2}x_{2} + ⋯ + a_{in}x_{n} = b_{i} (i = 1, 2, …, m)
x_{j} ≥ 0 (j = 1, 2, …, n)

に変換出来る。さらに、ベクトルと行列の記法を用いると

目的： c^{T} x → 最小化
条件： x ∈ X ≡ {x ≥ 0 : Ax = b}

と書ける。ただし、 A : m × n 定数行列、 b : m 次元定数列ベクトル、 c : n 次元定数列ベクトル、 x = (x_{1}, x_{2}, …, x_{n})^{T} : n 次元変数列ベクトルであり、 T はベクトルおよび行列の転置を表す。 X を許容領域（実行可能領域）、 x ∈ X を許容解（実行可能解）、目的関数 c^{T} x を最小にする x ∈ X を最小解と呼ぶ。以下では線形計画法の理論の中心をなす双対定理と相補性定理、および、代表的な解法である単体法（シンプレックス法）について解説し、最後に、最近発展した内点法にふれる。

上述の標準形線形計画問題（最小化問題）で使われている定数ベクトル b、 c および定数行列 A を用いた他の線形計画問題

目的： b^{T} y → 最大化
条件： (y, z) ∈ Y ≡ {(y, z) : A^{T} y + z = c, z ≥ 0}

を考える。ただし、 y = (y_{1}, y_{2}, …, y_{m})^{T} : m 次元変数列ベクトル、 z = (z_{1}, z_{2}, …, z_{n})^{T} : n 次元変数列ベクトル。この２つの問題の関係を論ずるときには、元の最小化問題を主問題、対応させて導入した最大化問題を双対問題と呼ぶ。

［双対定理：］

(a) 任意の x ∈ X と (y, z) ∈ Y に対して、 c^{T} x ≥ b^{T} y

(b) x ∈ X が主問題の最小解、かつ、 (y, z) ∈ Y が双対問題の最大解であるための必要十分条件は c^{T} x = b^{T} y

［相補性定理：］

(c) x ∈ X が主問題の最小解、かつ、 (y, z) ∈ Y が双対問題の最大解であるための必要十分条件は x_{j}z_{j} = 0 (j = 1, 2, …, n)

この２つの定理は線形計画法の理論の中心をなすばかりでなく、以下で述べる単体法や内点法等の計算手法にも深く関係している。双対問題も標準形線形計画問題に変換できるから、双対問題の双対問題を構成出来るが、その問題は主問題に一致する。すなわち、主問題と双対問題はたがいに双対になっている。

幾何学的には、標準形線形計画問題の許容領域 X は有限個の超平面で囲まれた多面集合になるが、最小解が存在したとすると X の頂点に対応する最小解が存在する。 1947 年に G.B. Dantzig によって開発された単体法は

I ： X の頂点 x^{0} を１つ求める

II ： x^{0} を初期頂点として、目的関数を小さくしながら X の隣接する頂点をたどって最小解に到達する

という２つのフェイズからなる。これを代数的に説明するために、許容領域を

X = {x = (x_{1}, x_{2}, …, x_{n})^{T} ≥ 0 : ∑_{j=1}^{n} a_{j}x_{j} = b}

と表わす。ただし、 A = [a_{1}, a_{2}, …, a_{n}]、 a_{j} : m 次元列ベクトル。さらに、「任意の許容解 x ∈ X に対して x_{j} > 0 なる要素が m 個以上である」を仮定する。この仮定は非退化の仮定と呼ばれ、単体法の説明を簡単にするためにしばしば仮定される。 x_{j} > 0 なる要素がちょうど m 個である許容解 x ∈ X を（許容または実行可能）基底解、基底解 x ∈ X に対して x_{j} > 0 なる変数 x_{j} を基底変数、それ以外の（x_{j} = 0 なる）変数を非基底変数と呼ぶ。基底変数がちょうど１つだけ異なる２つの基底解 x, y ∈ X は隣接するという。非退化の条件の下では X の頂点と基底解は１対１に対応する。したがって、単体法は I ：基底解 x^{0} を１つ求める

II ： x^{0} を初期基底解として、目的関数を小さくしながら隣接する基底解の列 {x^{p}} をた

どって最小基底解に到達するとなる。初期基底解 x^{0} は、自明な初期基底解を持つ線形計画問題を人工的に作り、それにフェイズ II を適用することによって得られる。各基底解 x^{p} は線形方程式

∑_{j=1}^{n} a_{j}x_{j} = b, x_{j} = 0 (j ∈ J_{p})

を解くことによって得られる。ただし、 J_{p} = {j : x_{j}^{p} = 0}。この際、 x^{p} に隣接する x^{p−1} を計算したときの情報が使えるので上の線形方程式系を初めから解く必要はない。実際には、ピボット演算（枢軸変換）と呼ばれる線形演算によって、 x^{p−1} から x^{p} が計算される。

単体法にはいくつかのバリエ−ション（主単体法 — 上述、双対単体法、主・双対単体法等）がある。計算効率を上げるために、さまざまな工夫が導入されている。特に、大規模な問題（変数の個数が数千〜数万）は過疎なデ−タ構造（行列 A のほとんどの要素が 0）をしており、計算を進める過程でそれを出来るだけ崩さないようにすることが計算効率を上げる鍵となる。

単体法が許容領域の境界上に位置する頂点を辿って最小解に到達する方法であるのに対して、内点法は許容領域の内部を通って最小解に近づこうとする方法である。この方法の契機となったのは 1984 年に提案された Karmarkar 法であり、それ以来数多くの内点法が発表されている。それらの中で現在主流となり、ソフトウェアとして実用化されているのはアフィン変換法と主・双対内点法である。２つの方法とも単体法では解けない超大規模な問題（変数の個数が数十万）の計算結果も報告されている [2]。単体法は 40 年以上の歴史があり、ソフトウェアとしても完成され、世界中に普及している。それに対して内点法の歴史は始ったばかりで、内点法がどのように単体法に置き換わっていくかは、もう数年様子を見なければ分らない。

単体法および双対定理を中心とした線形計画法の参考書は数多く出されている。例えば、 [1]。内点法を含む線形計画法の最近の発展については [3] を参照。

参考文献 [1 ] 今野浩、線形計画法、日科技連出版、１９８７。

[2 ] R.Marsten, R.Subramanian, M.Saltzman, I.Lustig and D.Shanno, “Interior point methods for linear programming: Just call Newton, Lagrange and Fiacco and Mc-Cormick!”, Interface 20 (1990) 105-116.

[3 ] D.Godfarb and M.J.Todd, “Linear Programming” in G.L. Nemhauser, A.H. Rinnooy Kan and M.J. Todd, ed., Handbooks in Operations Research and Management Science, Volume 1, Optimization, North-Holland, Amsterdam, 1989, pp.73-170.