最適化理論とカーマーカー特許と歴史 - at kaneshin

この記事は 数学 Advent Calendar 2016 - Qiita の6日目の記事です。 大学生の頃、ORを専攻していたため最適化理論について登壇した経験があります。 最適化問題を「線形計画法と整数計画法」で解く─プログラマのための数学勉強会5｜CodeIQ MAGAZINE 時々は最適化理論のことを書いて、最適化理論をアピールしようかと思います。 単体法について 最適化理論についての概要を知りたい場合は先ほどのリンクにあるスライドや動画を参照することをオススメします。 さて、線形計画問題の解法の一つに Dantzig 教授によって提案された単体法（シンプレックス法）という有限回で最適解に到達するということが保証されたアルゴリズムが有名です。 有限回で最適解に到達するのが保証されている理由は、最適解が端点に現れることを利用しているためです。 単体法の問題点 有限回で最適解に到達する