Linear Algebra (D. Cherney et al.) 一日目

CC BY-NC-SA 3.0

Chapter 1. What is Linear Algebra?

線形代数はベクトルと線形関数の研究である

Chapter 2. Systems of Linear Equations

ガウスの掃き出し法の話題

Chapter 3. The Simplex Method

線形連立不等式の話題.最適化やオペレーションリサーチに応用できる.

3.1 Pablo’s Problem

Example 35. (Pablo’s problem restated)

(Pabloは例に出てくる栄養士の名で,アルゴリズムの開発者とかではない)
$x\geq 5, y\geq 7, 15 \leq x+y \leq 25$のもとで, $s = 5x+10y$ を最小にする$x, y$を求める.

3.2 Graphical Solutions

fig.1 $x\geq 5, y\geq 7, 15 \leq x+y \leq 25$ 条件を満たす点を影に塗ったグラフ

$s = 5x + 10y$を最小にするには,$x+y=15$を満たし他の条件を満たす点を探せばよいのは明らかで,この場合は四角形の頂点$(8, 7)$.このように, 最適解が条件を満たす図形の頂点となるのがlinear programming problemの特徴である.

fig.2 $s= 5x + 10y$を追加した図

3.3 Dantzig’s Algorithm

Problem 38

線形関数 $f(x_1, \cdots, x_n)$を$x_i \geq 0$, $Mx = v$ ($M \in M(m, n), v \in \mathbb{R}^m, x = (x_1, ..., x_n)^T$)のもとで最大化する.
この問題は拡大係数行列に行基本変形を施して解ける.

Example 39

$f(x_1, ..., x_n)$ を$c(x_1, ..., x_n) = k$のもとで最大化するというのは,$c=k$が満たされているなら,
$f(x_1, ..., x_n) + \alpha c(x_1, ..., x_n)$を最大化するのと同じこと.$\alpha$をうまく選んで簡単な問題に変形する.

$f(x, y, z, w) = 3x - 3y -z +4w$を,
$$\begin{cases} c_1 = x + y + z + w &= 5 \\ c_2 = x+ 2y + 3z + 2w &= 6\end{cases}$$
をみたしつつ最大化する.
$f$の定義は$-3x + 3y + z - 4w + f = 0$と同値.
$$\left( \begin{array}{} 1 & 1 & 1 & 1 & 0 & 5 \\ 1 & 2 & 3 & 2 & 0 & 6 \\ -3 & 3 & 1 & -4 & 1 & 0\end{array} \right) \Leftrightarrow \begin{cases} c_1 = 5 \\ c_2 = 6 \\ f = 3x - 3y - z + 4w \end{cases}$$
こうして,問題から最後の行が最大化すべき関数$f$で, 他の行が制約条件であるような拡大係数行列を作れた.

Example 41 (Performing EROs)

上の拡大係数行列で, 最後の行の$x, y, z, w$の係数の部分,つまり$-3, 3, 1, -4$の部分がすべて非負で,かつ0が多くなるように行基本変形を施すと,
$$\left( \begin{array}{} 1/2 & 0 & -1/2 & 0 & 0 & 2 \\ 1 & 2 & 3 & 2 & 0 & 6 \\ 0 & 7 & 6 & 0 & 1 & 16\end{array} \right)$$
となって,最後の行の意味は$f = 16 - 7y - 6z$. $y, z \geq 0$だから, 最大の$f$は$f=16$.
$y, z = 0$としたときも制約条件を満たせるか確かめて計算終了.