線形計画では何を学ぶのか: 線形計画入門 1

この章では、線形計画で扱う内容を見ていきます。

線形計画の位置づけ

線形計画は最適化と呼ばれる分野に属するトピックです。最適の分野では、複数の設定の中から最も良い設定をコンピュータを使って発見することを考えます。線形計画は設定の良さと条件が線形関数で表される場合に相当します。線形計画は非線形の定式化に比べて簡単なので、最適化分野への入門用のトピックとして扱われるほか、より高度な最適化技法の基礎を担う重要なトピックです。

線形計画はオペレーションズリサーチと呼ばれる分野に属するトピックでもあります。オペレーションズリサーチでは、物資の運送計画、人事のスケジューリング、金融資産の投資方法などを数理的にモデリングし、最も良い方法を最適化によって発見することを考えます。線形計画は他のモデリング方法に比べ簡単で、より高度なモデルの最適化の基礎となるので、オペレーションズリサーチにおいても線形計画は基礎的かつ重要な話題です。

最適化問題の定式化

最適化の一般的な定式化

最適化問題は、制約条件と呼ばれる集合 \(\mathcal{C}\) と目的関数と呼ばれる実数値関数 \(f \colon \mathcal{C} \to \mathbb{R}\)との組で定義されます。\(\mathcal{C}\) の各要素は一つの設定を表し、\(f(x)\) は設定 \(x \in \mathcal{C}\) の良さを表します。最適化問題の目的は \(f(x)\) が最大となる \(x \in \mathcal{C}\) を見つけることです。

例: 金融資産の投資方法

例として、金融資産の投資方法を考えてみましょう。ここでは簡単のため、二種類の株式 A, B があるとし、株式 A を \(x\) 株、株式 B を \(y\) 株買うとします。あまりたくさん株を買うと予算が高く付きます。そこで、買う株数について制約条件を付けましょう。株式 A は 100 円、株式 B は 300 円、予算が 5 万円だとすると、\(\mathcal{C} = \{(x, y) \mid 100 x + 300 y \le 50000, x \ge 0, y \ge 0\}\) というように予算制約を表せます。\(f(x, y)\) を株式 A を \(x\) 株、株式 B を \(y\) 株買ったときの期待利益とすると、制約条件 \(\mathcal{C}\) の下で \(f\) を最適化することで最もよい投資方法が見つかります。

\(f\) を既知として話を進めましたが、実際は \(f\) を正確に指定するのは難しい問題です。過去の株価のデータや投資家の経験などをもとに良さそうな \(f\) を \(x, y\) の関数として表すことになります。例えば、過去の株式 A の一株あたりの利益の平均値が \(20\)、株式 B では \(30\) だとすると \(f(x, y) = 20x + 30y\) と表すことなどが考えられます。このように、過去のデータや経験から目的関数や制約条件を設定することをモデリングといいます。

線形計画の定式化

線形計画は最適化問題の特別な場合です。制約条件が \(\mathcal{C} = \{x \in \mathbb{R}^d \mid A x \le b\}\) というように線形不等式で表され、目的関数が \(f(x) = c^{\top} x\) というように線形関数で書けるとき、この問題を線形計画といいます。例えば、上述の金融資産の例において、\(\mathcal{C} = \{(x, y) \mid 100 x + 300 y \le 50000\}, f(x, y) = 20x + 30y\) は線形計画になります。

線形計画で学ぶこと

線形計画の講義で中心となるのは、制約条件と目的関数が（行列 \(A\)、ベクトル \(b\)、ベクトル \(c\) の形で）与えられたとき、どのようにすれば最適な \(x\) を計算できるかについての技法を学ぶことです。この記事ではシンプレックス法という最も基本的なアルゴリズムを紹介します。

線形計画で扱うのはこれだけではありません。まず、線形計画を活用するには、所望の問題を線形計画の形でモデリングしなければなりません。具体的にどのような定式化になるかは直面している問題やデータ次第ですが、このようにモデリングすると便利だというパターンやコツのようなものはあります。そのようなモデリングの基本パターンを身につけるのも重要です。この記事では第四章で応用例をいくつか紹介します。

また、最適化問題の特性を知ることも理論上・応用上ともに重要です。例えば、最適な \(x\) が満たすべき必要条件や、最適性の十分条件を数学的に示すことは、高性能なアルゴリズムを開発するのに重要なほか、アルゴリズムの正当性を示すことにも使われます。また、第八章では、最適ではない \(x\) が最適な \(x\) と比べてどれほど悪いかを調べたり、制約条件を少し変えたときに最適値にどのように影響するかを調べるのに双対という特性が役立つことを見ます。