線形計画法

参考文献

• 並木誠, 線形計画法, 応用最適化シリーズ, 朝倉書店, 2008
• 金谷健一, これなら分かる最適化数学 ―基礎原理から計算手法まで―, 共立出版, 2005
• 東京工業大学 塩浦先生の授業資料
• 東京工業大学 水野先生による数理計画法テキスト

阪大 情報科学研究科の梅谷先生がまとめているリストも参照のこと

• 数理最適化のウェブサイト
• 数理最適化の参考書

[証明] 線形計画問題の解は凸超多面体の頂点に存在する

次の式で表される不等式標準形の線形計画問題を考える。

\begin{cases} \ \text{minimize}\quad\quad{\bm c}^T{\bm x} \\ \ \text{subject.to.}\quad A{\bm x}\le {\bm b},\ {\bm x} \ge{\bm 0},\ {\bm x}\in\R^n \end{cases}

まず、 n 次元線形部分空間 P\sube \R^n に対して、 \exist A\in\R^{m\times n}, \exist{\bm b} \in \R^m, P=\{{\bm x}\in \R^n | A{\bm x} \le {\bm b} \} が成り立つとき、 P は凸多面体であると定義される。この定義に従うと、不等式標準形で表される線形計画問題の実行可能領域 X は、凸多面体である。
また X は凸集合でもある。実際、任意の {\bm x}, {\bm y} \in X と任意の \lambda \in [0,1] に対して、 A\left(\lambda{\bm x} + (1-\lambda){\bm y} \right) = \lambda A{\bm x} + (1-\lambda)A{\bm y} \le \lambda{\bm b}+(1-\lambda){\bm b}={\bm b} と \lambda{\bm x} + (1-\lambda){\bm y} \ge {\bm 0} だから、 \lambda{\bm x} + (1-\lambda){\bm y} \in X である。
さらに、 X に含まれる任意の要素 {\bm x} は、 {\bm x_1}, {\bm x_2},\dots,{\bm x_p}\in X の凸結合 \sum_{i=1}^{p}k_i{\bm x_i}=k_1{\bm x_1}+ k_2{\bm x_2}+\dots+k_p{\bm x_p}, \sum_{i=1}^{p}k_i=1, k_i\ge0 の形式で表せる。すなわち、実行可能領域 X は次のように表すことができる。

X = \left\{ \sum_{i=1}^pk_i{\bm x}_i \in \R^n\ |\ \sum_{i=1}^pk_i = 1,\ k_i \ge0,\ i=1,2,\dots, p \right\}

ここで、凸多面体の頂点を定義する。頂点とは、多面体の他のどんな2点を用いても、それらの凸結合では表せない点を意味する。すなわち、凸多面体の点 {\bm x}\in X が次の条件を満たすとき、 {\bm x} は凸多面体の頂点、あるいは端点であるという。

\exist\lambda\in(0,1), {\bm x=\lambda}{\bm y}+ (1-\lambda){\bm z}\Rightarrow {\bm x} = {\bm y} = {\bm z}

上で示した {\bm x_1}, {\bm x_2},\dots,{\bm x_p}\in X は、 X の頂点となっている。実際、 {\bm x} \ne{\bm y} \ne{\bm z} であるような {\bm x}, {\bm y}, {\bm z} \in X に対して、 {\bm x}_i=\lambda{\bm y}+(1-\lambda){\bm z} であるような \lambda\in(0,1) は存在しない。

さて、線形計画問題の目的関数は以下のように表せる。

{\bm c}^T{\bm x} = {\bm c}^T \left(\sum_{i=1}^pk_i{\bm v}_i\right)=\sum_{i=1}^pk_i{\bm c}^T {\bm v}_i

ここで、 \sum_{i=1}^pk_i = 1,\ k_i \ge0\ ( i=1,2,\dots, p) であるから、 {\bm c}^T {\bm x} の値は \min_i {\bm c}^T {\bm v_i}以上、 \max_i {\bm c}^T {\bm v}_i 以下となる。したがって、線形計画問題の最適解は、実行可能領域の頂点に存在する。

参考

• 現代応用数学講座 8 線形代数と凸解析 | コロナ社
• 朝倉書店｜ 線形計画法

[証明] 罰金法で求めた最適解は、もとの線形計画問題の最適解となる

以下の線形計画問題

(P)\quad \begin{cases} \ \text{minimize}\quad\ z={\bm c}^T{\bm x}\\ \ \text{subject.to}\quad A{\bm x} = {\bm b},\ {\bm x} \ge {\bm 0} \end{cases}

に対して、

(M)\quad\begin{cases} \text{minimize}\quad\ \bar{z} = \bar{\bm c}^T \begin{bmatrix}{\bm x}\\{\bm \mu}\end{bmatrix} = \begin{bmatrix}{\bm c}^T & M{\bm 1}^T_m\end{bmatrix}\begin{bmatrix}{\bm x}\\{\bm \mu}\end{bmatrix} \\ \text{subject.to.}\quad \bar{A}\begin{bmatrix}{\bm x}\\{\bm \mu}\end{bmatrix}=\begin{bmatrix}A &I_m\end{bmatrix}\begin{bmatrix}{\bm x}\\{\bm \mu}\end{bmatrix}={\bm b},\ {\bm x}\ge {\bm 0},\ {\bm \mu} \ge {\bm 0} \end{cases}\\ \text{where}\quad M\in\R_+, {\bm 1}_m = \begin{bmatrix}1 &1& \cdots1\end{bmatrix}^T\in\R^m

を考える。問題 (M) の最適解 \begin{bmatrix}{\bm x^*}^T&{\bm \mu^*}^T\end{bmatrix}^T が存在するならば、 {\bm \mu}^* = {\bm 0} でなければならない。

{\bm \mu}^*\ne{\bm 0} である問題 (M) 最適解 \begin{bmatrix}{\bm x^*}^T&{\bm \mu^*}^T\end{bmatrix}^T が存在すると仮定すると、問題 (M) の制約条件を満たす任意の実行可能解 \begin{bmatrix}{\bm x}^T&{\bm \mu}^T\end{bmatrix}^T に対して、以下の等式を満たす必要がある。

\bar{\bm c}^T \begin{bmatrix}{\bm x^*}\\{\bm \mu^*}\end{bmatrix}\le \bar{\bm c}^T \begin{bmatrix}{\bm x}\\{\bm \mu}\end{bmatrix}

ここで \begin{bmatrix}{\bm x}^T&{\bm 0}^T\end{bmatrix}^T は、問題 (M) の制約条件を満たすので実行可能解であるが、上の不等式を満たさない。

\bar{\bm c}^T \begin{bmatrix}{\bm x^*}\\{\bm \mu^*}\end{bmatrix}= \begin{bmatrix}{\bm c}^T & M{\bm 1}^T_m\end{bmatrix}\begin{bmatrix}{\bm x^*}\\{\bm \mu^*}\end{bmatrix}=\begin{bmatrix}{\bm c}^T{\bm x^*}\\{\bm M{\bm 1}^T_m\mu^*}\end{bmatrix} \le \bar{\bm c}^T \begin{bmatrix}{\bm x}\\{\bm 0}\end{bmatrix}

実際、問題 (M) の制約条件より {\mu}^* \ge {\bm 0} であり、 M は任意の大きさの正の実数を選ぶことができるため、 M\to+\infty とすればこの不等式の左辺は発散し、条件を満たさない。したがって、 {\bm \mu}^*\ne{\bm 0} である問題 (M) 最適解 \begin{bmatrix}{\bm x^*}^T&{\bm \mu^*}^T\end{bmatrix}^T は存在しない。ゆえに、問題 (M) の最適解 \begin{bmatrix}{\bm x^*}^T&{\bm \mu^*}^T\end{bmatrix}^T が存在するならば、 {\bm \mu}^* = {\bm 0} でなければならない。

問題 (M) の最適解 \begin{bmatrix}{\bm x^*}^T&{\bm \mu^*}^T\end{bmatrix}^T=\begin{bmatrix}{\bm x^*}^T&{\bm 0}^T\end{bmatrix}^T が存在するならば、問題 (M) の制約条件を満たす任意の {\bm x} に対して、以下の等式を満たす必要がある。

\bar{\bm c}^T \begin{bmatrix}{\bm x}^*\\{\bm 0}\end{bmatrix}=\begin{bmatrix}{\bm c}^T & M{\bm 1}^T_m\end{bmatrix}\begin{bmatrix}{\bm x^*}\\{\bm 0}\end{bmatrix}\le \bar{\bm c}^T \begin{bmatrix}{\bm x}\\{\bm 0}\end{bmatrix}\\ \therefore {\bm c}^T{\bm x}^* \le {\bm c}^T{\bm x}

ここで、問題 (M) の制約条件を満たす任意の実行可能解 \begin{bmatrix}{\bm x}^T&{\bm 0}^T\end{bmatrix}^T は、問題 (P) の実行可能解でもあるから、 {\bm x}^* は問題 (P) の最適解である。

参考

• ビッグM法により有限の最適解が求められたとき

[証明] 不等式標準形の線形計画問題の実行可能領域は凸集合である

不等式標準形の線形計画問題の実行可能領域 X は、 X=\{{\bm x\in\R^n|A{\bm x}={\bm b}, {\bm x\ge{\bm 0}}}\} と表せる。この集合 X が凸集合であることを示す。

まず任意の \lambda\in[0,1] と任意の {\bm x},{\bm y} \in X に対して {\bm z} = \lambda{\bm x}+ (1-\lambda){\bm y} とする。明らかに {\bm z} \ge {\bm 0} であり、 A{\bm z} = \lambda A{\bm x}+ (1-\lambda)A{\bm y}\le \lambda{\bm b}+(1-\lambda){\bm b}={\bm b} であるから、 {\bm z} \in X となる。

よって、 X は凸集合である。

[証明] 双対定理を用いたFarkas の補題

A\in\R^{m\times n}, {\bm b} \in \R^m とするとき、以下のうちいずれか一方が成り立つ

1. \exists{\bm x}\in\R^n, A{\bm x}={\bm b}, {\bm x} \ge{\bm 0}
2. \exist{\bm y}\in\R^m, A^T{\bm y}\le {\bm 0}, {\bm b}^T{\bm y}>0