線形計画法（読み）センケイケイカクホウ（その他表記）linear programming

デジタル大辞泉

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

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

出典　小学館

精選版 日本国語大辞典

せんけいけいかく‐ほう‥ケイクヮクハフ【線形計画法】

1. 〘 名詞 〙 生産計画、輸送計画、経済計画などを最適にするのに用いる数学的方法の一つ。制約条件が幾つかの変数 x₁, x₂ …, x_n の幾つかの一次方程式または一次の不等式で表わされ、計画の良否を測る尺度が x₁, x₂ …, x_n の一次式で表わされる場合に用いられる。近代経済学の重要な方法でもある。リニア‐プログラミング。

出典　精選版 日本国語大辞典

改訂新版　世界大百科事典

線形計画法 (せんけいけいかくほう)
linear programming

リニアプログラミング，略称LP。数理計画法の一種。目的関数の最大値または最小値を求める場合に，制約が一次（線形）の等式または不等式で与えられ，目的関数も一次式（線形）で与えられる場合の解法をいう。扱う問題を線形計画問題という。線形計画問題の特殊な場合に当たる輸送問題や献立の問題は，1940年代前半に発表されているが，線形計画法が注目され，急速に利用されるようになったのは，47年にアメリカのダンツィッヒG.B. Dantzigが，一般の線形計画問題を効率よく解く方法として単体法（シンプレックス法ともいう）を発表してからである。その後，多くの実用的な解法が示されているが，いずれも単体法に基づいている。線形計画法は，適用できる問題が多いこと，解法が確立していること，コンピューターのプログラムの開発が進んでいることなどにより，数理計画法の中でも，最も実用的価値の高いものである。一方，理論面では線形数学の一分野に当たるが，整然とした理論体系が構築されていて，多くの成果が得られている。たとえば，線形計画法より前から存在している定理の中には，線形計画問題を解く過程から眺めたほうが，見通しのよいものもある。

適用例

線形計画法が適用できる分野は，経営，工業，行政など実に多方面に及ぶ。（1）生産計画　限られた資源や労働力の下で，何種類かの品物を生産する場合，最大の利益を上げるような生産量を求める問題。（2）輸送計画　製品を生産地から消費地へ最小の費用で輸送する方法を求める問題。（3）配合問題　何種類かの飼料や原料を配合するとき，栄養素や成分の必要量を充足するような最小費用の配合方法を求める問題。（4）配分問題　限られた資金や資源を何通りかの使途に配分するとき，最悪の事態での損失を最小にする，または利益を最大にする配分方法を求める問題。これはゲーム理論におけるミニ・マックス問題またはマックス・ミニ問題であるが，線形計画問題に変換して解くことができる。

基本定理

線形等式または線形不等式（等号を含むものとする）で与えられる制約を満たす変数の数値の組を実行可能解というが，実行可能解の領域は，2変数であれば凸多角形，一般には凸多面体になる。実行可能解の中で，目的関数を最大または最小にするものを最適解というが，最適解が存在すれば，凸多面体の頂点の中に最適解が存在する。これを線形計画法の基本定理という。頂点を（幾何学的ではなく）線形代数的に表現するために，制約を連立一次方程式に直し，頂点に対応する解を実行可能基底解と呼ぶ。基本定理は，たかだか有限個の実行可能基底解を調べれば，最適解が見つかることを保証している。

単体法

基本定理に基づいて，実行可能基底解を順次作りだしていくことにより，最適解を求める方法。まず一つの実行可能基底解を求め，それが最適であるかどうかを判定し，最適でなければ，軸演算といわれる行列演算を行って，よりよい実行可能基底解を求めるという手順を繰り返す。はじめに実行可能基底解が得られていない場合に，人為的な変数を付加してから単体法を適用する二段階法や罰金法，はじめの係数に0が多い場合や条件や変数の数が多くてコンピューターの主記憶装置にすべての係数を格納できない場合に使える改訂単体法や積行列法など，単体法を発展させた解法がいくつか存在する。

双対性

一つの線形計画問題が与えられたときに，その条件式の係数行列を転置して，もう一つの線形計画問題が作られる。この1対の問題の関係を双対性（そうついせい）dualityといい，元の問題を主問題，新たに作られた問題を双対問題という。双対問題の変数および条件式は，それぞれ主問題の条件式および変数に対応する。たとえば，主問題が資源制約の下での最大利益を求める問題であれば，双対問題の最適解は資源の限界価値を表し，輸送問題であれば，生産地から消費地への限界輸送費を表す。双対問題を解くことで解を求める方法を双対法と呼ぶ。主問題の最適解と双対問題の最適解が満たす必要十分条件が求められていて，それを利用した双対単体法，主双対単体法などの解法が考えられている。

感度分析

最適解を求めたあとで係数が少しぐらい変動しても，最適解が変わらないことがある。変動がどの範囲にあれば最適解が変わらないかを調べるのを感度分析という。また最適でなくなったときに，少しの手間で最適解を求め直す方法もある。

整数線形計画法

線形不等式，線形等式以外に変数のとる値が整数であるという制約が加わった場合。設備投資問題，人員配置問題など適用例はきわめて多い。整数条件の代りに線形条件を付加して，線形計画問題の最適解が整数になるようにする切除平面法などの解法がある。
執筆者：古林 隆

コラム－生産計画における例

出典　株式会社平凡社「改訂新版　世界大百科事典」

百科事典マイペディア

線形計画法【せんけいけいかくほう】

リニア・プログラミング（略称LP）とも。企業の生産，輸送，原料購入などの諸計画，国家的な経済計画，ある種の工学的設計などに広範な適用分野をもつ数理的手法の一つ。限られた資源の最適配置といった問題に適用される。数学的には若干個の変数についての一次不等式または等式による制約条件下で，ある一次式（目的関数）を最大化または最小化する問題。実用的な解法としてはシンプレックス法がよく用いられる。制約条件や目的関数が線型（一次式）でないような問題を合わせて呼ぶときには数理計画法，または活動分析という。
→関連項目応用数学｜オペレーションズリサーチ｜線形写像｜利益計画

出典　株式会社平凡社

ブリタニカ国際大百科事典 小項目事典

線形計画法
せんけいけいかくほう
linear programming; LP

数理計画法の一手法で，最も基本的なもの。リニア・プログラミングともいう。いくつかの制約条件のもとで，ある一定の目的を達成するために，連立の線形式 (1次式) を解くことにより，最適な計画を求めること。1930年代後半に研究が始まったが注目されることはなく，1947年にアメリカ合衆国の数学者ジョージ・B.ダンツィークが，今日でも最も基本的な計算法として用いられているシンプレックス法を考案し，急速に広まった。各種の制約条件を相互の関係を示す線形の式で表し，目的の計画を評価する関数 (これも線形で表す) の値が最大または最小になるような各条件の値を求める。関数を表す式がすべて線形であり，平面上の直線で表現されるところから線形計画法と呼ばれる。当初は軍事分野で開発された方法だが，資源に多くの制約のある生産問題，最適人員配置問題，輸送計画など実際問題に広く適用されており，コンピュータにも線形計画法によって計算を行なうプログラムが一般に準備されている。

出典　ブリタニカ国際大百科事典 小項目事典

ASCII.jpデジタル用語辞典

線形計画法

一次式で制約条件を記述し、その制約条件の中で目標値が最大となる値を求めること。生産管理、オペレーションズリサーチなどに利用される。

出典　ASCII.jpデジタル用語辞典

世界大百科事典（旧版）内の線形計画法の言及

【アクティビティ･アナリシス】より

…学問領域としては，50年代までにすでに理論的基礎が完成し，近年では独自の領域として言及されることはまれだが，これはこの領域が死んだためではなく，生産分析における当然の前提として基礎理論の不可欠の一部に組み込まれ，いわば正統理論化された現実の反映にほかならない。さらに，アクティビティ･アナリシスによってはじめて生産の経済分析を線形計画法やゲーム理論と本質的に関連づけることができるようになり，また投入産出分析(産業連関表)の理論的基礎が用意された事実も見逃せない。　アクティビティ･アナリシスの鍵概念は工程(アクティビティ)である。…

※「線形計画法」について言及している用語解説の一部を掲載しています。

出典｜株式会社平凡社「世界大百科事典（旧版）」