11/16/22
線形計画(Linear Programming)は直接コンピュータ プログラミングと関わるものではない。
Programmingは1950年代、軍事用語で 訓練や物資の輸送、配備の計画を意味した。
線形計画法の「線形」は実行可能な条件が 線形不等式によって表されていることが 理由である。
数理経済学だけでなくコンピュータ・サイエンスに おいても重要な役割を果たす。
\[ 最大化： x_1 + x_2 \]
\[\begin{eqnarray*} 制約： && x_1 \geq 0 \\ && x_2\geq 0 \\ && x_2 - x_1 \leq 1 \\ && x_1 + 6x_2 \leq 15\\ && 4x_1 - x_2 \leq 10 \end{eqnarray*}\]
一般の線形計画問題においては、与えられた線形不等式や 線形等式の系を満たす ベクトル\({\bf x} = (x_1, x_2, \ldots, x_n)\)のなかで、 目的関数 \[ {\bf c}^T{\bf x} = c_1x_1 + c_2x_2 + \cdots + c_nx_n \] を最大化または最小化するものを見つけることが目的。
\({\bf x}\)が満たすべき等式や不等式を制約条件 と呼ぶ。
連立方程式が行列を使って \[ A{\bf x} = {\bf b} \] と簡単に表されたように行列を使って 表したい。
そのため、例えば等式 \[ x_1 + 3x_2 = 7 \] を不等式の組、
\[\begin{eqnarray*} x_1 + 3x_2 & \leq & 7\\ -x_1 - 3x_2 & \leq & -7\\ \end{eqnarray*}\]
のように表す。
最小化問題は目的関数\({\bf c}^T{\bf x}\)を \(-{\bf c}^T{\bf x}\)と変換することにより、 最大化問題に変形できる。
よって、線形計画問題はベクトル\({\bf c},{\bf b}\)と 行列\(A\)を適切に選ぶことにより、 \[\begin{eqnarray*} 最大化 & & {\bf c}^T{\bf x}\\ 制約 &&A{\bf x} \leq {\bf b} \end{eqnarray*}\] と表現できる。
\[ \begin{eqnarray*} 最大化: && x_1 + x_2\\ 制約： && x_1 \geq 0 \\ && x_2\geq 0 \\ && x_2 - x_1 \leq 1 \\ && x_1 + 6x_2 \leq 15\\ && 4x_1 - x_2 \leq 10 \end{eqnarray*} ~~~\Longrightarrow~~~ \begin{array}{c} {\bf c}^T = (1,1), \\ A = \begin{pmatrix} -1 & 0\\ 0 & -1 \\ -1 & 1 \\ 1 & 6 \\ 4 & -1\\ \end{pmatrix},\\ {\bf b}^T = (0,0,1,15,10) \end{array} \]
線形計画問題においてすべての制約を満たす \({\bf x}\)を実行可能解と呼ぶ。
つまり、実行可能解の集合は
\[ \{{\bf x}\in {\mathbb R}^n\,|\, A{\bf x}\leq {\bf c}\} \]
実行可能解のなかで目的関数を最大化する ものを最適解と呼ぶ。
一般に線形計画は最適解を
のいずれかである。
例えば上の例で制約を変えず、目的関数の\({\bf c}\)を \({\bf c}^T = (\frac{1}{6}, 1)\)と変更すると
\[ \begin{eqnarray*} 最大化: && x_1 + x_2\\ 制約： && x_1 \geq 0 \\ && x_2\geq 0 \\ && x_2 - x_1 {\color{red}\geq} 1 \\ && x_1 + 6x_2 \leq 15\\ && 4x_1 - x_2 {\color{red}\geq}10 \end{eqnarray*} \]
とすると
実行可能解が空
上の例では変数は２つだけで図を描くことで 問題が解けた。 しかし、一般には数千個の変数を持つ線形計画問題を 解くことは珍しくない。
次の点が重要：
線形計画問題は理論的にも実用的にも高速に解を 求めることが出来る。
ただし、高速なアルゴリズムは単純なものではないが、 そのようなアルゴリズムを実装した様々なソフトウエアが 存在する。
よって問題を線型計画法として定式化することが出来れば 高速な求解が可能
package タブ -> インストールボタン -> lpSoveを検索
\[ 最大化： x_1 + x_2 \]
\[\begin{eqnarray*} 制約： && x_1 \geq 0 \\ && x_2\geq 0 \\ && x_2 - x_1 \leq 1 \\ && x_1 + 6x_2 \leq 15\\ && 4x_1 - x_2 \leq 10 \end{eqnarray*}\]
library(lpSolve)
c = c(1,1)
A = matrix(c(-1, 0, 0, -1, -1, 1, 1, 6, 4, -1), ncol=2, byrow=T)
b = c(0,0,1,15,10)
dir = rep("<=",5)
sol=lp("max", c, A, dir, b)
A [,1] [,2]
[1,] -1 0
[2,] 0 -1
[3,] -1 1
[4,] 1 6
[5,] 4 -1