linear programmingとは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > デジタル大辞泉 > linear programmingの意味・解説 

エル‐ピー【LP】

読み方:えるぴー

《linear programming》⇒線形計画法


リニア‐プログラミング【linear programming】

読み方:りにあぷろぐらみんぐ

線形計画法


線形計画

読み方せんけいけいかく
【英】:linear programming

概要

最適化問題(数理計画問題)


\mbox{max.} \, f(x) \ ( \,あるいは, \min. \ f(x)) \,
\mbox{s.t.} \, x = (x_1,x_2,\ldots,x_n) \in F,
\,


において, 目的関数 f \,線形であり, かつ, 実行可能集合 F \,線形等式線形不等式用いて表現されている問題.この問題への定式化, および, 解法含めて線形計画と呼ぶ.

詳説

 線形計画(linear programming)(線形計画法, 線形計画問題)は, 複数等式あるいは不等式与えられる線形制約のもとで, 目的関数objective function)と呼ばれる線形関数最大化(または最小化)する問題である. 線形計画問題通常以下の形式により表現される.

\mbox{(P)} \quad
\begin{array}{lll}
          & \mbox{max.} & {\displaystyle \sum_{j=1}^{n}c_j x_j} \\
       & \mbox{s. t.}  & {\displaystyle \sum_{j=1}^{n}a_{ij} x_j}
                           \leq b_i \ (i=1,2,\ldots,m), 
       x_1,x_2,\ldots ,x_n \geq 0.
\end{array}


ここで, c_j (j=1,2,\ldots,n), \, b_i (i=1,2,\ldots,m),\,a_{ij} (i=1,2,\ldots,m, \ j=1,2,\ldots,n)実数, \boldsymbol{x}=(x_1,x_2,\ldots, x_m)n\,個の変数からなるn\,次元ベクトルである. すべての線形計画問題は, 簡単な変換により, この形式帰着される. 問題(P)の制約条件満たす\boldsymbol{x}実行可能解feasible solution)と呼び, 実行可能解のなかで目的関数最大にするものを最適解と呼ぶ.

 実社会における多く問題線形計画問題として定式化できる. 線形計画の応用は, 初期の頃は, 軍事, 経済学ゲーム理論中心であったが, 次第にその重点産業分野へと移行された [2, 3]. 1947年ダンツィクG. B. Dantzig)[2] によって提案され単体法simplex method)は, コンピュータ急速な発展大規模な線形方程式処理する技術の向上あいまって, 線形計画問題対す極めて実用的な解法となっている. しかし, 単体法は Klee-Minty [4] により, 問題入力サイズ変数個数制約本数に関する多項式時間解法ではないことが指摘された. カチヤン(L. G. Khachian)は楕円体法提案し, 最初多項式時間解法与えた. カーマーカー法およびその後開発され内点法は, 超大規模な線形計画問題対し, 理論および実用両面において, 単体法より優れた解法として認められている.

 以下では, 線形計画の理論重要な役割を果たす双対問題dual problem), 双対定理duality theorem)および相補性定理complementarity slackness theorem)について述べる.

 各々線形計画問題(P)には, 双対問題呼ばれる以下の線形計画問題(D)を対応させることができる:


\mbox{(D)} \quad
\begin{array}{lll}
          & \mbox{min.} & {\displaystyle \sum_{i=1}^{m}b_i y_i} \\
    & \mbox{s. t.}  & {\displaystyle \sum_{i=1}^{m}a_{ij}y_i}
                           \geq c_j \;  (j=1,2,\ldots,n), 
          y_1,y_2,\ldots,y_m \geq 0.
\end{array}


ここで, c_j \, (j=1,2,\ldots,n), \, b_i \, (i=1,2,\ldots,m),\, a_{ij} \, (i=1,2,\ldots,m, \ j=1,2,\ldots,n)は元の問題(P)で与えられデータ同一である. 元の問題(P)は主問題, 問題(D)は主問題(P)に対す双対問題呼ばれる. 双対問題双対問題が主問題になることは, 問題(D)を問題(P)の形式書き直すことにより容易に示せる. 主問題双対問題実行可能解について, 次のようなことが言える.

さらに, 以下の双対定理相補性定理が示すように, 主問題双対問題いずれか一方最適解は, 他方問題最適解に関する情報を含む.

双対定理:問題双対問題いずれか一方最適解をもつならば, 他方もまた最適解をもち, それらの目的関数値は一致する. また, いずれか一方問題実行可能解対す目的関数値が有界なければ, 他方問題実行可能解もたない.

相補性定理:問題実行可能解\boldsymbol{x}双対問題実行可能解\boldsymbol{y}それぞれの問題最適解であるための必要十分条件は, 以下の2条件(i),(ii)が成り立つことである.


\begin{array}{lll}
\mbox{(i)} & (c_j-\sum_{i=1}^{m}a_{ij}y_i)x_j=0,\ j=1,2,\ldots,n,\\
\\
\mbox{(ii)} & (\sum_{j=1}^{n}a_{ij}x_j-b_i)y_i =0,\ i=1,2,\ldots,m.
\end{array}


これらの最適性条件次のように言い換えることができる. いずれか一方問題k\,番目の制約式不等号成り立つならば, 他方問題において対応する変数の値はゼロになる. また, いずれか一方問題k\,番目の変数の値が正ならば, 他方問題においてそれに対応する制約式等号成り立つ.



参考文献

[1] V. Chvátal, Linear Programming, W. H. Freeman and Company, 1983, 阪田二郎, 藤野和建 訳, 『線形計画法』上, 下, 啓学出版.

[2] G. B. Dantzig, Linear Programming and Extensions, Princeton University Press, 1963.

[3] S. I. Gass, Linear Programming and Extensions, MaGram-Hill, 1975.

[4] V. Klee and G. J. Minty "How good is the simplex algorithm?" in Inequalities-III, O. Shisha, eds., Academic Press, 159-175, 1989.



英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「linear programming」の関連用語

1
エル‐ピー デジタル大辞泉
100% |||||

2
92% |||||

3
36% |||||

4
線形計画法 デジタル大辞泉
36% |||||




8
30% |||||



linear programmingのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



linear programmingのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
デジタル大辞泉デジタル大辞泉
(C)Shogakukan Inc.
株式会社 小学館
日本オペレーションズ・リサーチ学会日本オペレーションズ・リサーチ学会
Copyright (C) 2025 (社)日本オペレーションズ・リサーチ学会 All rights reserved.

©2025 GRAS Group, Inc.RSS