2. 線形最適化問題 #

2.2. 定義 #

線形最適化問題

目的関数および制約条件が線形式であるとき，その数理最適化問題を線形最適化問題もしくは線形計画問題 (Linear Programming) という．単に LP とも．

2.3. 小史 #

線形最適化問題の歴史は，第二次世界大戦時に於ける米空軍の 1942 年の軍事作戦 (後の SCOOP ¹ ¹Scientific Computation of Optimum Programs 計画 [4, 5]) の研究に遡ることができる．

第二次世界大戦中，輸送船の不足が連合国軍にとって危険な供給障害となった．オランダから米国に移住した経済学者の Tjalling Charles Koopmans はこの問題を最適計画問題として捉え，彼は線形計画法によって艦船の航行の最適解を得るに到ったという．

また George Bernard Dantzig は SCOOP 計画にリーダーの一人として加入し，戦後の 1947 年に米空軍の線形計画問題として定式化されたある計画問題を解くために単体法 (simplex method) ² ²単体法という名前は，Danzig がそのアルゴリズムを試した簡単な一つの例題に由来している [6]．その例題は制約条件が \(\sum_{j=1}^n x_j\leq 1\) および \(x_j\geq 0\) からなっており，これらの条件は \(n\) 次元空間の単体 (simplex) とよばれる三角形の高次元拡張図形の方程式となっている．現在では，この特殊な場合に限らず，線形な制約式で定まる一般の凸多胞体についても，単体法という用語が用いられている．を考案した．この出来事を境に，生産管理における非常に広範囲の見かけ上は全く無関係な問題が，線形計画問題 ³ ³当初，線形計画問題を Dantzig は「Programming in a Linear Structure」(線形構造における計画) と呼んでいたが，Koopmans に示唆されて「Linear Programming」という名称になったという．に還元されて新分野の開拓にまで至った．

歴史を語る上では旧ソ連の様々な科学者らもまた多くの貢献をなしているが，政治的に厳しい統制下にあったことや米国や西側諸国などとの交流が自由ではなかったこともあって，それら貢献が雪解けのように後年知られるようになることも珍しくはない．このことは数理最適化の分野に限ったことではない．

2.4. 基本性質 #

線形最適化問題については次のことが基本的である．

線形最適化問題は標準形と呼ばれる次の式の形にいつでも整理できる．

(1)#\[\begin{split}& \mathrm{Minimize\colon}~ f(\vec{x}) = \vec{c}^{\top}\vec{x} \\ & \mathrm{subject~to\colon}~ \\ & A\vec{x} = \vec{b}, \\ &\vec{x} \geq \vec{0}\end{split}\]
実行可能領域は凸多胞体 (convex polytope) の形状をしている．
最適解は実行可能領域である凸多胞体の何れかの頂点である．

上記の事柄を順に説明すると次のとおり．

2.4.1. 標準形について #

目的関数は線形であるから，その一般形はある定数ベクトル \(\vec{c}\) との線形結合となっている．そして制約条件について，等式制約と非負制約のみからなることは次のとおりである．

すべての自由変数は非負変数へ分解できた．またスラック変数を用いることで，不等式制約を等式制約に直すことができる．ここでスラック変数はすべて非負にとっている．よって元の変数の集まりにスラック変数の集まりを追加しても，それらはすべて非負変数である．

以上から，制約条件は等式制約と非負制約にまとめることができる．

2.4.2. 実行可能領域の形状について #

高次元の多面体のことを多胞体 (polytope) という．多胞体は超平面で囲われた図形であり，特に凸集合であるような多胞体を凸多胞体という．

今，線形最適化問題の実行可能領域の形状を問うとき，この図形を表す集合は凸集合となっている．それは次のとおり．

線形最適化問題であるから，一般性を失わず標準形を仮定できる．よって変数の数を \(n\) 個とすれば，実行可能領域 \(R\) は次の集合である．

(2)#\[R = \{\vec{x}\subset \mathbb{R}_{\geq0}^n \mid A\vec{x} = \vec{b}\}\]

任意の \(\vec{x},\vec{y}\in R\) および任意の \(\alpha\in[0,1]\) に対して，次を定める．

(3)#\[\vec{z} = \alpha\vec{x} + (1-\alpha)\vec{y}\]

このとき \(\vec{z}\) の各成分は非負成分の非負倍の線形結合であるから，それ自身の成分もまた非負である．つまり \(\vec{z}\in\mathbb{R}_{\geq0}\) である．

また \(A\vec{z} = \alpha A\vec{x} + (1-\alpha) A\vec{y} = \alpha\vec{b} + (1-\alpha)\vec{b} = \vec{b}\) が従う．よって以上から \(\vec{z} \in R\) である．

ところで \(\vec{z}\) は凸結合であるから，これは集合 \(R\) が凸集合であることを意味する．

2.4.3. 最適解の位置について #

目的関数が線形であることから，超平面を可能な限り平行移動していった位置に最適解があると考えられる．そこで実行可能領域である凸多胞体の端点として \(\{P_i\}_{i\in I}\) をとるとき，任意の実行可能解 \(\vec{x}\) を次の凸結合で表す [7]．

(4)#\[\vec{x} = \sum_{i\in I} \alpha_i P_i\]

ここで各 \(i\) について，\(\alpha_i\geq0\) かつ \(\sum_{i\in I}\alpha_i = 1\) である．今，最適化として最小化を考え，目的関数を \(f\) とおく．そして各端点に限定した中で最も小さい値を \(m^*\) とする．

(5)#\[m^* = \min_{i\in I} f(P_i)\]

このとき \(f\) が線形であることから，任意の実行可能解 \(\vec{x}\) について次が成り立つ．

(6)#\[f(\vec{x}) = \sum_{i\in I}\alpha_i f(P_i) \geq m^* \sum_{i\in I}\alpha_i = m^*\]

つまり \(m^*\) は端点に限らず，実行可能領域全体で最小値を与える．

端点以外の場合として凸領域の境界があり得るが，これは端点を含んでいるので，この意味でも主張は満足されている ⁴ ⁴このような場合には境界すべての各点が最適解を与える訳だから，何か他の新しい要求についての制約条件を課して，尖らせることで最適解を一意にすることができる．つまりもう少し厳しいことを要求できる余地があることをこの状況は述べている．．

ところで複数の端点 \(\{P_j\}_{j\in J\subsetneq I}\) で最小値 \(m^*=f(P_j)\) を与える可能性がある．この場合にはこれらの点のいかなる凸結合 \(\vec{x}_J\) に対しても，やはり同じ最小値 \(m^*\) を与える．これは次のとおりである．

前提から \(\bar{j}\in \bar{J}=I\setminus J\) に対しては最小値を与えないから，\(f(P_{\bar{j}}) > m^*\) が従う．ここで次の凸結合をとる (各 \(j\) について，\(\beta_j\geq0\) かつ \(\sum_{j\in J}\beta_j = 1\) とする)．

(7)#\[\vec{x}_J = \sum_{j\in J}\beta_j P_j\]

すると \(f\) の線形性と \(\vec{x}_J\) が凸結合であることから，直ちに次の評価が得られる．

(8)#\[f(\vec{x}_J) = m^*\]

さて一方で，\(\vec{x}_J\) と書けない他の任意の実行可能解 \(\vec{x}_{\bar{J}}\) は，すべての端点についての凸結合をとる必要がある．

(9)#\[\vec{x}_{\bar{J}} = \sum_{i\in I}\alpha_i P_i\]

すると \(\vec{x}_{\bar{J}}\) での目的関数値として次の評価ができる．

(10)#\[f(\vec{x}_{\bar{J}}) = \sum_{i\in I}\alpha_i f(P_i) > \sum_{i\in I}\alpha_i m^* = m^*\]

故に \(f(\vec{x})=m^*\) となるのは，最小値を与える端点の凸結合 \(\vec{x}_J\) に限られる．

以上に述べた線形最適化問題の基本的な性質は単体法とよばれる解法の論拠となる．

2.5. ベクトル行列記法 #

線形最適化問題の定式化について理論的側面で整理する際には，線形代数との親和性からベクトルと行列で記述することが専らである．先に述べた標準形 (1) はその最たる一例である．

ここでは下記に再掲する標準形について，それらは単体法を理解するうえで，基本的な概念や名称について述べる．

(11)#\[\begin{split}& \mathrm{Minimize\colon}~ f(\vec{x}) = \vec{c}^{\top}\vec{x} \\ & \mathrm{subject~to\colon}~ \\ & A\vec{x} = \vec{b}, \\ &\vec{x} \geq \vec{0}\end{split}\]

変数について
- \(\vec{x}\) は \(\vec{x}=(x_i,\xi_i)\) であってスラック変数 \(\xi\) も含む．このためその分だけ行列 \(A\) は正方行列のサイズからずれ，また制約条件は等式と非負条件として表される．
- 不等号は，ベクトルの各成分ごとに，記された不等号が両辺で成立することを意味する．
基底変数，非基底変数
- 変数をベクトルで書いたことにより， \(\vec{x}\) の成分のうち，スラック変数でない元の変数を基底変数，スラック変数である方を非基底変数という．
基底変数ベクトル，非基底変数ベクトル
- 基底変数を成分にもつベクトルをそれぞれ基底変数ベクトル \(\vec{x}_B\) という．
- 非基底変数を成分にもつベクトルを非基底変数ベクトル \(\vec{x}_N\) という．
行列 \(A\) について
- 基底変数と非基底変数の総数を \(n\) とし，基底変数の総数を \(m\) とする．つまり行列 \(A\) としては \(m\times n\) の型を考える．
- \(\operatorname{rank} A=m\) とし，基底変数はすべて独立変数で退化がないものとする．
基底行列，非基底行列
- 基底変数ベクトルおよび非基底変数ベクトルに作用する \(A\) の小行列をそれぞれ \(B,N\) とかくとき， \(B\) を基底行列， \(N\) を非基底行列という．
- \(B\) としてはしばしば正則に限る．
- \(A\) の転置に気を付ける．
(12)#\[\begin{split}A = \begin{bmatrix} B & N \end{bmatrix} \Leftrightarrow A^{\top} = \begin{bmatrix} B^{\top} \\ N^{\top} \end{bmatrix}\end{split}\]

標準形を \(\vec{x}_B,\vec{N},B,N\) で書き直して，線形最適化問題の構造をこれら二つの要因について言及できる．

基底解
- 最も単純な端点解である次は基底解とよばれる．
(13)#\[(\vec{x}_B , \vec{x}_N) = (\vec{\theta}_B , \vec{0})\]
実行可能基底解
- 制約条件 \(A\vec{x} = \vec{b}\) は次のように書き直せる．
(14)#\[B\vec{x}_B + N\vec{x}_N = \vec{b}\]
- \(B\) が正則だとすると，\(\vec{x}_N=\vec{0}\) と置いて次の基底解が得られる．
(15)#\[(\vec{x}_B , \vec{x}_N) = (B^{-1}\vec{b} , \vec{0})\]
- 特に \(B^{-1}\vec{b}\geq\vec{0}\) が成立しているならば，\(\vec{x}_B\geq 0\) であるから，実行可能解としての端点解となって，これを実行可能基底解とよぶ．
ピボット操作
- 実行可能基底解に対して，基底変数と非基底変数を入れ替えた基底解が，再び実行可能基底解となるとき，この操作をピボット操作 (枢軸演算とも) という．

基底解の何れかは最適解の可能性がある．適切にピボット操作を繰り返すことで，最適解に至ることになる．このために，最適解かどうかを判定する必要がある．それは次のとおり．

単体乗数
- 次の \(\vec{\pi}\) を単体乗数 (simplex multiplier) という．
(16)#\[\vec{\pi} = (B^T)^{-1}\vec{c}_B\]
- 但し目的関数を基底変数と非基底変数とで書き直した時の係数を次のように置いた．
(17)#\[f(\vec{x}) = \vec{c}^{\top}\vec{x} = \vec{c}_B^{\top}\vec{x}_B + \vec{c}_N^{\top}\vec{x}_N\]
単体辞書，相対費用係数
- 制約条件 \(A\vec{x}=\vec{b}\) を基底変数ベクトル \(\vec{x}_B\) を非基底変数ベクトル \(\vec{x}_N\) で書き直すと，\(B\vec{x}_B + N\vec{x}_N = \vec{b}\) であった．これから \(B\) が正則ならば，基底変数は非基底変数によって次ののように表される．
(18)#\[\vec{x}_B = B^{-1}\vec{b} - B^{-1}N\vec{x}_N\]
- これを用いて，元の標準形を非基底変数のみで書き直せば次のとおりである．
(19)#\[\begin{split}& \mathrm{Minimize\colon}~ f(\vec{x}_N) = \vec{\gamma}^{\top}\vec{x}_N + \vec{\pi}^{\top}\vec{b} \\ & \mathrm{subject~to\colon}~ \\ &B^{-1}\vec{b} - B^{-1}N\vec{x}_N \geq \vec{0}, \\ &\vec{x}_N \geq \vec{0}\end{split}\]
- 上記のうち，非負制約を除いた等式系を単体辞書 (simplex dictionary) または単に辞書という．
- なおここで次を定義した．これを非基底変数ベクトル \(\vec{x}_N\) の相対費用係数 (または単に相対費用 (relative cost)) という．相対費用は他にも被約費用 (reduced cost) などの様々な異称がある．
(20)#\[\vec{\gamma} = \vec{c}_N - N^{\top}\vec{\pi}\]
- 目的関数は \(\vec{\gamma}^{\top}\vec{x}_N\) という変数部分と定数項 \(\vec{\pi}^{\top}\vec{b}\) に分かれることになる．
最適性条件
- 実行可能解に対して，相対費用係数が次を満たす場合を考える．
(21)#\[\vec{\gamma} \geq \vec{0}\]
- すると実行可能解ならば，\(\vec{x}_N \geq \vec{0}\) を満たすので，上記の相対費用係数の条件と合わせて，目的関数は \(\vec{x}_N=\vec{0}\) (端点解) のとき最小値として次の値をとる．
(22)#\[f^*(\vec{x}_N=\vec{0}) = \vec{\pi}^{\top}\vec{b}\]
- つまりこのとき基底解は最適解となり，そうでない場合には単に実行可能基底解となる．即ち，相対費用係数の条件 (21) は最適性の条件を与えている．このことから (21) を線形最適化問題の最適性条件という．
最適基底解，最適基底行列
- 最適性条件を満たす実行可能基底解を最適基底解という．そしてこのときの基底行列を最適基底行列 (単に最適基底とも) という．

以上のように線形最適化問題は，ベクトル行列記法によって整理される．

線形最適化問題

目次

2. 線形最適化問題 #

2.1. 導入 #

2.2. 定義 #

2.3. 小史 #

2.4. 基本性質 #

2.4.1. 標準形について #

2.4.2. 実行可能領域の形状について #

2.4.3. 最適解の位置について #

2.5. ベクトル行列記法 #