線形計画法

デジタル大辞泉

せんけいけいかく‐ほう〔センケイケイクワクハフ〕【線形計画法】

読み方：せんけいけいかくほう

一次の不等式または一次式で表される制約条件のもとで、一次式で表される目的関数を最大または最小にする値を求める数学的手法。生産計画・輸送計画などに応用される。リニアプログラミング。LP（linear programming）。

ウィキペディア

線型計画法

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/03/11 08:29 UTC 版)

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

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

概要

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

線型計画問題

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

2変数 ${\displaystyle 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.
• 水野 眞治, 『シンプレックス法の巡回とその回避』, http://www.me.titech.ac.jp/~mizu_lab/text/PDF-LP/LP3A-simplex.pdf 
• 松井 知己, 『Bland の最小添字規則の有限性 -単体法の非巡回ピヴォット規則- 』, http://tomomi.my.coocan.jp/text/bland7.pdf 
• 藤重悟：「線形計画問題の強多項式解法について」,オベレーションズ・リサーチ，1987年1月号，pp.14-18.
• 室田一雄、杉原正顕：「線形代数II」、東京大学工学教程、丸善出版（2013）.

関連項目

• 線型代数学
• 非線型計画法

表 話 編 歴 数理最適化 • 最適化問題 : メソッド • ヒューリスティック
非線形（無制約）	… 関数　 黄金分割探索 直線探索 ネルダー–ミード法 放物線補間 パウエル法 勾配法 収束性 信頼領域 ウルフ条件 準ニュートン法 BFGS法 ブロイデン法 L-BFGS法 DFP法 SR1法 BHHH法 その他の求解法 ガウス・ニュートン法 最急降下法（確率的） レーベンバーグ・マーカート法 共役勾配法（非線形共役勾配法） 打ち切りニュートン法 ドッグレッグ法 鏡像 座標 バルジライ・ボールウェイン法 … ヘッセ行列 最適化におけるニュートン法	Optimization computes maxima and minima.
非線形（制約付き）	一般 バリア関数 ペナルティ関数法 微分可能 ラグランジュの未定乗数法 拡張ラグランジュ関数法 逐次二次計画法 逐次線形計画法
凸最適化	凸最小化 切除平面法 簡約勾配法 劣勾配法 近接勾配法 線形 および 二次 内点法 アフィンスケーリング法 カーマーカーの射影変換法 メロートラの予測子修正子法 基底-交換 単体法 改訂単体法 十文字法 レムケの相補掃き出し法 その他 カチヤンの楕円体法 有効制約法 列生成法 ベンダーズ分解法
組合せ最適化	系列範例 (Paradigms) 近似アルゴリズム 動的計画法 貪欲法 整数計画問題（分枝限定法・分枝カット法・分枝価格法） グラフ理論 最小全域木 ブルーフカ法 クラスカル法 プリム法 最短経路問題 ベルマン–フォード法 ダイクストラ法 ワーシャル–フロイド法 ジョンソン法 ネットワークフロー (最大流問題) ディニッツ法 エドモンズ・カープ法 フォード・ファルカーソン法 プリフロープッシュ法
メタヒューリスティクス	進化的アルゴリズム（進化戦略・遺伝的アルゴリズム） 山登り法 局所探索法 焼きなまし法 タブーサーチ ベイスンホッピング法 量子焼きなまし法
カテゴリ（最適化 • アルゴリズム） • ソフトウェア

典拠管理データベース: 国立図書館	フランス BnF data ドイツ イスラエル アメリカ 日本 チェコ

ウィキペディア小見出し辞書

線形計画法

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/04/27 00:35 UTC 版)

「ジョージ・ダンツィーグ」の記事における「線形計画法」の解説

線形計画法は線形関係として表される要件のいくつかのリストに対して、与えられた数学モデルの中で最も良い結果（最大利益や最小コストなど）を達成する方法を決定するための数学的方法である。線形計画法は、第二次世界大戦中に軍のコストを削減し、敵の損失を増やすための支出と見返りを計画するために開発された数学モデルとして生まれた。1947年まで秘密にされていた。戦後、多くの業界で日常の計画にそれを使う方法が見出された。 この主題の創始者は、1939年に線形計画問題を開発したロシアの数学者レオニート・カントロヴィチ、1947年にシンプレックス法を発表したダンツィーグ、同年に双対問題の理論を発表したジョン・フォン・ノイマンである。 ダンツィーグの元々の例である、70の仕事に70人を割り当てる最適を見つけるという例は、線形計画法の有用性を例証している。最適な割り当てを選ぶ目的で全ての順列を試験するのに必要な計算能力は膨大であり、可能な割り当ての数は宇宙の粒子数を超える。しかし、問題を線形プログラムとして与え、シンプレックス法を適用すれば、一瞬で最適解を見つけ出すことができる。線形計画法の背後にある理論は、確認しなければならない最適解の可能性を大幅に減らすことができる。 1963年、ダンツィーグのLinear Programming and Extensions（線形計画法とその拡張）がプリンストン大学出版局から出版された。洞察に富み、重要なトピックを網羅したこの本はすぐに線形計画法のバイブルとなった。

Weblio日本語例文用例辞書

「線形計画法」の例文・使い方・用例・文例

• 線形計画法という,最適化手法