線形計画問題とは？スメイルの問題全部解説するまで帰れま18（9）

「線形計画問題（せんけいけいかくもんだい）」って聞くと、なんだか難しそう…

でも実は数学や経済学、さらにはエンジニアリングの世界でも超よく使われる、超重要な問題なんです！
ざっくり言うと、「限られた資源の中で、いかに効率よく目的を達成するか？」という悩みを数式で解く方法なんですよ。

つまり、めちゃくちゃ役立つ“効率化の魔法”みたいなものなんです！
工場の生産計画から物流のルート、金融のポートフォリオまで、実は私たちの生活のあちこちに関わっています。

今回はスメイルが問題に掲げた、「線形計画問題の解法の計算効率」について、ポップに解説していきますよ〜！

線形計画問題って何？

ざっくり言うと、線形計画問題はこんな感じです：

数学的には、行列 A∈Rm×n とベクトル b∈Rm が与えられ、
ベクトル x∈Rnが条件 Ax≥b

を満たすかどうかを決める問題です。
ここで不等号は、ベクトルの各要素ごとに成り立つことを意味します。

例えばあなたが「お菓子を作る工場のマネージャー」だったとします。

このとき、「条件を全部満たすお菓子の作り方（x）はあるのか？」を調べるのが線形計画問題のひとつの形です。

スメイルが提示した問題の本質は、こういう問いの計算の効率化にあります。

という点がポイントです。

この問題はまだ完全には解決していませんが、

実は線形計画問題はとっても有名で、すでに応用分野も山ほどあります！

など、多くの現場で使われています。

古典的には、単体法（シンプレックス法）が現実的に使われていますが、
最悪計算時間が指数関数的になる可能性があるので、
多項式時間で解く「理論的に保証された」アルゴリズムが求められているのです。

ここでは、単体法など、現実的に使われているアルゴリズムを見てみましょう。

単体法（Simplex method）は、1947年にジョージ・ダンツィグによって考案された、最も古典的で広く使われている線形計画法です。

このアルゴリズムは、制約条件で定まる多面体（ポリトープ）の「頂点」をたどって最適解を探索します。

実際の問題では驚くほど高速に解けるため、現場では今でも根強く利用されています。

しかし理論的には、ある種の人工的な入力例では“指数時間”かかってしまうことが知られており、「最悪ケースでも多項式時間で解けるか？」というスメイルの問題9には直接的な解答になりません。

つまり、「現実には速いが、理論保証が弱い」という点で、部分的な実用解にはなっているが、厳密な意味での決定論的多項式時間アルゴリズムではないのです。

1984年にナルハリ・クフレ（Karmarkar）が発表したこのアルゴリズムは、線形計画問題に対して理論上「多項式時間」で解けることを初めて示した画期的な方法です。

いわゆる「内点法（Interior Point Method）」に分類され、従来の単体法のように頂点をたどるのではなく、ポリトープの“内部”を滑らかに進んで最適解へ向かうアプローチをとります。

これにより、「線形計画は多項式時間で解ける」という希望が一気に現実味を帯びました。

ただし、クフレ＝カチヤン法は浮動小数点の精度や初期値、スケーリングなどの数値的条件に依存する部分があり、厳密な決定論的保証としてはやや限定的とみなされることもあります。

そのため、スメイルの問題9に対しては「現実的にはポジティブな進展だが、完全な理論的解答には至っていない」という扱いです。

上で見たとおり、線形計画問題は現実的には使える解き方は存在し、実用されている例は多くあります。

部分的には解決されているという見方もできるものの、完全ではありません。

もしスメイルの問題が完全に解けて、高速で確実に線形計画問題を解くアルゴリズムが得られたら、

つまり、現代社会のあらゆる「効率化技術」に革命が起きる可能性があるんです。

次回も引き続き、スメイル問題の深掘りをポップにやっていきます！
ぜひお楽しみに〜！🎉