数理最適化（線形計画問題①）

線形計画問題は、次の特徴を持つ最適化問題です。
・目的関数が線形
・変数が0以上
・全ての制約条件が線形の等式、不等式で表現できる
・目的関数を最大化、または最小化する問題

線形とは

一次関数を示します。
一次関数とは、y = ax + b の形で表される関数です。
変数 x に対して、係数（定数）のみを掛けている関数です。

ナップサック問題が線形問題です。
品物Aと品物Bをナップサックに入れるとします。
重さをw、品物の個数（変数）をx、ナップサックに入れた品物の総重量をWとすると、

$$
W = ( w_A×x_A ) + ( w_B×x_B )
$$

となります。
変数 x に対して定数である重さ w のみを掛けているため、ナップサック問題の目的関数は一次関数になります。

制約条件を見てみます。
制約条件は、「総重量が Wmax 以下」です。
次のように表すことができます。

$$
W =  ( w_A×x_A ) + ( w_B×x_B ) \le W_{max}
$$

等式とは、左と右が等しいことを示す式です。

$$
A = B
$$

不等式とは、左と右が等しくないか、大小関係があることを示す式です。

$$
\begin{array}{l:l}
A \ne B & AとBは等しくない \\
\hline
A \le B & AはB以下\\
\hline
A < B & AはBより小さい\\
\hline
A \ge B & AはB以上\\
\hline
A > B & AはBより大きい\\
\end {array}
$$

ナップサック問題は、「目的関数が一次関数」「変数が0以上」「全ての制約条件が線形の不等式」「目的関数の最大化を目指す」問題です。
そのため、線形計画計画問題となります。

線形計画問題の表記方法

変数と制約条件をまとめて表すことが多いです。

目的関数

$$
最大化　\sum\limits_{i=1}^n w_ix_i
$$

制約条件

$$
条件　\sum\limits_{i=1}^n w_ix_i \le W_{max}\\
xi \ge0,    \forall i
$$

Σは、総和（sum）を示します。
i が 1 から n までなので、

$$
w_1x_1 + w_2x_2 + ・・・ + w_nx_n
$$

という意味になります。
∀iは、「全ての i 」という意味です。
全ての i が左の条件（変数が0以上）を満たすという意味です。

また、行列表記で以下のように表記します。

目的関数

$$
最大化　w ^\top x \\
$$

制約条件

$$
条件　w ^\top x \le W_{max} \\
x \ge 0
$$

記号 ⊤ は、行列の転置を示します。
転置とは、行列の行と列を入れ替える操作です。
もとの行列が下記だったとします。

$$
w =
\begin{bmatrix}
w_1 \\
w_2\\
…\\
w_n
\end{bmatrix}
$$

w に、⊤を付けると、行と列が入れ替わり、以下のようになります。

$$
w ^\top=
\begin{bmatrix}
w_1 w_2 … w_n
\end{bmatrix}
$$

このように、1列だったものが、1行になります。
元の w の行列が縦1列なのは、行列の考え方が
・列：特徴
・行：特徴の種類
ナップサック問題を例にとると、以下のようになります。

$$
\begin{array}{c:c:c}
 & 重さ & 個数 \\
\hline
品物_1 & w_1 & x_1\\
品物_2 & w_1 & x_1\\
… & … & …\\
品物_n & w_n & x_n\\
\end {array}
$$

そのため、w は1列になります。
なぜこのように行と列を入れ替えるのかというと、行列の掛け算の方法から来ています。
行列の掛け算は、左の行列の 行 と、右の行列の 列 との間の対応する数値の積の合計です。
つまり、
　　行列の掛け算　＝　左の行列の1行目1列目 × 右の行列の1行目1列目
　　　　　　　　　＋　左の行列の1行目2列目 × 右の行列の2行目1列目
　　　　　　　　　＋　左の行列の1行目3列目 × 右の行列の3行目1列目
　　　　　　　　　　　　　　・・・
　　　　　　　　　＋　左の行列の1行目n列目 × 右の行列のn行目1列目
　　　　　　　　　＋　左の行列の2行目1列目 × 右の行列の1行目2列目
　　　　　　　　　＋　左の行列の2行目2列目 × 右の行列の2行目2列目
　　　　　　　　　　　　　　・・・
そのため、以下のようになります。

$$
w ^\top x  = 
\begin{bmatrix}
w_1  w_2  …  w_n
\end{bmatrix}
×
\begin{bmatrix}
x_1 \\
x_2\\
…\\
x_n
\end{bmatrix}
 = 
w_1x_1 + w_2x_2 + … + w_nx_n
$$

現実問題の定式化

現実の問題を線形計画問題にあてはめる（定式化する）ことは、簡単なことではありません。
それは、現実問題が非線形である場合が多いためです。
しかし、現実問題をそのまま非線形計画問題にあてはめても、最適解を求めることが困難だったりします。
それよりも、若干正確性を落としても線形計画問題にあてはめた方が効率的に最適解を求められる場合が多いです。
一見非線形に見える最適化問題でも変数を追加したり、式を変形したりすると、線形計画問題にあてはめることができる場合があります。
そのため、すぐに非線形計画問題として扱うのではなく、線形計画問題に当てはめられないか、または近似できないかをよく考える必要があります。