線型計画法とは？わかりやすく解説

線型計画法（せんけいけいかくほう、英語: linear programming、略称: LP）は、数理計画法において、いくつかの1次不等式および1次等式を満たす変数の値の中で、ある1次式を最大化または最小化する値を求める方法である。線形計画法の対象となる最適化問題を線型計画問題という。

概要

線型計画法はいくつかの理由で最適化の重要な分野である。オペレーションズリサーチの多くの実際的な問題は線型計画問題として記述できる。ある特殊なケースのネットワークフロー問題（英語版）や多品種流問題（英語版）といった線型計画問題はこれらを解くために特別なアルゴリズムを考案するに値するほど重要だと考えられている。他のタイプの最適化問題に使われる多くのアルゴリズムは線型計画法を解くことで代用できる。歴史的には、線型計画法の考えによって双対性、分割、凸解析の重要性や一般化のような最適化の主要な理論を引き起こした。

線型計画問題

数学的には線型計画問題は、目的関数と制約条件がすべて線型の最適化問題である。

2変数 $x_{1}(\geq 0)$

出典は列挙するだけでなく、脚注などを用いてどの記述の情報源であるかを明記してください。 記事の信頼性向上にご協力をお願いいたします。（2023年12月）

Hodges, S. M. （1977年）, "A Model for Bond Portfolio Improvement," Journal of Financial and Quantitative Analysis, June 1977, pp.243-260.
Ronn, E. I. （1987年）, "A New Linear Programming Approach to Bond Portfolio Management," Journal of Financial and Quantitative Analysis, December 1987, pp. 439-466.
V. Chv'atal: Linear Programming, W. H. Freeman, New York, 1983.
G. B. Dantzig: Linear Programming and Extensions, Princeton University Press, Princeton, 1963.
Y. E. Nesterov and A. S. Nemirovskii: Interior-Point Polynomial Algorithms in Convex Programming, SIAM, Philadelphia, 1994.
A. Schrijver: Theory of Linear and Integer Programming, John Wiley and Sons, New York, 1986.
水野眞治, 『シンプレックス法の巡回とその回避』
松井知己, 『Bland の最小添字規則の有限性 -単体法の非巡回ピヴォット規則- 』
藤重悟：「線形計画問題の強多項式解法について」,オベレーションズ・リサーチ，1987年1月号，pp.14-18.
室田一雄、杉原正顕：「線形代数II」、東京大学工学教程、丸善出版（2013）.

線型計画法とは？わかりやすく解説