線形代数の応用:線形計画法~輸送コストの最小化を例に

どうも、木村(@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・画像処理(拡大縮小・反転、回転、せん断)について

漸化式(フィボナッチ数列)を線形代数(線形空間、固有ベクトル)で解く方法を解説

大学数学のロードマップ ~ 分野一覧と学ぶ順序