どうも、木村（@kimu3_slime）です。
今回は、線形代数学の応用として、線形計画法について、飲料の輸送コストの最小化問題を例に紹介します。
飲料の輸送コストの最小化
適切に選択肢を選ぶことで、かかるコスト（お金や移動距離など）を最小化・最大化したい。こうした問題は最適化問題と呼ばれます。線形計画法では、特に線形の最適化問題を扱います。
と言われてもピンと来ないと思うので、具体例を紹介していきましょう。
僕たちは、飲料を工場で生産し、販売店に輸送するメーカーだとします。
飲料はコーラ、ジュース、コーヒーの3種類で、それぞれの生産量を\(x:=(x_1,x_2,x_3)\)として、生産量を調整することによって、
輸送コスト（目的関数 objective function）：\(f(x)= x_1 + 2x_2 + 3 x_3\)
を最小化する\(x\)を探す問題を考えてみましょう。このような関数の場合、コーラよりジュースが、ジュースよりコーヒーが輸送コストがかかることになっています。ジュースは冷やしておく、コーヒーは温めておくコストがかかるということで。実際に考えたい問題に応じて係数を変えれば、各飲料のコストの重み付けが変えられますね。
このとき当然、生産量は正でなければなりません\(x_1,x_2,x_3\geq 0\)。
この条件だけでは、何も生産しないこと\(f(0,0,0)=0\)が輸送コストの最小化になります。間違ってはいませんが（笑）、意味はありません。そこで次の条件を設定しましょう。
工場での生産量の制約：\(x_1 + x_2 + x_3 =10\)
販売店からの需要：\(5 x_1 + x_3 =20\)
これらを満たしつつ、\(f(x)\)を最小にするような\(x\)（最適解 optimal solution）を求めたいのです。
変数の取りうる値は、3次元空間\(\mathbb{R}^3\)内の特定の部分に制限されています（図では\((x_1,x_2,x_3)= (x,y,z)\)） 。制限条件を満たす点を実行可能点（feasible point）、その集合を実行可能集合（feasible set）と呼びます。
制約条件\(x_1 + x_2 + x_3 =10\), \(5 x_1 + x_3 =20\)は、それぞれが\(\mathbb{R}^3\)内のある平面に対応します。したがって、条件2つを満たす\(x\)は、平面と平面の交点、すなわち図で示された線分上にあります。つまり、今回の問題では実行可能集合は線分です。一般に、それは三角形、そして多面体になります。
そして最適解は、実行可能集合の頂点、境界に位置することが知られています。\(f(x)= C\)という等高面を考え、パラメータ\(C\)を連続的に変化させたとき、実行可能集合の内部ではなく境界からまず交わるからです（実行可能集合が、多面体、凸集合のとき）。
つまり今回のケースでは、最適解の候補は線分の端点\(p=(5/2,0,15/2),q=(4,6,0)\)です。計算してみると、\(f(p)=5/2+3\times 15/2 =25\)、\(f(q)=4+2\times 6 =16\)なので、\(q=(4,6,0)\)が最適解であると言えました。
よって、コーラは4単位、ジュースは6単位、コーヒーは生産しないという分配が、工場の能力、販売店の需要を満たしつつ、輸送コストを最小化することがわかりました。
今回の問題では、非常に単純化された問題を扱いましたが、実際に日本コカ・コーラ株式会社は、製品の製造と輸送に線形計画法を使っているそうです。特に夏場に清涼飲料は売れていて（年間の40%）、計画次第で年間数千万の利益の違いになるようです。
その最適化問題では、飲料を22グループにまとめるとはいえ、変数が36000、制約式が10000も登場します。実行可能集合の頂点の個数\(_n C _m\)は、変数が増えるにつれ、爆発的に増加します。とても手計算は無理で、コンピュータ上でも工夫がいるのがわかりますね。
線形計画法とは
では、これまで扱ってきた問題を一般化して整理しましょう。線形代数学の言葉を使えば、多変数の問題がシンプルに記述できます。
変数の数を\(n\)、制約条件となる方程式の数を\(m\)、\(n>m\)とします。\(x,c \in \mathbb{R}^n\)、\(b \in \mathbb{R}^m\)、\(A\)を\(n\times m\)の行列として、
目的関数：\(f(x) = c \cdot x\)
制約条件：\(Ax =b, \, x \geq 0\)
としたとき、制約条件下で目的関数を最小化する問題を考えられます。制約条件を\(Ax \leq b\)または\(Ax \geq b\)と不等号で満たす問題を考えることもあります。
上で扱った具体例では、\(n=3,m=2\)、\(c=(1,2,3)\)で、\(A=\begin{pmatrix}1& 1& 1 \\5& 0 &1 \end{pmatrix}\)、\(b= (10,20)\)ですね。
また、今回は目的関数を最小化する問題を考えましたが、これは次の最大化する問題に対応しています。\(y \in \mathbb{R}^m\)として、
目的関数（最大化）：\(g(x) = b^{\mathsf{T}} \cdot y\)
制約条件：\(A^{\mathsf{T}}y =c, \, y \geq 0\)
となります（元の制約条件が\(Ax \leq b\)なら、制約条件の不等号を\(A^{\mathsf{T}}y \geq c \)と逆に対応させる）。この最大化問題を、元の問題の双対問題（dual problem）と言います。
もし元の問題が最適解を持つならば、双対問題も最適解を持ち、また両者における最適値もまた等しいことが知られています（双対定理）。つまり、最小化問題と最大化問題は、ある意味では等価なんですね。
今回紹介した問題は、目的関数や制約条件が、線形でした。変数が2倍されれば目的関数は2倍に増え、実行可能集合は直線的な平面に囲まれています。このような最適化問題について考える学問を、線形計画法（linear programming, LP）というわけです。
線形計画法では、最適化問題を解くためのアルゴリズムとして、単体法（シンプレックス法）や内点法といった方法が知られています。線形計画法、そして単体法は、1947年、アメリカの科学者：ジョージ・ダンツィグにより知られるようになりました。
線形でないより一般の最適化問題を扱う分野は、非線形計画法（nonlinear programming, NLP）と呼ばれます。こちらでは、数学の解析学で扱う、ラグランジュの未定乗数法などが有名でしょうか。
線形と非線形両方合わせ、最適化問題を数学的に解く分野は、数理最適化（mathematical optimization）と呼ばれます。さらにこれを含み、数学的または統計的なモデルを使って、生産や輸送の計画を考える分野が、オペレーションズ・リサーチ（operations research, OR）です。
線形計画法の良いテキストが、ウェブ上で無料で公開されています：学習・研究用テキスト(最適化,線形計画法,内点法,数理計画法) – 水野研究室
数理計画法の様々な分野への応用例が、日本語の研究発表としてまとまっています：事例編：数理計画法 – OR事典Wiki、日本オペレーションズ・リサーチ学会
今回は、飲料メーカーの輸送コスト最小化問題を例に、線形計画法を紹介してきました。
限りある資源の中で、コストや移動距離などを最大化・最小化し、望ましい選択肢を見出す問題は、最適化問題の枠組みに入ります。特に線形の問題はシンプルであり、それは線形代数学の言葉で書かれるわけです。
問題を解くためには線形計画法独自の知識が必要になりますが、その基礎段階として、線形代数学を学んでおくのは役立つことでしょう。
木村すらいむ（@kimu3_slime）でした。ではでは。
世界標準MIT教科書 ストラング:線形代数イントロダクション
近代科学社
売り上げランキング: 168,641
共立出版
売り上げランキング: 60,765
こちらもおすすめ
線形代数学の応用：CG・画像処理（拡大縮小・反転、回転、せん断）について
漸化式（フィボナッチ数列）を線形代数（線形空間、固有ベクトル）で解く方法を解説
